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 sm
- PDF / 223,072 Bytes
- 8 Pages / 439.37 x 666.142 pts Page_size
- 105 Downloads / 197 Views
Abstract. Self-driving cars belong to rapidly growing domain of cyberphysical 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. Keywords: Self-driving car · Autonomous car delivery · Genetic algorithms · City taxi
1
· Routing · Pickup and
Introduction
Usage of cyber-physical systems (CPS) such as medical devices, industrial robots or smart grid, showed extensive growth in the recent years [1]. It leads to high demand on algorithms for CPSs improving their performance and interaction with environment. Control systems of this type are thought to show high autonomy and to be able to solve typical tasks met in the domain of their application. Self-driving cars (SDC), also known as autonomous cars, are one of the CPSs with rapidly growing importance: SDCs share market with ordinary (humandriving) vehicles, and potential effect of its introduction is often referred as a revolution [9,21]. Consequences include improvements in traffic, vehicle usage and even implementation of new social strategy, so-called mobility as a service [5,25]. List of organizations racing for SDC includes not only well-known vehicle manufacturing companies, but also Google, Uber [15] and Baidu [10]. One of the possible applications of SDC is a taxi service in airports. Airports are usually a very intensive hub for taxi routing, due to many people use taxis to get to an airport or get to a city after arrival. It explains why many airports all over the world have their own taxi services or at least taxi services accredited c IFIP International Federation for Information Processing 2016 Published by Springer International Publishing Switzerland 2016. All Rights Reserved L. Iliadis and I. Maglogiannis (Eds.): AIAI 2016, IFIP AICT 475, pp. 348–355, 2016. DOI: 10.1007/978-3-319-44944-9 30
Genetic Search of Pickup and Delivery Problem Solutions
349
to be official for this airport. This policy shows several advantages. First of all, airport-associated taxis are less affected by the traffic situation in the city. Second, tariffs for taxi are usually fixed or can be simpler adjusted to the current demand, since regular taxi services have to take into account all the demands for mobility across the city. Many studies are devoted to SDC problem. They include: – – – – –
map generation and navigation [13,19,29]; sensor system [3,12]; motion planning [2,17,20,23,31]; distributed and parallel computational infrastructure [18,24,26]; routin
Data Loading...
