Fleet assignment and routing with schedule synchronization constraints |
| |
| Affiliation: | 1. State Key Laboratory of Rail Traffic Control and Safety, Beijing Jiaotong University, Beijing 100044, China;2. Department of Civil and Environmental Engineering, The Hong Kong Polytechnic University, Kowloon, Hong Kong;3. Key Laboratory of Road and Traffic Engineering, Tongji University, Shanghai 201804, China;1. Data Science and Analytics, Scotiabank, 40 King St. W, Toronto M5H 1H1, ON, Canada;2. Department of Mechanical and Industrial Engineering, University of Toronto, 5 King''s College Road, Toronto M5S 3G8, ON, Canada;1. Sorbonne Universités, Université Pierre et Marie Curie, Laboratoire LIP6 UMR 7606, 4 place Jussieu, 75005 Paris, France;2. BRT - Center of Excellence, Pontificia Universidad Católica de Chile, Vicuña Mackenna Macul, 4860 Santiago, Chile;3. Universidad Autónoma de Nuevo León, Av. Universidad s/n, San Nicolás de los Garza 66450, Mexico;1. College of Economics and Management, Nanjing University of Aeronautics and Astronautics, Nanjing, China;2. Shenzhen Research Institute of Big Data, Shenzhen, China;3. Sabre Inc, 3150 Sabre Drive, Southlake, TX 76092, USA;1. Chair of Logistics Management, Gutenberg School of Management and Economics, Johannes Gutenberg University Mainz, Germany, D-55128;2. GERAD and Département de sciences de la décision, HEC Montréal, Montreal, Canada, H3T 2A7;3. HEC Montréal & GERAD, Canada |
| |
| Abstract: | This paper introduces a new type of constraints, related to schedule synchronization, in the problem formulation of aircraft fleet assignment and routing problems and it proposes an optimal solution approach. This approach is based on Dantzig–Wolfe decomposition/column generation. The resulting master problem consists of flight covering constraints, as in usual applications, and of schedule synchronization constraints. The corresponding subproblem is a shortest path problem with time windows and linear costs on the time variables and it is solved by an optimal dynamic programming algorithm. This column generation procedure is embedded into a branch and bound scheme to obtain integer solutions. A dedicated branching scheme was devised in this paper where the branching decisions are imposed on the time variables. Computational experiments were conducted using weekly fleet routing and scheduling problem data coming from an European airline. The test problems are solved to optimality. A detailed result analysis highlights the advantages of this approach: an extremely short subproblem solution time and, after several improvements, a very efficient master problem solution time. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
