Aggregating disjoint partial sub-orders – an internal logistics application

Abstract

The problematic addressed in this work concerns an internal logistics issue that arises in warehousing. It first concerns the aggregation of a several ordered flows of loads (cartons, totes, containers, etc.) into a single flow, called the load sequencing problem. Then, this flow should be injected into the system at a maximal throughput, which gives the load injection problem. From the theoretical perspective, the load sequencing problem belongs to the class of partial-order aggregation problems, known to be NP-Hard. We describe a use-case application in logistics and formulate it in mathematical terms as a specific partial-order aggregation problem, namely disjoint partial sub-orders aggregation. We then present two exact solution methods in detail, one based on integer linear programming and the other using dynamic programming combined with a Branch & Cut scheme. All methods perform very well for randomly generated industrial instances. At the end, we provide a heuristic based on the dynamic programming algorithm. This heuristic is implemented for industrial use and gives near-optimal solutions in a very short computation time. The load injection problem falls in the category of scheduling problem (Job shop problem). In practice, this comes to compute the injection dates of loads in the collector with goal of ensuring a maximal debit exit flow with respect to the capacity of the system. We provide the formula for the injection date which achieves maximal debit exit flow. With respect to the application in hand, the proposed method outperforms the existing used method in terms of flow management and brings in practice a significant increase (up to 20%) of a number of loads proceeded for the same amount of time. Our findings are supported by numerical results.

Keywords:

• Logistic
• warehousing
• sorting
• partial orders
• dynamic programming
• optimisation
• heuristics

Disclosure statement

No potential conflict of interest was reported by the author(s).

Additional information

Notes on contributors

Blandine Vacher

Blandine Vacher graduated as a computer engineer, followed by a research master's degree in Operations Research. She received her PhD from University of Technology of Compiégne with a thesis on Optimization Techniques applied to the piloting of storage and retrieval systems in 2020. Since then, she has been working for different companies to analyze and optimize different problems in the various fields such as logistics, defense and nuclear.

Antoine Jouglet

Antoine Jouglet is a full professor with the Department of Information Processing Engineering, UTC. His research interests concern combinatorial optimization. His main contributions are in the resolution of scheduling problems, particularly by using constraint programming techniques. He is the author of more than 70 papers in journals and conferences proceedings and he has supervised7 Ph.D. dissertations. From 2014 to 2022, he has been the coordinator of the research group GoThA in theoretical and applied scheduling.

Dritan Nace

Dritan Nace received the degrees of Mathematics in 1991 (University of Tirana, Albania), MSc (DEA) in Computer Science in 1993 and PhD in Computer Science in 1997, both from University of Technology of Compiégne. Since 2008, he holds a position as full Professor in Computer Science at the University of Technology of Compiégne. His research interests include operations research with applications in networks, transport and logistic.

Marwane Bouznif

Marwane Bouznif received the degrees of MSc in computer science in 2008 from university of Montpellier II and PhD in Mathematics and Computer Science in 2012 from university of Grenoble. Since 2013 he works at Savoye a company that build both mechanical and software solution in warehousing where he holds the position of technical lead AI and optimization. His research interests include operations research and machine learning applied in internal logistic.