TL;DR
This paper introduces new sweep algorithm variants specifically designed for the Capacitated Vehicle Routing Problem with Structured Time Windows (cVRPsTW), a common scenario in attended home delivery. By adapting and extending traditional sweep methods, the authors achieve efficient and high-quality solutions for large-scale instances, outperforming existing approaches in certain scenarios.
What Problem Does This Paper Address?
The paper tackles the challenge of optimizing delivery routes for services like online grocery shopping, where customers specify preferred delivery time windows. This problem, known as the Capacitated Vehicle Routing Problem with Structured Time Windows (cVRPsTW), is a complex optimization task. The "structured" aspect refers to a scenario where there are many customers but relatively few, non-overlapping time windows, a realistic assumption for attended home delivery. Traditional sweep algorithms, effective for simpler vehicle routing problems, need adaptation to handle these time window constraints and the specific structure of the problem. The goal is to minimize costs, which are primarily driven by the number of vehicles used, followed by total delivery duration and travel time.
Methods
The authors propose a three-step strategy:
- Clustering: Using modified sweep algorithms to group customers into potential delivery routes.
- Simple Sweep: A generalization of traditional sweep that considers time and capacity feasibility for each cluster.
- Window-wise Sweep: Exploits the structured time windows by defining clusters based on these windows, making it efficient when time windows are the primary constraint.
- Corrective Sweep: Addresses scenarios where vehicle capacity is the main bottleneck, aiming to prevent early clusters from consuming too much capacity.
- Local Improvement: Applying heuristics to refine the initial clustering and improve solution quality.
- Routing: Computing optimal routes for each cluster using Mixed-Integer Linear Programming (MILP) formulations for the Traveling Salesperson Problem with Time Windows (TSPTW) or its structured variant (TSPsTW).
A key innovation is the adaptation of sweep algorithms to directly incorporate the structured time windows, allowing for window-dependent angle calculations. They also introduce a "tree-feasibility" check as a quick way to detect potential time infeasibilities.
Datasets
The authors created a new benchmark set specifically designed to mimic urban settlement structures and attended home delivery scenarios. This set features:
- Customers distributed on a 20 km x 20 km grid (similar to Vienna).
- A mix of uniform and clustered customer distributions.
- Travel times proportional to Euclidean distances, assuming a 20 km/h travel speed.
- Ten consecutive one-hour time windows per customer.
- A 5-minute service time per customer.
- Order weights sampled from a truncated normal distribution.
- Configurations with varying numbers of customers (n = 250, 500, 1000, 2000) and vehicle capacities (C = 200, 400).
- 100 instances generated for each configuration.
The benchmark instances are made publicly available.
Key Insights and Ideas
- Structured Time Windows Offer Opportunities: The specific structure of time windows (few, non-overlapping) is not just a constraint but an opportunity to develop more efficient algorithms, as demonstrated by the Window-wise Sweep.
- Capacity vs. Time Windows: The performance of different sweep variants is highly dependent on whether vehicle capacity or time window constraints are the more limiting factor in an instance.
- Local Improvement is Crucial for Duration/Travel Time: While local improvement heuristics don't significantly reduce the number of vehicles (λ1), they substantially improve the total schedule duration (λ2) and travel time (λ3).
- "Tree-Feasibility" as an Efficient Check: This concept provides a fast way to identify potential time infeasibilities in tours before resorting to more computationally expensive MILP solvers.
Key Results
The paper presents results for instances with n=2000 customers.
- Without Improvement:
- When capacity is limiting (C=200), Simple Sweep and Corrective Sweep performed similarly, outperforming Window-wise Sweep in terms of the number of vehicles (λ1).
- When time windows are limiting (C=400), Window-wise Sweep yielded the best results for both the number of vehicles (λ1) and schedule duration (λ2).
- With Improvement:
- Applying local improvement heuristics significantly reduced schedule duration (λ2) and travel time (λ3) for all sweep variants, though the reduction in the number of vehicles (λ1) was minimal.
- For large instances (n=2000), the algorithms could find feasible schedules in seconds to a few minutes, and improved schedules in under 25 minutes.
- The authors generally recommend Corrective Sweep as a good all-around algorithm, but suggest Window-wise Sweep when time window constraints are dominant or schedule duration is paramount.
Limitations and Future Work
- Limitations: The paper acknowledges that local improvement heuristics rarely reduce the primary objective (number of vehicles). The performance of algorithms is instance-dependent, requiring careful selection based on whether capacity or time windows are the stronger constraint.
- Future Work: The authors suggest that their approach is capable of finding good initial solutions for large instances, implying that further research could focus on integrating these heuristics with exact methods or exploring more advanced local search techniques. The benchmark set they created is also a foundation for future research in this area.
Summary updated