The complexity of cost constrained vehicle scheduling problem

Document Type : Original Article

Authors

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

2 Department of Mathematics and Computer Science, Amirkabir University of Technology (Tehran Polytechnic), Tehran, Iran

Abstract

This paper considered the cost constrained vehicle scheduling problem under the constraint that the total number of vehicles is known in advance. Each depot has a different time processing cost. The goal of this problem is to find a feasible minimum cost schedule for vehicles. A mathematical formulation of the problem is developed and the complexity of the problem when there are more than two depots is investigated. It is proved that in this case, the problem is NP-complete. Also, it is showed that there is not any constant ratio approximation algorithm for the problem, i.e., it is in the complexity class APX.

Keywords

Main Subjects

References

[1] R. K. Ahuja, T. L. Magnanti, J. B. Orlin, Network flows: theory, algorithms and applications, Prentice-Hall, Englewood Cliffs, NJ, 1993.
[2] D. P. Bertsekas, Linear Network Optimization: Algorithms and Codes, MIT Press, Cambridge, MA, 1991.
[3] L. Bodin, B. Golden, A. Assad, M. Ball, Routing and scheduling of vehicles and crews: the state of the art, Computers and Operations Research, 10 (1983) 63-211.
[4] G. Carpaneto, M. DellAmico, M. Fischetti, P. Toth, A branch and bound algorithm for the multiple vehicle scheduling problem, Computers and Operations Research, 19 (1989) 531-548.
[5] S. Carosi, A. Frangioni, L. Galli, L. Girardi, G. Vallese, A matheuristic for integrated timetabling and vehicle scheduling. Transportation Research Part B: Methodological, 127 (2019) 99-124.
[6] M. DellAmico, M. Fischetti, P. Toth, Heuristic algorithms for the multiple depot vehicle scheduling problem, Management Science, 39 (1993) 115-125.
[7] J. Desrosiers, Y. Dumas, M. M. Solomon, F. Soumis, Time constrained routing and schedulin, Handbooks in operations research and management science: Network routing, M. O. Ball, T. L. Magnanti, C. L. Monma and G. L. Nemhauser (Eds.), (1995) 35-139.
[8] D. T. Eliiyi, A. Ornek, S. S. Karaku tu, A vehicle scheduling problem with fixed trips and time limitations, International Journal of Production Economics, 117 (2009) 150-161.
[9] M. A. Forbes, J. N. Holt, A. M. Watts, An exact algorithm for multiple depot bus scheduling, European Journal of Operational Research, 72 (1994) 115-124.
[10] R. Freling, A. P. M. Wagelmans, J. M. P. Paixo, Models and Algorithms for Single-Depot Vehicle Scheduling, Transportation Science, 35 (2001) 165-180.
[11] M. R. Garey, D. S. Johnson, Computer and Intractability, A Guide to the Theory of NP-Completeness, New York, NY, USA, 2000.
[12] P. C. Guedes, D. Borenstein, Column generation based heuristic framework for the multiple-depot vehicle type scheduling problem, Computers & Industrial Engineering, 90 (2015), 361-370.
[13] V. Guihaire, J. K. Hao, Transit network design and scheduling: A global review, Transportation Research Part A, 42 (2008), 1251-1273.
[14] A. Hadjar, O. Marcotte, F. Soumis, A branch-and-cut algorithm for the multiple depot vehicle scheduling problem, Operations Research, 54 (2006) 130-149.
[15] N. Huimin, Z. Xuesong, T. Xiaopeng, Coordinating assignment and routing decisions in transit vehicle schedules: A variable-splitting Lagrangian decomposition approach for solution symmetry breaking, Transportation Research Part B: Methodological, 107 (2018) 70-101.
[16] O. J. Ibarra-Rojas, R. Giesen, Y. A. Rios-Solis, An integrated approach for timetabling and vehicle scheduling problems to analyze the tradeoff between level of service and operating costs of transit networks, Transportation Research Part B, 70 (2014) 35-46.
[17] B. Laurent, J.-K. Hao, Iterated local search for the multiple depot vehicle scheduling problem, Computers & Industrial Engineering, 57 (2009), 277-286.
[18] Q. Huang, E Lloyd, Cost Constrained Fixed Job Scheduling, Theoretical computer sciences, proceedings. Lecture notes in computer science, 2003.
[19] N. Kliewer, T. Mellouli, L. Suhl, A timespace network based exact optimization model for multi-depot bus scheduling, European Journal of Operational Research, 175 (2006) 1616-1627.
[20] S. Kulkarni, M. Krishnamoorthy, A. Ranade, A. T. Ernst, R. Patil, A new formulation and a column generation-based heuristic for the multiple depot vehicle scheduling problem, Transportation Research Part B: Methodological, 118 (2018) 457-487.
[21] M. Mesquita, J. Paixo, Multiple depot vehicle scheduling problem: a new heuristic based on quasi-assignment algorithms, Lecture notes in economics and mathematical systems, Computeraided transit scheduling, M. Desrochers and J.-M. Rousseau (Eds.), (1992) 167-180.
[22] M. Mnich, R. van Bevern, Parameterized complexity of machine scheduling: 15 open problems. Computers & Operations Research, 100 (2018) 254-261.
[23] H. Nagamochi, T. Ohnishi, Approximating a vehicle scheduling problem with time windows and handling times, Theoretical Computer Science, 393, (2008) 33-146.
[24] M. Niksirat, S. M. Hashemi, M. Ghatee, Branch-and-price algorithm for fuzzy integer programming problems with block angular structure, Fuzzy Sets and Systems, 296 (2016) 70-96.
[25] T. Liu, A. A. Ceder, Battery-electric transit vehicle scheduling with optimal number of stationary chargers. Transportation Research Part C: Emerging Technologies, 114 (2020) 118-139.
[26] E. Levner, V. Kats, D. A. L. de Pablo, T. E. Cheng, Complexity of cyclic scheduling problems: A state-of-the-art survey. Computers & Industrial Engineering, 59 (2010) 352-361.
[27] A. R. Odoni, J.-M. Rousseau, N. H. M. Wilson, Multiple depot vehicle scheduling problem: a new heuristic based on quasi-assignment algorithms, Handbooks in operations research and management, S. M. Pollock, M. H. Rothkopf, and A. Barnett (Eds.)”, (1994) 107-150.
[28] E. F. Olariu, C. Frasinaru, Multiple-Depot Vehicle Scheduling Problem Heuristics, 2020, arXiv preprint arXiv:2004.14951.
[29] C.Ribeiro, F. Soumis, A column generation approach to the multiple depot vehicle scheduling problem, Operations Research, 42 (1994) 41-52.
[30] J. Ren, D. Du, D. Xu, The complexity of two supply chain scheduling problems. Information Processing Letters, 113 (2013) 609-612.
[31] G. Simonin, R. Giroudeau, J. C. K¨onig, Complexity and approximation for scheduling problem for a torpedo. Computers & Industrial Engineering, 61 (2011) 352-356.
[32] C. Wang, H. Shi, X. Zuo, A multi-objective genetic algorithm based approach for dynamical bus vehicles scheduling under traffic congestion. Swarm and Evolutionary Computation, 54 (2020) 100667.
[33] E. Yao, T. Liu, T.Lu, Y. Yang, Optimization of electric vehicle scheduling with multiple vehicle types in public transport. Sustainable Cities and Society, 52 (2020) 101862.
[34] Y. Zheng, Y. Shang, Z. Shao, L. Jian, A novel real-time scheduling strategy with near-linear complexity for integrating large-scale electric vehicles into smart grid. Applied Energy, 217 (2018) 1-13.
AUT Journal of Mathematics and Computing
Volume 2, Issue 1
February 2021
Pages 109-115

Files

Share

How to cite

Statistics