A stochastic dynamic traveling salesman problem with hard time windows

Tsung-Sheng Chang*, Yat wah Wan, Wei Tsang OOI

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

63 Scopus citations


Just-in-time (JIT) trucking service, i.e., arriving at customers within specified time windows, has become the norm for freight carriers in all stages of supply chains. In this paper, a JIT pickup/delivery problem is formulated as a stochastic dynamic traveling salesman problem with time windows (SDTSPTW). At a customer location, the vehicle either picks up goods for or delivers goods from the depot, but does not provide moving service to transfer goods from one location to another. Such routing problems are NP-hard in deterministic settings, and in our context, complicated further by the stochastic, dynamic nature of the problem. This paper develops an efficient heuristic for the SDTSPTW with hard time windows. The heuristic is shown to be useful both in controlled numerical experiments and in applying to a real-life trucking problem.

Original languageEnglish
Pages (from-to)748-759
Number of pages12
JournalEuropean Journal of Operational Research
Issue number3
StatePublished - 1 Nov 2009


  • dynamic network
  • Just-in-time
  • Stochastic
  • Time windows
  • Traveling salesman problem

Fingerprint Dive into the research topics of 'A stochastic dynamic traveling salesman problem with hard time windows'. Together they form a unique fingerprint.

Cite this