An Exact Method to Solve the Multi-Trip Vehicle Routing Problem with Multi Time Windows

Giroudeau, Rodolphe; Hernandez, Florent; Naud, Olivier; Semet, Frédéric

Type de document :

Communication dans un congrès avec actes

Titre :

An Exact Method to Solve the Multi-Trip Vehicle Routing Problem with Multi Time Windows

Auteur(s) :

Giroudeau, Rodolphe [Auteur]
Methods, Algorithms for Operations REsearch [MAORE]
Hernandez, Florent [Auteur]
Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier [LIRMM]
Naud, Olivier [Auteur]
Information – Technologies – Analyse Environnementale – Procédés Agricoles [UMR ITAP]
Semet, Frédéric [Auteur]

LAGIS-OSL

Titre de la manifestation scientifique :

5th International Workshop on Freight Transportation and Logistics (ODYSSEUS)

Ville :

Mykonos Island

Pays :

Grèce

Date de début de la manifestation scientifique :

2012-05-21

Date de publication :

2012-05-24

Discipline(s) HAL :

Computer Science [cs]/Operations Research [math.OC]

Résumé en anglais : [en]

This article tackles the multi-trip vehicule routing problem with time windows and limited du-ration. A trip is a timed route such that a succession of trips can be assigned to one vehicle. We provide a two-phase exact ...
Lire la suite >This article tackles the multi-trip vehicule routing problem with time windows and limited du-ration. A trip is a timed route such that a succession of trips can be assigned to one vehicle. We provide a two-phase exact algorithm to solve it. The rst phase enumerates possible ordered lists of client matching trip maximum duration criterion. The second phase uses a Branch and Price scheme to generate and choose best set of trips to visit all customers. We propose a set covering formulation as the column generation master problem, where columns (variables) rep-resent trips. The sub-problem selects appropriate timing for trips and has a pseudo-polynomial complexity. Computional results on Solomon's benchmarks are presented. The computional times obtained with our new algorithm are much lower than the ones obtained in the sole exact algorithm previously published on this problemLire moins >

Langue :

Anglais

Comité de lecture :

Oui

Audience :

Internationale

Vulgarisation :

Non

Collections :

Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189

Source :

Harvested from HAL

Fichiers

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00702137/document
Accès libre
Accéder au document

document
Accès libre
Accéder au document

HERNANDEZ12.pdf
Accès libre
Accéder au document

document
Accès libre
Accéder au document

HERNANDEZ12.pdf
Accès libre
Accéder au document

An Exact Method to Solve the Multi-Trip ... BibTeX CSV Excel RIS

Fichiers

An Exact Method to Solve the Multi-Trip ...

BibTeX

CSV

Excel

RIS