Polynomial-Time Approximation Scheme for the Capacitated Vehicle Routing Problem with Time Windows
Tóm tắt
The capacitated vehicle routing problem with time windows (CVRPTW) is a well-known NP-hard combinatorial optimization problem. We present a further development of the approach first proposed by M. Haimovich and A. H. G. Rinnooy Kan and propose an algorithm that, for an arbitrary ε > 0, finds a (1 + ε)-approximate solution for the Euclidean CVRPTW in $$\text{TIME}\;(\text{TSP},\;\rho ,n)\; + \;O({n^2}) + O({e^{(q{{(\tfrac{q}{ \in })}^3}{{(p\rho )}^2}\log (p\rho ))}})$$, where q is an upper bound for the capacities of the vehicles, p is the number of time windows, and TIME(TSP, ρ, n) is the complexity of finding a ρ-approximation solution of an auxiliary instance of the Euclidean TSP. Thus, the algorithm is a polynomial-time approximation scheme for the CVRPTW with p3q4 = O(log n) and an efficient polynomial-time approximation scheme for arbitrary fixed values of p and q.
Tài liệu tham khảo
G. E. Andrews and K. Eriksson, Integer Partitions, 2nd ed. (Cambridge Univ. Press, Cambridge, 2004).
S. Arora, “Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems,” J. ACM 45 (5), 753–782 (1998). doi https://doi.org/10.1145/290179.290180
T. Asano, N. Katoh, H. Tamaki, and T. Tokuyama, “Covering points in the plane by k-tours: Towards a polynomial time approximation scheme for general k,” in Proceedings of the 29th Annual ACM Symposium on Theory of Computing, El Paso, USA, 1997 (ACM, New York, 1997), pp. 275–283. doi https://doi.org/10.1145/258533.258602
N. Christofides, Worst-Case Analysis of a New Heuristic for the Traveling Salesman Problem, Technical Report No. 388 (Carnegie Mellon Univ., Pittsburgh, 1976).
G. Dantzig and H. Ramser, “The truck dispatching problem,” Management Sci. 6 (1), 80–91 (1959).
A. Das and C. Mathieu, “A quasipolynomial time approximation scheme for Euclidean capacitated vehicle routing,” Algorithmica 73 (1), 115–142 (2015). doi https://doi.org/10.1007/s00453-014-9906-4
M. Haimovich and A. H. G. Rinnooy Kan, “Bounds and heuristics for capacitated routing problems,” Math. Oper. Res. 10 (4), 527–542 (1985). doi https://doi.org/10.1287/moor.10.4.527
M. Khachay and Y. Ogorodnikov, “Efficient PTAS for the Euclidean CVRP with time windows,” in Analysis of Images, Social Networks and Texts: Revised Selected Papers of the 7th International Conference, Moscow, Russia, 2018 (Springer, Cham, 2018), pp. 1–11.
M. Khachay and R. Dubinin, “PTAS for the Euclidean Capacitated Vehicle Routing Problem in Rd,” in Discrete Optimization and Operations Research: Proceedings of the 9th International Conference, Vladivostok, Russia, 2016 (Springer, Cham, 2016), pp. 193–205.
M. Khachay and H. Zaytseva, “Time approximation scheme for single-depot Euclidean capacitated vehicle routing problem,” in Combinatorial Optimization and Applications: Proceedings of the 9th International Conference, Houston, USA, 2015 (Springer, Cham, 2015), pp. 178–190.
S. Kumar and R. Panneerselvam, “A survey on the vehicle routing problem and its variants,” Intel. Inform. Management 4 (3), 66–74 (2012). doi https://doi.org/10.4236/iim.2012.43010
A. I. Serdyukov, “On some extremal routes in graphs,” Upravl. Sist., No. 17, 76–79 (1978).
L. Song and H. Huang, “The Euclidean Vehicle Routing Problem with multiple depots and time windows,” in Combinatorial Optimization and Applications: Proceedings of the 11th International Conference, Shanghai, China, 2017 (Springer, Cham, 2017), Part 2, pp. 449–456.
L. Song, H. Huang, and H. Du, “Approximation schemes for Euclidean vehicle routing problems with time windows,” J. Comb. Optimiz. 32 (4) (2016). doi 10.1007/s10878-015-9931-5
The Vehicle Routing Problem, Ed. by P. Toth and D. Vigo (SIAM, Philadelphia, 2001).