The complexity of cost constrained vehicle scheduling problem | ||
| AUT Journal of Mathematics and Computing | ||
| مقاله 12، دوره 2، شماره 1، اردیبهشت 2021، صفحه 109-115 اصل مقاله (442.97 K) | ||
| نوع مقاله: Original Article | ||
| شناسه دیجیتال (DOI): 10.22060/ajmc.2021.19454.1046 | ||
| نویسندگان | ||
| Malihe Niksirat* 1؛ Seyed Naser Hashemi2 | ||
| 1Department of Computer Science, Faculty of Computer and Industrial Engineering, Birjand University of Technology, Birjand, Iran | ||
| 2Department of Mathematics and Computer Science, Amirkabir University of Technology (Tehran Polytechnic), Tehran, Iran | ||
| چکیده | ||
| 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. | ||
| کلیدواژهها | ||
| Vehicle scheduling problem؛ Fixed job scheduling؛ NP-complete؛ Approximation algorithm؛ APX | ||
| مراجع | ||
|
| ||
|
آمار تعداد مشاهده مقاله: 1,529 تعداد دریافت فایل اصل مقاله: 1,029 |
||
| تعداد نشریات | 9 |
| تعداد شمارهها | 455 |
| تعداد مقالات | 5,771 |
| تعداد مشاهده مقاله | 8,375,705 |
| تعداد دریافت فایل اصل مقاله | 6,934,636 |