Vehicle scheduling problem under uncertainty: literature review and future perspective

Document Type : Review Article


Department of Computer Sciences, Faculty of Computer and Industrial Engineering, Birjand University of Technology, Birjand, Iran


Vehicle scheduling problem is an important combinatorial optimization problem arising in the management of transportation companies. The problem consists of assigning a set of timetabled trips to a set of vehicles to minimize a given objective function. In this paper, vehicle scheduling problem under undeterministic conditions is considered. The paper states the necessity of considering the uncertain condition in the problem and reviews the different solution approaches to deal with the conditions of uncertainty. The main objective of this paper is to discuss the importance of considering uncertainty in vehicle scheduling problem, review the relevant literature and present some directions for future work.


Main Subjects

[1] M. Aghamohagheghi, S. M. Hashemi, and R. Tavakkoli-Moghaddam, An advanced decision support framework to assess sustainable transport projects using a new uncertainty modeling tool: Interval-valued Pythagorean trapezoidal fuzzy numbers, Iran. J. Fuzzy Syst., 18 (2021), pp. 53–73.
[2] M. Akram, I. Ullah, T. Allahviranloo, and S. Edalatpanah, Fully pythagorean fuzzy linear programming problems with equality constraints, Comput. Appl. Math., 40 (2021), pp. 1–30.
[3] A. Alvarez and P. Munari, An exact hybrid method for the vehicle routing problem with time windows and multiple deliverymen, Comput. Oper. Res., 83 (2017), pp. 1–12.
[4] A. K. Beheshti and S. R. Hejazi, A novel hybrid column generation-metaheuristic approach for the vehicle routing problem with general soft time window, Information Sciences, 316 (2015), pp. 598–615.
[5] D. P. Bertsekas, Linear network optimization: algorithms and codes, MIT press, 1991.
[6] E. Cao and M. Lai, The open vehicle routing problem with fuzzy demands, Expert Syst. Appl., 37 (2010), pp. 2405–2411.
[7] A. A. Ceder, S. Hassold, and B. Dano, Approaching even-load and even-headway transit timetables using different bus sizes, Public Transport, 5 (2013), pp. 193–217.
[8] S. K. Das, Modified method for solving fully fuzzy linear programming problem with triangular fuzzy numbers, Int. J. Res. Ind. Eng., 6 (2017), pp. 293–311.
[9] B. David and M. Kr ´ esz ´ , The dynamic vehicle rescheduling problem, Cent. Eur. J. Oper. Res., 25 (2017), pp. 809–830.
[10] I. Dayarian, T. G. Crainic, M. Gendreau, and W. Rei, A column generation approach for a multiattribute vehicle routing problem, European J. Oper. Res., 241 (2015), pp. 888–906.
[11] G. Desaulniers and M. D. Hickman, Chapter 2 public transit, in Transportation, C. Barnhart and G. Laporte, eds., vol. 14 of Handbooks in Operations Research and Management Science, Elsevier, 2007, pp. 69–127.
[12] L. Desfontaines and G. Desaulniers, Multiple depot vehicle scheduling with controlled trip shifting, Transp. Res. B: Methodol., 113 (2018), pp. 34–53.
[13] J. Dong and S. Wan, A new method for solving fuzzy multi-objective linear programming problems, Iran. J. Fuzzy Syst., 16 (2019), pp. 145–159.
[14] A. Ebrahimnejad, An effective computational attempt for solving fully fuzzy linear programming using molp problem, J. Ind. Prod. Eng., 36 (2019), pp. 59–69.
[15] D. Feillet, A tutorial on column generation and branch-and-price for vehicle routing problems, 4OR-Q. J. Oper. Res., 8 (2010), pp. 407–424.
[16] M. D. Filabadi, A. Asadi, R. Giahi, A. T. Ardakani, and A. Azadeh, A new stochastic model for bus rapid transit scheduling with uncertainty, Future Transportation, 2 (2022), pp. 165–183.
[17] R. Freling, A. P. Wagelmans, and J. M. P. Paixao˜ , Models and algorithms for single-depot vehicle scheduling, Transportation Science, 35 (2001), pp. 165–180.
[18] C. Gauvin, G. Desaulniers, and M. Gendreau, A branch-cut-and-price algorithm for the vehicle routing problem with stochastic demands, Comput. Oper. Res., 50 (2014), pp. 141–153.
[19] M. Ghatee and M. Niksirat, A hopfield neural network applied to the fuzzy maximum cut problem under credibility measure, Information Sciences, 229 (2013), pp. 77–93.
[20] A. Ghodratnama, S. A. Torabi, and M. R. TAVAKKOLI, Credibility-based fuzzy programming models to solve the budget-constrained flexible flow line problem, Iran. J. Fuzzy Syst., (2012).
[21] P. C. Guedes and D. Borenstein, Column generation based heuristic framework for the multiple-depot vehicle type scheduling problem, Comput. Ind. Eng., 90 (2015), pp. 361–370.
[22] V. Guihaire and J.-K. Hao, Transit network design and scheduling: A global review, Transp. Res. Part A: Policy Pract., 42 (2008), pp. 1251–1273.
[23] A. Hadjar, O. Marcotte, and F. Soumis, A branch-and-cut algorithm for the multiple depot vehicle scheduling problem, Oper. Res., 54 (2006), pp. 130–149.
[24] S. Hassold and A. A. Ceder, Public transport vehicle scheduling featuring multiple vehicle types, Transp. Res. B: Methodol., 67 (2014), pp. 129–143.
[25] F. He, J. Yang, and M. Li, Vehicle scheduling under stochastic trip times: an approximate dynamic programming approach, Transp. Res. Part C: Emerg. Technol., 96 (2018), pp. 144–159.
[26] M. Hewitt, G. Nemhauser, M. Savelsbergh, and J.-H. Song, A branch-and-price guided search approach to maritime inventory routing, Comput. Oper. Res., 40 (2013), pp. 1410–1419.
[27] D. Huisman, R. Freling, and A. P. Wagelmans, A robust solution approach to the dynamic vehicle scheduling problem, Transportation Science, 38 (2004), pp. 447–458.
[28] , Multiple-depot integrated vehicle and crew scheduling, Transportation Science, 39 (2005), pp. 491–502.
[29] O. J. Ibarra-Rojas, R. Giesen, and Y. A. Rios-Solis, An integrated approach for timetabling and vehicle scheduling problems to analyze the trade-off between level of service and operating costs of transit networks, Transp. Res. Part B: Methodol., 70 (2014), pp. 35–46.
[30] E. Ilbahar, C. Kahraman, and S. Cebi, Location selection for waste-to-energy plants by using fuzzy linear programming, Energy, 234 (2021), p. 121189.
[31] S. Irnich, G. Desaulniers, J. Desrosiers, and A. Hadjar, Path-reduced costs for eliminating arcs in routing and scheduling, INFORMS Journal on Computing, 22 (2010), pp. 297–313.
[32] N. Kliewer, B. Amberg, and B. Amberg, Multiple depot vehicle and crew scheduling with time windows for scheduled trips, Public Transport, 3 (2012), pp. 213–244.
[33] N. Kliewer, T. Mellouli, and L. Suhl, A time–space network based exact optimization model for multidepot bus scheduling, European J. Oper. Res., 175 (2006), pp. 1616–1627.
[34] S. Kulkarni, M. Krishnamoorthy, A. Ranade, A. T. Ernst, and R. Patil, A new formulation and a column generation-based heuristic for the multiple depot vehicle scheduling problem, Transp. Res. Part B: Methodol., 118 (2018), pp. 457–487.
[35] P. Kundu, S. Majumder, S. Kar, and M. Maiti, A method to solve linear programming problem with interval type-2 fuzzy parameters, Fuzzy Optim. Decis. Mak., 18 (2019), pp. 103–130.
[36] B. Laurent and J.-K. Hao, Iterated local search for the multiple depot vehicle scheduling problem, Comput. Ind. Eng., 57 (2009), pp. 277–286.
[37] L. Li, H. K. Lo, and F. Xiao, Mixed bus fleet scheduling under range and refueling constraints, Transp. Res. Part C: Emerg. Technol., 104 (2019), pp. 443–462.
[38] M. A. Mehmood, M. Akram, M. G. Alharbi, and S. Bashir, Solution of fully bipolar fuzzy linear programming models, Math. Prob. Eng., 2021 (2021).
[39] A. Mehrabian, R. Tavakkoli-Moghaddam, and K. Khalili-Damaghani, Multi-objective routing and scheduling in flexible manufacturing systems under uncertainty, Iran. J. Fuzzy Syst., 14 (2017), pp. 45–77.
[40] M. Naumann, L. Suhl, and S. Kramkowski, A stochastic programming approach for robust vehicle scheduling in public bus transport, Procedia Soc. Behav. Sci., 20 (2011), pp. 826–835.
[41] M. Niksirat, State-of-the-art auction algorithms for multi-depot bus scheduling problem considering depot workload balancing constraints, Fuzzy Information and Engineering, 12 (2020), pp. 253–273.
[42] M. Niksirat, Intuitionistic fuzzy hub location problems: Model and solution approach, Fuzzy Information and Engineering, 14 (2022), pp. 74–83.
[43] M. Niksirat, S. M. Hashemi, and M. Ghatee, Branch-and-price algorithm for fuzzy integer programming problems with block angular structure, Fuzzy Sets and Systems, 296 (2016), pp. 70–96.
[44] M. Niksirat and S. N. Hashemi, The complexity of cost constrained vehicle scheduling problem, AUT J. Math. Com., 2 (2021), pp. 109–115.
[45] M. Niksirat and S. H. Nasseri, Knapsack problem in fuzzy nature: Different models based on credibility ranking method, Yugosl. J. Oper. Res., 32 (2022), pp. 203–218.
[46] N. Olsen, N. Kliewer, and L. Wolbeck, A study on flow decomposition methods for scheduling of electric buses in public transport based on aggregated time–space network models, Cent. Eur. J. Oper. Res., (2020), pp. 1–37.
[47] O. Ozturk, M. A. Begen, and G. S. Zaric, A branch and bound based heuristic for makespan minimization of washing operations in hospital sterilization services, European J. Oper. Res., 239 (2014), pp. 214–226.
[48] G. Pantazis, F. Fele, and K. Margellos, On the probabilistic feasibility of solutions in multi-agent optimization problems under uncertainty, European Journal of Control, 63 (2022), pp. 186–195.
[49] A.-S. Pepin, G. Desaulniers, A. Hertz, and D. Huisman, A comparison of five heuristics for the multiple depot vehicle scheduling problem, Journal of scheduling, 12 (2009), pp. 17–30.
[50] H. L. Petersen, A. Larsen, O. B. G. Madsen, B. Petersen, and S. Ropke, The simultaneous vehicle scheduling and passenger service problem, Transportation Science, 47 (2013), pp. 603–616.
[51] F. Pourofoghi, D. Darvishi Salokolaei, and J. Saffar Ardabili, A new approach to finding the solution of transportation problem with grey parameters, J. Oper. Res. Appl., 18 (2021), pp. 59–73.
[52] J. Puchinger and G. R. Raidl, Combining metaheuristics and exact algorithms in combinatorial optimization: A survey and classification, in International work-conference on the interplay between natural and artificial computation, Springer, 2005, pp. 41–53.
[53] F. Rahmanniyay, J. Razmi, and A. J. Yu, An interactive multi-objective fuzzy linear programming model for hub location problems to minimise cost and delay time in a distribution network, Int. J. Logist. Syst. Manag., 37 (2020), pp. 79–105.
[54] M. Saffarian, M. Niksirat, and S. M. Kazemi, A hybrid genetic-simulated annealing-auction algorithm for a fully fuzzy multi-period multi-depot vehicle routing problem, Int. J. Supply Oper. Manag., 8 (2021), pp. 96–113.
[55] S. Shahparvari and B. Abbasi, Robust stochastic vehicle routing and scheduling for bushfire emergency evacuation: An australian case study, Transp. Res. Part A: Policy Pract., 104 (2017), pp. 32–49.
[56] Y. Shen, J. Xu, and J. Li, A probabilistic model for vehicle scheduling based on stochastic trip times, Transp. Res. Part B: Methodol., 85 (2016), pp. 19–31.
[57] X. Shui, X. Zuo, C. Chen, and A. E. Smith, A clonal selection algorithm for urban bus vehicle scheduling, Applied Soft Computing, 36 (2015), pp. 36–44.
[58] A. A. Sori, A. Ebrahimnejad, H. Motameni, and J. L. Verdegay, Fuzzy constrained shortest path problem for location-based online services, Int. J. Uncertain. Fuzziness Knowl.-Based Syst., 29 (2021), pp. 231– 248.
[59] M. Spada, M. Bierlaire, and T. M. Liebling, Decision-aiding methodology for the school bus routing and scheduling problem, Transportation Science, 39 (2005), pp. 477–490.
[60] D. Tas¸, M. Gendreau, N. Dellaert, T. Van Woensel, and A. G. De Kok, Vehicle routing with soft time windows and stochastic travel times: A column generation and branch-and-price solution approach, European J. Oper. Res., 236 (2014), pp. 789–799.
[61] E. Uc¸ar, S¸. ˙I. Birbil, and ˙I. Muter, Managing disruptions in the multi-depot vehicle scheduling problem, Transp. Res. Part B: Methodol., 105 (2017), pp. 249–269.
[62] , Managing disruptions in the multi-depot vehicle scheduling problem, Transp. Res. Part B: Methodol., 105 (2017), pp. 249–269.
[63] M. W. Ulmer, Horizontal combinations of online and offline approximate dynamic programming for stochastic dynamic vehicle routing, Cent. Eur. J. Oper. Res., 28 (2020), pp. 279–308.
[64] R. van Lieshout, J. Mulder, and D. Huisman, The vehicle rescheduling problem with retiming, Comput. Oper. Res., 96 (2018), pp. 131–140.
[65] M. Wagale, A. P. Singh, A. K. Sarkar, and S. Arkatkar, Real-time optimal bus scheduling for a city using a dtr model, Procedia Soc. Behav. Sci., 104 (2013), pp. 845–854.
[66] C. Wang, H. Shi, and X. Zuo, A multi-objective genetic algorithm based approach for dynamical bus vehicles scheduling under traffic congestion, Swarm Evol. Comput., 54 (2020), p. 100667.
[67] M. Wei, X. Chen, B. Sun, and Y.-Y. Zhu, Model and algorithm for resolving regional bus scheduling problems with fuzzy travel times, J. Intell. Fuzzy Syst., 29 (2015), pp. 2689–2696.
[68] S. Yan and C.-H. Tang, An integrated framework for intercity bus scheduling under stochastic bus travel times, Transportation Science, 42 (2008), pp. 318–335.
[69] , Inter-city bus scheduling under variable market share and uncertain market demands, Omega, 37 (2009), pp. 178–192.
[70] X. Yu, S. Shen, and H. Wang, Integrated vehicle routing and service scheduling under time and cancellation uncertainties with application in nonemergency medical transportation, Service Science, 13 (2021), pp. 172–191.
[71] J. Zamani Kafshani, S. A. Mirhassani, and F. Hooshmand, Adopting grasp to solve a novel model for bus timetabling problem with minimum transfer and fruitless waiting times, AUT J. Math. Com., 1 (2020), pp. 125–134.