基于时间聚类推理的立体车库车位分配策略研究

马尚鹏，李建国，杨波; MA Shangpeng; LI Jianguo; YANG Bo

网刊加载中。。。

使用Chrome浏览器效果最佳，继续浏览，你可能不会看到最佳的展示效果，

确定继续浏览么?

复制成功，请在其他浏览器进行阅读

基于时间聚类推理的立体车库车位分配策略研究 PDF

- ORCID：
马尚鹏 ¹
✉
- ORCID：
李建国 ^1,2
- ORCID：
杨波 ¹

1. 兰州交通大学，自动化与电气工程学院兰州 730070 ； 2. 兰州交通大学，四电BIM工程与智能应用铁路行业重点实验室兰州 730070

中图分类号： U491.7

最近更新：2024-08-29

DOI：10.11835/j.issn.1000.582X.2024.08.005

摘要

采用立体车库车辆到达-离去时间数据，通过k-means聚类方法依据不同时段存取车到达频率对车辆进行类别划分，以立方聚类标准为评价指标对划分可信度进行评估。以车辆到达-离去时间划分推理结果及I/O至待存取车位的设备总服务时间与停留时间长短关系，建立立体车库车位分区分配数学模型。定义顾客平均等待时间为立体车库效率评价指标，仿真对比分析就近分配与本文设计聚类推理分区分配的效率指标。仿真结果表明：本文设计的分配策略相较于就近分配策略能有效缩短顾客等待时间，表现为顾客等待时间减少9.5%。研究结果为此类车库车位分配过程提供参考，为提高车库运行效率提供决策支持。

关键词

交通工程; 立体车库; k-means聚类; 车位分配; 顾客等待时间; 到达-离去时间

自动化立体车库能有效解决城市停车难问题，其中，平面移动式立体车库是一种重要的智能立体停车设备。该类型车库通过轨道引导小车（rail guide vehicle，RGV）和升降机配合实现不同层之间的车辆存取。该类型车库在实际运行过程中存在不同时间段到达车辆停留时间特性不同而车位分配策略不变的情况，导致顾客存取车等待时间长。设计基于时间特性聚类推理的车位分配策略可有效缩短顾客存取车等待时间，提高立体车库运行效率和顾客满意度。

立体车库作为立体仓储系统的特殊形式，库内存取车过程可考虑为单个货物存取过程。国内外学者对提高立体仓储系统效率做了大量研究。王小农等^[

1]介绍基于多色集合理论和果蝇算法模型，设计立体车库的分配模型，分析不同指标下车位分区原则，证明了基于多色集合理论车位分配的有效性。靳萌等^{[参考文献 2

百度学术}2]考虑物资的不同状态，设计了结合需求频率及相关性的多目标货位分配模型，结合Pareto保持机制提高存储效率。李明等^{[参考文献 3

百度学术}3]设计基于品项相关性的分配方法，以最小化拣货区拣选时间总和为目标建立品项分配模型，采用启发式聚类算法，缩短拣选总时间。杨玮等^{[参考文献 4

百度学术}4]构建以最小化行程时间为目标函数的集成优化数学模型，能在不同订单规模和载具数量下有效缩短作业时间。刘日等^{[参考文献 5

百度学术}5]以降低立体车库系统运行能耗为目标，利用支持向量机（support vector machine, SVM）对车辆停留时间范围进行预测，采用多色集合理论进行车位分区分配。汤洪涛等^{[参考文献 6

百度学术}6]设计基于k-Medoids聚类的粒子群优化算法，考虑动态移库提高仓库拣选效率。李珍萍^{[参考文献 7

百度学术}7]等使用k-means聚类方法划分客户集。Glock等^{[参考文献 8

百度学术}8]提出优先级受限的路径选择与存储分配策略，研究不同存储分配策略对选择路径的影响。Lee等^{[参考文献 9

百度学术}9]提出了立体仓库关联及流量均衡存储分配，分为聚类和分配2个阶段建模，建立兼顾出行效率交通流量均衡的双目标优化模型，较理想解决了交通流拥堵和拣选延迟问题。Zhang等^{[参考文献 10

百度学术}10]引入需求相关性模式（demand correlation pattern， DCP）概念来描述相关性，提出从历史数据中确定DCPs的方法，研究提出的方法在不同环境下的存储策略。Micale等^{[参考文献 11

百度学术}11]设计了不确定环境下基于消去和选择转换树(elimination et choice traduisant la realité tree, ELECTRE-TRI)和基于理想解相似度的订单优先技术(technique for order preferenceby similarity to ideal solution, TOPSIS)的方法，正确处理库位分配过程中的不确定性。Keung等^{[参考文献 12

百度学术}12]提出基于数据驱动的RMFS区域聚类和存储位置分配分类方法。

国内外学者主要考虑：1）仓储系统货位相关性和拣选效率；2）设备运行作业效率；3）不同策略之间的结合与优化。学者从不同角度对设备效率和货位分配进行研究，但在存取车过程中顾客到达-离去时间关系对车位分配策略设计的影响研究较少。本文研究立体车库不同时段车辆到达-离去时间对车位分配的影响，构建立体车库存取车设备运行状态模型。分析立体车库到达时刻与停留时间的规律，判断不同时间段存取车频率与到达-离去时间关系，用k-means聚类方法完成车辆到达-离去的时间划分，建立立体车库车位分区分配模型，有效缩短顾客存取车排队等待时间。

1 立体车库运行状态描述

平面移动式立体车库设备主要包括RGV、升降机Lift、车厅I/O、车位、巷道。以某商用立体车库为研究对象，该立体车库实体模型如图1所示。车库容量为6层×21列×2排，共有252个车位。车库有3个车厅，每个车厅占用3个车位；车库中有3个RGV，其运动方向在巷道中是水平的，实现车辆在立体车库中列与列之间的移动；车库有2台Lift，位于巷道2端，通过Lift实现车辆在层与层之间移动。

图1 立体车库实体模型

Fig. 1 Stereo garage structure model

平面移动式立体车库系统存在2种服务类型：1）顾客存车过程，顾客到达I/O口，系统根据车库可用车位情况分配车位，RGV与Lift配合完成存车；2）顾客取车过程，顾客到达I/O口取车，RGV将待取车辆从存储车位运载至I/O口，完成取车过程。为准确描述立体车库状态转换过程，定义立体车库存取车运行位置、运行状态等参数符号，如表1所示。

表1 位置及运行状态参数符号

Table 1 Position and Running status parameter symbol

位置参数	描述	状态参数	描述	状态参数	描述
POS_RGV	RGV初始位置	L_Empr	Lift空载运行	R_Outl	RGV伸出装载
POS_I/O	I/O位置	R_Empol	RGV空载上Lift	R_Recl	RGV收回装载
(x_s，z_s)	存车车位坐标	R_Empdl	RGV空载下Lift	R_Outul	RGV伸出卸载
(x_r，z_r)	取车车位坐标	L_LoadrRe	Lift满载运行（RGV空载）	R_Recul	RGV收回卸载
(x_R，z_R)	RGV初始位置坐标	L_LoadrRl	Lift满载运行（RGV载车）	R_Loadr	RGV满载运行
(x_I/O，z_I/O)	I/O口坐标	R_Loadol	RGV满载上Lift	R_Empr	RGV空载运行
				R_Loaddl	RGV满载下Lift

顾客到达准备存车时，立体车库控制系统为当前车辆分配存车车位，依据运行状态中I/O位置、存车车位和RGV初始位置之间关系，存车过程设备运行状态分为6种情况，如表2所示。存车服务时间为RGV在I/O处装载车辆至目标车位卸载车辆过程设备的运行时间。

表2 存车过程设备运行状态

Table 2 The running state of the storage equipment

类别	RGV初始位置和I/O关系	车位层与I/O层关系	存车过程运行状态
1	POS_RGV=POS_I/O	y_s= y_I/O	S₇-S₈-S₉-S₁₄-S₁₅
2	POS_RGV=POS_I/O	y_s≠ y_I/O	S₇-S₈-S₉-S₁₀-S₁₁-S₁₂-S₁₃-S₁₄-S₁₅
3	POS_RGV≠POS_I/O，y_R=y_I/O	y_s= y_I/O	S₆-S₇-S₈-S₉-S₁₄-S₁₅
4	POS_RGV≠POS_I/O，y_R=y_I/O	y_s≠ y_I/O	S₆-S₇-S₈-S₉-S₁₀-S₁₁-S₁₂-S₁₃-S₁₄-S₁₅
5	POS_RGV≠POS_I/O，y_R≠y_I/O	y_s= y_I/O	S₁-S₂-S₃-S₄-S₅-S₆-S₇-S₈-S₉-S₁₄-S₁₅
6	POS_RGV≠POS_I/O，y_R≠y_I/O	y_s≠ y_I/O	S₁-S₂-S₃-S₄-S₅-S₆-S₇-S₈-S₉-S₁₀-S₁₁-S₁₂-S₁₃-S₁₄-S₁₅

立体车库取车过程是存车过程的逆过程。取车过程中，RGV和Lift接收指令，将车辆从车位运载至I/O口。根据取车运行状态中I/O位置、取车车位与RGV初始位置之间关系，取车过程设备运行状态有4种情况，见表3，取车服务时间为RGV从取车车位运载车辆至I/O卸载车辆过程设备的运行时间。

表3 取车过程设备运行状态

Table 3 The running state of the retrieval equipment

类别	车位位置与RGV初始位置关系	车位位置和I/O关系	取车过程运行状态
1	y_r = y_R	y_r = y_I/O	R₆-R₇-R₈-R₉-R₁₄-R₁₅
2	y_r = y_R	y_r ≠ y_I/O	R₆-R₇-R₈-R₉-R₁₀-R₁₁-R₁₂-R₁₃-R₁₄-R₁₅
3	y_r ≠ y_R	y_r = y_I/O	R₁-R₂-R₃-R₄-R₅-R₆-R₇-R₈-R₉-R₁₄-R₁₅
4	y_r ≠ y_R	y_r ≠ y_I/O	R₁-R₂-R₃-R₄-R₅-R₆-R₇-R₈-R₉-R₁₀-R₁₁-R₁₂-R₁₃-R₁₄-R₁₅

平面移动式立体车库RGV与Lift完成存取任务配合运行状态转换如图2所示，其中：S₁~S₁₅表示存车过程中RGV与Lift的运行状态；R₁~R₁₅表示取车过程中RGV与Lift的运行状态。

图2 立体车库存取车运行状态图

Fig. 2 Running status diagram of stereo garage access to vehicle

2 立体车库运行模型建立

2.1 车位分配原则

车位分配是在车库布局、存取设备、存储策略和车位编号过程都完成后进行的，平面移动式立体车库车位分配主要遵循以下几种原则：

1）先到先服务原则。根据出入库顾客到达顺序依次进行存取操作，避免交叉服务过程中RGV出现阻塞，延长顾客等待时间和存取车服务时间。

2）出库优先原则。存车过程中，顾客只需要发出存车请求后即可离开，不存在等待服务过程。取车过程中，顾客发出取车请求需要等待RGV与Lift将车辆运载至I/O口，故应确保出库车辆以最短等待时间接受出库服务。

2.2 车库运行的数学模型

以某商用立体车库单侧为研究对象，依据上节存取车运行状态建立车库运行数学模型。由于本文研究立体车库遵循先到先服务原则，避免交叉存取操作引起RGV阻塞的时间消耗。存取车过程服务时间为RGV运行时间+Lift运行时间，如式（1）和式（2）所示，相关参数符号定义见表4。

表4 参数符号及含义

Table 4 Parameter symbol and meaning

符号	含义	符号	含义
s $/$ m	单个车位宽度	$T_{0} /$ s	RGV上下Lift的时间
h $/$ m	车位高度	$T_{1} /$ s	RGV在水平方向运行时间
$v_{1} /$ (m·s^-1)	RGV在水平方向上的运行速度	$p /$ 个	水平方向I/O至Lift的车位数量
$v_{2} /$ (m·s^-1)	Lift在垂直方向上运行速度	$T_{2} /$ s	Lift在垂直方向运行时间
i $/$ 个	水平方向存车位置到I/O车位个数	$T_{3} /$ s	RGV将车辆存入或取出车位的时间
j $/$ 层	垂直方向存车层到I/O层的层数	${\bar{T}}_{w a i t}^{} /$ s	顾客平均等待时间

T_{1} = \frac{(2 p - i) \times s}{v_{1}}

，

（1）

T_{2} = \frac{j \times h}{v_{2}}

，

（2）

{\bar{T}}_{w a i t} = \frac{T_{w a i t 1} + T_{w a i t 2} + \dots + T_{w a i t n}}{n} = \frac{\sum_{i = 1}^{n} T_{w a i t i}}{n}

。

（3）

3 基于k-means聚类的车位分区分配

以某商用立体车库单侧为研究对象，可用车位数量为117个，车库结构位于地上2层，地下4层，I/O位于地上1层（即第5层）。统计该车库2017年6—8月共20个非工作日的顾客到达-离去数据，计算得到1 702个车辆库内停留时间数据，采用k-means聚类方法^[

13]，将聚类个数分别设置为k=4，5，6，7，8，9。以立方聚类标准（cubic cluster criterion，CCC）作为判断拟合效果的评价指标，最佳聚类效果由最高CCC值确定，6种聚类下CCC值如表5所示。

表5 6种聚类下CCC值

Table 5 CCC values under 6 clusters

方法	聚类个数	CCC
k-means聚类	4	-1.151 2
k-means聚类	5	-7.086 0
k-means聚类	6	-2.669 2
k-means聚类	7	-0.195 2
k-means聚类	8	-2.063 0
k-means聚类	9	-0.800 6

当聚类个数k =7时，CCC值最大，车辆到达时间与停留时间聚类个数为7时，聚类效果最好。聚类结果如图3所示，其中，k =7的聚类均值如表6所示。本文研究到达时段为07:00—23:00，其中，聚类4数据集整体表现为单任务存车过程，在实际运行过程中对车位分区影响较小，所以，在实际分析过程中不考虑聚类4的所有数据。

图3 车辆到达-停留时间聚类结果

Fig. 3 Clustering results of vehicle arrival-residence time

表6 车辆到达-停留时间聚类均值

Table 6 Mean value of vehicle arrival-stay time cluster

聚类	车辆到达时间/s	车辆停留时间/s	计数
1	25 221.690 20	21 985.335 50	162
2	5 596.149 52	21 919.749 20	124
3	14 739.740 60	5 604.434 23	435
4	44 674.921 70	45 867.168 30	12
5	28 699.970 60	5 372.902 48	523
6	39 639.539 10	6 405.219 15	337
7	8 041.022 66	38 933.136 10	109

根据图3聚类结果，分析到达时间与停留时间关系，得出在不同存取车时段车辆到达和离去的频率，分析各时间段车辆停留的时间范围，使用上述给定的存取车设备运行状态计算存取车服务时间。设定距I/O近且设备总服务时间短的车位存放停留时间短的车辆，距I/O远且设备总服务时间长的车位存放停留时间长的车辆，依据车辆停留时间与车辆出入库频率划分车位区域。立体车库单侧分区如图4所示，其中，车位分区由各时段内车辆到达频率和设备总服务时间决定。分区结果与停留时间、存取车频率的关系如表7所示。若同一时段到达多个车辆，对应聚类1、2、3的车辆到达过程，该时段属于立体车库运行繁忙时段，由表7可知，在立体车库实际运行过程中将该繁忙时段到达车辆存放在相应分区①②③中。

图4 立体车库前排车位分区图

Fig. 4 Partition plan of parking space in front of stereo garage

表7 评价指标与分区结果关系

Table 7 Relationship between evaluation indexes and zoning results

参量	分区①	分区②	分区③	分区④	分区⑤	分区⑥
存车频率	高	高	较高	低	低	低
取车频率	低	高	高	高	低	低
停留时间	短	短	短	较长	较长	长

4 仿真结果及分析

基于车辆到达-离去时间的聚类划分结果，参照前面的分区基础，选取2017年6月—8月10个非工作日共861个到达-离去数据。仿真比较本文设计基于到达-离去时间聚类推理的车位分区分配与车位就近分配过程的顾客平均等待时间。本文设计车位分区分配与就近分配下顾客平均等待时间见图5和图6。

图5 就近分配原则下效率指标

Fig. 5 Efficiency index under the principle of nearby

图6 分区分配原则下效率指标

Fig. 6 Efficiency index under the principle of partition allocation

采用本文设计分区分配策略与就近分配策略的顾客平均等待时间如表8所示，本文设计策略较就近分配策略的顾客平均等待时间缩短了9.5%。

表8 不同车位分配策略下车库运行效率指标

Table 8 The garage operation efficiency indexes under different on a strategy

车位分配策略	顾客平均等待时间 ${\bar{T}}_{w a i t}$ /min
就近分配	2.012
本文设计分区分配	1.821

5 结论

研究得到的主要结论如下：

1）以到达-离去时间相关性进行k-means聚类，对不同时刻到达车辆的停留时长特性进行分析，根据聚类结果按车位与I/O的距离和运行时长设计车位分区分配策略；

2）采用工程实际数据对比分析了本文设计车位分区分配策略与就近分配策略下车库运行的顾客平均等待时间，表明使用本文设计策略较就近分配策略顾客平均等待时间缩短9.5%，证明本文设计车位分区分配策略可有效缩短顾客存取车排队等待时间，提高立体车库运行效率。

采用车辆到达-离去时间特征数据进行了k-means动态聚类，将聚类结果应用于车位动态分区分配，但未充分考虑聚类结果不准确对车位分配的影响，设计策略在其他同类型车库的适用性有待进一步验证。

参考文献

王小农, 李建国, 贺云鹏. 平面移动式立体车库车位分配的建模与仿真[J]. 南京理工大学学报, 2019, 43(1):54-62. [百度学术]

Wang X N,Li J G,He Y P. Modeling and simulation of parking space allocation in plane mobile stereo garage[J]. Journal of Nanjing University of Science and Technology, 2019, 43(1): 54-62. (in Chinese) [百度学术]

靳萌, 穆希辉, 罗偲语, 等. 基于两级策略的器材立体仓库货位分配方法[J]. 系统工程与电子技术, 2017, 39(8): 1774-1781. [百度学术]

Jin M,Mu X H,Luo S Y,et al.Slot assignment method for maintenance material warehouse based on two levels policy[J].Systems Engineering and Electronics, 2017, 39(8): 1774-1781. (in Chinese) [百度学术]

李明, 吴耀华, 陈宁宁, 等. 串行合流下阵列式自动拣选系统品项分配优化[J]. 计算机集成制造系统, 2016, 22(9): 2127-2134. [百度学术]

Li M,Wu Y H,Chen N N,et al.Items assignment optimization for array automated picking device based on serial order accumulation[J]. Computer Integrated Manufacturing Systems, 2016, 22(9): 2127-2134. (in Chinese) [百度学术]

杨玮, 刘江, 岳婷, 等. 多载具自动化立体仓库货位分配与作业调度集成优化[J]. 计算机集成制造系统, 2019, 25(1):247-255. [百度学术]

Yang W, Liu J, Yue T, et al. Integrated optimization of location assignment and job scheduling in multi-carrier automated storage and retrieval system[J]. Computer Integrated Manufacturing Systems, 2019, 25(1): 247-255. (in Chinese) [百度学术]

刘日, 李建国, 王小农. 立体车库车位分配建模与仿真[J]. 江苏大学学报(自然科学版), 2018, 39(1): 19-25. [百度学术]

Liu R, Li J G,Wang X N. Modeling and simulation of parking space allocation in stereo garage[J]. Journal of Jiangsu University(Natural Science Edition), 2018, 39(1): 19-25. (in Chinese) [百度学术]

汤洪涛, 闫伟杰, 陈青丰, 等. 自动化立体仓库货位分配与作业调度集成优化[J]. 计算机科学, 2019, 10: 204-211. [百度学术]

Tang H T, Yan W J, Chen Q F, et al. Integrated optimization of location assignment and job scheduling in automated storage and retrieval system[J]. Computer Science, 2019, 10: 204-211. (in Chinese) [百度学术]

李珍萍, 赵雨薇, 张煜炜. 共同配送选址-路径优化模型与算法[J]. 重庆大学学报, 2020, 43(1): 28-43. [百度学术]

Li Z P, Zhao Y W, Zhang Y W.Optimization model and algorithm of location-routing for joint distribution[J]. Journal of Chongqing University, 2020, 43(1): 28-43. (in Chinese) [百度学术]

Zulj I, Glock C H, Gross E H, et al.Picker routing and storage-assignment strategies for precedence-constrained order picking[J].Computers & Industrial Engineering, 2018, 123: 338-347. [百度学术]

Lee I, Chung S, Yoon S. Two-stage storage assignment to minimize travel time and congestion for warehouse order picking operations[J]. Computers & Industrial Engineering, 2020, 139: 106129. [百度学术]

Zhang R Q, Wang M, Pan X. New model of the storage location assignment problem considering demand correlation pattern[J]. Computers & Industrial Engineering, 2019, 129: 210-219. [百度学术]

Micale R, La Fata C M, La Scalia G. A combined interval-valued ELECTRE-TRI and TOPSIS approach for solving the storage location assignment problem[J]. Computers and Industrial Engineering, 2019, 135(C): 199-210. [百度学术]

Keung K L, Lee C K M, Ji P. Data-driven order correlation pattern and storage location assignment in robotic mobile fulfillment and process automation system[J]. Advanced Engineering Informatics, 2021, 50: 101369. [百度学术]

Borgwardt S, Brieden A, Gritzmann P. An LP-based k-means algorithm for balancing weighted point sets[J]. European Journal of Operational Research, 2017, 263(2): 349-355. [百度学术]

Home