Geodesic
Optimal scheduling of passenger air transportation in regional network
Matematičeskoe modelirovanie, Tome 32 (2020) no. 9, pp. 73-86.

Voir la notice de l'article provenant de la source Math-Net.Ru

This paper deals with the problem of air passenger transportation optimal planning. The aim is to minimize renting and operational costs, taking into account heterogeneous fleet, feasibility of multiple visits to the same location, restrictions on the set of available airways, etc. Two multi-index formalizations — as a binary linear programming problem and as a mixed-integer linear programming problem (depending on the consideration of time windows for takeoffs and landings) — are presented for the regarded task. In the future constructed analytical model can become the basis for the development of the globally optimal schedules approximation algorithms.
Keywords: vehicle routing problem, multiple trips, mixed-integer linear programming. 
@article{MM_2020_32_9_a4,
     author = {I. P. Bogdanov},
     title = {Optimal scheduling of passenger air transportation in regional network},
     journal = {Matemati\v{c}eskoe modelirovanie},
     pages = {73--86},
     publisher = {mathdoc},
     volume = {32},
     number = {9},
     year = {2020},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MM_2020_32_9_a4/}
}
TY  - JOUR
AU  - I. P. Bogdanov
TI  - Optimal scheduling of passenger air transportation in regional network
JO  - Matematičeskoe modelirovanie
PY  - 2020
SP  - 73
EP  - 86
VL  - 32
IS  - 9
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MM_2020_32_9_a4/
LA  - ru
ID  - MM_2020_32_9_a4
ER  - 
%0 Journal Article
%A I. P. Bogdanov
%T Optimal scheduling of passenger air transportation in regional network
%J Matematičeskoe modelirovanie
%D 2020
%P 73-86
%V 32
%N 9
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MM_2020_32_9_a4/
%G ru
%F MM_2020_32_9_a4
I. P. Bogdanov. Optimal scheduling of passenger air transportation in regional network. Matematičeskoe modelirovanie, Tome 32 (2020) no. 9, pp. 73-86. http://geodesic.mathdoc.fr/item/MM_2020_32_9_a4/

[1] P. Toth, D. Vigo, The vehicle routing problem, SIAM Monographs on Discrete Mathematics and Applications, Philadelphia, 2002 | MR

[2] K. Braekers, K. Ramaekers, I. Van Nieuwenhuyse, “The vehicle routing problem: State of the art classification and review”, Comp. Industrial Engineering, 99 (2016), 300–313

[3] D. Cattaruzza, N. Absi, D. Feillet, “Vehicle routing problems with multiple trips”, 4OR quarterly journal of the Belgian, French and Italian Operations Research Societies, 14:3 (2016), 223–259 | MR | Zbl

[4] C. K.Y. Lin, R. C.W. Kwok, “Multi-objective metaheuristics for a location-routing problem with multiple use of vehicles on real data and simulated data”, European Journal of Operational Research, 175:3 (2006), 1833–1849 | Zbl

[5] M. Battarra, M. Monaci, D. Vigo, “An adaptive guidance approach for the heuristic solution of a minimum multiple trip vehicle routing problem”, Computers Operations Research, 36:11 (2009), 3041–3050 | Zbl

[6] A. Ceselli, G. Righini, M. Salani, “A column generation algorithm for a rich vehicle-routing problem”, Transportation Science, 43:1 (2009), 56–69

[7] M. Oberscheider, J. Zazgornik, M. Gronalt, P. Hirsch, “An exact approach to minimize the greenhouse gas emissions in timber transport”, Journal of Applied Operational Research, 7:2 (2015), 43–59

[8] M. R. Garey, D. S. Johnson, Computers and intractability: a guide to the theory of NP-completeness, W. H. Freeman and Company, San Francisco, 1979 | MR | Zbl

[9] C. Prins, “Efficient heuristics for the heterogeneous fleet multi-trip VRP with application to a large-scale real case”, J. of Math. Model. Algorithms, 1:2 (2002), 135–150 | MR | Zbl

[10] J. Caceres-Cruz, A. Grasas, H. Ramalhinho, A. A. Juan, “A savings-based randomized heuristic for the heterogeneous fixed fleet vehicle routing problem with multi-trips”, Journal of Applied Operational Research, 6:2 (2014), 69–81

[11] F. Despaux, S. Basterrech, “Multi-Trip Vehicle Routing Problem with Time Windows and Heterogeneous Fleet”, Intern. J. of Comp. Information Systems Industrial Management Applications, 8 (2016), 355–363

[12] J. Brandão, A. Mercer, “A tabu search algorithm for the multi-trip vehicle routing and scheduling problem”, European J. of Operational Research, 100:1 (1997), 180–191 | MR | Zbl

[13] S. Salhi, R. J. Petch, “A GA based heuristic for the vehicle routing problem with multiple trips”, J. of Math. Model Algorithms in Operations Res., 6:4 (2007), 591–613 | MR | Zbl

[14] F. Alonso, M. J. Alvarez, J. E. Beasley, “A tabu search algorithm for the periodic vehicle routing problem with multiple vehicle trips and accessibility restrictions”, Journal of the Operational Research Society, 59:7 (2008), 963–976 | Zbl

[15] R. J. Petch, S. Salhi, “A multi-phase constructive heuristic for the vehicle routing problem with multiple trips”, Discrete Applied Mathematics, 133:1–3 (2003), 69–92 | MR | Zbl

[16] N. Azi, M. Gendreau, J. Y. Potvin, “An adaptive large neighborhood search for a vehicle routing problem with multiple routes”, Comp. Operations Research, 41 (2014), 167–173 | MR | Zbl

[17] Z. Ye, H. Mohamadian, “Multiple ant colony optimization for single depot multiple trip vehicle routing problems”, PSI 2014. Ershov Informatics Conf., EPiC Series in Comp., 23, 2014, 43–54

[18] I. P. Bogdanov, “Formirovanie optimalnyh marshrutov regionalnyh passazhirskih aviaperevozok”, Keldysh Institute preprints, 2019, 113, 20 pp.

[19] A. Mingozzi, R. Roberti, P. Toth, “An exact algorithm for the multi-trip vehicle routing problem”, INFORMS Journal on Computing, 25:2 (2013), 193–207 | MR

[20] I. Karaoğlan, “A branch-and-cut algorithm for the vehicle routing problem with multiple use of vehicles”, International Journal of Lean Thinking, 6:1 (2015), 21–46 | MR

[21] N. Azi, M. Gendreau, J. Y. Potvin, “An exact algorithm for a vehicle routing problem with time windows and multiple use of vehicles”, European Journal of Operational Research, 202:3 (2010), 756–763 | MR | Zbl

[22] R. Macedo, C. Alves, J. M.V. de Carvalho, F. Clautiaux, S. Hanafi, “Solving the vehicle routing problem with time windows and multiple routes exactly using a pseudo-polynomial model”, European Journal of Operational Research, 214:3 (2011), 536–545 | MR | Zbl

[23] F. Hernandez, D. Feillet, R. Giroudeau, O. Naud, “A new exact algorithm to solve the multi-trip vehicle routing problem with time windows and limited duration”, 4OR — A Quarterly Journal of Operations Research, 12:3 (2014), 235–259 | MR | Zbl

[24] M. P. Seixas, A. B. Mendes, “A branch-and-price approach for a multi-trip vehicle routing problem with time windows and driver work hours”, Congreso Latino-Iberoamericano de Investigación Operativa. Simpósio Brasileiro de Pesquisa Operacional (September 24–28, 2012, Rio de Janeiro, Brazil), 3469–3480

[25] I. Gribkovskaia, B. O. Gullberg, K. J. Hovden, S. W. Wallace, “Optimization model for a livestock collection problem”, International Journal of Physical Distribution Logistics Management, 36:2 (2006), 136–152