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.

Optimization Phases and Hierarchy

When running the Transport Navigator solve, the solver will optimize several objectives. These objectives are ranked in order of importance.

The most important objective in the “main” solve is the actual cost objective. This objective function consists of several components:

Mileage cost – the number of miles driven by each vehicle, multiplied by the cost per mile for that vehicle.

Hourly cost – applied to both driving time and waiting time.

Fixed cost – includes a fixed daily operating cost per vehicle and a fixed cost for owning a vehicle.

Lateness cost – the penalty for arriving late at a customer. This cost encourages the solver to minimize total lateness. By penalizing late deliveries rather than strictly prohibiting them, we allow some flexibility. For example, if arriving late enables us to remove a vehicle from the solution, the overall cost may be reduced.

Dispatch and delivery costs – the cost of dispatching from the warehouse and delivering to the customer.

Layover cost – a penalty applied for each layover during a route.

Besides the aforementioned objective functions, there are three other objectives that are considered:

The number of miles driven.

An auxiliary objective function designed to reduce the number of vehicles.

The total number of vehicles used.

The auxiliary objective encourages uneven distribution of customer assignments across vehicles. While it may seem counterintuitive, since a balanced load often appears ideal, this function helps guide the solver toward using fewer vehicles.

For example, suppose the model has ten customers and two vehicles. Two possible solutions are:

Both vehicles visit five customers.
One vehicle visits nine customers; the other visits one.

Assuming all else is equal, the auxiliary objective will prefer the second solution. While it may not seem optimal at first glance, this uneven split moves the model closer to an ideal scenario where one vehicle serves all ten customers and the other is unused, thus reducing total vehicle count.

It is important to note that the model is solved in several phases, and not all phases include the same objectives. For example, during the pre-solve phase, the cost objective is ignored. In that phase, the focus is on finding a feasible solution, primarily by minimizing the number of late orders and total lateness.