Introduction
Routing a fleet of vehicles to pick up and drop off customers is a classic "hard" problem in computer science. Known as the Multiple Vehicle Pickup and Delivery Problem (MVPDP), it is a complex extension of the Traveling Salesman Problem. Because it is NP-Hard, researchers typically choose between fast but non-optimal heuristics or exact methods that struggle to scale as the number of customers grows.
Researchers at the University of Michigan have introduced a novel approach by reimagining the problem through matrix algebra. They developed an exact solution method using Integer Quadratic Programming (IQP) that scales significantly better than traditional techniques.
The Challenge of MVPDP
The core challenge of the MVPDP is the "combinatorial explosion." As customers are added, the number of possible routes grows factorially. Existing exact methods typically use Mixed Integer Linear Programming (MILP). However, MILP's primary weakness in routing is sub-tour elimination. To prevent "loops" that don't connect to a depot, solvers require a massive, often exponential, number of extra constraints. This makes MILP formulations computationally heavy, often failing beyond 15–18 customers.
A Matrix-Based Approach
The researchers depart from standard edge-based linear approaches, utilizing a Matrix Representation:
- Permutation Matrices: A vehicle's tour is represented as a permutation of a "reference tour" (a simple cycle through all locations). By using a permutation matrix ($X$), the formulation mathematically guarantees a single cycle, inherently handling sub-tour elimination without thousands of extra constraints.
- Integer Quadratic Programming (IQP): The cost function is formulated as a quadratic expression ($x^T Q x$).
- Convexification: Generally, IQP problems are non-convex and difficult to solve. The authors provide a mathematical transformation to ensure the objective function is convex when integer constraints are relaxed. This allows modern solvers (like CPLEX or Gurobi) to find global optima efficiently.
Key Insights: Efficiency through Convexity
By using the matrix approach, the number of "Generalized Order" constraints—which handle sub-tour elimination and precedence—drops from $O(n^2)$ in MILP to just $O(n)$. This drastically reduces memory and computational overhead.
The "aha moment" is the realization that a constant term can be added to a non-convex cost function to make it convex without altering the optimal integer solution. This "convexification" is the primary driver behind the IQP's superior performance. Furthermore, this unified framework handles multiple depots and vehicles naturally within the same structure.
Experimental Results
The approach was evaluated using both simulated data (8 to 50 customers) and real-world Yellow cab trip records from Manhattan, NYC.
- Scaling: In CPLEX benchmarks, traditional MILP failed to find feasible solutions for more than 12 customers within two hours. The new IQP method solved instances with 50 customers to within a 3.5% optimality gap in the same timeframe.
- Real-World Performance: On the NYC taxi dataset, the IQP method optimized tours for 18 customers in approximately 5 minutes. The state-of-the-art MILP was unable to find any feasible solution within 10 minutes.
Limitations and Future Work
Currently, the model is static, assuming all requests are known at the start. Real-world ride-sharing is dynamic, with requests appearing in real-time. While the IQP method could serve as a fast "inner loop" for a dynamic system, this integration remains for future work. Additionally, the team aims to incorporate stricter time windows and time-varying traffic speeds into the matrix framework.
Summary updated