Abstract
In this paper, we focus on a particular version of the dynamic service network design (DSND) problem, namely the case of a single-terminal that dispatches services to a number of customers and other terminals. We present a time-dependent, stochastic formulation that aims to optimize the problem over a given planning horizon, and propose a solution approach based on dynamic programming principles. We also present a static, single-period, formulation of the single-node problem that appears as a subproblem when addressing the time-dependent version and general service network design cases. Despite its apparent simplicity, it is still a network design problem and exact solution methods are not sufficiently fast. We therefore propose two tabu search meta-heuristics based on the ejection-chain concept. We also introduce a learning mechanism that takes advantage of experience gathered in repeated executions. Experiments with problem instances derived from real cases indicate that the proposed solution methods are efficient and yield good solutions.
Original language | English (US) |
---|---|
Pages (from-to) | 1-23 |
Number of pages | 23 |
Journal | European Journal of Operational Research |
Volume | 170 |
Issue number | 1 |
DOIs | |
State | Published - Apr 1 2006 |
All Science Journal Classification (ASJC) codes
- Computer Science(all)
- Modeling and Simulation
- Management Science and Operations Research
- Information Systems and Management
Keywords
- Approximate dynamic programming
- Dynamic service network design
- Ejection chains
- Stochastic formulation
- Tabu search