Scientific Program > Talks by Speaker > Gschwind Timo

For the exact solution of many types of vehicle routing problems, column-generation based algorithms have become predominant. The column-generation subproblems are then variants of the shortest-path problem with resource constraints which can be solved well with dynamic programming labeling algorithms. For vehicle routing problems with a pickup-and-delivery structure, the strongest known dominance between two labels requires the delivery triangle inequality (DTI) for reduced costs to hold. When the direction of labeling is altered from forward labeling to backward labeling, the DTI requirement becomes the pickup triangle inequality (PTI). DTI and PTI cannot be guaranteed at the same time. The consequence seemed to be that bidirectional labeling, one of the most successful acceleration techniques developed over the last years, cannot be effectively applied to pickup and delivery problems. In this paper, we show that bidirectional labeling with the strongest dominance rules in forward as well as backward direction is possible and computationally beneficial. A full-fledged branch-and-price-and-cut algorithm is tested on the pickup and delivery problem with time windows.