Introduction

One key feature of NearMe’s shared ride service is that we optimize shared rides every time a new reservation is placed. Compared with a naive approach where we close reservations at a fixed time and decide all ride groupings at once, this has clear advantages: we can grasp sharing conditions earlier, make vehicle arrangements more easily, and keep optimizing until shortly before departure (Reference 1, Reference 2).

On the other hand, from an optimization perspective, trying to optimize for every single incoming order means limited computational resources, which can leave us with suboptimal solutions. In the current implementation, to reduce computational cost, we recompute using orders that are temporally and spatially close to the newly arrived order. In that setup, even if we can optimize locally at each moment, those partial solutions gradually become “stale” as orders continue to arrive.

When the total number of orders was small, this still produced satisfactory solutions. As order volume grew, however, we started seeing more and more patterns where different combinations could clearly do better.

To address these aging solutions, we began reconstructing solutions using Large Neighborhood Search (LNS) (reference: Pisinger 2010). The name sounds complicated, but the method itself is fairly simple. Internally, based on how it behaves, we casually call it “garapon” (like a lottery reshuffle).

By running this reconstruction process periodically, we can obtain better solutions over time. In this article, I explain LNS, how we applied it to our shared ride service, and the overall system design.

About Large Neighborhood Search

Note: this section is explained mostly with support from ChatGPT.

Large Neighborhood Search is one of the heuristic methods for solving optimization problems. It is especially useful for combinatorial optimization problems (for example, vehicle routing and scheduling) where efficient solution improvement is needed.

The basic idea of LNS is as follows:

Basic Flow

• Build an initial solution: First, generate one solution to the problem. In many cases, a simple heuristic (for example, a greedy algorithm) is used.
• Destroy a partial solution: “Break” part of the solution by removing some components (routes, schedule fragments, etc.).
• Repair: Rebuild the removed part to generate a new solution while satisfying the original constraints.
• Evaluate and update: Compare the new solution with the current one and decide whether to adopt it, typically using metaheuristic rules (for example, simulated annealing or tabu search).
• Repeat: Improve the solution gradually by repeating these steps.

Characteristics

LNS extends local search and gets its name from re-evaluating “large” portions of the search space. It can escape local optima and increases the chance of finding better global solutions. Because the destroy/repair steps are highly flexible, it can be applied to many different problems.

• Pros

Can search for high-quality solutions while controlling computational cost. Can achieve better performance when combined with metaheuristics (for example, simulated annealing).

• Cons

Designing destroy/repair operators is problem-dependent, and poor design can limit effectiveness. No guarantee of optimality (often only approximate solutions are obtained).

LNS is particularly effective for large-scale problems and problems with complex constraints, where its flexibility and strong search performance are highly valued.

Note: the 2-opt neighborhood operation, which is common in route optimization, shares the same idea of breaking and rebuilding part of a solution. 2-opt is a simple, fixed destroy/repair method in a narrow search space, especially suited to tour-order optimization. In contrast, LNS uses flexible, large-scale destroy/repair strategies to improve solutions over a broader search space. It adapts to a wide range of problems and has stronger ability to escape local optima. You can also view LNS as a more general framework that can include methods like 2-opt.

Applying LNS to Our Shared Ride Service

Applying LNS to our shared ride service was relatively straightforward. That is because we had already implemented partial recomputation among temporally and spatially close orders when an order is added or removed (for example, canceled). Given that, the basic approach is simple: remove some orders, then insert them again. Then add logic to overwrite the current solution when a reconstructed one scores better according to the objective function.

Note: if constraints prevent us from finding a feasible solution with the current vehicle set, we increase the number of vehicles so we can always obtain a feasible partial solution.

Below is an example of a partial solution reconstructed by this approach.

In this figure, the three black routes on the left are the original solution, and the two red routes on the right are the reconstructed solution. Each route reaches the destination airport via several waypoints. Both sides use the same waypoints, but you can see that reconstruction reduces the number of routes. You can also see that this kind of reconstruction does not happen by only reassigning waypoints between two nearby routes in the original solution; it appears when all waypoints are rearranged together.

In practice, which orders can be rearranged also changes over time. For example, once an operating company has accepted an order, that order may only be allowed to be rearranged with other orders handled by the same company. Our implementation also accounts for these dynamic operational constraints.

We apply LNS by service on a daily basis, but there are cases where it should not run: too few orders, too little time elapsed since the previous run, or just before dispatch when rearrangement is not allowed. Our implementation includes these applicability conditions as well.

System Overview

The overall system consists of a real-time process that optimizes shared rides whenever an order arrives, and a batch process that periodically runs LNS.

The real-time process itself has two services: a Routing service dedicated to optimization, and a Ride service that manages state and controls the overall workflow.

The batch process similarly consists of an LNS job and the Routing service. Because reconstruction is attempted repeatedly, the Routing service for batch processing runs separately from the real-time one. When a solution update is needed, it requests the Ride service to rearrange ride groupings.

For this rearrangement in the Ride service, we assume the calling job might return invalid values due to bugs, and we perform multiple layers of validation. For example: whether data consistency is preserved, whether constraints are satisfied, and whether basic metrics actually improve. This makes the system safe to operate even as we continue improving the LNS job in the future.

Conclusion

LNS is simple yet powerful, and highly versatile for a wide range of complex problems. Because it remains effective even in environments that change continuously and make solutions stale, it fits very well with our shared ride service. In fact, this method has steadily improved our solutions in production. Going forward, we expect further improvements by incorporating machine learning elements as well.

Finally, NearMe is hiring engineers. This domain still has a lot of untapped potential, and we would love to hear from you if you are interested.

• Careers

Author: Kenji Hosoda