TL;DR
This paper presents an optimization system for a sedan service that dynamically schedules drivers and routes vehicles to meet customer demands within tight time windows. By combining a powerful integer programming solver with a fast local-search heuristic, the system significantly improves operational efficiency and driver productivity in a highly dynamic environment.
What Problem Does This Paper Address?
The core challenge addressed is the real-time optimization of vehicle routing and driver scheduling for a sedan service. This involves efficiently assigning drivers to rides, planning their routes, and managing their shifts to satisfy customer requests that have specific pickup times and tight delivery windows. The dynamic nature of this problem is crucial: new ride requests arrive, existing ones change or are canceled, and actual ride start times and durations can deviate from forecasts. Traditional manual scheduling methods struggle to keep up with these constant changes, leading to inefficiencies and increased costs. The paper aims to create a system that can adapt to these dynamics and provide near-optimal schedules quickly enough to be useful.
Methods
The paper proposes a multi-faceted approach combining optimization techniques:
- Integer Programming (IP) with Column Generation: The core of the static problem (planning for a given set of demands) is formulated as an integer program. To handle the vast number of possible driver schedules, a column generation technique is employed. This involves iteratively generating "columns" (representing driver schedules) that have the potential to improve the current solution, rather than enumerating all possibilities upfront.
- Volume Algorithm: Instead of the traditional simplex algorithm, the authors use the volume algorithm for solving the linear programming relaxations within column generation. This is noted to improve convergence and provide higher-quality dual solutions.
- Fix-and-Price Heuristic: To bridge the gap between the near-optimal LP solution and a feasible integer solution, a fix-and-price heuristic is used. This involves fixing some variables (representing schedules) to 1 and then re-optimizing. This process is iterative, progressively reducing the problem size and finding a high-quality integer solution.
- Local-Search Heuristics: For rapid updates in response to immediate events (like a ride running late) or to refine solutions, local-search heuristics are employed. These include "depth-one" and "depth-two" searches for assigning individual rides and a "Ripup-redo" strategy that randomly removes and reinserts rides to escape local optima.
- Handling Lateness: A key challenge is incorporating lateness. The system models this with penalties and adapts the shortest path subproblem in column generation to account for allowed lateness within certain buffers.
Datasets
The paper evaluates its approach on six sample instances, referred to as "Prob 1" through "Prob 6." These instances represent real-world scenarios with varying numbers of rides, drivers, and time periods. The paper does not introduce new benchmark datasets but uses these instances to demonstrate the performance of their system.
Key Insights and Ideas
- Column Generation is Key for Scale: The sheer number of possible driver schedules makes enumerating them infeasible. Column generation is essential for tackling this combinatorial explosion by generating only the most promising schedules as needed.
- Duals Drive Schedule Generation: The "reduced cost" of a potential schedule is calculated using dual values from the linear program. Generating schedules with negative reduced costs is equivalent to finding shortest paths in a specially constructed graph, making the problem computationally tractable.
- Heuristics for Speed and Robustness: While IP provides near-optimal solutions, it can be slow. Local-search heuristics are crucial for real-time responsiveness and for refining IP solutions, especially in dynamic environments where immediate adjustments are needed.
- Balancing Static and Dynamic Optimization: The system effectively separates the static problem of initial scheduling from the dynamic problem of maintaining that schedule. This allows for periodic re-optimization while also handling immediate, event-driven changes.
- "Follow-on Fixing" for Efficiency: Identifying pairs of rides that frequently appear together in optimal solutions and fixing them as a unit significantly speeds up the heuristic process.
Key Results
- Significant Productivity Gains: The system, in full-time use since March 2003, has "improved the provider's productivity significantly."
- Near-Optimal Solutions Quickly: The fix-and-price heuristic solves problems to near-optimality in under 3 minutes on average, with most of the time spent obtaining a high-quality LP solution.
- Modest Cost Degradation in Online Mode: The average cost per ride (CPR) increased by 7% to 28% from the offline (clairvoyant) estimate to the actual online cost. This degradation is attributed to factors like travel time estimation errors, human factors, and demand changes, and is considered "quite modest."
- Reduced Column Generation Iterations: Using the volume algorithm instead of simplex reduced column generation iterations and the number of generated schedules by about 20%.
Limitations and Future Work
- Snapshot Staleness: The paper acknowledges that the data snapshot used for optimization is "somewhat obsolete by the time the solution is computed." However, they mitigate this by solving quickly and using minor modifications.
- Heuristic Nature: While the system provides near-optimal solutions, it is not guaranteed to find the absolute global optimum. The local-search heuristics are purely heuristic.
- Future Work: The authors suggest that this type of continual optimization will become more common in other service operations (e.g., mobile installation, repair services, package delivery) that share similar characteristics of complex optimization problems and constantly changing demands.
Summary updated