Route optimization objectives: the benefits of the lexicographic method
- May 7, 2021
- 3 mins
Route optimization consists in finding the best solution to visit a set of locations while complying with a set of constraints. The notion of “best” solution remains to be defined… Indeed, what makes a route better than another one? Depending on the field, one could say “the one with the least number of miles to travel” or “the one with the least delay”, or even “a bit of both”. In practice, the answer is often complex to find since it implies to be very clear about one’s own business objectives beforehand, and to be able to model them in the algorithm’s formula.
Here is a brief overview of this subject, which is more complex than it seems, and which is ultimately decisive in the adoption of an optimization solution software.
Requirements: the importance of optimization objectives in route optimization
A round optimization problem is composed of a set of essential elements which, when tackled by a solving algorithm, provide a solution of optimized routes. These elements are:
- the optimization objectives (e.g. “minimize the number of miles traveled”),
- the data of the problem (for example: location of the points to be visited, predictive traffic data, etc.)
- the constraints of the problem (e.g., the drivers’ work schedules)
Conventional methods: setting a single or aggregated optimization objective
In most methods and tools, the user defines a single objective for the algorithm. This approach is by far the easiest to implement from an algorithmic point of view. With this method, it is essential to choose an objective that best reflects the company’s business priorities. Although this approach is very simple, it quickly reaches its limits when applied to real problems.
Indeed, route optimization problems are always multi-criteria. It is rarely possible to choose a single indicator. To overcome this limitation, optimization tools often use “aggregated” objectives, which combine several indicators into one thanks to a formula. The most used (if not the only one) is the weighted average: each indicator will be given a weight, and the optimized indicator will be the weighted sum of these indicators.
Once again, the problem is how to define the weights so that they truly reflect the business objectives. This is a complex task! To simplify the problem, most of the software on the market simply ignores most of the objectives, and only proposes a few (the classic ones). By trying to simplify their approaches, they end up making them simplistic or difficult to use.
At Kardinal, we believe that our algorithms must solve the problems encountered on the field, otherwise they simply aren’t relevant So not only can we handle all of our clients’ business objectives simultaneously, but the user can easily set the optimization to match their business objectives.
Lexicographic optimization: prioritizing over weighting to better match business objectives
Kardinal optimization is based on a multi-criteria optimization algorithm called “lexicographic”. This means that the objectives are not aggregated into a single indicator, but prioritized, ordered from most important to least important. Thus, a solution will be deemed better than another if it is better on the first priority objective, regardless of the values of the other lower priority objectives. The same principle applies to all objectives.
Let’s take a practical example to show what this approach can do in terms of weighting:
Let’s imagine a last mile delivery problem. Some customers have paid for a (expensive) “Premium” delivery in 24h within a specific time slot, others for a (less expensive) “Silver” delivery in 24h, others again for a “Standard” delivery in 48h which is optional. Part of the fleet is made up of service providers who must try to make a €250 turnover if used, but we prefer to rely on our employees. Of course, we try to limit the number of miles traveled as much as possible, but we first try to use as few vehicles as possible to make priority deliveries (within the limits of the available fleet).
The optimization objectives that can be identified here are the following:
- Maximize “Premium” scheduled deliveries
- Maximize planned “Silver” deliveries
- Maximize planned “Standard” deliveries
- Minimize the number of employee rounds
- Minimize the number of provider routes
- Minimize the “unprofitability” of providers
- Minimize the number of miles traveled
- Minimize delays on “Premium” deliveries
This gives us 8 optimization objectives. Clearly, finding weights that accurately match business priorities (not to mention maximizing some objectives and minimizing others) is quite complex. On the other hand, prioritizing is very simple, and the consequences of a decision are instantly obvious to the decision maker. So, let’s imagine the following prioritization:
- Maximize planned “Premium” deliveries
- Minimize delays on “Premium” deliveries
- Maximize planned “Silver” deliveries
- Minimize the number of provider routes
- Minimize the number of employee routes
- Maximize optional scheduled “Standard” deliveries
- Minimize the “unprofitability” of providers
- Minimize the number of miles traveled
With this setup, service to “Premium” customers comes first. We even prefer to deliver a “Premium” customer on time than to deliver a “Silver” customer at all. The “Standard” deliveries are positioned after the minimization of the number of routes, which means that they are optional deliveries: we will not use extra vehicles to make these deliveries. Finally, objectives 1 to 7 allow the optimization of the distribution of work between all the routes, and it is only once the dispatch is optimal that the 8th objective will seek to optimize the routes themselves.
The advantage of this approach is that it is easy to understand: we know what the algorithm is going to do, and we know what impact the adjustments will have. For example, if you think that delivering a “Premium” customer (on time) rather than delivering a “Silver” customer (at all) is too extreme, you can simply swap objectives 2 and 3. If you consider the delay to be secondary to the economic performance, you can switch to objective 2 after objective 5. And so on.
With this approach, the complex optimization setup phase becomes a mere formality and making it easier for users to manage. Technically, the difficulty of a lexicographic multicriteria optimization problem is much higher than conventional optimization approaches, but we believe that they are one of the keys to the implementation of relevant optimization solutions in the field.
About the Author
Cédric Hervet has a PhD in Applied Mathematics and is co-founder of Kardinal. For over 10 years, he has been studying and designing Artificial Intelligence systems for industrial applications in telecommunications, digital marketing and transportation.
His dual expertise in statistics/machine learning and algorithms/operational research allows him to bring together these two major sets of techniques to design the intelligent systems of tomorrow.
