A new way to plan routes: mathematical models and algorithms overcome unpredictability

How can we ensure that vehicles arrive at their destinations in a synchronised way, even when travel times are not exact? To answer this question, a team of researchers from INESC TEC and the JKU Business School (Austria) has developed a solution to improve the efficiency and reliability of transportation and logistics services, even when faced with unexpected delays.

VRPSync (The Vehicle Routing Problem with Synchronization) is considered a classic problem in logistics: on one hand, the goal is to minimise total route costs; on the other, some tasks need to be carried out simultaneously, even when they are assigned to different vehicles. These synchronisation requirements are particularly relevant when tasks must be performed by vehicles within specific time windows to minimise waiting times or the idleness of vehicles or other equipment involved in logistics operations.

But what if an unforeseen event disrupts this coordination? What happens, for example, if two lorries are required to arrive at the same location at the same time and one of them is delayed by an accident or traffic congestion? How can we manage said occurrences?

Until now, many studies have addressed the problem assuming that travel times are fixed and predictable. The research, recently published in Networks, proposes an innovative and robust optimisation approach to VRPSync: travel times are uncertain, not fixed, yet it is still possible to find a robust solution that remains feasible up to a degree of uncertainty defined by the planner. Within this set level of uncertainty, the planned routes remain implementable in practice, even when synchronisation constraints and travel time variations – caused, for instance, by traffic – are present.

Building on previous studies, the researchers developed mathematical models and branch-and-cut algorithms – an approach that, starting from a mathematical model, is used to solve combinatorial optimisation problems. “We present a new way of planning vehicle routes that contributes to improving transportation logistics by ensuring that plans remain valid even when unforeseen delays occur, particularly when several vehicles need to be time-coordinated,” explained Ricardo Soares, INESC TEC researcher.

Specifically, the team defined a set of possible travel times and established constraints ensuring that, for any scenario within that set, synchronisation and deadlines are respected. The result is an algorithm capable of solving problems and achieving a balance between quality, total cost and reliability.

The study shows that it is possible to combine safety and efficiency, even knowing that solutions providing greater robustness under uncertainty may lead to increased costs. “This increase stabilises, even if the degree of uncertainty grows – it does not become unmanageable.” According to the researcher, “the goal is to find solutions that work and remain efficient even when travel times vary within a given range.”

The researcher mentioned in this news piece is associated with INESC TEC.