The generalized vehicle routing problem with time windows

Yuan, Yuan; Cattaruzza, Diego; Ogier, Maxime; Semet, Frédéric; Vigo, Daniele

Type de document :

Autre communication scientifique (congrès sans actes - poster - séminaire...): Communication dans un congrès avec actes

Titre :

The generalized vehicle routing problem with time windows

Auteur(s) :

Yuan, Yuan [Auteur]
Integrated Optimization with Complex Structure [INOCS]
Cattaruzza, Diego [Auteur]

Integrated Optimization with Complex Structure [INOCS]
Ogier, Maxime [Auteur]

Integrated Optimization with Complex Structure [INOCS]
Semet, Frédéric [Auteur]

Integrated Optimization with Complex Structure [INOCS]
Vigo, Daniele [Auteur]
Alma Mater Studiorum Università di Bologna = University of Bologna [UNIBO]

Titre de la manifestation scientifique :

VeRoLog 2019 - Workshop of the EURO Working Group on Vehicle Routing and Logistics optimization

Ville :

Seville

Pays :

Espagne

Date de début de la manifestation scientifique :

2019-06-02

Mot(s)-clé(s) en anglais :

generalized vehicle routing problem
time windows
set covering

Discipline(s) HAL :

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

Résumé en anglais : [en]

Global e-commerce sales are estimated to hit $4.5 trillion in 2021. This poses huge challenges forlast mile delivery services. Currently deliveries are performed at customer?s home/workplacewhere customers wait to get ...
Lire la suite >Global e-commerce sales are estimated to hit $4.5 trillion in 2021. This poses huge challenges forlast mile delivery services. Currently deliveries are performed at customer?s home/workplacewhere customers wait to get orders. Recently, companies developed locker delivery. Customerschoose a nearby locker as their pickup location for orders. In the past two years, trunk de-livery has been proposed: orders can be delivered to the trunks of cars. Trunk delivery isdifferent from the former two since the car may be in different locations during the day. Thus,synchronization between cars and couriers is required to perform the delivery.This work studies a last-mile system that combines home/workplace, locker and trunk deliv-ery services. We call the resulting problem the generalized vehicle routing problem with timewindows (GVRPTW).We describe the GVRPTW with a set covering model. The solution is obtained by solvingthis model on a restricted route pool, subset of all feasible routes. The route pool is first filledusing construction heuristic: first pivots customers are selected, then next inserted customersare selected based on a regret paradigm. Finally routes are re-optimized with a labelingalgorithm. The route pool is iteratively enriched 1) with routes obtained by exploiting thedual information retrieved by the resolution of the linear relaxation of the set covering model;2) with new routes obtained by intensification of the research around feasible solutions via alocal search procedure.The algorithm is tested on benchmark instances from the literature.Lire 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

The generalized vehicle routing problem ... BibTeX CSV Excel RIS

The generalized vehicle routing problem ...

BibTeX

CSV

Excel

RIS