Approximation Schemes for Capacity Vehicle Routing Problems: A Survey
Электронный научный архив УРФУ
Информация об архиве | Просмотр оригинала| Поле | Значение | |
| Заглавие |
Approximation Schemes for Capacity Vehicle Routing Problems: A Survey
|
|
| Автор |
Chen, Y.
|
|
| Тематика |
APPROXIMATION ALGORITHMS
CAPACITY VEHICLE ROUTING PROBLEMS COMBINATORIAL OPTIMIZATION POLYNOMIAL-TIME APPROXIMATION SCHEME APPROXIMATION ALGORITHMS POLYNOMIAL APPROXIMATION ROUTING ALGORITHMS VEHICLE ROUTING VEHICLES APPROXIMATION SCHEME CAPACITATED VEHICLE ROUTING PROBLEM CAPACITY CONSTRAINTS CAPACITY VEHICLE ROUTING PROBLEMS CLASSIFIEDS COMBINATORIAL OPTIMIZATION PROBLEMS LOGISTICS NETWORK OPTIMAL ROUTES POLYNOMIAL TIME APPROXIMATION SCHEMES TOTAL DISTANCES COMBINATORIAL OPTIMIZATION |
|
| Описание |
The Capacity Vehicle Routing Problem (CVRP) pertains to the combinatorial optimization problem of identifying the optimal route for vehicles with a capacity constraint of k to travel from the depots to customers, which minimizes the total distance traveled. The Capacitated Vehicle Routing Problem (CVRP), which is essential to modelling logistics networks, has drawn a lot of interest in the field of combinatorial optimization. It has been established that the CVRP (Capacitated Vehicle Routing Problem) with a value of k greater than or equal to three exhibits computational complexity that is classified as NP-hard. Furthermore, it has been established that the problem is APXhard. It has been previously established that the solution is not approximatable in a metric space. Furthermore, this constitutes the principal challenge among the array of issues that confront Arora's approximation algorithm. The outstanding matter concerns the presence of a (1+$\epsilon$) PTAS (polynomial time approximation scheme) for the capacity vehicle routing problem in Euclidean space, regardless of the vehicle's capacity. The objective of this manuscript is to furnish a thorough and all-encompassing survey of the research progressions in the domain, encompassing the evolution of the field from its inception to the most recent cutting-edge discoveries. © 2023 IEEE.
|
|
| Дата |
2024-04-05T16:38:49Z
2024-04-05T16:38:49Z 2023 |
|
| Тип |
Conference Paper
Conference object (info:eu-repo/semantics/conferenceObject) info:eu-repo/semantics/submittedVersion |
|
| Идентификатор |
Chen, Y 2023, Approximation Schemes for Capacity Vehicle Routing Problems: A Survey. в Proceedings - 2023 2nd International Conference on Computational Modelling, Simulation and Optimization, ICCMSO 2023: book. Institute of Electrical and Electronics Engineers Inc., стр. 277-282, 2023 2nd International Conference on Computational Modelling, Simulation and Optimization (ICCMSO), 23/06/2023. https://doi.org/10.1109/ICCMSO59960.2023.00059
Chen, Y. (2023). Approximation Schemes for Capacity Vehicle Routing Problems: A Survey. в Proceedings - 2023 2nd International Conference on Computational Modelling, Simulation and Optimization, ICCMSO 2023: book (стр. 277-282). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ICCMSO59960.2023.00059 9798350326666 Final All Open Access, Green https://www.scopus.com/inward/record.uri?eid=2-s2.0-85181172283&doi=10.1109%2fICCMSO59960.2023.00059&partnerID=40&md5=f24e85db0e8ce863d2acdf7e0f49fd2f https://arxiv.org/pdf/2306.01826 http://elar.urfu.ru/handle/10995/131099 10.1109/ICCMSO59960.2023.00059 85181172283 |
|
| Язык |
en
|
|
| Права |
Open access (info:eu-repo/semantics/openAccess)
|
|
| Формат |
application/pdf
|
|
| Издатель |
Institute of Electrical and Electronics Engineers Inc.
|
|
| Источник |
2023 2nd International Conference on Computational Modelling, Simulation and Optimization (ICCMSO)
Proceedings - 2023 2nd International Conference on Computational Modelling, Simulation and Optimization, ICCMSO 2023 |
|