Genetic Search of Pickup and Delivery Problem Solutions for Self-driving Taxi Routing

Abstract : Self-driving cars belong to rapidly growing domain of cyber-physical systems with many open problems. In this paper, we study routing problem for taxis. In mathematical terms, it is well-known Pickup and Delivery problem (PDP). We use with the standard small-moves technique, which is to apply small changes to a solution for PDP in order to obtain a better one; and an approach that works with small-moves as mutations in genetic algorithms. We propose a strategy-based framework for managing set of small changes and suggest different strategies. We tested algorithms for routing on real-world dataset on taxi orders to airports in United Kingdom. The results show that algorithms using mixed strategies outperform algorithms using a single small move.
Document type :
Conference papers
Complete list of metadatas

Cited literature [30 references]  Display  Hide  Download

https://hal.inria.fr/hal-01557588
Contributor : Hal Ifip <>
Submitted on : Thursday, July 6, 2017 - 1:54:56 PM
Last modification on : Friday, December 1, 2017 - 1:16:27 AM
Long-term archiving on : Wednesday, January 24, 2018 - 8:11:41 PM

File

430537_1_En_30_Chapter.pdf
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

Viacheslav Shalamov, Andrey Filchenkov, Anatoly Shalyto. Genetic Search of Pickup and Delivery Problem Solutions for Self-driving Taxi Routing. 12th IFIP International Conference on Artificial Intelligence Applications and Innovations (AIAI), Sep 2016, Thessaloniki, Greece. pp.348-355, ⟨10.1007/978-3-319-44944-9_30⟩. ⟨hal-01557588⟩

Share

Metrics

Record views

86

Files downloads

97