Transport Navigator Technical Details

Transport Navigator is designed as a tactical transport planning solution that supports fixed route design and fleet sizing within SC Navigator. It extends SC Navigator’s network modeling capabilities by adding transport optimization features.

Transport Navigator uses the Hexaly solver to generate efficient and feasible transport plans. The model designs routes while respecting key operational constraints such as vehicle capacities, delivery time windows, maximum duty and drive times, and service times at customer locations.

Our Approach to Solving the Vehicle Routing Problem

The Transport Navigator module uses the Hexaly solver for solving the routing problems. It is important to note that Hexaly behaves very differently compared to classical LP and MIP solvers (like CPLEX and Gurobi). Hexaly is most suitable for solving combinatorial problems (problems like routing, scheduling, and assignment). Transport Navigator solves one such combinatorial problem, a vehicle routing problem. Routing problems are known to be very difficult to solve to optimality, this means that many solvers make use of heuristics, which can reliably give very good (near-optimal) solutions. The time required to solve combinatorial problems to optimality usually increases exponentially when the size of the problem increases. In the case of vehicle routing, increasing components such as the number of stops that need to be made can increase the size of the problem.

A well known combinatorial problem is the Traveling Salesman Problem (TSP), which is a special case of the routing problem that Transport Navigator solves.

In the TSP, we have a set of customers that need to be visited by a single truck. The truck should visit each customer exactly once. The goal is to find a solution where the distance traveled by the truck is minimal. Although it may seem straightforward, this is a very difficult problem to solve optimally. For example, if we have a TSP with 100 customers, the number of possible combinations is more than 10^155. As a comparison, there are roughly 10^80 atoms in the universe. Consequently, there is absolutely no chance that we would find the optimal solution by naively checking each potential solution. It is a widely accepted anecdote in the optimization community that even if we had a computer that was trying to solve this problem since the beginning of time, it still would not be finished. And even if we were somehow given an optimal solution, it would still be difficult for us to verify that the solution is indeed optimal.

One could attempt to solve such a problem with a classical optimization solver such as Gurobi or CPLEX, but this problem is notoriously difficult for these solvers as well.

The Transport Navigator model (and any practical-scale vehicle routing problem) that we solve is much harder than a traditional TSP. The real-world problem that we are interested in has:

Around 1000 customers, each with one or more time-windows.

Multiple vehicle types, with different volume capacities, weight capacities and other restrictions.

Driver regulations such as a maximum driving or duty time and layovers.

An intricate objective function.

And many more business rules that must be adhered to…

Therefore, we need a clever strategy to find solutions. This is were Hexaly comes in. Hexaly is a heuristic solver that is very good at exploring the solution space of difficult problems like these, making use of the combinatorial properties of the problem.

The behavior of Hexaly differs from classical solvers, as it does not stop when it finds a solution. Hexaly will continually try to find better solutions until it reaches the time-limit that you impose. Within the allowed time, Hexaly will strive to find better solutions. It is up to the user to determine a time limit for the solver. Usually it makes sense to start solving some problems with different time limits. This will give you an idea about how long it will take Hexaly to find good solutions to your problem.

Usually, Hexaly will find a feasible solution to the problem relatively quickly. Within the first few seconds or minutes, a lot of progress will be made and the cost of the best solution will quickly decrease. At some point, progress will slow down and the objective function will not improve as rapidly as before, or even stay constant for some time. This does not necessarily mean that this is the optimal solution, as the solver may be (temporarily) stuck in a local optimum. Eventually, the solver can also get out of a local optimum and continue to improve the solution after being stuck for some time.

Guiding the Solver

There are some options available for the user to guide the solver in finding a good solution. Those are:

Setting First or Last Stops - When a customer is marked as ‘first stop’, this means that this customer should always be the first stop after leaving the depot.

Fixed Routes - When you know beforehand that certain customers should always be serviced by the same vehicle, in the same order, you can input this as a fixed route. The solver will then not touch these routes. These routes can also form a subset of a larger route that is determined by the solver, should that be desired.

Grouping Codes - Using a grouping code, one can enforce certain customers to be visited by a limited set of vehicles. For example, if some (but not all) trucks have a cooling compartment then a customer that requires cold goods needs to be serviced by such a truck only.

It is important to note that in consecutive solves the solver will automatically try to use the previous solution as a starting point for the solve. This means it does not begin from scratch, but instead builds on the last feasible solution.