Title: A New Formulation Approach for Vehicle Routing Problem with Backhauls by Barış Yıldız, Koç University, Department of Industrial Engineering
November 4, Friday 13:40
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.
Baris Yildiz has got his Ph.D. from Bilkent University Industrial Engineering Department in 2016. He holds an M.S. degree in Operations Research from U.S. Naval Postgraduate School and a B.S. degree in Systems Engineering from Turkish Army Academy. After working as an operations research analyst at Turkish General Staff HQ during 2011-2016, he joined Koc University Industrial Engineering Department in 2016 as a faculty member. His research focuses on network design problems and their applications in telecommunication and transportation networks.