Addressing Orientation Symmetry in the Time Window Assignment Vehicle Routing Problem

Kevin Dalmeijer () and Guy Desaulniers ()
Additional contact information
Kevin Dalmeijer: H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332; Econometric Institute, Erasmus School of Economics, Erasmus University Rotterdam, 3062 PA Rotterdam, Netherlands
Guy Desaulniers: Department of Mathematics and Industrial Engineering, Polytechnique Montréal, Montréal, Québec H3T 1J4, Canada; Group for Research in Decision Analysis (GERAD), Montréal, Québec H3T 1J4, Canada

INFORMS Journal on Computing, 2021, vol. 33, issue 2, 495-510

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.

Keywords: vehicle routing; time window assignment; symmetry; synchronization; consistency; branch-price-and-cut (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2020.0974 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:33:y:2021:i:2:p:495-510

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().