Local Search Based Metaheuristics for Two-Echelon Distribution Network with Perishable Products

Sona Kande (1, 2) , Christian Prins (1) , Lucile Belgacem (2) , Benjamin Redon (2)

1 LOSI - Laboratoire d'Optimisation des Systèmes Industriels
2 FuturMaster - FuturMaster

This article presents a planning problem in a distribution network incorporating two levels inventory management of perishable products, lot-sizing, multi-sourcing and transport capacity with a homogeneous fleet of vehicles. A mixed integer linear programming (MILP) and a greedy heuristic are developed to solve this real planning problem. There are some instances for which the solver cannot give a good lower bound within the limited time and for other instances it takes a lot of time to solve MILP. The greedy heuristic is an alternative to the mixed integer linear program to quickly solve some large instances taking into account original and difficult constraints. For some instances the gap between the solutions of the solver (MILP) and the heuristic becomes quite significant. The variable neighborhood descent (VND), the iterated local search (ILS) and the multi-start iterated local search (MS-ILS) are implemented. These methods are included in an APS (Advanced Planning System) and compared with a MILP solver. The instances are derived from actual data or built using a random generator of instances to have wider diversity for computational evaluation. The VND significantly improves the quality of solutions.

Keywords: Distribution network; Multi-start iterated local search; Local search; Lot-sizing; Metaheuristic; Multi-echelon inventory; Multi-sourcing; Perishable product; Supply planning; Transport capacity; Variable neighborhood descent

Domains: Operations Research [cs.RO]

Sona Kande, Christian Prins, Lucile Belgacem, Benjamin Redon. Local Search Based Metaheuristics for Two-Echelon Distribution Network with Perishable Products. Operations Research and Enterprise Systems, 577, pp.212-231, 2015, Communications in Computer and Information Science, 978-3-319-27680-9. ⟨10.1007/978-3-319-27680-9_13⟩. ⟨hal-02495743⟩