Séminaire conjoint CIRRELT-Chaire de recherche du Canada en distributique-Chaire de recherche du Canada en logistique et en transport

TITRE : A Heuristic for the Cyclic Inventory Routing Problem

CONFÉRENCIER : Masoud Chitsaz, KU Leuven, Belgique,

DATE et ENDROIT : 29 janvier 2014, 10h30, salle 5441, Pavillon André-Aisenstadt, Campus de l’Université de Montréal

RESPONSABLE : Jean-François Cordeau

RÉSUMÉ : The Cyclic Inventory Routing Problem (CIRP) is concerned with finding a cyclic schedule for the distribution of a single product to a number of sales-points. The problem involves multiple vehicles that can be dispatched several times during their shift. Each sales-point has a local inventory capacity, a constant consumption rate and stockouts are not allowed. The goal is to compose multiple trips which serve all sales-points and minimize the combination of transportation, inventory and vehicle costs, in a cyclic distribution pattern. Each trip can have a different frequency in the vehicle schedule. This is an important aspect that makes this so called Cyclic Inventory Routing Problem (CIRP) more complex than other Inventory Routing Problems. Our solution approach decomposes the problem into two different but related sub-problems. For each subproblem, we propose a new heuristic. Our first heuristic composes trips based on cost estimations for node transfers between trips. The second algorithm tries to combine these trips in an acceptable cyclic schedule. In order to search the feasible area efficiently, three diversification moves are designed. Also a new type of “hash function” is used to prevent searching the same part of the solution space repeatedly. The proposed algorithm is capable of finding high quality solutions in a reasonable time, especially for large instances. Applying the algorithm on 320 available benchmark instances, for more than half of them,the best known solution is improved. The results show, on average, a 2.5% improvement in the objective function value compare to the best known results in the literature.