Load balancing in the mail sorting process: a case study at the French postal company La Poste

This paper investigates a load balancing problem within the context of postal sorting operations at La Poste, the French postal service. Faced with declining mail volumes, La Poste must reorganize its processes to maintain service quality and operational efficiency. Mail sorting is modeled as a Simple Assembly Line Balancing Problem (SALBP-2), where mail items (tasks) are assigned to containers (stations) in a way that minimizes load imbalances while respecting precedence constraints. These constraints take the form of independent chains, as each mail route follows a fixed delivery sequence. We propose three resolution methods: an exact approach based on a Mixed Integer Linear Programming (MILP) formulation, a metaheuristic algorithm based on simulated annealing, and a fast heuristic designed for industrial deployment which exploits the precedence constraint structure for faster convergence. The metaheuristic and the heuristic are tested on academic and real-world datasets much larger than those commonly used in the literature. In order to use them several times a day, the resolution method needs to be fast in terms of calculation time. Due to its strong performance and low computation time, the heuristic we propose has been implemented on industrial platforms at La Poste and is now used daily.