2026-08-06T09:02:24Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22187 2024-12-04T06:53:45Z ddc:004 open_access

Approximation Algorithms for Cumulative Vehicle Routing with Stochastic Demands Zhao, Jingyang Xiao, Mingyu Cumulative Vehicle Routing Stochastic Demands Approximation Algorithms In the Cumulative Vehicle Routing Problem (Cu-VRP), we need to find a feasible itinerary for a capacitated vehicle located at the depot to satisfy customers' demand, as in the well-known Vehicle Routing Problem (VRP), but the goal is to minimize the cumulative cost of the vehicle, which is based on the vehicle’s load throughout the itinerary. If the demand of each customer is unknown until the vehicle visits it, the problem is called Cu-VRP with Stochastic Demands (Cu-VRPSD). In this paper, we propose a randomized 3.456-approximation algorithm for Cu-VRPSD, improving the best-known approximation ratio of 6 (Discret. Appl. Math. 2020). Since VRP with Stochastic Demands (VRPSD) is a special case of Cu-VRPSD, as a corollary, we also obtain a randomized 3.25-approximation algorithm for VRPSD, improving the best-known approximation ratio of 3.5 (Oper. Res. 2012). At last, we give a randomized 3.194-approximation algorithm for Cu-VRP, improving the best-known approximation ratio of 4 (Oper. Res. Lett. 2013). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jingyang Zhao and Mingyu Xiao 2024 Is Part Of LIPIcs, Volume 322, 35th International Symposium on Algorithms and Computation (ISAAC 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2024.59 urn:nbn:de:0030-drops-221878 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.59 eng https://creativecommons.org/licenses/by/4.0/legalcode