Minimizing the number of sorting sessions at La Poste as a variant of vector bin-packing – Elliot Braud (University of Nantes)

Minimizing the number of sorting sessions at La Poste as a variant of vector bin-packing

This paper addresses a mail sorting optimization problem faced by La Poste, the major French mail delivery service provider. As part of a broader effort to optimize La Poste’s sorting processes, we introduce a new variant of the Vector Bin Packing (VBP) problem that incorporates specific precedence constraints within partially filled vectors, allowing elements to be spread across the vector while maintaining their original order. The objective of this variant is to minimize the number of sorting sessions (bins) required to process a given set of postal routes (partially filled vectors). By addressing these constraints, this approach aims to reduce energy costs and enhance overall efficiency in La Poste’s sorting centers.

To solve this problem, we develop and evaluate several methods, including an exact binary Linear Program (0-1 LP) model, an adaptation of the Best-Fit (BF) heuristic, and a Genetic Algorithm (GA) meta-heuristic. These methods are tested on both industrial-alike cases and challenging generated instances, where optimal solutions are known.

Our results indicate that while the 0-1 LP model is effective for small problem instances, it becomes impractical for medium to large ones due to excessive computation time. In contrast, the adapted heuristic and meta-heuristic algorithms consistently yield high-quality solutions, demonstrating their effectiveness in handling complex and large-scale sorting problems.