A branch-and-cut algorithm for the Time Window Assignment Vehicle Routing Problem

Kevin Dalmeijer, Remy Spliet

Research output: Contribution to journalArticleAcademicpeer-review

27 Citations (Scopus)

Abstract

This paper presents a branch-and-cut algorithm for the Time Window Assignment Vehicle Routing Problem (TWAVRP), the problem of assigning time windows for delivery before demand volume becomes known. A novel set of valid inequalities, the precedence inequalities, is introduced and multiple separation heuristics are presented. In our numerical experiments the branch-and-cut algorithm is 3.8 times faster when separating precedence inequalities. Furthermore, in our experiments, the branch-and-cut algorithm is 193.9 times faster than the best known algorithm in the literature. Finally, using our algorithm, instances of the TWAVRP are solved which are larger than the instances previously presented in the literature.
Original languageEnglish
Pages (from-to)140-152
Number of pages13
JournalComputers and Operations Research
Volume89
DOIs
Publication statusPublished - 2018

Fingerprint

Dive into the research topics of 'A branch-and-cut algorithm for the Time Window Assignment Vehicle Routing Problem'. Together they form a unique fingerprint.

Cite this