A Hierarchical Grouping Algorithm for the Multi-Vehicle Dial-a-Ride Problem
Pages 1195 - 1207
Abstract
Ride-sharing is an essential aspect of modern urban mobility. In this paper, we consider a classical problem in ride-sharing - the Multi-Vehicle Dial-a-Ride Problem (Multi-Vehicle DaRP). Given a fleet of vehicles with a fixed capacity stationed at various locations and a set of ride requests specified by origins and destinations, the goal is to serve all requests such that no vehicle is assigned more passengers than its capacity at any point in its trip.
We give an algorithm HGR, which is the first non-trivial approximation algorithm for the Multi-Vehicle DaRP. The main technical contribution is to reduce Multi-Vehicle DaRP to a certain capacitated partitioning problem, which we solve using a novel hierarchical grouping algorithm.
Experimental results show that the vehicle routes produced by our algorithm not only exhibit less total travel distance compared to state-of-the-art baselines, but also enjoy a small in-transit latency, which crucially relates to each individual rider's traveling time. This suggests that HGR enhances rider experience while being energy-efficient.
References
[1]
Xiaohui Bei and Shengyu Zhang. 2018. Algorithms for Trip-Vehicle Assignment in Ride-Sharing. In Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, (AAAI-18), the 30th innovative Applications of Artificial Intelligence (IAAI-18), and the 8th AAAI Symposium on Educational Advances in Artificial Intelligence (EAAI-18), New Orleans, Louisiana, USA, February 2-7, 2018. 3--9.
[2]
Hua Cai, Xi Wang, Peter Adriaens, and Ming Xu. 2019. Environmental benefits of taxi ride sharing in Beijing. Energy 174 (2019), 503--508.
[3]
Moses Charikar and Balaji Raghavachari. 1998. The finite capacity dial-a-ride problem. In Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science (FOCS'98), November 8-11, 1998, Palo Alto, California, USA. 458--467.
[4]
Peng Cheng, Hao Xin, and Lei Chen. 2017. Utility-Aware Ridesharing on Road Networks. In Proceedings of the 2017 ACM International Conference on Management of Data (Chicago, Illinois, USA) (SIGMOD '17). New York, NY, USA, 1197--1210.
[5]
Regina R Clewlow and Gouri S Mishra. 2017. Disruptive transportation: The adoption, utilization, and impacts of ride-hailing in the United States. (2017). https://escholarship.org/uc/item/82w2z91j
[6]
Jean-François Cordeau. 2006. A Branch-and-Cut Algorithm for the Dial-a-Ride Problem. Oper. Res. 54, 3 (2006), 573--586.
[7]
Jean-François Cordeau and Gilbert Laporte. 2003. A Tabu search heuristic for the static multi-vehicle dial-a-ride problem. Transportation Research Part B: Methodological 37 (07 2003), 579--594.
[8]
Claudio Cubillos, Enrique Urra, and Nibaldo Rodríguez. 2009. Application of genetic algorithms for the DARPTW problem. International Journal of Computers Communications & Control 4, 2 (2009), 127--136.
[9]
Willem E. de Paepe, Jan Karel Lenstra, Jiri Sgall, René A. Sitters, and Leen Stougie. 2004. Computer-Aided Complexity Classification of Dial-a-Ride Problems. INFORMS Journal on Computing 16, 2 (2004), 120--132.
[10]
Paolo Detti, Francesco Papalini, and Garazi Zabalo Manrique de Lara. 2017. A multi-depot dial-a-ride problem with heterogeneous vehicles and compatibility constraints in healthcare. Omega 70 (2017), 1--14.
[11]
Ran Duan and Seth Pettie. 2010. Approximating maximum weight matching in near-linear time. In Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2010), October 23-26, 2010, Las Vegas, Nevada, USA. 673--682.
[12]
Jack Edmonds. 1965. Maximum matching and a polyhedron with 0, 1-vertices. Journal of research of the National Bureau of Standards B 69, 125-130 (1965), 55--56.
[13]
Harold N Gabow. 1990. Data structures for weighted matching and nearest common ancestors with linking. In Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 1990), 22-24 January 1990, San Francisco, California, USA. 434--443.
[14]
Thierry Garaix, Christian Artigues, Dominique Feillet, and Didier Josselin. 2010. Vehicle routing problems with alternative paths: An application to on-demand transportation. European Journal of Operational Research 204, 1 (2010), 62--75.
[15]
Timo Gschwind and Michael Drexl. 2019. Adaptive large neighborhood search with a constant-time feasibility test for the dial-a-ride problem. Transportation Science 53, 2 (2019), 480--491.
[16]
Timo Gschwind and Stefan Irnich. 2015. Effective handling of dynamic time windows and its application to solving the dial-a-ride problem. Transportation Science 49, 2 (2015), 335--354.
[17]
Anupam Gupta, MohammadTaghi Hajiaghayi, Viswanath Nagarajan, and Ramamoorthi Ravi. 2010. Dial a ride from k-forest. ACM Transactions on Algorithms (TALG) 6, 2 (2010), 1--21.
[18]
Sin C Ho, Wai Yuen Szeto, Yong-Hong Kuo, Janny MY Leung, Matthew Petering, and Terence WH Tou. 2018. A survey of dial-a-ride problems: Literature review and recent developments. Transportation Research Part B: Methodological 111 (2018), 395--421.
[19]
Yan Huang, Favyen Bastani, Ruoming Jin, and Xiaoyang Sean Wang. 2014. Large scale real-time ridesharing with service guarantee on road networks. Proceedings of the VLDB Endowment 7, 14 (2014), 2017--2028.
[20]
Jang-Jei Jaw. 1984. Solving large-scale dial-a-ride vehicle routing and scheduling problems. FTL report (Massachusetts Institute of Technology. Flight Transportation Laboratory) (1984). https://hdl.handle.net/1721.1/68045
[21]
Jang-Jei Jaw, Amedeo R Odoni, Harilaos N Psaraftis, and Nigel HM Wilson. 1986. A heuristic algorithm for the multi-vehicle advance request dial-a-ride problem with time windows. Transportation Research Part B: Methodological 20, 3 (1986), 243--257.
[22]
Rene Munch Jorgensen, Jesper Larsen, and Kristin Berg Bergvinsdottir. 2007. Solving the dial-a-ride problem using genetic algorithms. Journal of the operational research society 58, 10 (2007), 1321--1331.
[23]
Vladimir Kolmogorov. 2009. Blossom V: a new implementation of a minimum cost perfect matching algorithm. Mathematical Programming Computation 1, 1 (2009), 43--67.
[24]
Silvio Lattanzi, Benjamin Moseley, Siddharth Suri, and Sergei Vassilvitskii. 2011. Filtering: A Method for Solving Graph Problems in MapReduce. In Proceedings of the 23rd Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA'11), San Jose, CA, USA, June 4-6, 2011 (San Jose, California, USA). New York, NY, USA, 85--94.
[25]
Kelin Luo, Chaitanya Agarwal, Syamantak Das, and Xiangyu Guo. 2022. The Multi-vehicle Ride-Sharing Problem. In Proceedings of the Fifteenth ACM International Conference on Web Search and Data Mining (WSDM'22), Virtual Event / Tempe, AZ, USA, February 21 - 25, 2022. 628--637.
[26]
Kelin Luo, Alexandre M Florio, Syamantak Das, and Xiangyu Guo. 2022. A Hierarchical Grouping Algorithm for the Multi-Vehicle Dial-a-Ride Problem. arXiv preprint arXiv:2210.05000 (2022). https://arxiv.org/abs/2210.05000
[27]
Kelin Luo and Frits CR Spieksma. 2020. Approximation algorithms for car-sharing problems. In Proceedings of the 26th International Conference on Computing and Combinatorics (COCOON 2020), Atlanta, GA, USA, August 29-31, 2020 (Lecture Notes in Computer Science), Vol. 12273. Springer, 262--273.
[28]
Shuo Ma, Yu Zheng, and Ouri Wolfson. 2013. T-share: A large-scale dynamic taxi ridesharing service. In 2013 IEEE 29th International Conference on Data Engineering (ICDE'13). 410--421.
[29]
Mohamed Masmoudi, Kris Braekers, Malek Masmoudi, and Abdelaziz Dammak. 2016. A Hybrid Genetic Algorithm for the Heterogeneous Dial-A-Ride Problem. Computers and Operations Research 81 (12 2016).
[30]
NYCTLC. 2020. New York City Taxi & Limousine Commission trip data. https://www1.nyc.gov/site/tlc/about/tlc-trip-record-data.page.
[31]
OpenStreetMap. 2021. San Francisco and New York City street map data. https://www.openstreetmap.org.
[32]
Sophie N Parragh, Karl F Doerner, and Richard F Hartl. 2010. Variable neighborhood search for the dial-a-ride problem. Computers & Operations Research 37, 6 (2010), 1129--1138.
[33]
Seth Pettie and Vijaya Ramachandran. 2000. An optimal minimum spanning tree algorithm. In International Colloquium on Automata, Languages, and Programming (ICALP'2000), Geneva, Switzerland, July 9-15, 2000. 49--60.
[34]
Michal Piorkowski, Natasa Sarafijanovic-Djukic, and Matthias Grossglauser. 2009. CRAWDAD dataset EPFL/mobility. https://crawdad.org/epfl/mobility/20090224/cab.
[35]
Stefan Ropke, Jean-François Cordeau, and Gilbert Laporte. 2007. Models and branch-and-cut algorithms for pickup and delivery problems with time windows. Networks: An International Journal 49, 4 (2007), 258--272.
[36]
Alexander Schrijver et al. 2003. Combinatorial optimization: polyhedra and efficiency. Vol. A. Springer. 453--458 pages.
[37]
Yongxin Tong, Yuxiang Zeng, Zimu Zhou, Lei Chen, Jieping Ye, and Ke Xu. 2018. A Unified Approach to Route Planning for Shared Mobility. Proceedings of the VLDB Endowment 11, 11 (2018), 1633--1646.
[38]
Yuxiang Zeng, Yongxin Tong, and Lei Chen. 2019. Last-Mile Delivery Made Practical: An Efficient Route Planning Framework with Theoretical Guarantees. Proceedings of the VLDB Endowment 13, 3 (2019), 320--333.
[39]
Yuxiang Zeng, Yongxin Tong, Yuguang Song, and Lei Chen. 2020. The Simpler the Better: An Indexing Approach for Shared-Route Planning Queries. Proceedings of the VLDB Endowment 13, 13 (Sept. 2020), 3517--3530.
[40]
Libin Zheng, Lei Chen, and Jieping Ye. 2018. Order Dispatch in Price-Aware Ridesharing. Proceedings of the VLDB Endowment 11, 8 (April 2018), 853--865.
[41]
Libin Zheng, Peng Cheng, and Lei Chen. 2019. Auction-Based Order Dispatch and Pricing in Ridesharing. In 35th IEEE International Conference on Data Engineering (ICDE 2019), Macao, China, April 8-11, 2019. 1034--1045.
Recommendations
The Multi-vehicle Ride-Sharing Problem
WSDM '22: Proceedings of the Fifteenth ACM International Conference on Web Search and Data MiningRide-sharing is one of the most popular models of economical and eco-friendly transportation in modern smart cities, especially when riding hybrid and electric vehicles. Usually multiple passengers with similar itineraries are grouped together, which ...
Minimum Makespan Multi-Vehicle Dial-a-Ride
Dial-a-Ride problems consist of a set V of n vertices in a metric space (denoting travel time between vertices) and a set of m objects represented as source-destination pairs {(si,ti)}mi=1, where each object requires to be moved from its source to ...
Vehicle Ride Comfort Analysis and Optimization Using Design of Experiment
IHMSC '10: Proceedings of the 2010 Second International Conference on Intelligent Human-Machine Systems and Cybernetics - Volume 01In this paper the fundamental of the component mode synthesis was reviewed. In order to optimize the ride comfort of the vehicle, a rigid-flexible coupling model of a car was established by using multibody system dynamics method and component mode ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Publisher
VLDB Endowment
Publication History
Published: 01 January 2023
Published in PVLDB Volume 16, Issue 5
Check for updates
Badges
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 93Total Downloads
- Downloads (Last 12 months)32
- Downloads (Last 6 weeks)4
Reflects downloads up to 24 Nov 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in