A Matrix Representation of the Multiple Vehicle Routing Problem for Pickup and Delivery

Jinsun Liu, Hyongju Park, Matthew Johnson‐Roberson, Ram VasudevanarXiv 2018 · DOI · arXiv

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:

  1. 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.
  2. Integer Quadratic Programming (IQP): The cost function is formulated as a quadratic expression ($x^T Q x$).
  3. 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.
Reference tour (a) and its corresponding adjacency matrix (b).

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.

A specific optimized tour (a) and its resulting permutation matrix (b).

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

Abstract

This paper develops a computationally efficient algorithm for the Multiple Vehicle Pickup and Delivery Problem (MVPDP) with the objective of minimizing the tour cost incurred while completing the task of pickup and delivery of customers. To this end, this paper constructs a novel 0-1 Integer Quadratic Programming (IQP) problem to exactly solve the MVPDP. Compared to the state-of-the-art Mixed Integer Linear Programming (MILP) formulation of the problem, the one presented here requires fewer constraints and decision variables. To ensure that this IQP formulation of the MVPDP can be solved in a computationally efficient manner, this paper devises a set of sufficient conditions to ensure convexity of this formulation when the integer variables are relaxed. In addition, this paper describes a transformation to map any non-convex IQP formulation of the MVPDP into an equivalent convex one. The superior computational efficacy of this convex IQP method when compared to the state-of-the-art MILP formulation is demonstrated through extensive simulated and real-world experiments.
BibTeX
@misc{liu2018matrix,
  author = {Jinsun Liu and Hyongju Park and Matthew Johnson‐Roberson and Ram Vasudevan},
  title = {{A Matrix Representation of the Multiple Vehicle Routing Problem for Pickup and Delivery}},
  year = {2018},
  eprint = {1805.04965},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1805.04965},
}
Figure