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

Yiannis Koskosidis, Warren Buckler Powell, Marius Solomon

Research output: Contribution to journalArticle

114 Scopus citations

Abstract

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
Volume26
Issue number2
DOIs
StatePublished - Jan 1 1992
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Transportation

Fingerprint 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