Journal of Jilin University(Engineering and Technology Edition) ›› 2022, Vol. 52 ›› Issue (3): 564-571.doi: 10.13229/j.cnki.jdxbgxb20200843

Previous Articles    

Ride⁃sharing matching model and algorithm of online car⁃hailing under condition of uncertain destination

Hong-fei JIA(),Zi-han SHAO,Li-li YANG()   

  1. College of Transportation，Jilin University，Changchun 130022，China
  • Received:2020-11-03 Online:2022-03-01 Published:2022-03-08
  • Contact: Li-li YANG E-mail:jiahf@jlu.edu.cn;yanglili@jlu.edu.cn

RICH HTML

 8   

PDF (PC)

187

Abstract:

To improve the situation of high demand and low occupancy rate of taxis， the study focuses on the problem of online ride-sharing. Considering the turnover of passengers， vehicle transportation mileage， travel time， and travel cost， a mathematical model of single-vehicle carpooling matching was established. Based on the principle of fairness and considering the bilateral interests of drivers and passengers， a rate calculation method was proposed. Passenger clustering is conducted with the path fitting degree as its basis. Based on the Dijkstra algorithm， the shortest path algorithm by section with obligatory nodes was proposed. Simulation results show that， compared with the traditional taxi operation mode， online taxi-sharing has a significant effect on improving transportation efficiency and reducing transportation cost.

Key words: engineering of communication and transportation system, urban traffic, ride-sharing, path fitting degree, path optimization

CLC Number: 

  • U492.2

Fig.1

Fitting between passenger′s origin-destination and vehicle route"

Fig.2

Schematic diagram of orderly adjustment of necessary nodes"

Fig.3

Algorithm flow chart"

Fig.4

Road system of study area"

Fig.5

Location of vehicle and passengers"

Table 1

Information of passenger’s requirements"

乘客编号起点及时间窗终点及时间窗
A4，［5，10］48，［29，44］
B10，［30，35］5，［43，53］
C14，［15，20］50，［36，46］
D19，［10，35］39，［31，46］
E23，［20，25］5，［37，52］
F33，［20，30］1，［43，58］
G38，［25，35］51，［47，52］
H44，［15，20］7，［39，54］
I49，［15，20］10，［38，48］
J52，［10，15］13，［32，47］

Table 2

Degree of path fitting"

乘客编号路径拟合度乘客编号路径拟合度
A1.000F-0.079
B0.024G0.225
C0.116H-0.177
D0.353I-0.082
E-0.082J-0.028

Fig.6

Carpooling route"

Fig.7

Complete carpooling route"

Table 3

Comparison between traditional traveldistance and after carpooling"

乘客编号合乘里程/km非合乘里程/km
乘客周转量/（人·km）36.530.7
A9.17.2
D2.32.3
G6.74.5
I7.07.0
F4.44.4
B7.05.3

Table 4

Comparison between traditional travelcost and after carpooling"

乘客编号合乘费用/元非合乘费用/元
总计62.595.7
A11.322.5
D8.08.0
G9.117.2
I12.517.9
F8.012.2
B13.617.9

Fig.8

Effect of passenger clustering"

1 Herbawi W, Weber M. The ride matching problem with time windows in dynamic ridesharing: A model and a genetic algorithm[C]∥Evolutionary Computation, Brisbane, QLD, Australia, 2012: 1-8.
2 Naor M. On fairness in the carpool problem[J]. Journal of Algorithms, 2005, 55(1): 93-98.
3 Lee K T, Wu P J, Wang S H. The planning and design of taxi pooling on feeder system[C]∥2004 IEEE International Conference on Networking, Sensing and Control, Taipei, Taiwan, China, 2004: 376-381.
4 Ma S, Zheng Y, Wolfson O. T-share: a large-scale dynamic taxi ridesharing service[C]∥2013 IEEE 29th International Conference on Data Engineering, Brisbane, QLD, Australia, 2013: 410-421.
5 Lauri H. An adaptive insertion algorithm for the single-vehicle dial-a-ride problem with narrow time windows[J]. European Journal of Operational Research, 2011, 209(1): 11-22.
6 Alonso-Mora J, Samaranayake S, Wallar A, et al. On-demand high-capacity ride-sharing via dynamic trip-vehicle assignment[J]. Proceedings of the National Academy of Sciences of the United States of America, 2017, 114(3): 462-467.
7 沈弼龙, 赵颖, 黄艳, 等. 大数据背景下动态共乘的研究进展[J]. 计算机研究与发展, 2017, 54(1): 34-43.
Shen Bi-long, Zhao Ying, Huang Yan, et al. Survey on dynamic ride sharing in big data era[J]. Journal of Computer Research and Development, 2017, 54(1): 34-43.
8 覃运梅, 石琴. 出租车合乘模式的探讨[J]. 合肥工业大学学报: 自然科学版, 2006, 29(1): 77-79, 101.
Qin Yun-mei, Shi Qin. Research on the combined-taxi mode[J]. Journal of Hefei University of technology (Natural Science), 2006, 29(1): 77-79, 101.
9 吴玥琳, 袁振洲, 陈秋芳, 等. 考虑轨迹相似度的综合客运枢纽出租车合乘方法研究[J]. 交通运输系统工程与信息, 2020, 20(2): 188-195.
Wu Yue-lin, Yuan Zhen-zhou, Chen Qiu-fang, et al. Taxi pooling method of urban integrated passenger transport hub with trajectory similarity[J]. Journal of Transportation Systems Engineering and Information Technology, 2020, 20(2): 188-195.
10 宋超超, 王洪国, 邵增珍, 等. 一种求解多车辆合乘匹配问题的适应性算法[J]. 计算机科学, 2013, 40(2): 222-228.
Song Chao-chao, Wang Hong-guo, Shao Zeng-zhen, et al. Adaptive algorithm for MRMP[J]. Computer Science, 2013, 40(2): 222-228.
11 唐方慧. 出租车合乘路径选择及费率优化问题研究[D]. 兰州:兰州交通大学交通运输学院, 2016.
Tang Fang-hui. The research on the optimization of taxi ride-sharing route and rate[D]. Lanzhou: School of Traffic and Transportation, Lanzhou Jiaotong University, 2016.
12 卢雨婷, 李登峰, 胡勋锋. 基于破产模型的出租车合乘定价方法[J]. 交通运输系统工程与信息, 2017, 17(4): 7-12.
Lu Yu-ting, Li Deng-feng, Hu Xun-feng. A pricing method for ride-sharing taxi based on the bankruptcy model[J]. Journal of Transportation Systems Engineering and Information Technology, 2017, 17(4): 7-12.
13 鹿应荣, 杨印生, 吕锋. 基于模糊聚类分析的车辆优化调度[J]. 吉林大学学报: 工学版, 2006, 36(): 147-151.
Lu Ying-rong, Yang Yin-sheng, Lyu Feng. Optimal vehicle routing problem based on fuzzy clustering analysis[J] Journal of Jilin University (Engineering and Technology Edition), 2006, 36(Sup.2): 147-151.
14 赵宏伟, 刘宇琦, 董立岩, 等.智能交通混合动态路径优化算法[J].吉林大学学报:工学版, 2018, 48(4): 1214-1223.
Zhao Hong-wei, Liu Yu-qi, Dong Li-yan, Wang Yu, Liu Pei. Dynamic route optimization algorithm based on hybrid in ITS[J]. Journal of Jilin University (Engineering and Technology Edition), 2018, 48(4): 1214-1223.
15 高德地图. 2019年Q3中国主要城市交通分析报告[Z].
[1] Tian-jun FENG,Xue-lu SUN,Jia-sheng HUANG,Xiu-juan TIAN,Xian-min SONG. Two-phase signal intersection delay based on three crossing modes [J]. Journal of Jilin University(Engineering and Technology Edition), 2022, 52(3): 550-556.
[2] Xian-tong LI,Wei QUAN,Hua WANG,Peng-cheng SUN,Peng-jin AN,Yong-xing MAN. Route travel time prediction on deep learning model through spatiotemporal features [J]. Journal of Jilin University(Engineering and Technology Edition), 2022, 52(3): 557-563.
[3] Shi-jun YANG,Yu-long PEI,Heng-yan PAN,Guo-zhu CHENG,Wen-hui ZHANG. Characteristics analysising and prediction of dwelling time of urban bus [J]. Journal of Jilin University(Engineering and Technology Edition), 2021, 51(6): 2031-2039.
[4] Yan-feng JIA,Da-yi QU,Lu LIN,Rong-han YAO,Xiao-long MA. Coordinated speed control of connected mixed traffic flow based on trajectory [J]. Journal of Jilin University(Engineering and Technology Edition), 2021, 51(6): 2051-2060.
[5] Yan MAO,Kai CHENG. Telescoping path optimization of a single-cylinder pin⁃type multi⁃section boom based on Hopfield neural network [J]. Journal of Jilin University(Engineering and Technology Edition), 2020, 50(1): 53-65.
[6] Chang-fu ZONG,Long WEN,Lei HE. Object detection based on Euclidean clustering algorithm with 3D laser scanner [J]. Journal of Jilin University(Engineering and Technology Edition), 2020, 50(1): 107-113.
[7] Liang JIANG,Yi HE. Risky driving behavior and influencing factors analysis for electric two⁃wheeler [J]. Journal of Jilin University(Engineering and Technology Edition), 2019, 49(4): 1107-1113.
[8] Xiao⁃qin LUO,Dian⁃hai WANG,Sheng JIN. Traffic signal actuated control at isolated intersections for heterogeneous traffic [J]. Journal of Jilin University(Engineering and Technology Edition), 2019, 49(3): 695-704.
[9] Zhi⁃hui LI,Tao ZHONG,Yong⁃hua ZHAO,Yong⁃li HU,Hai⁃tao LI,Jing⁃wei ZHAO. Pedestrian tracking algorithm for autonomous driving [J]. Journal of Jilin University(Engineering and Technology Edition), 2019, 49(3): 680-687.
[10] Lei CHEN,Jiang⁃feng WANG,Yuan⁃li GU,Xue⁃dong YAN. Multi⁃source traffic data fusion algorithm based onmind evolutionary algorithm optimization [J]. Journal of Jilin University(Engineering and Technology Edition), 2019, 49(3): 705-713.
[11] QU Da-yi,YANG Jing-ru,BING Qi-chun,WANG Wu-lin,ZHOU Jing-chun. Arterial traffic offset optimization based on queue characteristics at adjacent intersections [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(6): 1685-1693.
[12] LI Zhi-hui, HU Yong-li, ZHAO Yong-hua, MA Jia-lei, LI Hai-tao, ZHONG Tao, YANG Shao-hui. Locating moving pedestrian from running vehicle [J]. 吉林大学学报(工学版), 2018, 48(3): 694-703.
[13] SUN Zong-yuan, FANG Shou-en. Hierarchical clustering algorithm of moving vehicle trajectories in entrances and exits freeway [J]. 吉林大学学报(工学版), 2017, 47(6): 1696-1702.
[14] ZHANG Zhe, JIA Li-min, QIN Yong, YUN Ting. Equalization-based feedback control model of pedestrian counter flow [J]. 吉林大学学报(工学版), 2017, 47(6): 1728-1737.
[15] SHAO Sai, BI Jun, GUAN Wei. Electric vehicle routing problem with charging and dynamic customer demands [J]. 吉林大学学报(工学版), 2017, 47(6): 1688-1695.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
Copyright © Journal of Jilin University(Engineering and Technology Edition), All Rights Reserved.
Tel: +86-431-85095297　Fax: +86-431-85094074　E-mail: xbgxb@jlu.edu.cn
Powered by Beijing Magtech Co. Ltd