A Large Neighborhood Search for the Daily Drayage Problem
Diana Abi-Nader  1, 2@  , Nabil Absi  1@  , Dominique Feillet  1@  , Thierry Garaix  1@  , Taki Eddine Korabi  2@  
1 : Mines Saint-Etienne and LIMOS
Mines Saint-Etienne, Univ Clermont Auvergne, INP Clermont Auvergne, CNRS, UMR 6158 LIMOS, F - 42023 Saint-Etienne France
2 : DMS Logistics
DMS Logistics, 7 rue de la République, 13002 Marseille, France

The Daily Drayage Problem with Time Windows can be seen as a generalization of the Pickup and Delivery Problem with Time Windows (PDPTW). In our problem, in addition to traditional PDP constraints for picking and delivering containers, we should satisfy a precedence constraint between two interrelated requests by introducing a minimum time-lag constraint between some pairs of pickup and delivery requests. Our problem is formulated as a PDPTW with precedence constraints between requests and heterogeneous fleet of vehicles and containers. In order to solve the problem efficiently, we develop a Large Neighborhood Search (LNS) heuristic. LNS heuristics are mainly based on destroy and repair operators that consist in removing and inserting a set of requests in an iterative schema. In our problem, routes are strongly interdependent due to interrelated requests. It is import to check quickly if inserting a request into a partial solution is feasible or not. In this work, we present an approach to check the feasibility of request insertion in constant time.


Personnes connectées : 2 Vie privée
Chargement...