A Column Generation Based Heuristic for the Dial-A-Ride Problem

Nastaran Rahmani 1, 2, 3 Boris Detienne 3 Ruslan Sadykov 3, 2 François Vanderbeck 2, 3
3 Realopt - Reformulations based algorithms for Combinatorial Optimization
LaBRI - Laboratoire Bordelais de Recherche en Informatique, IMB - Institut de Mathématiques de Bordeaux, Inria Bordeaux - Sud-Ouest
Abstract : The Dial-a-Ride Problem is a variant of the pickup and delivery problem with time windows, where the user inconvenience must be taken into account. In this paper, ride time and customer waiting time are modeled through both constraints and an associated penalty in the objective function. We develop a column generation approach, dynamically generating feasible vehicle routes. Handling ride time constraints explicitly in the pricing problem solver requires specific developments. Our dynamic programming approach for pricing problem makes use of a heuristic dominance rule and a heuristic enumeration procedure, which in turns implies that our overall branch-and-price procedure is a heuris-tic. However, in practice our heuristic solutions are experimentally very close to exact solutions and our approach is numerically competitive in terms of computation times.
Type de document :
Communication dans un congrès
International Conference on Information Systems, Logistics and Supply Chain (ILS), Jun 2016, Bordeaux, France. 2016
Liste complète des métadonnées

https://hal.inria.fr/hal-01425755
Contributeur : François Vanderbeck <>
Soumis le : mardi 3 janvier 2017 - 18:57:42
Dernière modification le : jeudi 11 janvier 2018 - 06:22:12
Document(s) archivé(s) le : mardi 4 avril 2017 - 15:18:55

Fichier

ILSDarpHeu20.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01425755, version 1

Collections

Citation

Nastaran Rahmani, Boris Detienne, Ruslan Sadykov, François Vanderbeck. A Column Generation Based Heuristic for the Dial-A-Ride Problem. International Conference on Information Systems, Logistics and Supply Chain (ILS), Jun 2016, Bordeaux, France. 2016. 〈hal-01425755〉

Partager

Métriques

Consultations de la notice

365

Téléchargements de fichiers

173