Show simple item record

dc.contributor.advisorJohnson, Ellis
dc.contributor.authorQiu, Shengli
dc.date.accessioned2014-05-09T19:28:57Z
dc.date.available2014-05-09T19:28:57Z
dc.date.issued2012-04-11
dc.identifier.urihttp://hdl.handle.net/1853/51717
dc.description.abstractCrew 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.en_US
dc.language.isoen_USen_US
dc.publisherGeorgia Institute of Technologyen_US
dc.subjectCrew pairingen_US
dc.subjectDuty treeen_US
dc.subjectPrimal-dual subproblem simplexen_US
dc.subjectCapacitated vehicle routingen_US
dc.subjectSet partitioningen_US
dc.subject.lcshCombinatorial optimization
dc.subject.lcshScheduling
dc.subject.lcshAirlines Planning
dc.subject.lcshFlight crews
dc.titleAirline crew pairing optimization problems and capacitated vehicle routing problemsen_US
dc.typeDissertationen_US
dc.description.degreePh.D.
dc.contributor.departmentIndustrial and Systems Engineering
dc.embargo.termsnullen_US
thesis.degree.levelDoctoral
dc.contributor.committeeMemberCook, William
dc.contributor.committeeMemberNemhauser, George L.
dc.contributor.committeeMemberSmith, Barry
dc.contributor.committeeMemberSokol, Joel


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record