×

A bi-objective approach for scheduling ground-handling vehicles in airports. (English) Zbl 1349.90118

Summary: In the present paper, we propose a new approach for scheduling ground-handling vehicles, tackling the problem with a global perspective. Preparing an aircraft for its next flight requires a set of interrelated services involving different types of vehicles. Planning decisions concerning each resource affect the scheduling of the other activities and the performance of the other resources. Considering the different operations and vehicles instead of scheduling each resource in isolation allows integrating decisions and contributing to the optimization of the overall ground-handling process. This goal is defined through two objectives: (i) minimizing the waiting time before an operation starts and the total reduction of corresponding time windows and (ii) minimizing the total completion time of the turnarounds. We combine different technologies and techniques to solve the problem efficiently. A new method to address this bi-objective optimization problem is also proposed. The approach has been tested using real data from two Spanish airports, thereby obtaining different solutions that represent a trade-off between both objectives. Experimental results permit inferring interesting criteria on how to optimize each resource, considering the effect on other operations. This outcome leads to more robust global solutions and to savings in resources utilization.

MSC:

90B06 Transportation, logistics and supply chain management
90B35 Deterministic scheduling theory in operations research
90C29 Multi-objective and goal programming

Software:

MACS-VRPTW
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[3] Clausen, T.; Pisinger, D., Airport ground staff scheduling, Kgs. Lyngby, 231 p. (DTU Management 2011; No. 2). (2011), Technical University of Denmark (DTU): Technical University of Denmark (DTU) Denmark
[4] van Leeuwen, P., Modelling the turnaround process, CARE INO III: the co-ordinated airport through extreme decoupling, Eurocontrol (2007)
[5] Schmidberger, S.; Bals, L.; Hartmann, E.; Jahns, C., Ground handling services at European hub airports: development of a performance measurement system for benchmarking, Int J Prod Econ, 117, 1, 104-116 (2009)
[7] Ho, S. C.; Leung, J. M.Y., Solving a manpower scheduling problem for airline catering using metaheuristics, Eur J Oper Res, 202, 3, 903-921 (2010) · Zbl 1175.90251
[8] Cordeau, J. F.; Desaulniers, G.; Desrosiers, J.; Solomon, M. M.; Soumis, F., The VRP with time windows, (Toth, P.; Vigo, D., The vehicle routing problem (2002), SIAM: SIAM USA), 157-186 · Zbl 1076.90543
[9] Sourirajan, K.; Uzsoy, R., Hybrid decomposition heuristics for solving large-scale scheduling problems in semiconductor wafer fabrication, J Sched, 10, 1, 41-65 (2007) · Zbl 1154.90491
[10] Solomon, M. M., Algorithms for the vehicle routing and scheduling problems with time window constraints, Oper Res, 35, 2, 254-265 (1987) · Zbl 0625.90047
[11] Guimarans, D., Hybrid algorithms for solving routing problems, PhD thesis (2012), Autonomous University of Barcelona
[12] Kallehauge, B., Formulations and exact algorithms for the vehicle routing problem with time windows, Comput Oper Res, 35, 7, 2307-2330 (2008) · Zbl 1180.90052
[13] Lenstra, J. K.; Kan, A. H.G. R., Complexity of vehicle routing problem with time windows, Networks, 11, 221-227 (1981)
[14] Bräysy, O.; Gendreau, M., Vehicle routing problem with time windows, part I: route construction and local search algorithms, Transp Sci, 39, 1, 104-118 (2005)
[15] Bräysy, O.; Gendreau, M., Vehicle routing problem with time windows, part II: metaheuristics, Transp Sci, 39, 1, 119-139 (2005)
[16] Jourdan, L.; Basseur, M.; Talbi, E. G., Hybridizing exact methods and metaheuristics: a taxonomy, Eur J Oper Res, 199, 3, 620-629 (2009) · Zbl 1176.90499
[17] Gambardella, L. M.; Taillard, E.; Agazzi, G., MACS-VRPTW. A multiple ant colony system for vehicle routing problems with time windows, (Corne, D.; Dorigo, M.; Glover, F., New ideas in optimization (1999), McGraw-Hill: McGraw-Hill London), 63-76
[18] Tan, K. C.; Chew, Y. H.; Lee, L. H., A hybrid multiobjective evolutionary algorithm for solving vehicle routing problem with time windows, Comput Optim Appl, 34, 1, 115-151 (2005) · Zbl 1111.90022
[19] Collette, Y.; Siarry, P., Multiobjective optimization: principles and case studies (2003), Springer: Springer Berlin
[20] Ombuki, B.; Ross, B. J.; Hanshar, F., Multi-objective genetic algorithms for vehicle routing problem with time windows, Appl Intell, 24, 1, 17-30 (2006)
[21] Ghoseiri, K.; Ghannadpour, S. F., Multi-objective vehicle routing problem with time windows using goal programming and genetic algorithm, Appl Soft Comput, 10, 1096-1107 (2010)
[22] Liu, C.; Chang, T. C.; Huang, L. F., Multi-objective heuristics for the vehicle routing problem, Int J Oper Res, 3, 3, 173-181 (2006) · Zbl 1134.90037
[23] Hong, S. C.; Park, Y. B., A heuristic for bi-objective vehicle routing with time window constraints, Int J Prod Econ, 62, 3, 249-258 (1999)
[24] Müller, J., Approximative solutions to the bicriterion vehicle routing problem with time windows, Eur J Oper Res, 202, 1, 223-231 (2010) · Zbl 1173.90517
[25] Jozefowiez, N.; Semet, F.; Talbi, E. G., Multi-objective vehicle routing problems, Eur J Oper Res, 189, 2, 293-309 (2008) · Zbl 1148.90338
[26] Miettinen, K., Introduction to multi-objective optimization: noninteractive approaches, (Branke, J.; Deb, K.; Kaisa, Miettinen; Słowiński, R., Multiobjective optimization interactive and evolutionary approaches, lecture notes in computer science, Vol. 5252 (2008), Springer: Springer Berlin), 1-25
[27] Miettinen, K.; Ruiz, F.; Wierzbicki, A. P., Introduction to multi-objective optimization: interactive approaches, (Branke, J.; Deb, K.; Miettinen, K.; Słowiński, R., Multiobjective optimization interactive and evolutionary approaches, lecture notes in computer science, Vol. 5252 (2008), Springer: Springer Berlin), 27-57
[28] Fonseca, C. M.; Fleming, P. J., An overview of evolutionary algorithms in multiobjective optimization, Evolut Comput, 3, 1, 1-16 (1995)
[29] Rossi, F.; Beek, P.; van, Walsh, T., Handbook of constraint programming (2006), Elsevier Inc: Elsevier Inc New York · Zbl 1175.90011
[30] Focacci, F.; Laburthe, F.; Lodi, A., Local search and constraint programming, (Glover, F.; Kochenberger, G. A., Handbook of metaheuristics (2003), Kluwer Academic: Kluwer Academic Boston), 369-403 · Zbl 1137.90729
[31] Bessiere, C., Constraint propagation, ((2006), Elsevier, Science Inc), 29-69
[32] Kilby, P.; Shaw, P., Vehicle routing, ((2006), Elsevier, Science Inc), 801-836
[33] Adams, J.; Balas, E.; Zawack, D., The shifting bottleneck procedure for job shop scheduling, Manag Sci, 3, 391-401 (1988) · Zbl 0637.90051
[34] Balas, E.; Lenstra, J. K.; Vazacopoulos, A., The one machine problem with delayed precedence constraints and its use in job shop scheduling, Manag Sci, 41, 94-109 (1995) · Zbl 0824.90076
[35] Lafayette, W., A computational study of shifting bottleneck procedures for shop scheduling problems, J Heuristics, 3, 2, 111-137 (1997)
[37] Rousseau, L. M.; Gendreau, M.; Pesant, G., Using constraint-based operators to solve the vehicle routing problem with time windows, J Heuristics, 8, 1, 43-58 (2002) · Zbl 1073.90056
[38] Mladenovic, N.; Hansen, P., Variable neighborhood search, Comput Oper Res, 24, 11, 1097-1100 (1997) · Zbl 0889.90119
[39] Bräysy, O., A reactive variable neighborhood search for the vehicle routing problem with time windows, Informs J Comput, 15, 4, 347-368 (2003) · Zbl 1238.90136
[40] Guimarans, D.; Herrero, R.; Ramos, J. J.; Padrón, S., Solving vehicle routing problems using constraint programming and lagrangian relaxation in a metaheuristics framework, Int J Inf Syst Supply Chain Manag, 4, 2, 61-81 (2011)
[44] Jozefowiez, N.; Glover, F.; Laguna, M., Multi-objective meta-heuristics for the traveling salesman problem with profits, J Math Model Algorithms, 7, 2, 177-195 (2008) · Zbl 1140.90018
[45] Apt, K.; Wallace, M. G., Constraint logic programming using ECLiPSe (2007), Cambridge University Press: Cambridge University Press Cambridge · Zbl 1119.68044
[46] Boeing737, B737-airplane characteristics for airport planning (2009), The Boeing Company
[47] Boeing767, B767-Airplane Characteristics for Airport Planning (2009), The Boeing Company
[48] Boeing777, B777 -Airplane Characteristics for Airport Planning (2009), The Boeing Company
[49] Woch, M.; Łebkowski, P., Sequential simulated annealing for the vehicle routing problem with time windows, Decis Mak Manuf Serv, 1-2, 3, 87-100 (2009) · Zbl 1202.90039
[51] Woch, M., Rozwiazanie problemu dostaw z oknami czasowymi za pomoca symulowanego wyzarzania (Solving vehicle routing problem with time windows using simulated annealing), Stud Inf, 25, 2, 67-81 (2004)
[52] Berger, J.; Barkaoui, M.; Bräysy, O., A route-directed hybrid genetic approach for the vehicle routing problem with time windows, Inf Syst Oper Res, 41, 179-194 (2003) · Zbl 07682301
[53] Hong, L., An improved LNS algorithm for real-time vehicle routing problem with time windows, Comput Oper Res, 39, 2, 151-163 (2012) · Zbl 1251.90019
[54] Garcia-Najera, A.; Bullinaria, J. A., An improved multi-objective evolutionary algorithm for the vehicle routing problem with time windows, Comput Oper Res, 38, 1, 287-300 (2011) · Zbl 1231.90087
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.