The single-node dynamic service scheduling and dispatching problem

Leonardo Campo Dall'Orto, Teodor Gabriel Crainic, José Eugenio Leal, Warren Buckler Powell

Research output: Contribution to journalArticle

14 Scopus citations

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 languageEnglish (US)
Pages (from-to)1-23
Number of pages23
JournalEuropean Journal of Operational Research
Volume170
Issue number1
DOIs
StatePublished - 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

Fingerprint Dive into the research topics of 'The single-node dynamic service scheduling and dispatching problem'. Together they form a unique fingerprint.

  • Cite this