一种基于聚类分析的公共自行车调度方法

摘要

本发明公开了一种基于聚类分析的公共自行车调度方法，共有如下6个步骤：1)收集各公共自行车租赁点的基本信息及历史运营数据，计算各时刻的租赁点的满载率。2)：通过聚类分析对各租赁点的满载率进行聚类，区分不同租赁点的运行特征。3)基于聚类分析对所有公共自行车租赁点进行筛选，明确在调度工作中需考虑的站点。4)结合租赁点的实时数据确定各租赁点的调度需求，进一步筛选出需要进行调度的站点。5)以调度路径总长度最短为优化目标，构建调度方案模型。6)考虑调度车从场站出发时载运的自行车初始数量取不同值的情境，分别计算最优的调度方案，比选出最终调度车行驶的调度路径。本发明可为公共自行车调度工作的开展提供参考。

权利要求

1.一种基于聚类分析的公共自行车调度方法，其特征在于：包括以下步骤：步骤1：收集各公共自行车租赁点的基本信息及历史运营情况数据，所述租赁点的基本信息包括租赁点的名称、位置、自行车桩的数量；所述历史运营情况数据包括租赁点各时刻可借用的自行车数量和各时刻的租赁点的满载率，满载率由式(1)得到：load_factori,k＝num_availi,k/num_totali  (1)其中，load_factori,k为租赁点i在k时刻的满载率；num_availi,k为租赁点i在k时刻可借用的公共自行车数量，num_totali为租赁点i的自行车桩总数量；

步骤2：运行聚类分析对各租赁点的全天满载率数据集进行聚类；所述数据集记录各时间间隔计算所得的满载率值，该数据集的记录条数为公共自行车租赁点的总数量；

步骤3：基于聚类分析对公共自行车系统的所有租赁点进行筛选，明确在调度工作中需考虑的租赁点；

步骤4：在调度时间内，结合租赁点的实时数据确定各租赁点的调度需求；

步骤5：以调度路径总长度最短为目标，构建调度方案模型；

步骤6：考虑调度车从场站出发时的载运的自行车初始数量取不同值的情境，分别计算最优的调度方案，并对不同情境的路径长进行比选，以确定调度车辆的最终调度路径；

所述步骤5的优化模型如下：

优化目标：min Z＝∑∑dijxij  (2)其中，Z表示调度车在整个调度过程中所行驶的总路径长；

dij表示从租赁点i径向到租赁点j的路段长；

i,j表示公共自行车的租赁点，当其取值为1时，表示调度车的场站；

N表示所有公共自行车租赁点的集合，包括调度车场站；

xij为0-1变量，取值为1时表示调度车的行驶路径中包括有租赁点i径向到租赁点j的路段；反之，则取值为0；

其中，ui为防止模型计算结果出现多个回路而设定的一个变量，n表示需要进行调度的租赁点数量；

b1＝p1  (6)

其中，bi表示从租赁点i离开时，调度车上的自行车数量；

pi表示租赁点i需要被调度车调运走的公共自行车数量；

qi表示租赁点i需要补给的公共自行车数量；

除了调度车场站，所有在集合N中的租赁点均满足pi+qi＞0与pi·qi＝0；

C表示调度车的容量，即一辆调度车可运载的自行车数量的最大值；

M为常数；

所述步骤6具体实现如下：

6.1、在既定的p2、p3、p4………pn、q2、q3、q4、……qn条件下，求出所有满足 p1≤C的p1值，每个值均对应一个情境；

6.2、记总的情境的数量为R，将第r各情境对应的p1值带入步骤5的模型中，得到的模型最优解为Zr，构成备选方案集{Z1,Z2,…ZR}，对R种情境的最优解进行比较，取最小值。

2.根据权利要求1所述的一种基于聚类分析的公共自行车调度方法，其特征在于：所述步骤2具体为：基于欧式距离对数据集进行分析，并采用方差分析检验各类别间的差异性，依据聚类结果对公共自行车系统中不同租赁点的运行特征进行区分。

3.根据权利要求1所述的一种基于聚类分析的公共自行车调度方法，其特征在于：所述步骤4具体实现如下：

4.1、结合调度人力物力情况，确定系统调度的时间间隔；

4.2、预先设定安全阈值范围[load_factorlower,load_factorupper]，其中load_factorlower为满载率建议下限值，load_factorupper为满载率建议上限值，调度量的计算以该时段开始时的时刻k为准，qi为租赁点i需补给的公共自行车辆数，pi为租赁点i需调走的公共自行车辆数；

在具体的调度时段内，对租赁点i：

若load_factori,k∈[load_factorlower,load_factorupper]，则不需调度，pi＝qi＝0，此类租赁点可从调度系统中移除；

若load_factori,k＜load_factorlower，则该租赁点需补给公共自行车，调度量为pi＝0，符号 表示向上取整；

若load_factorupper＜load_factori,k，则该租赁点需取走一定量的公共自行车，调度量为 qi＝0。

说明书

一种基于聚类分析的公共自行车调度方法

技术领域

[0001] 本发明属于公共自行车调度领域，具体涉及一种基于聚类分析的公共自行车调度方法。

背景技术

[0002] 公共自行车系统具有环保、使用便捷等优点，在我国许多城市得到运用。在公共自行车系统规模扩大、租赁点数量增多的同时，运营中的问题也影响着公共自行车系统的服务质量，其中一个常见问题是出行者可能会遇到需借车时租赁点无车可借，或还车时无桩可还的现象，不能及时地满足出行者的需求，及时利用调运车辆对公共自行车车辆进行调度是解决上述问题的有效方法之一。

[0003] 城市公共自行车的使用特性往往呈现出一定的时变特征，由于租赁点所在地点用地性质、人口分布、服务人群类型等因素的不同，导致租赁点间的使用时变特征具有差异性。现有对公共自行车的调度研究未有结合其使用的时间分布情况。由于调度人力、物力的约束，应尽量将有限的资源投入到最必要的调度工作中，而结合租赁点使用的时变特征，可以有效缩减调度规模，减小调度压力。

发明内容

[0004] 本发明为了克服现有技术中存在的问题，提供一种基于聚类分析的公共自行车调度方法。运用聚类分析技术分析公共自行车系统各租赁点的满载率时变特征，据此对各租赁点进行分类，筛选出不需进行调度的公共自行车租赁点，并结合满载率安全阈值范围进行二次筛选，以实现缩减调度规模的目的；以总调度路径最短为目的进行建模，根据调度车从场站出发时所运载的自行车数量初始值的不同设定情境，分别求解模型，比选出最优调度方案，达到调度成本最小化的效果。

[0005] 为解决上述技术问题，本发明提供了一种基于聚类分析的公共自行车调度方法，包括以下步骤：

[0006] 步骤1：收集各公共自行车租赁点的基本信息及历史运营情况数据，所述租赁点的基本信息包括租赁点的名称、位置、自行车桩的数量；所述历史运营情况数据包括租赁点各时刻可借用的自行车数量和各时刻的租赁点的满载率，满载率由式(1)得到：

[0007] load_factori,k＝num_availi,k/num_totali  (1)

[0008] 其中，load_factori,k为租赁点i在k时刻的满载率；num_availi,k为租赁点i在k时刻可借用的公共自行车数量，num_totali为租赁点i的自行车桩总数量；

[0009] 步骤2：运行聚类分析对各租赁点的全天满载率数据集进行聚类；

[0010] 步骤3：基于聚类分析对公共自行车系统的所有租赁点进行筛选，明确在调度工作中需考虑的租赁点；

[0011] 步骤4：在调度时间内，结合租赁点的实时数据确定各租赁点的调度需求；

[0012] 步骤5：以调度路径总长度最短为目标，构建调度方案模型：

[0013] 步骤6：考虑调度车从场站出发时的载运的自行车初始数量取不同值的情境，分别计算最优的调度方案，并对不同情境的路径长进行比选，以确定调度车辆的最终调度路径。

[0014] 步骤2具体为：所获得满载率数据集的条数为公共自行车租赁点的总数量，每条数据中各时间隔计算所得的满载率值，并按时间顺序排列(如表1)。基于欧式距离对数据集进行分析，并采用方差分析检验各类别间的差异性，依据聚类结果对公共自行车系统中不同租赁点的运行特征进行区分。

[0015] 表1聚类分析所基于的数据集示意表

[0016] 租赁点标号i load_factori,1 load_factori,2 load_factori,3 load_factori,4 ……1          
2          
……          

[0017] 步骤4具体实现如下：

[0018] 4.1、结合调度人力物力情况，确定系统调度的时间间隔；

[0019] 4.2、预先设定安全阈值范围[load_factorlower,load_factorupper]，其中load_factorlower为满载率建议下限值，load_factorupper为满载率建议上限值，调度量的计算以该时段开始时的时刻k为准，qi为租赁点i需补给的公共自行车辆数，pi为租赁点i需调走的公共自行车辆数；

[0020] 在具体的调度时段内，对租赁点i：

[0021] 若load_factori,k∈[load_factorlower,load_factorupper]，则不需调度，pi＝qi＝0，此类租赁点可从调度系统中移除；

[0022] 若load_factori,k＜load_factorlower，则该租赁点需补给公共自行车，调度量为符号 表示向上取整；

[0023] 若load_factorupper＜load_factori,k，则该租赁点需取走一定量的公共自行车，调度量为 qi＝0。

[0024] 步骤5的优化模型如下：

[0025] 优化目标：min Z＝∑∑dijxij  (2)

[0026]

[0027]

[0028] 其中，Z表示调度车在整个调度过程中所行驶的总路径长；

[0029] dij表示从租赁点i径向到租赁点j的路段长；

[0030] i,j表示公共自行车的租赁点，当其取值为1时，表示调度车的场站；

[0031] N表示所有公共自行车租赁点的集合，包括调度车场站；

[0032] xij为0-1变量，取值为1时表示调度车的行驶路径中包括有租赁点i径向到租赁点j的路段；反之，则取值为0；

[0033]

[0034] 其中，ui为防止模型计算结果出现多个回路而设定的一个变量，n表示需要[0035] 进行调度的租赁点数量包括调度车场站；

[0036] b1＝p1  (6)

[0037]

[0038]

[0039]

[0040]

[0041]

[0042]

[0043] 其中，bi表示从租赁点i离开时，调度车上的自行车数量；

[0044] pi表示租赁点i需要被调度车调运走的公共自行车数量；

[0045] qi表示租赁点i需要补给的公共自行车数量；

[0046] 除了调度车场站，所有在集合N中的租赁点均满足pi+qi＞0与pi·qi＝0；

[0047] C表示调度车的容量，即一辆调度车可运载的自行车数量的最大值；

[0048] M为常数；

[0049]

[0050]

[0051]

[0052] 步骤6具体实现如下：

[0053] 6.1、在既定的p2、p3、p4………pn、q2、q3、q4、……qn条件下，求出所有满足p1≤C的p1值，每个值均对应一个情境；

[0054] 6.2、记总的情境的数量为R，将第r各情境对应的p1值带入步骤5的模型中，得到的模型最优解为Zr，构成备选方案集{Z1,Z2,L ZR}，对R种情境的最优解进行比较，取最小值。

[0055] 有益效果：本发明与现有技术相比，本发明基于聚类分析对公共自行车系统各站点的时间维度的使用特性进行分类研究，在此基础上确定调度考虑的租赁点并求解调度车行驶的最优路径，可为城市公共自行车调度工作的开展提供参考。

附图说明

[0056] 图1为本发明公共自行车调度流程图；

[0057] 图2为公共自行车系统时间特性聚类结果示意图；

[0058] 图3为公共自行车调度站点筛选过程示意图。

具体实施方式

[0059] 下面结合实施例进一步阐述该发明方法。

[0060] 如图1所示的公共自行车调度方法，包括如下步骤：

[0061] 步骤1：收集各自行车租赁点的基本信息及历史运营情况数据。

[0062] 可通过互联网技术抓取如下开源数据：a.租赁点的基本信息，包括租赁点的名称、位置、自行车桩的数量；b.每隔5分钟获取一次租赁点可借用的自行车数量，获得公共自行车全日的历史数据，并计算各时刻的租赁点的满载率：

[0063] load_factori,k＝num_availi,k/num_totali  (1)

[0064] 其中，load_factori,k为租赁点i在k时刻的满载率；num_availi,k为租赁点i在k时刻可借用的公共自行车数量，num_totali为租赁点i的自行车桩数量。

[0065] 步骤2：运行聚类分析对各租赁点的全天满载率数据集进行聚类。所获得满载率数据集的条数为公共自行车租赁点的总数量，每条数据中各时间隔计算所得的满载率值，并按时间顺序排列(如表1)。

[0066] 表1聚类分析所基于的数据集示意表

[0067] 租赁点标号i load_factori,1 load_factori,2 load_factori,3 load_factori,4 ……1          
2          
……          

[0068] 运用统计分析软件，基于欧式(Euclidean)距离对数据集进行分析，并以0.05的显著性水平采用方差分析(ANOVA)检验各类别间的差异性。依据聚类结果对公共自行车系统中不同租赁点的运行特征进行区分。

[0069] 步骤3：基于聚类分析对公共自行车系统的所有租赁点进行筛选，明确在调度工作中需考虑的站点。预先设定安全阈值范围[load_factorlower,load_factorupper]，其中load_factorlower为满载率建议下限值，load_factorupper为满载率建议上限值。

[0070] 1)对于全天满载率均处于较平稳且多数时间内(多于70％)满载率属于安全阈值范围内的租赁点，一方面公共自行车的使用情况可基本实现“借还平衡”，不会对使用者造成不便，另一方面不会对自行车资源造成浪费，可将此类站点从系统中移除，不进行调度需求分析。

[0071] 2)对于全天满载率均处于较平稳但总体满载率高于安全阈值上限值或低于安全阈值下限值的租赁点，会造成一定的浪费或有可能出现“无桩可还”、“无车可借”的问题，应纳入考虑。

[0072] 3)对于满载率最高值与最低值的差值大于0.4，呈现明显使用高峰与低峰的租赁点应重点考虑。

[0073] 步骤4：在具体的调度时间内，结合租赁点的实时数据确定各租赁点的调度需求。

[0074] 可结合调度人力物力情况，确定系统调度的时间间隔(如每2小时进行一次重新调度)。调度量的计算以该时段开始时的时刻k为准。qi为租赁点i需补给的公共自行车辆数，pi为租赁点i需调走的公共自行车辆数。

[0075] 在具体的调度时段内，对租赁点i：

[0076] 1)若load_factori,k∈l[oad_factorlower lo,ad fa_ctorupper]，则不需调度，pi＝qi＝0，此类租赁点可从调度系统中移除。

[0077] 2)若load_factori,k＜load_factorlower，则该租赁点需补给公共自行车，调度量为pi＝0，

[0078] 3)若load_factorupper＜load_factori,k，则该租赁点需取走一定量的公共自行车，调度量为 qi＝0。

[0079] 步骤5：以调度路径总长度最短为目标，构建优化模型。

[0080] 1)做如下假定：

[0081] 调度时段中，所有需调度站点的调度量均由该时段开始时刻的状态获得，按步骤4要求进行计算，作为已知输入；

[0082] 公共自行车系统的设施固定，整个系统所处范围被划分为适宜规模的小区域，每个区域可由一辆调度货车完成调度工作，调度车出发的场站已知。下述模型针对这样的区域进行建模。

[0083] 以i＝1的编号表示场站，且场站内存有一定量的备用公共自行车，使区域内的所有租赁点与场站的补给总需求可以得到满足。由于需调度走的自行车数量多于需补给的自行车数量的情况不合理性，模型中不予考虑。

[0084] 所有的租赁点的调度需求可在调度车访问一次后得到满足。

[0085] 2)构建优化模型如下。

[0086] min Z＝∑∑dijxij  (2)

[0087]

[0088]

[0089]

[0090] b1＝p1  (6)

[0091]

[0092]

[0093]

[0094]

[0095]

[0096]

[0097]

[0098]

[0099]

[0100] 各变量的定义为：

[0101] i,j表示公共自行车的租赁点。特殊情况为，当其取值为1时，表示调度车的场站。

[0102] N表示所有公共自行车租赁点的集合，包括调度车场站。

[0103] xij为0-1变量，取值为1时表示调度车的行驶路径中包括有租赁点i径向到租赁点j的路段；反之，则取值为0。

[0104] bi表示从租赁点i离开时，调度车上的自行车数量。

[0105] n表示需要进行调度的租赁点数量(包括调度车场站)。

[0106] pi表示租赁点i需要被调度车调运走的公共自行车数量。

[0107] qi表示租赁点i需要补给的公共自行车数量。除了调度车场站，所有在集合N中的租赁点均满足pi+qi＞0与pi·qi＝0。

[0108] dij表示从租赁点i径向到租赁点j的路段长。

[0109] C表示调度车的容量，即一辆调度车可运载的自行车数量的最大值。

[0110] M为一个值足够大的常数。

[0111] ui为防止模型计算结果出现多个回路而设定的一个变量。变量uj的添加是为了防止求解得到的路径为多个回路(如：1—3—9—12—1，2—6—4—7—2，……)的情况出现。该变量不具有实际的物理含义，仅是为解决多回路产生而考虑增加的数学变量。其作用的发挥证明如下：

[0112] 对应的约束条件为：ui-uj+nxij≤n-1

[0113] (1)任何含有多回路的调度路线都不满足该约束条件。

[0114] 采用反证法证明：假设存在含有多回路的调度路线满足该约束条件。

[0115] 求解的调度线路含有多回路时，则至少有两条回路，必有一条回路不包含站点1。假定该回路为2—6—4—7—2，对于回路上的路径有xij＝1，因此

[0116] u2-u6+n≤n-1

[0117] u6-u4+n≤n-1

[0118] u4-u7+n≤n-1

[0119] u7-u2+n≤n-1

[0120] 以上4式相加，得到n≤n-1，该不等式不成立，因此假设不成立，论述(1)得证。

[0121] (2)所有的不含有多回路的调度路段都可以通过取适当的uj值满足该约束。

[0122] 对调度路线上的路径均有xij＝1。可取uj为该站点被访问的顺序数，则对于选用的路径i到j有ui-uj＝-1，此时约束条件则变为-1+n≤n-1，该式恒成立。因此论述(2)成立。

[0123] 综上所述，变量uj及约束条件ui-uj+nxij≤n-1的添加可起到相应作用。

[0124] 3)模型的解释。

[0125] 本模型运用了单旅行商问题，并在其基础上增加了调度车容量的约束条件。

[0126] 表达式(2)为优化目标，旨在求出满足约束条件的可行解中调度路径长度最短的调度方案。

[0127] 二元变量xij为本模型的决策变量，约束条件(14)，用来标记所求最优解路径中所包含的路段。约束条件(3)与(4)表示所有需调度的站点均被访问，且仅可访问一次。约束条件(5)与(15)用以避免求解结果中出现多回路。调度车开始工作时从场站出发，约束条件(6)表示对模型而言，调度车上初始的自行车为确定值。约束条件(7)-(10)用来表示每次访问完一个租赁点时，调度车上自行车数量的更新情况。约束条件(11)表示调度车上的自行车数量应为非负值，使其符合现实情况。约束条件(12)表示调度车上的自行车数量不能超过调度车的容量。因为租赁点i到其本身的路径是无意义的，约束(13)用来避免这样的路径在求解结果中出现，使求解结果的可理解性更好。

[0128] 由于单旅行商问题的求解方法在现有研究中较为成熟，本发明中不对其进行赘述。

[0129] 步骤6：考虑调度车从场站出发时的载运的自行车初始数量取不同值的情境，分别计算最优的调度方案，并对不同情境的路径长进行比选，以确定调度车辆的最终调度路径。

[0130] 调度车从场站出发时的载运的自行车初始数量不同时，求解得到的最短路径长度往往也有所不同，为了能够在既有资源条件下，实现调度成本的最小化，对所有可能的情况均进行考虑。

[0131] 在既定的p2、p3、p4………pn、q2、q3、q4、……qn条件下，求出所有满足p1≤C的p1值，每个值均对应一个情境。

[0132] 记总的情境的数量为R。将第r各情境对应的p1值带入步骤5的模型中，得到的模型最优解为Zr，构成备选方案集{Z1,Z2,L ZR}，对R种情境的最优解进行比较，取最小值。则调度问题的最终调度路径为方案集中路径长度最小值所对应的方案。

[0133] 现，以南京市某区的公共自行车系统为例具体说明。

[0134] 该区共有62个公共自行车租赁点及1个调度场站，通过互联网技术收集各租赁点的相关信息。

[0135] 使用IBM SPSS Statistics软件对获取的租赁点6：00-21：00的满载率数据进行基于欧式距离的分层聚类分析，分析共得到5类，聚类结果如图2。聚类结果可通过显著性水平为0.05的方差分析。

[0136] 由于第4类租赁点(共22个租赁点)的满载率较为适中且稳定，可形成某种程度上的借还平衡，故将不考虑该类站点的调度问题。剩余站点与调度车场站的总数为41。

[0137] 基于聚类分析对公共自行车系统的所有租赁点进行筛选，明确在调度工作中需考虑的站点。设定满载率的安全阈值范围[0.15,0.4]，由于有12个站点的满载率均落在安全阈值范围内，故不考虑这些站点的调度。余下28个站点的调度需求计算如表1。

[0138] 表1各租赁点调度需求计算结果

[0139]

[0140] (注：“--”表示其取值为0)

[0141] 站点筛选的过程如图2。图中的所有点表示该区的公共自行车租赁点与调度车场站的位置情况。方形表示在步骤2中筛选掉的不予考虑调度的22个租赁点；三角形表示依据安全阈值范围判断不予考虑调度的12个租赁点；圆形表示最终调度模型中考虑的28个租赁点和1个调度车场站位置。

[0142] 输入实际数据，构建相关的优化模型。设定调度车的容量为30。

[0143] 考虑调度车从场站出发时的载运的自行车初始数量取不同值的情境，分别计算最优的调度方案，并对不同情境的路径长进行比选，以确定调度车辆的最终调度路径。

[0144] 在此实例中，当 时，p1值为7。故本问题p1可取的值为7、8、9……30，每个值均对应一个情境。考虑篇幅所限，这里仅对p1取的值7、15、20、25的五个情境进行分析，采取启发式算法对各模型进行求解，所得结果如表2。

[0145] 表2.各情境计算所得调度方案比较表

[0146]

[0147] 在所列举的4中情境中，当p1＝25时，所得的调度路径最短，即该情境为最终的调度方案。