TY - JOUR
ID - 4274
TI - The complexity of cost constrained vehicle scheduling problem
JO - AUT Journal of Mathematics and Computing
JA - AJMC
LA - en
SN - 2783-2449
AU - Niksirat, Malihe
AU - Hashemi, Seyed Naser
AD - Department of Computer Science, Faculty of Computer and Industrial Engineering, Birjand University of Technology, Birjand, Iran
AD - Department of Mathematics and Computer Science, Amirkabir University of Technology (Tehran Polytechnic), Tehran, Iran
Y1 - 2021
PY - 2021
VL - 2
IS - 1
SP - 109
EP - 115
KW - Vehicle scheduling problem
KW - Fixed job scheduling
KW - NP-complete
KW - Approximation algorithm
KW - APX
DO - 10.22060/ajmc.2021.19454.1046
N2 - 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.
UR - https://ajmc.aut.ac.ir/article_4274.html
L1 - https://ajmc.aut.ac.ir/article_4274_68f3cbb47d8809e62a4acbba2ee0cc75.pdf
ER -