Anticipatory Vehicle Routing for Same-Day Pick-up and Delivery using Historical Data Clustering

Jelmer van Lochem, Maximilian Kronmueller, Pim Van t. Hof, Javier Alonso-Mora

Research output: Chapter in Book/Conference proceedings/Edited volumeConference contributionScientificpeer-review

Abstract

In this paper we address the problem of same-day pick-up and delivery where a set of tasks are known a priori and a set of tasks are revealed during operation. The vehicle routes are precomputed based on the known and predicted requests and adjusted online as new requests are revealed. We propose a novel anticipatory insertion method which incorporates a set of predicted requests to beneficially adjust the routes of a fleet of vehicles in real-time. Requests are predicted based on historical data, which is clustered in advance. We exploit inherent patterns of the demand, which are captured by historical data and include them in a dynamic vehicle routing solver based on heuristics and adaptive large neighborhood search. The proposed method is evaluated using numerical simulations on a variety of real-world problems with up to 1655 requests per day. Their degree of dynamism ranges from 0.70 to 0.93. These instances represent dynamic multi-depot pickup and delivery problems with time windows. The method has shown to require less driven kilometers than comparable methods.

Original languageEnglish
Title of host publicationProceedings of the IEEE 23rd International Conference on Intelligent Transportation Systems, ITSC 2020
Place of PublicationPiscataway, NJ, USA
PublisherIEEE
Number of pages6
ISBN (Electronic)978-1-7281-4149-7
DOIs
Publication statusPublished - 2020
Event23rd IEEE International Conference on Intelligent Transportation Systems, ITSC 2020 - Rhodes, Greece
Duration: 20 Sep 202023 Sep 2020

Conference

Conference23rd IEEE International Conference on Intelligent Transportation Systems, ITSC 2020
CountryGreece
CityRhodes
Period20/09/2023/09/20

Fingerprint Dive into the research topics of 'Anticipatory Vehicle Routing for Same-Day Pick-up and Delivery using Historical Data Clustering'. Together they form a unique fingerprint.

Cite this