Program > By author > Rousseau Louis-Martin

A large neighborhood based matheuristic for the vehicle routing problem with cross-docking and dock resource constraints
Philippe Grangier  1, 2@  , Michel Gendreau  1, 3@  , Fabien Lehuédé  2@  , Louis-Martin Rousseau  1, 3@  
1 : Centre Interuniversitaire de Recherche sur les Réseaux d'Entreprise, la Logistique et le Transport  (CIRRELT)  -  Website
Pavillon André-Aisenstadt, bureau 3520 2920, Chemin de la Tour Montréal (Québec) H3T 1J4 CANADA -  Canada
2 : LUNAM / Ecole des Mines de Nantes / IRCCyN  (EMN)
Ecole des Mines de Nantes
1, rue de la Noë - BP 92101 - 44321 NANTES CEDEX 3 - France -  France
3 : Ecole Polytechnique de Montreal  (EPM)  -  Website
Campus de l'Université de Montréal 2500, chemin de Polytechnique Montréal (Québec) H3T 1J4 -  Canada

The Vehicle Routing Problem with Cross-Docking (VRPCD) is a variant of the Pickup and Delivery Problem with Transfers with one compulsory transfer point: vehicles start by collecting items, then return to the cross-dock where they unload/reload some items and eventually visit delivery locations. The VRPCD has been proposed to model the routing part of the cross-docking distribution strategy, whict has been largely used since 1980s and is known to help reducing delivery costs compared to traditional distribution systems. In the VRPCD, it is assumed that a truck undergoes consolidation operations as soon as it arrives at the cross-dock. However, in real life the processing capacity of the cross-dock is a limiting factor, and as such several recent articles have outlined the need for a model that would take it into account in the routing problem. To that end, we introduce an extension of the VRPCD in which the number of vehicles that can simultaneously be processed at the cross-dock is limited. We call it the Vehicle Routing Problem with Cross-Docking and Dock Resource Constraints (VRPCD-DR). To solve it, we adapt a recently proposed method for VRPCD that relies on large neighborhood search and periodic calls to a set partitioning based problem. In particular we focus on feasibility tests in the reinsertion part of the LNS, as the capacity constraints at the cross-dock makes the scheduling subproblem NP-Hard. Our method has been tested on instances adapted from the VRPCD.


Online user: 1