A greedy approach for carpool scheduling optimisation in smart cities. Issue 5 (2nd September 2020)

• Record Type: Journal Article
• Authors: Duan, Yubin; Wu, Jie; Zheng, Huanyang
• Is Part Of: International journal of parallel, emergent and distributed systems. Volume 35:Issue 5(2020)
• Page Start: 535
• Page End: 549
• Publication Date: 2020-09-02
• Subjects: Carpool problem -- greedy algorithm -- cluster merging -- maximum matching; Parallel computers -- Periodicals; Electronic data processing -- Distributed processing -- Periodicals; Computer algorithms -- Periodicals; 004.35
• DOI: 10.1080/17445760.2018.1539718
• Languages: English
• ISSNs: 1744-5760

Abstract

ABSTRACT: Nowadays, large cities face numerous problems caused by the rapidly increasing number of vehicles on road. Carpooling has been shown as an efficient solution to ease the traffic pressure. The objective of our carpool scheduling problem is to minimise the number of carpools needed to transport users. Previous research on the similar topic introduces static capacity constraint which limits the carpool size to the vehicle's capacity. However, it is unnecessary since a seat in the vehicle can be occupied by several passengers if their routes are not overlapped. In this paper, we remove this constraint, which allows a vehicle to serve more users than its capacity. We propose a greedy approach based on the iterative matching and merging. Specifically, starting from a set of single-user carpools, the algorithm iteratively checks the merge-ability between carpools, and then applies the maximum matching algorithm to maximise the number of carpools merged. In addition, two methods are proposed to reduce the time complexity of merge-ability checking process. Furthermore, we improve the time efficiency of our algorithms by exploiting geometry properties. Experimental results on synthetic and real-world datasets show that our algorithms have better performances than baseline. GRAPHICAL ABSTRACT: