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

摘要

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.