Vehicle Routing by Learning from Historical Solutions

Research output: Chapter in Book/Report/Conference proceedingConference paperResearch

24 Downloads (Pure)

Abstract

The goal of this paper is to investigate a decision support system for vehicle routing, where the routing engine learns from the subjective decisions that human planners have made in the past, rather than optimizing a distance-based objective criterion. This is an alternative to the practice of formulating a custom VRP for every company with its own routing requirements. Instead, we assume the presence of past vehicle routing solutions over similar sets of customers, and learn to make similar choices. The approach is based on the concept of learning a first-order Markov model, which corresponds to a probabilistic transition matrix, rather than a deterministic distance matrix. This nevertheless allows us to use existing arc routing VRP software in creating the actual route plans. For the learning, we explore different schemes to construct the probabilistic transition matrix. Our results on a use-case with a small transportation company show that our method is able to generate results that are close to the manually created solutions, without needing to characterize all constraints and sub-objectives explicitly. Even in the case of changes in the client sets, our method is able to find solutions that are closer to the actual route plans than when using distances, and hence, solutions that would require fewer manual changes to transform into the actual route plan.

Original languageEnglish
Title of host publicationPrinciples and Practice of Constraint Programming - 25th International Conference, CP 2019, Proceedings
EditorsThomas Schiex, Simon de Givry
PublisherSpringer
Pages54-70
Number of pages17
Volume11802
ISBN (Print)9783030300470
DOIs
Publication statusPublished - 1 Jan 2019
Event25th International Conference on Principles and Practice of Constraint Programming, CP 2019 - Stamford , United States
Duration: 30 Sep 20194 Oct 2019

Publication series

NamePRINCIPLES AND PRACTICE OF CONSTRAINT PROGRAMMING, CP 2019
ISSN (Print)0302-9743

Conference

Conference25th International Conference on Principles and Practice of Constraint Programming, CP 2019
CountryUnited States
CityStamford
Period30/09/194/10/19

Fingerprint Dive into the research topics of 'Vehicle Routing by Learning from Historical Solutions'. Together they form a unique fingerprint.

Cite this