TY - GEN
T1 - Multi-destination vehicular route planning with parking and traffic constraints
AU - Hakeem, Abeer
AU - Gehani, Narain
AU - Ding, Xiaoning
AU - Curtmola, Reza
AU - Borcea, Cristian
N1 - Publisher Copyright:
© 2019 Association for Computing Machinery.
PY - 2019/11/12
Y1 - 2019/11/12
N2 - This paper aims to provide an efficient solution for people in a city who drive their cars to visit several destinations, where they need to park for a while, but do not care about the visiting order. This instance of the multi-destination route planning problem is novel in terms of its constraints: the real-time traffic conditions and the real-time free parking conditions in the city. The paper proposes a novel Multi-Destination Vehicle Route Planning (MDVRP) system to optimize the travel time for all drivers. MDVRP's design has two components: a mobile app running on the drivers' smart phones that submits real-time route requests and guides the drivers toward destinations, and a server in the cloud that optimizes the routes by finding the most efficient order to visit the destinations. MDVRP uses TDTSP-FPA, an algorithm that finds the fastest route to the next destination and also assigns free curbside parking spaces that minimize the total travel time for drivers. We evaluate MDVRP using a driver trip dataset that contains real vehicular mobility traces of over two million drivers from the city of Cologne, Germany. By learning the spatio-temporal distribution of real driver destinations from this dataset, we build a novel experimental platform that simulates real, multi-destination driver trips. Extensive simulations executed over this platform demonstrate that TDTSP-FPA delivers the best performance when compared to three baseline algorithms.
AB - This paper aims to provide an efficient solution for people in a city who drive their cars to visit several destinations, where they need to park for a while, but do not care about the visiting order. This instance of the multi-destination route planning problem is novel in terms of its constraints: the real-time traffic conditions and the real-time free parking conditions in the city. The paper proposes a novel Multi-Destination Vehicle Route Planning (MDVRP) system to optimize the travel time for all drivers. MDVRP's design has two components: a mobile app running on the drivers' smart phones that submits real-time route requests and guides the drivers toward destinations, and a server in the cloud that optimizes the routes by finding the most efficient order to visit the destinations. MDVRP uses TDTSP-FPA, an algorithm that finds the fastest route to the next destination and also assigns free curbside parking spaces that minimize the total travel time for drivers. We evaluate MDVRP using a driver trip dataset that contains real vehicular mobility traces of over two million drivers from the city of Cologne, Germany. By learning the spatio-temporal distribution of real driver destinations from this dataset, we build a novel experimental platform that simulates real, multi-destination driver trips. Extensive simulations executed over this platform demonstrate that TDTSP-FPA delivers the best performance when compared to three baseline algorithms.
KW - Cooperative System
KW - Mobile App
KW - Multiple Destinations
KW - Parking Assignment
KW - Route planning
UR - http://www.scopus.com/inward/record.url?scp=85079831462&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85079831462&partnerID=8YFLogxK
U2 - 10.1145/3360774.3360824
DO - 10.1145/3360774.3360824
M3 - Conference contribution
AN - SCOPUS:85079831462
T3 - ACM International Conference Proceeding Series
SP - 298
EP - 307
BT - Proceedings of the 16th EAI International Conference on Mobile and Ubiquitous Systems
PB - Association for Computing Machinery
T2 - 16th EAI International Conference on Mobile and Ubiquitous Systems: Computing, Networking and Services, MobiQuitous 2019
Y2 - 12 November 2019 through 14 November 2019
ER -