{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,18]],"date-time":"2025-10-18T20:58:06Z","timestamp":1760821086163,"version":"3.37.3"},"reference-count":28,"publisher":"Oxford University Press (OUP)","issue":"11","license":[{"start":{"date-parts":[[2019,11,22]],"date-time":"2019-11-22T00:00:00Z","timestamp":1574380800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Science Foundation of China","doi-asserted-by":"publisher","award":["61876138","61702391"],"award-info":[{"award-number":["61876138","61702391"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020,11,19]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Due to the positive impact of ride sharing on urban traffic and environment, it has attracted a lot of research attention recently. However, most existing researches focused on the profit maximization or the itinerary minimization of drivers, only rare work has covered on adjustable price function and matching algorithm for the batch requests. In this paper, we propose a request matching algorithm and an adjustable price function that benefits drivers as well as passengers. Our request-matching algorithm consists of an exact search algorithm and a group search algorithm. The exact search algorithm consists of three steps. The first step is to prune some invalid groups according to the total number of passengers and the capacity of vehicles. The second step is to filter out all candidate groups according to the compatibility of requests in same group. The third step is to obtain the most profitable group by the adjustable price function, and recommend the most profitable group to drivers. In order to enhance the efficiency of the exact search algorithm, we further design an improved group search algorithm based on the idea of original simulated annealing. Extensive experimental results show that our method can improve the income of drivers, and reduce the expense of passengers. Meanwhile, ride sharing can also keep the utilization rate of seats 80%, driving distance is reduced by 30%.<\/jats:p>","DOI":"10.1093\/comjnl\/bxz075","type":"journal-article","created":{"date-parts":[[2019,11,5]],"date-time":"2019-11-05T20:10:20Z","timestamp":1572984620000},"page":"1607-1623","source":"Crossref","is-referenced-by-count":3,"title":["Driving Route Recommendation With Profit Maximization in Ride Sharing"],"prefix":"10.1093","volume":"63","author":[{"given":"Longji","family":"Huang","sequence":"first","affiliation":[{"name":"School of Computer Science and Technology, Xidian University, Xi\u2019an 710071, China, 2 Taibai Nan Road, Xi'an, Shaanxi Province"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jianbin","family":"Huang","sequence":"additional","affiliation":[{"name":"School of Computer Science and Technology, Xidian University, Xi\u2019an 710071, China, 2 Taibai Nan Road, Xi'an, Shaanxi Province"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yueshen","family":"Xu","sequence":"additional","affiliation":[{"name":"School of Computer Science and Technology, Xidian University, Xi\u2019an 710071, China, 2 Taibai Nan Road, Xi'an, Shaanxi Province"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhiqiang","family":"Zhao","sequence":"additional","affiliation":[{"name":"Microelectronic Technology Institute, 189 Taiyi Road, Xi'an Beilin District, Xi\u2019an 610100, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhenghao","family":"Zhang","sequence":"additional","affiliation":[{"name":"School of Computer Science and Technology, Xidian University, Xi\u2019an 710071, China, 2 Taibai Nan Road, Xi'an, Shaanxi Province"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2019,11,22]]},"reference":[{"key":"2020111609500354800_ref1","doi-asserted-by":"crossref","first-page":"422","DOI":"10.1287\/opre.1030.0106","article-title":"An exact method for the car pooling problem based on lagrangean column generation","volume":"52","author":"Baldacci","year":"2004","journal-title":"Oper. Res."},{"key":"2020111609500354800_ref2","doi-asserted-by":"crossref","first-page":"2263","DOI":"10.1016\/S0305-0548(03)00186-2","article-title":"A distributed geographic information system for the daily car pooling problem","volume":"31","author":"Calvo","year":"2004","journal-title":"Comput. Oper. Res."},{"key":"2020111609500354800_ref3","doi-asserted-by":"crossref","first-page":"352","DOI":"10.1109\/PERCOMW.2011.5766904","article-title":"Saving time, money and the environment-vhike a dynamic ride-sharing service for mobile devices","volume-title":"2011 IEEE International Conference on Pervasive Computing and Communications Workshops (PERCOM Workshops)","author":"Stach","year":"2011"},{"key":"2020111609500354800_ref4","doi-asserted-by":"crossref","first-page":"678","DOI":"10.1145\/1353343.1353425","article-title":"Highly scalable trip grouping for large-scale collective transportation systems","volume-title":"Proceedings of the 11th international conference on Extending database technology: Advances in database technology","author":"Gidofalvi","year":"2008"},{"key":"2020111609500354800_ref5","first-page":"440","article-title":"T-share: A large-scale dynamic taxi ridesharing service","author":"Wolfson","year":"2013","journal-title":"IEEE Int. Conf. on Data Engineering"},{"key":"2020111609500354800_ref6","doi-asserted-by":"crossref","first-page":"955","DOI":"10.1145\/2783258.2783261","article-title":"Scram: A sharing considered route assignment mechanism for fair taxi route recommendations","volume-title":"Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining","author":"Qian","year":"2015"},{"key":"2020111609500354800_ref7","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1016\/j.ejor.2012.05.028","article-title":"Optimization for dynamic ride-sharing: A review","volume":"223","author":"Agatza","year":"2012","journal-title":"Eur. J. Oper. Res."},{"key":"2020111609500354800_ref8","first-page":"99","article-title":"T-drive: driving directions based on taxi trajectories","volume-title":"In Proceedings of the 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems","author":"Yuan","year":"2010"},{"key":"2020111609500354800_ref9","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1145\/2030112.2030128","article-title":"Where to find my next passenger?","volume-title":"In Proceedings of the 13th IInternational Conference on Ubiquitous Computing","author":"Yuan","year":"2011"},{"key":"2020111609500354800_ref10","doi-asserted-by":"crossref","first-page":"330","DOI":"10.1002\/net.20182","article-title":"A branch-and-regret heuristic for stochastic and dynamic vehicle routing problems","volume":"49","author":"Hvattum","year":"2007","journal-title":"Networks"},{"key":"2020111609500354800_ref11","doi-asserted-by":"crossref","first-page":"1117","DOI":"10.1109\/ICDE.2017.156","article-title":"Xhare-a-ride: A search optimized dynamic ride sharing system with approximation guarantee","author":"Thangaraj","year":"2017","journal-title":"2017 IEEE 33rd Int. Conf. on Data Engineering (ICDE)"},{"key":"2020111609500354800_ref12","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1016\/j.trc.2015.07.016","article-title":"Agent based model for dynamic ridesharing","volume":"64","author":"Nourinejad","year":"2016","journal-title":"Transport. Res. C"},{"key":"2020111609500354800_ref13","first-page":"985","article-title":"Noah: A dynamic ridesharing system","volume-title":"In ACM SIGMOD International Conference on Management of Data","author":"Tian","year":"2013"},{"key":"2020111609500354800_ref14","doi-asserted-by":"crossref","first-page":"853","DOI":"10.14778\/3204028.3204030","article-title":"Order dispatch in price-aware ridesharing","volume":"11","author":"Zheng","year":"2018","journal-title":"Proc. Vldb Endowment"},{"key":"2020111609500354800_ref15","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1007\/s10288-006-0018-0","article-title":"An effective and fast heuristic for the dial-a-ride problem","volume":"5","author":"Calvo","year":"2007","journal-title":"Q. J. Oper. Res."},{"key":"2020111609500354800_ref16","doi-asserted-by":"crossref","first-page":"573","DOI":"10.1287\/opre.1060.0283","article-title":"A branch-and-cut algorithm for the dial-a-ride problem","volume":"54","author":"Cordeau","year":"2006","journal-title":"Oper. Res."},{"key":"2020111609500354800_ref17","doi-asserted-by":"crossref","first-page":"579","DOI":"10.1016\/S0191-2615(02)00045-0","article-title":"A tabu search heuristic for the static multi-vehicle dial-a-ride problem","volume":"37","author":"Cordeau","year":"2003","journal-title":"Transport. Res. B Meth."},{"key":"2020111609500354800_ref18","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1016\/0377-2217(92)90192-C","article-title":"The vehicle routing problem: An overview of exact and approximate algorithms","volume":"59","author":"Laporte","year":"1992","journal-title":"Eur. J. Oper. Res."},{"key":"2020111609500354800_ref19","doi-asserted-by":"crossref","first-page":"2017","DOI":"10.14778\/2733085.2733106","article-title":"Large scale real-time ridesharing with service guarantee on road networks","volume":"7","author":"Huang","year":"2014","journal-title":"Proc. VLDB Endowment"},{"key":"2020111609500354800_ref20","doi-asserted-by":"crossref","first-page":"462","DOI":"10.1073\/pnas.1611675114","article-title":"On-demand high-capacity ride-sharing via dynamic trip-vehicle assignment","volume":"114","author":"Alonsomora","year":"2017","journal-title":"Proc. Nat. Acad. Sci."},{"key":"2020111609500354800_ref21","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1145\/2792838.2800177","article-title":"Recommending fair payments for large scale social ridesharing","author":"Bistaffa","year":"2015","journal-title":"Proceedings of the 9th ACM Conference on Recommender Systems"},{"key":"2020111609500354800_ref22","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1007\/s10479-007-0170-8","article-title":"The dial-a-ride problem: Models and algorithms","volume":"153","author":"Cordeau","year":"2007","journal-title":"Ann. Oper. Res."},{"key":"2020111609500354800_ref23","doi-asserted-by":"crossref","first-page":"1450","DOI":"10.1016\/j.trb.2011.05.017","article-title":"Dynamic ride-sharing: A simulation study in metro Atlanta","volume":"45","author":"Agatz","year":"2011","journal-title":"Transport. Res. B"},{"key":"2020111609500354800_ref24","article-title":"A proposed methodology for estimating rideshare viability within an organization, applied to the MIT community.","volume-title":"TRB Annual Meeting Procediings","author":"Amey","year":"2011,"},{"key":"2020111609500354800_ref25","first-page":"266","article-title":"A mechanism for dynamic ride sharing based on parallel auctions","volume-title":"In International Joint Conference on Artificial Intelligence","author":"Kleiner","year":"2011"},{"key":"2020111609500354800_ref26","first-page":"165","article-title":"Smize: A spontaneous ride-sharing system for individual urban transit","volume-title":"Multiagent System Technologies, German Conference, Mates 2009, Hamburg, Germany, September 9\u201311, 2009 Proc.","author":"Xing","year":"2009"},{"key":"2020111609500354800_ref27","doi-asserted-by":"crossref","first-page":"899","DOI":"10.1080\/13658810600816664","article-title":"Ad hoc shared-ride trip planning by mobile geosensor networks","volume":"20","author":"Nittel","year":"2006","journal-title":"Int. J. Geogr. Inf. Sci."},{"key":"2020111609500354800_ref28","doi-asserted-by":"crossref","first-page":"2263","DOI":"10.1016\/S0305-0548(03)00186-2","article-title":"A distributed geographic information system for the daily car pooling problem","volume":"31","author":"Calvo","year":"2004","journal-title":"Comput. Oper. Res."}],"container-title":["The Computer Journal"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/academic.oup.com\/comjnl\/article-pdf\/63\/11\/1607\/34315033\/bxz075.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"http:\/\/academic.oup.com\/comjnl\/article-pdf\/63\/11\/1607\/34315033\/bxz075.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,1,27]],"date-time":"2021-01-27T10:06:32Z","timestamp":1611741992000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/comjnl\/article\/63\/11\/1607\/5628026"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,11,22]]},"references-count":28,"journal-issue":{"issue":"11","published-online":{"date-parts":[[2019,11,22]]},"published-print":{"date-parts":[[2020,11,19]]}},"URL":"https:\/\/doi.org\/10.1093\/comjnl\/bxz075","relation":{},"ISSN":["0010-4620","1460-2067"],"issn-type":[{"type":"print","value":"0010-4620"},{"type":"electronic","value":"1460-2067"}],"subject":[],"published-other":{"date-parts":[[2020,11]]},"published":{"date-parts":[[2019,11,22]]}}}