Une heuristique à grand voisinage pour un problème de confection de tournée pour un seul véhicule avec cueillettes et livraisons et contrainte de chargement

Abstract

Dans ce mémoire, nous présentons un nouveau type de problème de confection de tour- née pour un seul véhicule avec cueillettes et livraisons et contrainte de chargement. Cette variante est motivée par des problèmes similaires rapportés dans la littérature. Le véhi- cule en question contient plusieurs piles où des colis de hauteurs différentes sont empilés durant leur transport. La hauteur totale des items contenus dans chacune des piles ne peut dépasser une certaine hauteur maximale. Aucun déplacement n’est permis lors de la li- vraison d’un colis, ce qui signifie que le colis doit être sur le dessus d’une pile au moment d’être livré. De plus, tout colis i ramassé avant un colis j et contenu dans la même pile doit être livré après j. Une heuristique à grand voisinage, basé sur des travaux récents dans le domaine, est proposée comme méthode de résolution. Des résultats numériques sont rapportés pour plusieurs instances classiques ainsi que pour de nouvelles instances.

In this work, we consider a new type of pickup and delivery routing problem with last- in-first-out loading constraints for a single vehicle with multiple stacks. This problem is motivated by similar problems reported in the literature. In the problem considered, items are collected and put on top of one of multiple stacks inside the vehicle, such that the total height of the items on each stack does not exceed a given threshold. The loading constraints state that if items i and j are in the same stack and item i is collected before item j, then i must be delivered after j. Furthermore, an item can be delivered only if it is on the top of a stack. An adaptive large neighborhood heuristic, based on recent studies in this field, is proposed to solve the problem. Numerical results are reported on many classical instances reported in the literature and also on some new ones.