Goods Consumed During Transit in Split Delivery Vehicle Routing Problems: Modeling and Solution

Wenzhe Yang, Di Wang, Wei Pang, Ah-Hwee Tan, You Zhou

Introduction

In traditional logistics modeling, the Vehicle Routing Problem (VRP) focuses on optimizing delivery routes to minimize total distance or cost, assuming that the cargo remains constant until it is delivered to the customer. However, in high-stakes or harsh environments—such as disaster relief in deserts or military replenishment in conflict zones—the vehicle often consumes the very resources it is transporting (e.g., fuel, water, or food) to complete the journey.

This paper introduces a novel variant: the Split Delivery Vehicle Routing Problem with Goods Consumed during Transit (SDVRP-GCT). In this scenario, vehicle capacity is depleted not only by deliveries but also by the distance traveled, creating a complex optimization challenge where the "cost" of the road must be balanced against customer demand.

Problem Definition: The GCT Constraint

The SDVRP-GCT model extends the standard split delivery framework by incorporating a consumption parameter ($h$). This parameter represents the rate at which goods are consumed per unit of distance. Unlike standard models where capacity is a simple subtraction of delivered goods, the SDVRP-GCT requires accounting for a "transit tax" on the cargo at every kilometer.

Figure (a): Network representation showing customer demands at nodes.

As illustrated in the figures above, a central depot (#0) serves multiple customers (#1, #2, #3). Each customer has a specific demand (e.g., 10, 7, or 5 units), and each path between nodes has a defined distance. In the GCT model, a vehicle leaving the depot must carry enough cargo to satisfy the customer's demand plus the amount it will consume to reach that customer and return to the depot. If the total requirement exceeds the vehicle's capacity, the delivery must be split across multiple trips or vehicles.

Methodology: Adapted Ant Colony Optimization

To solve this NP-hard problem, the researchers adapted three variants of Ant Colony Optimization (ACO), a meta-heuristic inspired by the pheromone-trailing behavior of ants:

  1. ASGCT (Ant System): The baseline algorithm where pheromone trails are updated based on the total cost of all paths found by the "ants" (simulated vehicles).
  2. ACGCT (Ant Colony System): A more advanced version utilizing local pheromone updates to encourage exploration and a global update reserved for the best-performing path.
  3. MMGCT (Max-Min Ant System): Designed to prevent premature convergence on sub-optimal solutions by restricting pheromone levels to a specific range ($[\tau_{min}, \tau_{max}]$).

The algorithms incorporate split-delivery logic: if an ant's remaining capacity cannot fulfill a customer's total demand while still allowing for the return trip's consumption, it delivers the maximum possible amount and leaves the remainder for subsequent vehicles.

Experimental Evaluation and Key Insights

The study tested these algorithms against three distinct datasets: modified SDVRPLIB benchmarks, large-scale "Kelly" instances (up to 480 customers), and a real-world case study involving travel across China. In the China instance, the "cargo" was abstractly defined as time, where the vehicle's capacity was a 15-day vacation limit and consumption represented travel time between provinces.

Key Results

  • Algorithm Performance: The MMGCT variant proved most robust, achieving an average gap of only 0.96% from theoretical optima on standard benchmarks. However, ACGCT outperformed others in high-demand scenarios where vehicle capacity was tightly constrained.
  • Scaling Capabilities: On large-scale instances, the proposed ACO methods were highly effective, even surpassing previously known optimal values for certain complex datasets (e.g., kelly03 and kelly04).
  • Impact of Consumption: As the consumption rate ($h$) increases, the total travel distance rises significantly. This is because vehicles must return to the depot more frequently to replenish their capacity, effectively reducing their delivery range.

Conclusion and Future Directions

The SDVRP-GCT model provides a more realistic framework for logistics in environments where resources are scarce or travel costs are intrinsically linked to the cargo. While the current ACO-based heuristics show great promise, the authors note that future work could incorporate variable consumption rates (e.g., fuel consumption changing as the vehicle gets lighter) and multi-depot configurations. Combining ACO with other heuristics like Genetic Algorithms could further refine solutions for real-time, high-complexity logistics operations.

Summary updated

Abstract

This article presents the modeling and solution of an extended type of split delivery vehicle routing problem (SDVRP). In SDVRP, the demands of customers need to be met by efficiently routing a given number of capacitated vehicles, wherein each customer may be served multiple times by more than one vehicle. Furthermore, in many real-world scenarios, consumption of vehicles en route is the same as the goods being delivered to customers, such as food, water and fuel in rescue or replenishment missions in harsh environments. Moreover, the consumption may also be in virtual forms, such as time spent in constrained tasks. We name such a real-world SDVRP as Split Delivery Vehicle Routing Problem with Goods Consumed during Transit (SDVRP-GCT). In this paper, we give mathematical formulas to model SDVRP-GCT and provide solutions by extending three ant colony algorithms. To the best of our knowledge, this is the first research work specifically focussing on the SDVRP-GCT problem and its solutions. To assess the effectiveness of our proposed ant colony algorithms, we first apply them on widely adopted SDVRP benchmarking instances on different scales and their correspondingly extended SDVRP-GCT instances. Then, we formulate a real-world SDVRP-GCT instance for further assessment. Based on the extensive experimental results, we discuss the pros and cons of our proposed solutions and subsequently suggest their preferable application scenarios. In summary, our proposed solutions are shown as highly efficient in solving SDVRP-GCT instances.
BibTeX
@article{yang2020goods,
  author = {Wenzhe Yang and Di Wang and Wei Pang and Ah-Hwee Tan and You Zhou},
  title = {{Goods Consumed During Transit in Split Delivery Vehicle Routing Problems: Modeling and Solution}},
  journal = {IEEE Access},
  year = {2020},
  doi = {10.1109/access.2020.3001590},
}
Figure