The Ride-Sharing Gap
In this day and age, the concepts of ride-hailing and shared mobility is something we largely take for granted.
Whether you're embarking on a night on the town with friends or need to catch a ride to the airport, Uber—or maybe Lyft, depending on where you live—is usually the most convenient and ubiquitous option to get you there.
However, the transportation options in Japan couldn't be more different. Uber, and ride-sharing services in general are non-existent. Taxis dominate the roadways, and the subway and railway systems are the most accessible, cost-effective and reliable way to move from A to B.
In urban areas, bodies crowd the train station for their daily commute, packing into train cars so tightly that a passenger often cannot even reach above his or her head to grab the stabilizing rings. In some station during rush hour, "train pushers" have been implemented to ensure that trains were loaded to capacity. Bodies are squished so tightly against one another that most people can’t physically move. It is a shameful price to pay for efficiency.
So efficient and reliable is the train travel in Japan that the operating companies have developed a reputation for issues apologies for departing or arriving even seconds behind schedule. It's this level of accuracy and punctuality that allows residents to plan their schedules weeks in advance, and plan their days down to the minute.
Traveling through rural areas in Japan is a stark contrast. Seeing commuters on bikes and on foot is common in smaller towns such as Wakabaidai, a suburb outside of Tokyo. Although bus stops abound in the small community, all who have ridden a bus before know that the time tables are rigid and that your destinations are limited. Want to get somewhere off the beaten path? Better be prepared to change buses or walk a distance. Some people drive their own vehicles, however most older folks find it increasingly more difficult to drive themselves, and with an increasing population age, fewer and fewer residents are able to drive on their own.
Even more challenging, some of the older residents have to make their way into town for periodic appointments, groceries or work. The train, though a reliable and efficient option, can be an endeavor for even the youngest and fittest of souls, let alone those of advanced age. And heaven forbid you have one or two children in a stroller!
MONET
In response to the ride-sharing vacuum identified, Toyota Motor Co. partnered with Softbank Corp. to build MONET, an on-demand ride sharing application targeted specifically towards an aging population in rural Japan. In a press release dated March 4th, 2019, an agreement between the city of Yokohama and MONET was announced.
The vehicle routing problem
As part of the MONET application, Toyota Connected of North America was contracted to develop a proprietary, real-time optimization engine for ride assignments. Think Uber Pool that offers reservations that can either be scheduled in advance or in real-time. The ride-share assignment problem represents a subset of the classical traveling salesman problem and vehicle routing problem, and is part of a family of combinatorial optimization problems that scales in an explosive fashion, meaning a perfect solution cannot be solved-for in any reasonable amount of time.
To address this challenge, we adopted a metaheuristic approach based on bee colony-inspired optimization algorithms. The outcome was an algorithm that was designed specifically to meet the following objectives:
- Ensure that all constraints (requested pickup time, vehicle capacity, etc.) are met
- Prioritize the discovery of a feasible solution in a very short amount of time (< 5 seconds)
- Produce good quality results. All things considered, the solution must be close to the global optimum (as tested in benchmarks)
- Designed in a parallelizable fashion
- Will accommodate pickup time for users who scheduled their pickup ahead of time, while also satisfying on-demand ride share requests
- Accommodate specified delivery time of customers within some slack parameter while permitting the vehicle the flexibility to deviate course to add on-demand passengers
- Penalize routes which would cause a passenger to remain in the vehicle for a significant amount of time longer than the length of their estimated direct route
With two ride requests, the solution is reasonably straight forward. However, with 5, 10 or 20, and a fleet size of 2, 5, or 10, find the optimal routes and vehicle assignments becomes a non-trivial task, and certainly not one that can be easily solved in real-time.
The Bees algorithm
Meta-heuristics are high level optimization techniques that act as iterative frameworks, identifying a rough, sub-optimal solution quickly and incrementally searching for improvements. They're easily adapted to handle arbitrary constraints, and have shown to perform really well in PDP scenarios, where every problem is slightly different from the next.
The Bees algorithm (Pham, et al., 2005) is one such meta-heuristic algorithm that approaches the VRP from a swarm intelligence perspective. Inspired by the "waggle dance" that bees perform in nature to guide their peers to viable food sources, the bees algorithm exploits searches of random local subspaces to create candidate solutions that have been shown to approximate problems' best known solutions in a short amount of time.
Image courtesy of BIODIDAC
Informally, the algorithm deploys bees (or proposed solutions) from their "site", or "patch," to randomly search a subspace, creating new candidate solutions which are ranked according to some fitness function. Similarly to their entomological namesake, highly fit candidates then recruit more bees to search the solution they've found.
Pham, et al., showed that the bees algorithm could effectively be applied to a continuous space for function optimization by demonstrating so on inverted Shekel's foxholes.
However, the PDP domain is not a combinatorial optimization problem, so the bees algorithm can't be directly applied given their implementation.
The Enhanced Bees algorithm
In his 2016 paper, Aish Fenton proposed the "Enhanced Bees Algorithm," adapting the classical algorithm to a VRP context with several added objectives:
- Ensure all constraints are met
- Have a good runtime performance (his metric was reaching a delta of 5% from the known optimal value of benchmarks within 60 seconds)
- Produce quality results
- Be parallelizable
However, his proposed solution does not impose any hard constraints, unlike most similar algorithms. Rather, he specifies an amended loss function that steeply penalizes infeasible solutions, and proposes annealing steps between each iteration that add further entropy to candidate solution.
Furthermore, sites are killed off over time if they continually produce poor candidate bees, while "successful" sites are kept alive for longer in order to explore permuted variations.
Fitness function
In measuring the effectiveness of a solution, meta-heuristics like the bees algorithm have adopted the term, "fitness function" in lieu of the conventional "loss function." In the enhanced bees algorithm, a proposed solution (or bee), is made up of a number of routes, R.
Our objective is to find the bee that minimizes fitness function (a bit terminologically confusing):
The fitness function is composed of several sub-functions. c(R) computes the direct cost of a route (estimated route duration in seconds, for our case), which coaxes solutions away from inefficient, long routes:
d(R) calculates the capacity overage penalty, where proposed solutions that require vehicles to carry more than their specified maximum capacity, q, are heavily penalized:
Function t(R) calculates the "route overage," or the amount of time or distance over its required maximum a route would require a vehicle to travel, t. This is particularly helpful in commercial settings where drivers are required by law or union to take a rest after a period of time (i.e., Japan):
The coefficients α, β and γ are tunable hyper-parameters that affect the degree to which a solution is penalized for one type of offense vs. another. The beauty of this fitness function is its built-in ability to adapt to whatever organizational priority is driving the problem.
OBHIVE
Unfortunately, a ride-sharing scenario is a bit more complex than being straight forward VRP. And, while the majority of literature and implementations of the bees algorithm and its variants revolve around VRP solutions, we needed a PDP solution that could effectively account for requested pickup or drop-off times, and that could both schedule rides in advance as well as operate quickly enough that users could request rides and receive an assigned driver in near real-time (on-demand rides).
In addition to Fenton's algorithmic requirements, our algorithm requires the following:
- Accommodate users who scheduled their pickup ahead of time, as well as satisfying ride-share requests of passengers already on-board and of those submitting requests in an on-demand fashion
- Prioritize delivery of customers on-board within some slack amount while permitting the vehicle the flexibility to deviate course and add on-demand passengers in real time
- Penalize routes which would cause a customer to remain in the vehicle for a significant amount of time longer than the estimate of their direct route
The algorithm
We propose the OBHIVE (On-demand Bee Hive-Inspired VEhicle routing) algorithm (paper forthcoming) as follows (in simplified Python pseudocode):
S = seed_sites()
while (not early_stopping_criteria) and \
n_iter < max_iter:
for site in S: # parallelizable
site.explore(d) # update site's bees
S = sort_sites_according_to_best_bee(S)
S = remove_worst_n_pct_sites(S)
You'll notice the procedure itself is rather similar to that of the enhanced bees algorithm. Similar to Fenton's enhanced bees, the algorithm maintains a collection of sites, each of which produces and explores candidate bees. Also similar to his algorithm, OBHIVE's implementation allows for an embarrassingly parallelizable site search. In our case, we use Python's joblib to explore sites independent of one another.
There are, however, several notable differences that may not be readily apparent in the pseudocode:
- The destroy/reconstruct heuristic is different in that we cannot simply remove & reinsert points that are near each other, since we have to account for both pickup and drop-off points. Removing a customer on the basis of one and not the other could degrade the solution.
- We also have to take great care in selecting which customer to try to re-arrange in the system, since we can't feasibly rearrange a customer who is already on board a vehicle!
To elaborate on the first point, consider that in VRP, we could simply add or rearrange waypoints independent of one another. But in PDP, each ride-share request is actually a composite of two jobs:
That is, a pickup and a drop-off that must occur in that order, but not necessarily contiguously. Furthermore, in the enhanced bees algorithm, we can pop a waypoint out of one vehicle route, and into another's. However, in OBHIVE each removal/reinsertion must reallocate the entire customer, and not just one of the jobs.
The fitness function
But there's more than just that. The current VRP fitness function leaves us with several major PDP liabilities:
There is no assurance that a passenger’s total trip time will be minimized. Without such a term, the algorithm will find the path that minimizes the existing fitness function and satisfies all constraints such that the passenger will be picked up, but it may not prioritize dropping them off until well beyond the duration of what would be considered a reasonable trip length.
The existing fitness function does not enforce that a customer be picked-up at the time requested. This is a key part of our application, which supports scheduled pickups in addition to on-demand rides.
You'll notice that we've added two new terms, p and s, into our amended fitness function:
p(P) is the "promptness" penalty, where a vehicle is penalized for being late to a pickup, and P is the subset of stops in the route that are pickups:
And s is the customer-level duration penalty ("s" for "estimate"). The ratio of actual customer trip duration to the expected duration of a direct route is used as an exponential weighting factor, which is applied to φ:
Similar to the enhanced bees algorithm, we avoid enforcing hard constraints as much as possible by leveraging the penalty coefficients α, β, γ, τ and φ to discourage infeasible or suboptimal solutions.
Conclusion
We developed an algorithm, OBHIVE, to address the ride-sharing vacuum in Japan and to aid an aging suburban population in navigating the city. While the OBHIVE algorithm works great for our usecase (and we hope it helps you in some fashion as well!), VRP and PDP are active fields of research, and the problems are by no means solved definitively. The highly customizable problem set and the varying set of arbitrary constraints that accompanies each makes this an incredibly difficult-to-solve problem.
If this post piqued your interest, we hope you'll take some time to review the formal paper.
