A new branching strategy for time constrained routing problems with application to backhauling |
| |
Authors: | Sylvie Gélinas Martin Desrochers Jacques Desrosiers Marius M Solomon |
| |
Institution: | (1) GERAD and École Polytechnique de Montréal, H3C 3A7 Montréal, Canada;(2) GERAD and École des Hautes Études Commerciales de Montréal, H3T 1V6 Montréal, Canada;(3) Northeastern University, 02115 Boston, MA, USA |
| |
Abstract: | In this paper, we explore a new branching strategy for branch-and-bound approaches based on column generation for the vehicle routing problems with time windows. This strategy involves branching on resource variables (time or capacity) rather than on network flow variables. We also examine criteria for selecting network nodes for branching. To test the effectiveness of the branching strategy, we conduct computational experiments on time window constrained vehicle routing problems where backhauling is permitted only after all the shipments to clients have been made. The branching method proved very effective. In cases where time was the more binding constraint, time-based branching succeeded in decreasing the number of nodes explored by two thirds and the total computation time by more than half when compared to flow-based branching. The computational results also show that the overall algorithm was successful in optimally solving problems with up to 100 customers. It produced an average cost decrease of almost 7% when backhauling was permitted as compared to the cost involved when the client and the distributor routes were distinct. |
| |
Keywords: | Routing scheduling time windows backhauling column generation branch-and-bound |
本文献已被 SpringerLink 等数据库收录! |
|