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.
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:
- 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).
- 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.
- 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.,
kelly03andkelly04). - 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