Learning to Branch-and-Bound to Route an Autonomous Mobility on Demand System

Claire Xu, Robin Brown, Somrita Banerjee, Marco PavoneJournal of Student Research 2022 · DOI

TL;DR

This paper presents a method to accelerate Autonomous Mobility on Demand (AMoD) routing by using a neural network to optimize the Branch-and-Bound (BB) algorithm. By predicting the most efficient initial branching order for customer requests, the researchers achieved an average 40% reduction in computation time without ever compromising solution quality.

What Problem Does This Paper Address?

Routing a fleet of autonomous vehicles across a city is a complex optimization puzzle. To minimize total distance traveled while respecting road capacity constraints, the system must solve a Mixed Integer Programming (MIP) problem. The "integer" part is crucial: you cannot send half a vehicle down one street and half down another.

The standard tool for solving these problems is the Branch-and-Bound (BB) algorithm. BB works by systematically exploring a tree of possible routing combinations, "pruning" branches that are mathematically proven to be sub-optimal. However, the efficiency of BB is highly sensitive to the order in which it explores these branches. A poor ordering leads to an exhaustive, slow search, while a good ordering finds the optimum quickly. Currently, there is no universal method for determining this optimal ordering in an AMoD context.

Methods

The authors propose a "learning to branch-and-bound" approach. They model the city as a network flow graph where nodes are origins/destinations and edges are roads with specific capacities.

  1. The BB Framework: They adapted the BB algorithm to the routing context, using "relaxation" (solving the problem as if vehicles could be split into fractions) to establish upper and lower bounds for pruning.
  2. Neural Network (NN) Integration: They trained a multi-layer perceptron (MLP) with two hidden layers to act as a "search" heuristic. Instead of picking a branch at random, the BB algorithm uses the NN's prediction to decide which customer request to process first.
  3. Hyperparameter Sweep: The team tested 28 different NN configurations, varying the hidden layer sizes (from 512 to 1024 nodes) and learning rates (0.01 to 0.5) to find the most effective model.

Datasets

The researchers generated a custom synthetic dataset for this study:

  • Road Network: A fixed 18-node graph with arbitrarily assigned edge capacities.
  • Request Sets: 3,000 sets of randomly generated customer requests (origin-destination pairs).
  • Ground Truth: To create labels for training, they ran the BB algorithm on every possible permutation of these request sets to identify which "first request" resulted in the absolute minimum number of computations.
  • Data Split: 75% of the 3,000 sets were used for training, and 25% were reserved for testing.

Key Insights and Ideas

  • The "First Request" Heuristic: The most surprising finding was that the identity of the very first request branched upon is the primary determinant of computational complexity. Shuffling the order of the 2nd through $n$th requests had no impact on the total number of computations. This allowed the authors to simplify the NN's task from predicting a full sequence to simply identifying the best starting request.
  • Search vs. Diving: While many ML-for-MIP papers focus on "diving" (finding any feasible solution quickly), this paper focuses on "searching" (minimizing the total work needed to prove a solution is optimal).
  • Zero-Risk Acceleration: In their trials, the NN-predicted ordering never performed worse than the average runtime. This suggests that "learning to branch" is a low-risk, high-reward strategy for fleet management.

Key Results

  • Significant Speedup: The optimal NN configuration (1024x512 nodes with a 0.1 learning rate) resulted in an average 40% decrease in runtime compared to average runtimes.
  • Peak Efficiency: In all 10 test trials highlighted, the NN successfully predicted the request that led to the absolute minimum number of computations possible for that set.
  • Generalization: Other NN parameter combinations still yielded a respectable ~25% decrease in runtime, showing the approach is robust across different model architectures.
  • Scalability Potential: While the test cases were small (up to 30 requests), the authors argue that a 40% reduction is transformative when scaled to city-wide systems where computation might otherwise take hours.

Limitations and Future Work

  • Static vs. Dynamic: The current model is "static," assuming all vehicles move instantaneously and all requests are known at once. Real-world AMoD requires a "dynamic" model that accounts for travel time and requests arriving over a continuous timeline.
  • Fixed Geography: The NN was trained on a specific 18-node map. Future work is needed to determine if a model trained on one city's topology can generalize to another, or if it must be retrained for every new road network.
  • Rebalancing: The paper focuses on routing active requests but does not yet incorporate "rebalancing"—the process of moving empty vehicles to high-demand areas to prepare for future requests.
  • Scale: The study was limited to a maximum of 30 requests; testing on "at-scale" datasets with thousands of requests is a necessary next step.

Summary updated

Abstract

Autonomous Mobility on Demand (AMoD) is a system consisting of a fleet of centrally-controlled, autonomous vehicles that take customers from their requested origins to their requested destinations. In order to minimize the distance traveled by the fleet, a routing scheme must be developed to service all customer requests. This paper investigates the usage of the branch-and-bound algorithm (BB) to find such a scheme, as well as the usage of a neural network (NN) to speed up BB. Given a fixed road network, sets of randomly generated requests were passed into BB to obtain the ordering of each set that minimized the number of computations, and a NN was trained on this data. New randomly generated request sets were then passed into the trained NN, and runtimes given the NN-predicted orderings were compared to average runtimes over all permutations. For a NN with 1024 nodes in the first and 512 in the second hidden layer and a learning rate of 0.1, using the NN resulted in an average 40% decrease from average runtimes; furthermore, NN-orderings never resulted in increased runtime. Other combinations of NN parameters resulted in around 25% decrease in runtime. Also, BB performed the same number of computations for all permutations with the same first request, simplifying the problem to only finding the next request. These results show that training the NN results in a more efficient, faster routing algorithm that is therefore easier to scale up, enabling at-scale adoption of AMoD.
BibTeX
@article{xu2022learning,
  author = {Claire Xu and Robin Brown and Somrita Banerjee and Marco Pavone},
  title = {{Learning to Branch-and-Bound to Route an Autonomous Mobility on Demand System}},
  journal = {Journal of Student Research},
  year = {2022},
  doi = {10.47611/jsrhs.v11i4.3606},
}
Figure