基于细节层次模型的公共自行车调度方法

胡正华; 周继彪; 周涵林; 张敏捷

doi:10.3963/j.jssn.1674-4861.2022.04.016

基于细节层次模型的公共自行车调度方法

doi: 10.3963/j.jssn.1674-4861.2022.04.016

胡正华^{1, 2,},
周继彪^{1, 3, ,},
周涵林¹,
张敏捷¹

1.
宁波工程学院建筑与交通工程学院浙江宁波 315211
2.
浙江大学信息与电子工程学院杭州 310063
3.
同济大学交通运输工程学院上海 201804

基金项目:

国家自然科学基金项目 52002282

浙江省自然科学基金项目 LQ18D010008

浙江省哲学社会科学规划课题项目 21NDJC163YB

浙江省哲学社会科学规划课题项目 22NDQN279YB

详细信息

作者简介:
胡正华（1986—），博士. 研究方向：智能交通系统. E-mail：huzhenghua@zju.edu.cn

通讯作者:
周继彪（1986—），博士，副教授. 研究方向：交通运输规划与管理. E-mail：zhoujibiao@tongji.edu.cn

中图分类号: U491.1
计量
- 文章访问数: 1036
- HTML全文浏览量: 443
- PDF下载量: 22
- 被引次数: 0
出版历程
- 收稿日期: 2021-12-15
- 网络出版日期: 2022-09-17

A Dispatch Strategy for Shared Bicycles Based on a Levels-of-Detail Model

HU Zhenghua^{1, 2
,},
ZHOU Jibiao^{1, 3
, ,},
ZHOU Hanlin¹,
ZHANG Minjie¹

1.
School of Civil and Transportation Engineering, Ningbo University of Technology, Ningbo 315211, Zhejiang, China
2.
College of Information Science & Electronic Engineering, Zhejiang University, Hangzhou 310027, China
3.
School of Transportation Engineering, Tongji University, Shanghai 201804, China

摘要

摘要: 公共自行车系统作为城市公共交通的重要组成部分，对于缓解城市交通拥堵和建设低碳、环保的出行体系起到了积极的作用。然而，由于公共自行车系统的借还车需求在时间和空间分布上存在不均衡性，在使用公共自行车时，经常遇到“借车难”或者“还车难”的问题，使得出行者不得不放弃使用公共自行车出行。为了有效地提升出行者借还公共自行车的成功率，研究了1种基于细节层次模型的自行车调度方法。基于公共自行车站点之间的相似度，采用谱聚类算法对站点进行层次划分，形成基于空间范围（即公共自行车站点所占据的地理空间区域）的站点簇；在每个划分层级上统计不同簇之间的自行车借/还需求，结合遗传算法对调度车辆的运输路径进行求解；将不同层级上的调度方案叠加，形成1种调度粒度由粗到细的自行车调度方案。通过对比实验证明：基于细节层次模型的公共自行车调度方法较传统方法减少了42.70%的调度路径，进而减少了相应的调度时间。
- 交通工程 /
- 调度策略 /
- 公共自行车 /
- 层次调度
Abstract: As an important part of urban public transportation, the shared bicycles have played a positive role in relieving traffic congestion and promoting a low-carbon, environmentally friendly travel system. However, people often encounter difficulties with borrowing or returning a bicycle when tending to use shared bicycles, due to the uneven temporal and spatial distributions of the demands of borrowing and returning bicycles. Such difficulties sometimes make travelers give up using shared bicycles. In order to effectively improve the success rate of borrowing and returning bicycles, a dispatch strategy based on a levels-of-detail model is proposed. First, based on the similarity among bicycles stations, a spectral clustering algorithm is adopted to hierarchically classify the areas where stations locate. Thus, station clusters are formed based on station scopes (i.e., the geographic spatial area of a public station occupied). Second, the total demand of borrowing/returning bicycles among different station clusters at each level is counted, and a genetic algorithm is adopted to solve the transport route for dispatch vehicles. Third, the dispatch strategies at each level are overlaid to form a dispatch strategy for shared bicycles with the granularity from coarse to fine. Compared with the traditional methods, the proposed strategy reduces the total length of dispatch path by 42.70%, and therefore the corresponding dispatch time can also be shortened accordingly.
- traffic engineering /
- dispatch strategy /
- shared bicycles /
- levels of details

HTML全文

图 1 基于细节层次模型的公共自行车调度算法流程图

Figure 1. The flow chart of the rebalancing algorithm based on the hierarchical scheme for bike-sharing system

下载: 全尺寸图片幻灯片

图 2 宁波市公共自行车站点的层级划分示意图

Figure 2. Sketch map of the hierarchical division of the stations from bike-sharing system in Ningbo

下载: 全尺寸图片幻灯片

图 3 调度方案的示意图

Figure 3. Sketch map of the rebalancing scheme

下载: 全尺寸图片幻灯片

图 4 传统调度方案与本文调度方案对比图

Figure 4. Comparison of the traditional rebalancing scheme and the one proposed in the article

下载: 全尺寸图片幻灯片

表 1 早高峰时各调度单元的自行车需求与相应的时间窗

Table 1. Demand and the corresponding time window of each rebalancing unit during morning peak

区域编号	锁桩数	需求量/辆	时间窗
C1	1 406	-141	08：20—09：20
C3	1 711	171	07：48—08：48
C11	341	-34	08：16—09：16
C12	490	-50	08：14—09：14
C22	507	-51	08：23—09：23
C31	672	68	07：51—08：51
C32	635	64	07：43—08：43
C111	90	-10	07：51—08：51
C112	136	-14	07：45—08：45
C113	115	12	07：38—08：38
C122	160	17	07：48—08：48
C123	155	-16	07：46—08：46
C132	170	18	08：05—09：05
C133	205	-21	08：08—09：08
C211	210	-22	08：14—09：14
C212	265	27	07：49—08：49
C213	250	-26	07：56—08：56
C221	180	19	07：41—08：41
C222	207	21	07：52—08：52
C223	120	-13	07：51—08：51
C231	155	16	08：21—09：21
C233	60	7	08：30—09：30
C311	225	23	08：09—09：09
C312	268	27	07：40—08：40
C313	179	18	08：18—09：18
C321	125	13	07：47—08：47
C322	195	20	07：37—08：37
C323	315	32	07：46—08：46
C331	130	-14	07：55—08：55
C332	150	16	07：38—08：38
C333	124	0	07：51—08：51

下载: 导出CSV

表 2 不同层级上各调度单元之间的调度方案

Table 2. Rebalancing scheme between each unit on different levels

调度区域	调度路径	调度的自行车数/辆	累计行驶距离/m
原始站点区域	C0→C1→C3→C0	312	5 799.84
1	C1→C12→C11→C1	84	3 886.81
11	C11→C113→C112→C111→C11	36	2 858.69
12	C12→C123→C122→C12	33	1 739.27
13	C13→C132→C133→C13	39	1 944.85
2	C2→C22→C2	51	1 617.62
21	C21→C212→C213→C211→C21	75	2 729.55
22	C22→C221→C222→C223→C22	53	2 782
23	C23→C231→C233→C23	23	5 055.13
3	C3→C32→C31→C3	132	2 543.63
31	C31→C312→C311→C313→C31	68	1 986.14
32	C32→C322→C323→C321→C32	65	4 133.90
33	C33→C332→C331→C33	30	3 033.95

下载: 导出CSV

表 3 传统调度方法的调度路径长度与调度时间

Table 3. The length of the path and the rebalancing time of the traditional method

调度线路	调度的行驶距离/m	耗费的时间/min
1	6 654.40	27.73
2	3 446.78	14.36
3	12 221.27	50.92
4	7 893.78	32.89
5	3 460.06	14.42
6	5 786.12	24.11
7	3 851.25	16.05
8	1 429.91	5.96
9	1 541.74	6.42
10	4 962.13	20.68
11	2 501.04	10.42
12	8 495.44	35.40
13	7 761.66	32.34
总计	70 005.58	291.70

下载: 导出CSV

表 4 基于层次调度方法的路径长度与调度时间

Table 4. The length of the path and the rebalancing time of the hierarchical method

调度区域	调度的行驶距离/m	耗费的时间/min
最上层调度区域	5 799.84	24.17
1	3 886.81	16.20
11	2 858.69	11.91
12	1 739.27	7.25
13	1 944.85	8.10
2	1 617.62	6.74
21	2 729.55	11.37
22	2 782	11.59
23	5 055.13	21.06
3	2 543.63	10.60
31	1 986.14	8.28
32	4 133.90	17.22
33	3 033.95	12.64
总计	40 111.38	167.13

下载: 导出CSV

参考文献(21)

[1]	周继彪, 王群燕, 张敏捷, 等. 7种因素对电动自行车忍耐时间的实证研究[J]. 交通运输系统工程与信息, 2017, 17(5): 242-249. https://www.cnki.com.cn/Article/CJFDTOTAL-YSXT201705035.htm ZHOUJ B, WANGQ Y, ZHANGM J, et al. Assessing factors related to E-bike crash and E-bike license plate use[J]. Journal of Transportation Systems Engineering and Information Technology, 2017, 17(5): 242-249. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-YSXT201705035.htm
[2]	张昕明, 弓棣, 谢秉磊, 等. 计划行为理论视角下基于出行行为的公交防疫策略影响效果研究[J]. 交通信息与安全, 2021, 39(6): 117-125. doi: 10.3963/j.jssn.1674-4861.2021.06.014 ZHANGX M, GONG D, XIE B L, et al. A study of the effectiveness of epidemic prevention policies on public transit usage based on the theory of planned behaviors[J]. Journal of Transport Information and Safety, 2021, 39(6): 117-125. (in Chinese) doi: 10.3963/j.jssn.1674-4861.2021.06.014
[3]	万明, 吴倩, 严利鑫, 等. 道路交通安全研究的现状与热点分析[J]. 交通信息与安全, 2022, 40(2): 11-21+37. doi: 10.3963/j.jssn.1674-4861.2022.02.002 WAN M, WU Q, YAN L X, et al. A review of current situation and hot spots of road safety research[J]. Journal of Transport Information and Safety, 2022, 40(2): 11-21+37. (in Chinese) doi: 10.3963/j.jssn.1674-4861.2022.02.002
[4]	周传钰. 共享单车投放量测算和调度方法研究[D]. 北京: 北京交通大学, 2018. ZHOUC Y. Study on demand measurement and scheduling method of bike sharing system[D]. Beijing: Beijing Jiaotong University, 2018. (in Chinese)
[5]	聂帅钧. 共享电单车的政府监管研究[J]. 重庆大学学报(社会科学版), 2019, 25(1): 162-177. https://www.cnki.com.cn/Article/CJFDTOTAL-CDSK201901013.htm NIE S J. The research on government regulation of electric bicycle sharing in China[J]. Journal of Chongqing University (Social Science Edition), 2019, 25(1): 162-177. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-CDSK201901013.htm
[6]	徐笑梅. 公共自行车使用特性与分层调度研究[D]. 南京: 东南大学, 2019. XU X M. Usage patterns and hierarchical scheduling of a bicycle-sharing system[D]. Nanjing: Southeast University, 2019. (in Chinese)
[7]	ZHU Y, DIAO M. Understanding the spatiotemporal patterns of public bicycle usage: A case study of Hangzhou, China[J]. International Journal of Sustainable Transportation, 2020, 14 (3): 163-176. doi: 10.1080/15568318.2018.1538400
[8]	张敏捷, 周继彪, 董升, 等. 城市公共自行车准动态调度方法[J]. 交通运输系统工程与信息, 2019, 19(5): 185-192. https://www.cnki.com.cn/Article/CJFDTOTAL-YSXT201905026.htm ZHANGM J, ZHOUJ B, DONG S, et al. Quasi-dynamic balancing method for urban public bike-sharing system[J]. Journal of Transportation Systems Engineering and Information Technology, 2019, 19(5): 185-192. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-YSXT201905026.htm
[9]	YANG C, Gidófalvi G. Mining and visual exploration of closed contiguous sequential patterns in trajectories[J]. International Journal of Geographical Information Science, 2018, 32(7): 1282-1304.
[10]	HAIDER Z, NIKOLAEV A, KANG J E, et al. Inventory rebalancing through pricing in public bike sharing systems[J]. European Journal of Operational Research, 2018, 270(1): 103-117. doi: 10.1016/j.ejor.2018.02.053
[11]	KADRI A A, KACEM I, LABADI K. A branch-and-bound algorithm for solving the static rebalancing problem in bicycle-sharing systems[J]. Computers&Industrial Engineering, 2016, 95: 41-52.
[12]	PAL A, ZHANG Y. Free-floating bike sharing: Solving real-life large-scale static rebalancing problems[J]. Transportation Research Part C: Emerging Technologies, 2017, 80: 92-116. doi: 10.1016/j.trc.2017.03.016
[13]	CRUZ F, SUBRAMANIAN A, BRUCK B P, et al. A heuristic algorithm for a single vehicle static bike sharing rebalancing problem[J]. Computers & Operations Research, 2017, 79: 19-33.
[14]	REN Y, MENG L, ZHAO F, et al. An improved general variable neighborhood search for a static bike-sharing rebalancing problem considering the depot inventory[J]. Expert Systems with Applications, 2020, 160: 113752. doi: 10.1016/j.eswa.2020.113752
[15]	CHIARIOTTI F, PIELLI C, ZANELLA A, et al. A dynamic approach to rebalancing bike-sharing systems[J]. Sensors, 2018, 18(2): 512. doi: 10.3390/s18020512
[16]	HU R, ZHANG Z, MA X, et al. Dynamic rebalancing optimization for bike-sharing system using priority-based MOEA/ D algorithm[J]. IEEE Access, 2021(9): 27067-27084.
[17]	周素静, 徐宝林, 刘冬华, 等. 基于聚类分析法的公共自行车服务系统研究[J]. 郑州铁路职业技术学院学报, 2015, 27 (1): 28-31,38. https://www.cnki.com.cn/Article/CJFDTOTAL-ZTZY201501008.htm ZHOUS J, XUB L, LIUD H, et al. The research of bike sharing system based on cluster analysis[J]. Journal of Zhengzhou Railway Vocational and technical College, 2015, 27 (1): 28-31,38. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-ZTZY201501008.htm
[18]	王超. 城市公共自行车分区调度模型研究[D]. 杭州: 杭州电子科技大学, 2016. WANG C. Research on partition scheduling model of public bicycle system[D]. Hangzhou: Hangzhou Dianzi University, 2016. (in Chinese)
[19]	CLARK J H. Hierarchical geometric models for visible surface algorithms[J]. Communications of the ACM, 1976, 19 (10): 547-554. doi: 10.1145/360349.360354
[20]	MURTAGH F, CONTRERAS P. Algorithms for hierarchical clustering: An overview, Ⅱ[J]. Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery, 2017, 7(6): e1219.
[21]	REDDY M, MAKARA V, SATISH R. Divisive hierarchical clustering with k-means and agglomerative hierarchical clustering[J]. International Journal of Computer Science Trends and Technology(IJCST), 2017, 5(5): 5-11.