A reactive GRASP and path relinking for a combined production–distribution problem

Mourad Boudia (1) , Mohamed Aly Ould Louly (1) , Christian Prins (1)

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

An NP-hard production–distribution problem for one product over a multi-period horizon is investigated. The aim is to minimize total cost taking production setups, inventory levels and distribution into account. An integer linear model is proposed as a compact problem specification but it cannot be solved to optimality for large instances. Instead of using a classical two-phase approach (production planning and then route construction for each day), metaheuristics that simultaneously tackle production and routing decisions are developed: a GRASP (greedy randomized adaptive search procedure) and two improved versions using either a reactive mechanism or a path-relinking process. These algorithms are evaluated on 90 randomly generated instances with 50, 100 and 200 customers and 20 periods. The results confirm the interest of integrating production and distribution decisions, compared to classical two-phase methods. Moreover, reaction and path-relinking give better results than the GRASP alone.

Mots clés: Greedy randomized adaptive search procedure; Path relinking; Production planning; Vehicle routing

Domaines: Recherche opérationnelle [math.OC]

Mourad Boudia, Mohamed Aly Ould Louly, Christian Prins. A reactive GRASP and path relinking for a combined production–distribution problem. Computers and Operations Research, 2007, 34 (11), pp.3402-3419. ⟨10.1016/j.cor.2006.02.005⟩. ⟨hal-02478710⟩