Online Vehicle Routing: The Edge of Optimization in Large-Scale Applications

Dimitris Bertsimas, Patrick Jaillet, and Sébastien Martin, Online Vehicle Routing: The Edge of Optimization in Large-Scale Applications, Operations Research, Vol. 67, No. 1, 2019, Pages:143–162.

With the emergence of ride-sharing companies that offer transportation on demand at a large scale and the increasing availability of corresponding demand data sets, new challenges arise to develop routing optimization algorithms that can solve massive problems in real time. In this paper, we develop an optimization framework, coupled with a novel and generalizable backbone algorithm, that allows us to dispatch in real time thousands of taxis serving more than 25,000 customers per hour. We provide evidence from historical simulations using New York City routing network and yellow cab data to show that our algorithms improve upon the performance of existing heuristics in such real-world settings.

Model and Data

We consider the online taxi-routing problem a special case of the online dial-a-ride problem with time windows. In this application, vehicles are only allowed to serve one customer at a time. 

We represent each customer as a node in a directed graph G. An arc (c′, c) in G represents the possibility for a vehicle to pick up customer c immediately after servicing customer c′.

A customer c is associated with a pickup time window.

Decisions

A solution to the taxi-routing problem is a subset of arcs of G that designate the sequences of customers assigned to each taxi. Each customer must only be picked up by at most one taxi while respecting its pickup time window constraint.

The goal is to maximize the total profit of the solution. 

Off-line Routing: The Edge of Optimality

When all the demand information is known beforehand, the problem is called off-line (or static). 

We present a linear mixed-integer optimization (MIO) formulation of the off-line problem along with a set of heuristics, e.g., Max-Flow, Greedy Insertion, Local Improvement with 2-opt. 

MIO:

mixed-integer optimization with the pickup time window constraints

Max-Flow: 

Theorem 1: If each customer has a fixed pickup time, then the mixed-integer formulation (5)–(14) is (a max-flow problem) and integral.

Greedy Insertion: 

We iterate through the customers by order of t^min_c (earliest customers first), and we assign them to the closest available taxi or reject them if no taxi is available.

 Local Improvement with 2-opt

We perform a swap between two nearby taxis, exchanging their assigned customers.

Scaling Optimization to Real-World Applications

One way to increase the tractability of MIOoptimal is to decrease the number of binary decision variables in the mixed-integer optimization formulation. 

For a given sparsity parameter K, we prune G to create a sparser graph by only keeping the K-lowest cost incoming and outgoing arcs for every node in G. 

To make MIOoptimal tractable for large instances of the taxi-routing problem, we need to remove a lot of arcs from G. 

In Theorem 1, we have shown that for fixed pickup times the maxflow algorithm solves the problem optimally.... If we resolve several times the fixed pickup time problem with the tractable maxflow and random pickup time within the time windows and collect all the optimal arcs across the different solutions, we obtain a set of arcs that are likely to be optimal. 

Taxi Routing in New York City: This large network, with 4,324 intersections and 9,518 directed arcs, was chosen because taxis and on-demand ride-sharing vehicles are an extremely popular means of transportation in this city with more than 500,000 trips every day.

Algorithm 3. Local Backbone

Local backbone is an algorithm that combines the advantages of a local-improvement and global optimization.  It aims to avoid local minima by using an MIO solver and usually provides near-optimal solutions. Its main strength is when the problem is hard to solve or when we have tight constraints on computational time: the difficulty of the problem can be limited by using a very sparse graph B& and compensating for the corresponding decrease in the solution quality by doing more iterations of local backbone to keep improving the solution as with any local-improvement method.

The computational time is limited to five minutes for each algorithm.

Online Taxi Routing in New York City

In Section 3.1, we have introduced a reoptimization strategy to solve online taxi routing. This iterative algorithm requires being able to solve large-scale off-line taxi-routing problems within a limit of 15 seconds, which is the limit we have chosen for our applications.