期刊菜单

Optimization Model of Shared Parking Space Allocation Based on Genetic Algorithm Online
DOI: 10.12677/OJTT.2022.114038, PDF, HTML, XML, 下载: 76  浏览: 120

Abstract: In the context of the high popularity of private cars and the increasing number of cars, this paper studies the problem of parking difficulties in shared parking spaces. Adopting the method of reservation in advance, all parking demands within a certain period of time will be allocated globally according to the existing shared parking spaces. Taking the minimum distance between the starting position of the parking space and the demand originator and the destination location as the objective function, considering the time window constraint of the passenger and the parking space, the walking distance constraint, and the rationality constraint of the parking space, a shared parking space allocation is optimized model. And based on the idea of genetic algorithm, it researches and designs the corresponding solving algorithm. According to the research results, the shared parking space allocation optimization model can achieve a reasonable allocation of parking spaces.

1. 引言

2. 问题的描述

Figure 1. Matching process of shared parking spaces

Table 1. Model parameters and variables

3. 共享停车位优化模型

3.1. 目标函数

$\mathrm{min}{Z}_{\text{1}}=\underset{x\in O}{\sum }\underset{j\in D}{\sum }\underset{m\in M}{\sum }{x}_{ij}{y}_{jm}\cdot {d}_{jm}$ (1)

${x}_{ij}=\left\{\begin{array}{l}1\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}i\text{ }\text{ }点的客户到\text{ }\text{ }j\text{ }\text{ }停车位停车\\ 0\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}否则\end{array}$ ${y}_{jm}=\left\{\begin{array}{l}1\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}j\text{ }\text{ }停车位的客户终点位置为\text{ }\text{ }m\\ 0\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}否则\end{array}$

3.2. 共享停车位的基本约束

$\text{0}<\underset{j\in D}{\sum }{x}_{ij}\le \text{1}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\forall i\in O$ (2)

$\underset{i\in O}{\sum }{x}_{ij}=\underset{m\in M}{\sum }{y}_{jm}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\forall j\in D$ (3)

3.3. 客户步行距离约束

${y}_{jm}\cdot {d}_{jm}\le {D}_{0}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\forall j\in D,\forall m\in M$ (4)

3.4. 时间窗约束

${T}_{j1}-B\le Arr{T}_{ij}\cdot {x}_{ij}-B\cdot {x}_{ij}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\forall i\in O,\forall j\in D$ (5)

${T}_{j\text{2}}-B\cdot {x}_{ij}\le Dep{T}_{ij}\cdot {x}_{ij}-B\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\forall i\in O,\forall j\in D$ (6)

$\left(Dep{T}_{pj}-Arr{T}_{kj}\right)\cdot \left(Arr{T}_{pj}-Dep{T}_{kj}\right)\cdot {x}_{pj}\cdot {x}_{kj}\ge 0\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\forall p,k\in O,p\ne k,\forall j\in D$ (7)

${t}_{ij}=\frac{{d}_{ij}}{{v}_{i}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\forall i\in O,\forall j\in D$ (8)

$Arr{T}_{ij}={T}_{i}+{t}_{ij}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\forall i\in O,\forall j\in D$ (9)

4. 基于遗传算法的模型优化求解

4.1. 信息预处理

4.2. 遗传算法设计方案

${f}_{i}=\frac{{Z}^{\prime }}{{Z}_{i}}$ (10)

${p}_{i}=\frac{{f}_{i}}{\sum f}$ (11)

Figure 3. Optimization model solution algorithm flow

5. 案例分析

Table 2. On-street parking lot around Xi’an Road commercial district

Table 3. The construction of parking lots around Xi’an Road commercial district

Figure 4. Distribution of parking spaces in surrounding houses and on the road

Figure 5. User needs and surrounding parking space information

Table 4. Passenger information

Table 5. Parking time window information

Table 6. List of genetic algorithm parameter settings

Figure 6. Iteration curve

Table 7. Genetic algorithm solution

6. 结论

NOTES

*通讯作者。

 [1] 关于印发青岛市机动车停车场建设和管理暂行办法通知[EB/OL]. 青岛政务网. http://m.qingdao.gov.cn/n172/n68422/n68424/n31280468/n31280470/160104154824993638.html, 2022-09-10. [2] 促进本市停车资源共享利用的指导意见[EB/OL]. 上海本地宝. http://sh.bendibao.com/news/2016923/169653.shtm, 2016-09-23. [3] 沈阳首个政府部门共享停车场推出[EB/OL]. 人民网. http://finance.people.com.cn/n1/2018/0619/c1004-30066897.html, 2018-06-19. [4] Kim, O.T., Tri, N.D., Nguyen, V., Tran, N.H. and Hong, C.S. (2015) A Shared Parking Model in Vehicular Network Using Fog and Cloud Environment. 2015 17th Asia-Pacific Network Operations and Management Symposium (APNOMS), Busan, Korea (South), 19-21 August 2015, 321-326. https://doi.org/10.1109/APNOMS.2015.7275447 [5] Shao, C., Yang, H., Zhang, Y. and Ye, J.T. (2016) A Simple Reservation and Allocation Model of Shared Parking Lots. Transportation Research Part C: Emerging Technologies, 71, 303-312. https://doi.org/10.1016/j.trc.2016.08.010 [6] Xu, S.X., Cheng, M., Kong, X.T. Yang, H. and Huang, G.Q. (2016) Private Parking Slot Sharing. Transportation Research Part B: Methodological, 93, 596-617. https://doi.org/10.1016/j.trb.2016.08.017 [7] Yang, B., Yuan, Z., Yang, Y., et al. (2017) The Study on Allocation Model of Shared Parking Slots in Multi-parking Lots. International Conference on Mechatronics, Bali, Indonesia, 1-3 April 2017, 457-465. https://doi.org/10.2991/icmmcce-17.2017.87 [8] Cai, Y., Chen, J., Zhang, C. and Wang, B. (2018) A Parking Space Allocation Method to Make a Shared Parking Strategy for Appertaining Parking Lots of Public Buildings. Sustainability, 11, Article No. 1-20. https://doi.org/10.3390/su11010120 [9] Xiao, H., Xu, M. and Gao, Z. (2018) Shared Parking Problem: A Novel Truthful Double Auction Mechanism Approach. Transportation Research Part B: Methodological, 109, 40-69. https://doi.org/10.1016/j.trb.2018.01.008 [10] 朱成娟, 贾斌, 韩凌辉. 基于Stackelberg博弈的停车位分配与定价[J]. 交通运输系统工程与信息, 2015, 15(3): 19-24. [11] 林小围, 周晶, 卢珂. 私家车位共享系统的车位动态预约与分配[J]. 系统工程理论与实践, 2018, 38(11): 2907-2917. [12] 林小围, 周晶, 卢珂, 徐媛. 基于合作博弈的停车位分配模型[J]. 系统管理学报, 2019, 28(1): 62-66, 85. [13] 卢凯, 林茂伟, 邓兴栋, 徐广辉, 徐建闽. 停车总成本最小的停车位动态分配与诱导模型[J]. 华南理工大学学报(自然科学版), 2018, 46(9): 82-91, 98. [14] 陈峻, 王斌, 张楚. 基于时空容量的配建停车资源共享匹配方法[J]. 中国公路学报, 2018, 31(3): 96-104,115. [15] 路扬, 何胜学, 王冬冬, 等. 基于时间窗与优先级的网络共享停车匹配模型[J]. 武汉理工大学学报(交通科学与工程版), 2019, 43(2): 306-310.