Optimization-based heuristic for Vehicle Routing and Scheduling with soft Time Window constraints

Yiannis Koskosidis, Warren Powell, Marius Solomon

Research output: Contribution to journalArticlepeer-review

131 Scopus citations


The Vehicle Routing and Scheduling Problem with Time Window constraints is formulated as a mixed integer program, and optimization-based heuristics which extend the cluster-first, route-second algorithm of Fisher and Jaikumar are developed for its solution. We present a new formulation based on the treatment of the time window constraints as soft constraints that can be violated at a cost and we heuristically decompose the problem into an assignment/clustering component and a series of routing and scheduling components. Numerical results based on randomly generated and benchmark problem sets indicate that the algorithm compares favorably to state-of-the-art local insertion and improvement heuristics.

Original languageEnglish (US)
Pages (from-to)69-85
Number of pages17
JournalTransportation Science
Issue number2
StatePublished - 1992

All Science Journal Classification (ASJC) codes

  • Civil and Structural Engineering
  • Transportation


Dive into the research topics of 'Optimization-based heuristic for Vehicle Routing and Scheduling with soft Time Window constraints'. Together they form a unique fingerprint.

Cite this