Airline crew pairing optimization problems and capacitated vehicle routing problems

Crew pairing;Duty tree;Primal-dual subproblem simplex;Capacitated vehicle routing;Set partitioning

Qiu, Shengli ; Johnson, Ellis Industrial and Systems Engineering Cook, William Nemhauser, George L. Smith, Barry Sokol, Joel ; Johnson, Ellis

University:Georgia Institute of Technology

Department:Industrial and Systems Engineering

关键词: Crew pairing;    Duty tree;    Primal-dual subproblem simplex;    Capacitated vehicle routing;    Set partitioning;   

Others  :  https://smartech.gatech.edu/bitstream/1853/51717/1/Qiu_Shengli_201305_phd.pdf

美国|英语

来源: SMARTech Repository

【 摘 要 】

Crew pairing and vehicle routing are combinatorial optimization problems that have been studied for many years by researchers worldwide. The aim of this research work is to investigate effective methods for solving large scale crew pairing problems and vehicle routing problems. In the airline industry, to address the complex nature of crew pairing problems, we propose a duty tree method followed by a primal-dual subproblem simplex method. The duty tree approach captures the constraints that apply to crew pairings and generate candidate pairings taking advantage of various proposed strategies. A huge number of legal pairings are stored in the duty tree and can be enumerated. A set partitioning formulation is then constructed, and the problem is solved using a primal-dual subproblem simplex method tailored to the duty tree approach. Computational experiments are conducted to show the effectiveness of the methods. We also present our efforts addressing the capacitated vehicle routing problem (CVRP) that is the basic version of many other variants of the problem. We do not attempt to solve the CVRP instances that have been solved to optimality. Instead, we focus on investigating good solutions for large CVRP instances, with particular emphasis on those benchmark problems from the public online library that have not yet been solved to optimality by other researchers and determine whether we can find new best-known solutions. In this research, we propose a route network that can store a huge number of routes with all routes being legal, a set partitioning formulation that can handle many columns, and the primal-dual subproblem simplex method to find a solution. The computational results show that our proposed methods can achieve better solutions than the existing best-known solutions for some difficult instances. Upon convergence of the primal-dual subproblem simplex method on the giant-tour based networks, we use the near optimal primal and dual solution as well as solve the elementary shortest path problem with resource constraints to achieve the linear programming relaxation global optimal solution.