Addressing orientation-symmetry in the Time Windows Assignment Vehicle Routing Problem

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 difficult to solve by current methods, we observe many similar solutions in which one or more routes have a different orientation, i.e., the clients are visited in the reverse order. We introduce a new branching method that eliminates this 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 the new branching method. Through computational experiments, we show that our algorithm outperforms other solution methods, and we solve 29 previously unsolved benchmark instances to optimality. We conclude that properly addressing orientation-symmetry significantly improves the computational tractability of the TWAVRP. 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.

Registration to Remy Spliet, spliet@ese.eur.nl is required for availability of lunch.