Route-neighborhood-based metaheuristic for vehicle routing problem with time windows

Fuh-Hwa Liu, Sheng Yuan Shen

Research output: Contribution to journalArticle

73 Scopus citations

Abstract

In this paper, a two-stage metaheuristic based on a new neighborhood structure is proposed to solve the vehicle routing problem with time windows (VRPTW). Our neighborhood construction focuses on the relationship between route(s) and node(s). Unlike the conventional methods for parallel route construction, we construct routes in a nested parallel manner to obtain higher solution quality. Valuable information extracted from the previous parallel construction runs is used to enhance the performance of parallel construction. In addition, when there are only a few unrouted customers left, we design a special procedure for handling them. Computational results for 60 benchmark problems are reported. The results indicate that our approach is highly competitive with all existing heuristics, and in particular very promising for solving problems of large size.

Original languageEnglish
Pages (from-to)485-504
Number of pages20
JournalEuropean Journal of Operational Research
Volume118
Issue number3
DOIs
StatePublished - 1 Nov 1999

Fingerprint Dive into the research topics of 'Route-neighborhood-based metaheuristic for vehicle routing problem with time windows'. Together they form a unique fingerprint.

  • Cite this