The generalized vehicle routing problem with time windows

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

Document type :

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

Title :

The generalized vehicle routing problem with time windows

Author(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]

Conference title :

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

City :

Seville

Country :

Espagne

Start date of the conference :

2019-06-02

English keyword(s) :

generalized vehicle routing problem
time windows
set covering

HAL domain(s) :

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

English abstract : [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 ...
Show more >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.Show less >

Language :

Anglais

Peer reviewed article :

Oui

Audience :

Internationale

Popular science :

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