The Cost of Speed in Route Optimization

When evaluating route optimization APIs, two critical factors to consider are optimality and computational speed. Many API providers boast about having the fastest and most scalable route optimization in the market, and some even claim to have set new world records on academic benchmark data sets. However, these claims may only present a partial picture. The real questions that remain unanswered are: What is the trade-off between optimality and speed? And how much does speed impact optimality, and vice versa?

The data

In this section, we will be using some academic instances from both CVRP and VRPTW lib to conduct the experiment. Note that, instances of VRPTW are also capacitated. The objectives of these benchmark problems are firstly, minimize the number of vehicles deployed, secondly minimize the total Euclidian distance. All the best-known solutions are also provided.

Exploring the search options in LogisticsOS route optimization API

Let’s take a look at VRPTW instance c1_10_1 which contains 1000 locations (best known solution in distance is 42478.95, total number of vehicles used is 100). First, we set exhaustive_search to false in the solver_parameters object from LogisticsOS route optimization JSON request. The result came back as below:

  "solver_time": "17600ms",
  "plan_summary": {
    "distance": 42498.71058530219,
    "total_time": 132482.3101637099,
    "travel_time": 42482.3101637099,
    "wait_time": 0.0,
    "late_time": 0.0,
    "service_time": 90000.0,
    "num_routes": 100,
    "unassigned": 0,
    "assigned": 1000
  },

It took the solver 17.6 seconds to return a solution. The gap to optimality is 0.0466%. Not bad, can we do better? Now we set exhaustive_search to true and solve again.

  "solver_time": "34473ms",
  "plan_summary": {
    "distance": 42496.41066570116,
    "total_time": 132496.4106657011,
    "travel_time": 42496.4106657011,
    "wait_time": 0.0,
    "late_time": 0.0,
    "service_time": 90000.0,
    "num_routes": 100,
    "unassigned": 0,
    "assigned": 1000
  }

After setting exhaustive_search to true, the gap was reduced to 0.0411%. However, it came at the cost of doubling the solver time to approximately 34.4 seconds. Whether this increase in time is worth the marginal improvement may depend on the specific needs of the project. However, it is worth noting that the optimal solution can be found with further exploration using hill climbs and Markov chain algorithms, but this comes at a much greater cost of 31 minutes. In most cases, this level of additional computation may not be justified.

To gain a deeper understanding of the trade-off between speed and optimality, let us consider a larger instance of the problem. For this purpose, we will use flanders1 from the cvrplib, which consists of 20,000 locations with a best-known solution of 7240118 and 684 vehicles. We started by setting exhaustive_search to false and the solver took approximately 621 seconds to return a solution, which was only 2% from the best-known solution. The output is presented below:

  "solver_time": "620872ms",
  "plan_summary": {
    "distance": 7390018.0,
    "total_time": 7390018.0,
    "travel_time": 7390018.0,
    "wait_time": 0.0,
    "late_time": 0.0,
    "service_time": 0.0,
    "num_routes": 684,
    "unassigned": 0,
    "assigned": 20000
  },

When we turn on the exhaustive search, we got a better solution, see below:

  "solver_time": "1244727ms",
  "plan_summary": {
    "distance": 7381912.0,
    "total_time": 7381912.0,
    "travel_time": 7381912.0,
    "wait_time": 0.0,
    "late_time": 0.0,
    "service_time": 0.0,
    "num_routes": 684,
    "unassigned": 0,
    "assigned": 20000
  },

After the initial run with exhaustive_search set to false, we were able to achieve an improvement of 0.05% with the same solver by setting exhaustive_search to true. However, the solver time doubled to 1245 seconds. Whether this increase in time is justified may depend on the specific needs of the project.

Unfortunately, we were unable to find the best-known solution even with exhaustive search, indicating that there may be limitations to the solver's ability to optimize beyond a certain point.

While it may seem that exhaustive search is unnecessary in academic benchmarking, real-world route optimization cases often involve more complex constraints and limited numbers of vehicles. Therefore, we have found that in some cases, turning on the exhaustive search can result in more orders being assigned or even reduce the number of routes required. So, it's important to consider the specifics of each optimization problem and the potential benefits of using exhaustive search before dismissing it as unnecessary.

The VRP problem is notoriously difficult to solve optimally, and the difficulty increases with the size of the problem. Route optimization solvers typically work by iterating quickly in the initial stages and landing on a local optimal solution that is difficult to improve upon further. As a result, achieving the last 1-2% improvement in optimality can take double or even triple the time required for the initial optimization. This tradeoff between optimality and computational speed is a fundamental challenge in route optimization, and it highlights the importance of selecting an appropriate solver for the specific needs of the project.

Conclusion

It's great to know that LogisticsOS route optimization API provides a default search parameter that can quickly land on a near-optimal solution. This can save a lot of time and manual work for the end-user. It's also valuable that LogisticsOS offers the option for exhaustive_search to push for optimality, giving users the flexibility to choose between speed and optimality based on their specific needs. This can be especially helpful when dealing with larger VRP instances where the optimality is harder to achieve, and the time to solve becomes a more critical factor.

About LogisticsOS

LogisticsOS is the most powerful route optimization system on the market. Our flexible, hosted route optimization and planning/replanning APIs require no knowledge of optimization techniques. High-quality results are returned within seconds— even at scale. From time reduction and vehicle capacity to depot automation and cost customization, our feature-rich software can create the efficiency and cost-savings that you need. Contact us today for a free product demo.