Addressing orientation symmetry in the time window assignment vehicle routing problem

Kevin Dalmeijer, Guy Desaulniers

Research output: Contribution to journalArticleAcademicpeer-review

1 Citation (Scopus)
5 Downloads (Pure)

Abstract

The time window assignment vehicle routing problem (TWAVRP) is the problem of assigning time windows for delivery before demand volume becomes known. This implies that vehicle routes in different demand scenarios have to be synchronized such that the same client is visited around the same time in each scenario. For TWAVRP instances that are relatively difficult to solve, we observe many similar solutions in which one or more routes have a different orientation, that is, the clients are visited in the reverse order. We introduce an edge-based branching method combined with additional components to eliminate orientation symmetry from the search tree, and we present enhancements to make this method efficient in practice. Next, we present a branch-price-and-cut algorithm based on this branching method. Our computational experiments show that addressing orientation symmetry significantly improves our algorithm: The number of nodes in the search tree is reduced by 92.6% on average, and 25 additional benchmark instances are solved to optimality. Furthermore, the resulting algorithm is competitive with the state of the art. The main ideas of this paper are not TWAVRP specific and can be applied to other vehicle routing problems with consistency considerations or synchronization requirements.

Original languageEnglish
Pages (from-to)495-510
Number of pages16
JournalINFORMS Journal on Computing
Volume33
Issue number2
DOIs
Publication statusPublished - 9 Sep 2021

Bibliographical note

Publisher Copyright:
Copyright: © 2020 INFORMS.

Fingerprint

Dive into the research topics of 'Addressing orientation symmetry in the time window assignment vehicle routing problem'. Together they form a unique fingerprint.

Cite this