A New Formulation Approach for Vehicle Routing Problem with Backhauls
Seminar by
Barış Yıldız
Department of Industrial Engineering , Bilkent University
Abstract:
Due to their practical importance and interesting theoretical properties vehicle routing problems (VRP) constitute one of the major research areas in operations research literature. Various formulations and solution algorithms have been proposed to solve these challenging problems. Motivated by a practical problem that arises in air-cargo delivery we focus on a specific generalization of VRP: vehicle routing problem with backhauls, and propose a novel path-segment formulation and an efficient branch-and-price algorithm to solve it. Using path-segments to represent different stages of transportation, linehaul and backhaul stages, our formulation can very easily handle multiple vehicle types and operational constraints such as vehicle capacity, customs regulations, total delivery/pickup time, etc. We show that the optimal solution of the problem is always a tree in the closure graph of the transportation network and using this property we suggest valid cuts that strengthen our formulation and speed up the branch-and-price algorithm. Our initial computational studies show that our solution approach can significantly extend the size of the problems that can be solved exactly.
