Approximation Algorithms for the Cumulative Vehicle Routing Problem with Stochastic Demands
Jingyang Zhao, Mingyu Xiao · 2025
Read Approximation Algorithms for the Cumulative Vehicle Routing Problem with Stochastic Demands by Jingyang Zhao, Mingyu Xiao (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-08316.txt.
Introduction
Jingyang Zhao and Mingyu Xiao present a 2025 study of delivery routing when customer demand is unknown until the truck arrives. The cost they minimize is cumulative, meaning it grows with the load the truck carries along the whole route, not just the distance driven. They design approximation algorithms, methods that are fast and come with a proof of how close their answers sit to the best possible.
Their main method improves the best known guarantee for the uncertain-demand version, cutting the worst-case bound from six times optimal to about 3.46. A related version of the problem gains a bound of about 3.25. For the version with known demand, their bound of about 3.19 beats the old mark of four. Allowing split deliveries improves the bounds further.
Catalog record
| CREATOR | Jingyang Zhao, Mingyu Xiao |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 142 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-08316
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Approximation Algorithms for the Cumulative Vehicle Routing Problem with Stochastic Demands Jingyang Zhao, Mingyu Xiao Abstract 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). Assume that the approximation ratio of metric TSP is 1.5 1.5 . In this paper, we propose a randomized 3.456 3.456 -approximation algorithm for Cu-VRPSD, improving the best-known approximation ratio of 6 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 3.25 -approximation algorithm for VRPSD, improving the best-known approximation ratio of 3.5 3.5 (Oper. Res. 2012). For Cu-VRP, we give a randomized 3.194 3.194 -approximation algorithm, improving the best-known approximation ratio of 4 4 (Oper. Res. Lett. 2013). Moreover, if each customer is allowed to be satisfied by using multiple tours, we obtain further improvements for Cu-VRPSD and Cu-VRP. 1 Introduction In the well-known Vehicle Routing Problem (VRP) [ 8 ] , we are given an undirected complete graph G=(V,E) with V=\{v_{0},v_{1},\dots,v_{n}\} , where v_{0} denotes the depot, and the other n vertices denote n customers. Moreover, there is a metric weight function w on the edges representing the length of edges, which satisfies the triangle inequality, and a demand vector d=(d_{1},...,d_{n}) implying that each customer v_{i} has a demand of d_{i} . The objective is to determine an itinerary for a vehicle with a capacity of Q , starting from and ending at the depot, that fulfills every customer’s demand while minimizing the total weight of the edges in the itinerary. In the Cumulative Vehicle Routing Problem (Cu-VRP) [ 20 , 21 ] , the goal is also to find an itinerary for the vehicle, but with the objective of minimizing the cumulative cost of the itinerary. Here, the cumulative cost for the vehicle traveling from u to v carrying a load of x_{uv}\leq Q units of goods is defined as a\cdot w(u,v)+b\cdot x_{uv}\cdot w(u,v) , where a,b\in\mathbb{R}_{\geq 0} are given parameters. Specifically, a represents the cost of moving an empty vehicle per unit distance, and b represents the cost of transporting one unit of goods per unit distance. Moreover, when a=1 and b=0 , Cu-VRP reduces to VRP. For example, consider an itinerary T=v_{0}v_{1}v_{2}v_{0} , where we let e_{i}=v_{i-1}v_{i\bmod 3} and w(e_{i})=1 for each i\in\{1,2,3\} . Assume that the vehicle picks up 8 units of goods at the depot and delivers 2 units each to v_{1} and v_{2} along the itinerary, respectively. We can obtain x_{e_{1}}=8 , x_{e_{2}}=6 , x_{e_{3}}=4 , and thus the cumulative cost of T is a\cdot 3+b\cdot(8+6+4)=3a+18b . Note that the item b\cdot x_{e_{3}}\cdot w(e_{3}) , where e_{3} is the last edge of T , represents the additional carrying cost incurred by the vehicle for goods that are picked up but not delivered during the itinerary. Cu-VRP captures the fuel consumption in transportation and logistics, as fuel consumption depends on both the weight of the empty vehicle and the weight of the goods being carried by the vehicle [ 25 , 13 ] . In fact, it is a simplified model for fuel consumption with a linear objective function for VRP [ 30 ] . Since fuel consumption can account for as much as 60% of a vehicle’s operational costs [ 26 ] , Cu-VRP has been studied extensively through experimental algorithms [ 12 , 28 , 9 , 11 , 24 ] . Specifically, Gaur and Singh 2017 proposed a heuristic algorithm using the column generation method. Wang et al. 2016 generalized Cu-VRP into the model with multi-depots. Cu-VRP with time windows was investigated in [ 9 ] , and Cu-VRP with a limitation on the number of used tours was studied in [ 11 , 24 ] . A recent survey of Cu-VRP can be found in [ 7 ] . In VRP with Stochastic Demands (VRPSD) [ 3 ] , the demand of each customer is represented by an independent random variable with a known distribution, and its value is unknown until the vehicle visits the customer. The goal is to design a policy such that the expected weight of the itinerary is minimized. This model has natural applications in logistic where the demands of customers are unknown before routing the vehicle, and early surveys on this topic can be found in [ 16 , 4 ] . Cu-VRP with Stochastic Demands (Cu-VRPSD) was proposed in [ 14 ] , and similarly, the goal is to design a policy such that the expected cumulative cost of the itinerary is minimized. Moreover, Cu-VRPSD reduces to VRPSD when a=1 and b=0 . We observe that in VRPSD, the vehicle can always be fully loaded before departing from the depot. However, in Cu-VRPSD, due to the fact that both higher and lower loads may result in higher cumulative costs, we need to carefully consider how the vehicle is loaded. This property makes Cu-VRPSD both more challenging and more interesting compared to VRPSD. In each of the above problems, the splittable (resp., unsplittable ) variant requires that the demand of each customer can be satisfied partially within the vehicle’s visits (resp., must be satisfied entirely in one of the vehicle’s visits). Usually, the unsplittable variants are more difficult. For example, unsplittable VRP generalizes the bin packing problem even on a line shape graph [ 29 ] , and thus cannot be approximated with an approximation ratio of less than 1.5 unless P=NP. In contrast, while splittable VRP is known to be APX-hard [ 2 ] , the best-known inapproximability bound is significantly smaller than 1.5. 1.1 Related Works We mainly focus on the design of approximation algorithms , which can generate solutions with a theoretical guarantee in polynomial time. For Cu-VRP, an algorithm is called a \rho -approximation algorithm if it can output a solution with a cumulative cost of at most \rho\cdot\mbox{OPT} in polynomial time, where OPT is the cumulative cost of the optimal solution. For Cu-VRPSD, an algorithm is called a \rho -approximation algorithm if it can employ a policy to obtain a solution with an expected cumulative cost of at most \rho\cdot\mbox{OPT} in polynomial time, where OPT is the cumulative cost of the minimum expected cumulative cost solution obtained by the optimal policy. Let \alpha denote the approximation ratio of the metric Traveling Salesman Problem (TSP). It is well-known that \alpha\leq 1.5 [ 6 , 27 ] , which was slightly improved to \alpha\leq 1.5-10^{-36} [ 22 , 23 ] . The approximation ratio \alpha for TSP will be frequently used in VRP related problems. VRP(SD). For VRP, there is an (\alpha+1) -approximation algorithm for the splittable case [ 19 ] , and an (\alpha+2) -approximation algorithm for the unsplittable case [ 1 ] . Recently, Blauth et al. 2023 improved the approximation ratio to \alpha+1-\varepsilon for the splittable case,