Mutualisation de tournées entre marchands à Rungis
Date:
Talk at SEMES Lyon 2026, Polytech Lyon, France
Abstract. In this topic, we will focus on vehicle routing problems. Let’s begin by describing the problem Califrais faces daily: a non-shared vehicle routing problem. The rungismarket.com platform allows its customers to place orders the day before to receive their products the following day. Therefore, it is only at midnight on the day of delivery that all the delivery points are known. A decision must then be made quickly (in practice, in less than ten minutes) on how to carry out the deliveries. Califrais has a fixed fleet that can be expanded as needed. Each vehicle can be either a heavy goods vehicle or a light commercial vehicle, each with a specific capacity. Solving the non-shared vehicle routing problem therefore involves deciding how many vehicles are needed to complete the route, which customers are assigned to each vehicle, and then in what order these customers should be visited. The choices are guided by cost minimization, which includes fixed vehicle rental costs and variable costs related to fuel consumption. Finally, deliveries must adhere to time slots defined by customers, and road traffic, which varies depending on the time of day in urban areas, must be taken into account.
In the shared scenario, several merchants decide to share certain vehicles, which can deliver to each other’s customers. The objective is to maximize the utilization of these trucks and reduce the number of trucks on the road. Indeed, sharing allows in principle for better delivery optimization: if two merchants have customers who are very close, or even the same customer, it makes sense for them to be delivered by the same truck. Thus, the optimization problem is modified: we have each merchant’s customer list and must decide which customers to group together from among all the merchants’ customers. These customers are then delivered via a separate fleet known as the shared fleet.
The scientific literature on vehicle routing problems is very extensive in operations research. These problems are known to be algorithmically difficult due to the combinatorial explosion in the number of possible routes depending on the number of delivery points. Thus, rather than trying to solve these problems with exact methods, one can focus on modeling aspects and use more generic and faster approximate solution methods called metaheuristics.
For the non-shared scenario, one can draw inspiration from models of the Traveling Salesman Problem (TSP), the Vehicle Routing Problem (VRP), and its classic variants with capacity (CVRP), with delivery slots (VRPTW, CVRPTW), or even with time dependencies on travel times (TDCVRPTW). This should greatly help in modeling the shared scenario. We can also simplify the complex industrial problem to move more towards modeling shared scenarios for these VRP variants.
Realistic instances of both non-shared and shared problems will be made available. Furthermore, we should not hesitate to take advantage of the numerous meta-heuristic implementations, generic or specific to classic VRP variants, available in open-source libraries such as OR-Tools.
More information: