Approximation schemes for capacity vehicle routing problems: A survey
| Autor: | Chen, Yongyu |
|---|---|
| Rok vydání: | 2023 |
| Předmět: | |
| Zdroj: | 2nd International Conference on Computational Modelling, Simulation and Optimization (ICCMSO-2023) |
| Druh dokumentu: | Working Paper |
| DOI: | 10.1109/ICCMSO59960.2023.00059 |
| Popis: | Finding the shortest travelling tour of vehicles with capacity k from the depot to the customers is called the Capacity vehicle routing problem (CVRP). CVRP plays an essential position in logistics systems, and it is the most intensively studied problem in combinatorial optimization. In complexity, CVRP with k $\ge$ 3 is an NP-hard problem, and it is APX-hard as well. We already knew that it could not be approximated in metric space. Moreover, it is the first problem resisting Arora's famous approximation framework. So, whether there is, a polynomial-time (1+$\epsilon$)-approximation for the Euclidean CVRP for any $\epsilon>0$ is still an open problem. This paper will summarize the research progress from history to up-to-date developments. The survey will be updated periodically. Comment: This work has been submitted to the IEEE for possible publication. Copyright may be transferred without notice, after which this version may no longer be accessible |
| Databáze: | arXiv |
| Externí odkaz: |
|