基于时空聚类预测的共享单车调度优化研究

陈植元 林泽慧 金嘉栋 李建斌

(1.武汉大学 经济与管理学院, 湖北 武汉 430072; 2.上海交通大学 中美物流研究院, 上海 200030;3.华中科技大学 管理学院, 湖北 武汉 430074)

0 引言

共享单车服务是指单车租赁企业在校园、地铁站点、公交站点、居民区、商业区、公共服务区等区域提供自行车单车分时租赁服务。作为共享经济热潮的产物,共享单车在城市公共交通中发挥着越来越重要的作用,为城市用户提供了一种更具可持续性的无碳运输模式,显著减少了交通拥堵、空气污染。当前共享单车运营模式分为传统带桩共享单车(station-based bike sharing,SBBS)和无桩共享单车(freefloating bike sharing,FFBS)。SBBS系统合理的网络设计能够在方便用户出行的同时提高运营商的管理效率,但由于基站的设立是有限的,当最近的基站与用户目的地相距较远时,用户将增加不必要的行程以停放共享单车。与传统的带桩共享单车不同,无桩共享单车(FFBS)不再设立基站,用户可以根据自己的行程自由安排出发点和停车点。由于FFBS在实际运营中展现出了极高的自由度和便利性,越来越多的用户选择使用相应的服务。

我国共享单车服务行业近年来发展迅速,多家提供共享单车服务企业的出现加快了服务模式的升级和创新。艾媒咨询(iiMedia Research)提供的数据显示,2018年中国共享单车用户规模已达到2.35亿人,2019年预计将增至2.59亿人。在共享单车的使用频率上,45.1%的用户平均每周使用共享单车5次及以下;54.9%的用户平均每周使用在5次以上。其中,82.9%的用户平均每次使用共享单车的时长在60分钟内。显然,共享单车用户数量规模大,且使用单车的主要目的是满足短途出行需要。巨大的市场规模与不断走高的行业发展形势也带来了激烈的竞争,企业不得不通过降低运营成本来应对残酷的价格战。由于用户的行为具有自主性,在实际运营中,共享单车的分布会逐渐偏离均衡,从而导致系统内部资源分布的不合理。为了提高运营效率和用户满意度,越来越多的企业将优化目标锁定在了单车调度上。

共享单车的调度指通过有效的方式实现单车资源在网络中的合理布局,本文正是对共享单车的调度方式进行优化研究,其可能的贡献在于:(1) 对运营商而言,调度路径的优化能够减少调度车在工作过程中的行驶距离,对各节点的调度任务进行合理分配则可以减少调度车和相关工作人员的投入从而降低成本;(2) 对使用共享单车的用户而言,调度方式的优化能保证他们在合适的距离内即时获得共享单车。在本文中,如何选择投车点也是受关注的一个重要问题,合理的投车点应该在用户有取车意愿的距离内,以避免当步行距离过大时,用户使用体验受到影响甚至选择放弃使用共享单车;(3) 对社会总体福利而言,共享单车资源的有效分配有助于提高社会资源的有效利用水平。共享单车调度的优化有助于识别服务区域内共享单车的需求情况,在整体需求无爆炸增长的情况下,通过调度以有限的单车资源满足所服务区域的社会需求。

目前对于单车调度的学术研究主要集中在基于运营商的调度上。共享单车的调度优化本质上属于车辆路径问题(Vehicle Routing Problem,VRP),车辆路线问题(VRP)最早是由Dantzig和Ramser于1959年提出,它是指一定数量的用户,各自有不同数量的货物需求,配送中心向用户提供货物,由一个车队负责分送货物,组织适当的行车路线,目标是使得用户的需求得到满足,并能在一定的约束下,达到诸如路程最短、成本最小、耗费时间最少等目的。与传统的车辆路径问题不同,共享单车调度中的“用户”不仅是需求方,也可以是供给方。相应地,调度车辆在完成配货的同时,也需要完成取货任务。作为一个NP难问题,共享单车调度优化问题目前并没有直接求解的可行方法,学术界主要通过运用启发式算法对可行解进行优化。

本论文的目的是通过聚类分析的方法为研究无桩共享单车的网络模型提供新的思路和方法,同时通过研究共享单车调度优化问题来探讨启发式算法在解决具体路线问题上的效果,为共享单车调度优化问题的研究提出了从网络分析到调度优化的完整框架,论文研究内容如下:梳理共享单车调度优化问题研究的相关文献,分为对传统共享单车的研究和对新式的无桩共享单车的研究;利用共享单车需求的时空属性设计了聚类模型,以聚类产生的集群为调度对象构建了以调度成本最小为目标函数的VRP模型;设计了贪心算法、遗传算法来求解调度模型,并对每个算法的流程进行了详细的说明;最后进行数据模拟,按照一定的规则生成共享单车需求的数据以及当前时段的单车网络分布情况,通过对数据的模拟来考察思路框架与模型在实际调度中发挥的作用。

1 文献综述

当前共享单车运营模式分为传统带桩共享单车(stationbased bike sharing,SBBS)和无桩共享单车(free-floating bike sharing,FFBS)。其区别是相对于SBBS,FFBS用户可以根据自己的行程自由安排出发点和停车点。国内外对于共享单车调度优化问题的研究主要分为SBBS调度和FFBS调度两个方向。

1.1 SBBS调度优化

在SBBS调度优化的相关研究中,Chemla[1]第一次提出了SBBS中的静态完全再平衡问题(SCRP),建立了目标函数为总调度距离最短的模型。在Chemla[1]之后,Erdŏɡan[2]提出了静态模型的时间扩展网络公式并使用混合整数算法求解;为了解决多辆货车同时参与调度任务的问题,Albarezvaldes[3]提出了一种解决多辆车调度的启发式算法;Raviv[4]等人研究了多辆调度车下的共享单车静态调度问题,在模型中提出并量化了顾客满意度。在SCRP的相关文献中,越来越多的算法被引入以解决SBBS的调度优化问题:分支定界法[5];混合大规模领域搜索算法[6]、社会网络分析法[7]、三阶段启发式算法[8]、双层禁忌搜索算法[9]、离散差分进化算法[10]、容差插入启发式算法[11]等等。

考虑到静态调度对用户反应的迟缓而无法即时对资源进行合理调度,动态调度的相关研究逐渐深入。Contardo[12]提出了基于租赁点的调度分解方案;Pfrommer[13]等通过对公共自行车服务点设定动态变化的租车价格建立了再平衡调度模型;

Xu[14]提出了基于短期需求预测的动态调度模型;Mao[15]等学者建立站点的整体可视化信息,采用梯度提升回归树算法实时预测站点的自行车流入/流出情况;Liu[16]基于GIS的原型系统中建立采用滚动视野调度算法的车辆调度模型。

国内对于共享单车的研究虽然起步稍晚,但也取得了相当丰富的成果。吴满金[17]等学者建立了关于调度成本以及用户满意度的多目标函数,综合考虑了服务优先级、时间窗等约束条件;杨珈惠[18]等学者提出了允许局部路径重复的共享单车调度模型;文蝶斐[19]提出了以调度车初始携带共享单车数量最少为目标的调度优化模型;王涵霄[20]等学者在车辆调度模型的基础上考虑共享单车的维修问题;卢琰[21]根据共享单车网络的特性构建了混合轴辐式网络调度结构;徐国勋[22]等学者在共享单车调度问题中考虑了对损坏自行车的回收;王宁[23]等学者针对站点车辆时空分布不均衡制约共享模式快速发展的问题,提出基于用户激励的共享电动汽车自适应调度的成本最优模型。

1.2 FFBS调度优化

随着FFBS模式的发展并逐渐成为主流,对共享单车调度优化问题的研究也由SBBS扩展到了FFBS。与SBBS拥有固定的单车停放基站不同,FFBS系统网络中单车的分布是随机、无序的,没有任何的先验知识明确网络中单车的分类。因此,如何对网络中的单车进行访问以及如何准确地预测网络中单车的分布情况成为了FFBS调度优化研究的重点。

但是目前对于FFBS调度优化的相关研究仍然较少,国外的Pal和Zhang[24]提出了一种处理FFBS静态再平衡问题的算法,他们通过分解需求的方法打破了以往调度模型中调度车对节点访问次数的限制,设计了嵌套大邻域搜索和可变邻域下降的混合算法求解最优路径。Caggiani[25]等为FFBS的动态管理提出了模型框架。通过聚类方法划分单车网络的时空分布,使用BP神经网络算法预测各聚类群的需求,提出了总体调度时间最短为目标函数的调度模型,设计了一种两阶段VPR优化算法。David[26]引入了负价格的动态定价方案,通过用户的自发行为实现自行车的调度。

国内方面,罗毅军[27]等学者通过奖惩机制建立自动规划调度方法,从用户角度实现共享单车再平衡;鄢章华[28]利用马尔可夫链与状态转移矩阵来分析和描述单车的流转过程,构建不同调度方案下的投放量优化模型;高楹[29]等学者结合时间分布特征、土地类型信息提出了共享单车的空间调度模型;邓力凡[30]等学者根据用户骑行行为的时空特征定义了骑行区域的划分类型;贾永基[31]针对无桩式共享单车运营中所出现的乱停乱放和分布不平衡问题,引入电子围栏并将其作为单车停放站点,通过调节各电子围栏的单车数量以实现供需平衡。

同时随着大数据技术及数字化管理的发展,国内外学者逐渐将聚类算法与VPR问题相结合,如设施选址、车辆路径、选址-路径等问题[32]。Calvet[33]等将客户聚类操作与启发式算法结合提出了一种混合智能算法,经过预测获得新客户对应的服务费用并应用方法于求解多中心车辆路径问题。阮俊虎[34]等提出一种基于聚类的两阶段医疗物资联合运输方法,构建了医疗物资联合运输网络结构,在此基础上建立基于聚类的运送路线优化模型,确定从应急中转点到医疗救助点的具体运送路线。

综上所述,SBBS调度的研究已经非常成熟,但涉及FFBS调度研究则相当空缺,造成该问题的原因有两点:(1)无桩共享单车兴起的时间比较晚;(2)无桩共享单车网络难以描述以及需求的难以预测。鉴于此,本文研究FFBS调度优化问题,通过聚类分析的方法将具有相似时空属性的单位区域聚合为调度集群,提出了将用户对取车距离的敏感性量化为考核集群划分是否合理的惩罚成本,使单车调度问题转化为有时间窗与载重量限制的车辆路径问题,构建共享单车调度路径优化模型,并分别使用了贪婪算法、遗传算法对模型进行求解。

2 调度优化模型

共享单车作为一种短途出行交通工具,其分布受到用户行为的影响。与带桩共享单车不同,无桩共享单车的停放可以是任意位置的,因此如何准确地对网络中单车的分布情况进行描述与分类成为了需求预测与调度的关键。聚类分析是一种在没有先验知识的情况下对物理或抽象对象进行相似分组的统计方法。结合共享单车需求的时空特征,合理利用聚类分析将网络中单车分布情况与需求趋势相似的地区聚合成虚拟“基站”进行统一调度是本文处理共享单车网络的主要分析方法。本文所构建调度优化模型流程如图1所示。

图1 基于时空聚类预测的共享单车调度优化模型Figure 1Optimal model of shared bicycle scheduling based on spatio-temporal clustering prediction

2.1 参数及符号说明

模型所涉及的参数与变量如表1所表示。

表1 参数、变量解释表Table 1Table of notations

2.2 网络聚类模型

2.2.1 时间聚类

用户不同时段的出行选择导致了需求高峰期以及低谷期的产生,引起时间维度上的供需失衡,因此需要探究区域单车使用需求在时间维度上所呈现出的稳定规律以及变化趋势,以预测某区域在特定日期的总体需求状况。

为了尽可能消除特殊样本对整体的影响,本文选择以一年为周期进行分析。本文参考WeiKl[35]对德国慕尼黑共享汽车需求情况的时段划分,根据用户出行时间选择的特点将一天分成七个时段(Time Slice),同时在两个时段之间留出了一个小时的间隔以满足调度所需的时间。选定某个时间段作为分析对象,通过聚类分析得到在该时段具有类似需求情况的日期的集合,以及不同集群中的日期情况、不同集群之间的需求均值差异等时间特征。

聚类分析算法可以分为划分聚类和层次聚类两个大类[36]。层次聚类主要包括聚合型层次聚类与分裂型层次聚类,而划分聚类算法需要预先指定聚类数目和聚类中心,将数据集分成若干互不相交的簇[37]。其代表算法是 k-means、混合密度聚类、图聚类、模糊聚类等。1967年提出的 k-means算法使同一类中的数据样本具有高度相似性,不同类中的数据样本具有高度的相异性[38]。该算法是一种基于距离的经典算法,因其效果优异、易实现且可解释性较强,被广泛应用于机器学习等领域,因此本文选择k-means聚类算法对时段内的需求数据进行划分,并将设定具体的K值。

为分析同一日期不同时段间的需求变化趋势,将当前时段与下一时段的聚类结果进行比对分析,判断当前时段的日期集群中在下一时段是否依然分布集中。如果分布集中,说明此部分日期需求呈现稳定变化趋势。例如,在当前时段某集群A(i)有85%集中在下一时段的集群B(j)中,则有理由认为B(j)有效地反映了A(i)中日期的需求变化趋势,并通过对比B(j)与A(i)中需求均值得到需求变化的趋势指数(Trend)。如果分布过于平均,则需要分析具体情况,如有必要则对集群中的样本分别进行计算。

图2 时间段划分图Figure 2Time division diagram

2.2.2 空间聚类

不同于时间特征,共享单车需求的空间特征则是由地区功能差异引起的。如同带桩共享单车网络设计时需要考虑基站的选址一样,无桩共享单车调度系统也需要考虑单车投放地点以尽可能满足用户需求。本研究通过投放地点所服务的地区间距离、需求情况相似度来确定投放地点以及服务范围。

进行空间聚类之前,首先需要确定集群的个数K值,这取决于运营成本与用户服务之间的权衡。当集群个数过多时,用户到达单车投放点的平均距离减少,用户服务水平提高,但过多的集群将增加调度成本。当集群个数过少时,用户则会因为投放点过远而放弃使用共享单车,转而选择其他交通出行方式。

为具体考量不合理的集群分类带来的负面影响,本文提出加入衡量集群划分是否合理的惩罚成本。假设若用户到取车点的距离distance(i)在[0,α],集群内潜在用户不会因为取车距离而产生放弃的意愿;若distance(i)在[α,β]范围内,潜在用户的放弃意愿将随距离增加而提高,且递增的速度上升。因此,以e为底的指数函数来描述两者之间的关系:当取车距离在[0.75,1.5]范围内时,用户的放弃意愿变化趋势如图3所示。步行距离越远时,在增加等量步行距离情况下,用户的放弃意愿上升速度越高。为了将这种放弃意愿的变化转换成对运营商的惩罚成本,加入惩罚系数s,并用归一化的方法处理该系数。如果取车距离超出了β,则认为几乎所有的用户都因为无法忍受过于远的步行距离而放弃使用共享单车。惩罚系数s定义如下:

图3 放弃意愿变化图Figure 3Change of willingness to give up

式中,λ是用户放弃意愿增长情况的参数。λ越小,则随着取车距离的增加,用户放弃使用共享单车意愿的增速较为平缓。λ越大,则用户在初期对取车距离增加的敏感性较低,但随着该距离的不断走高,用户的放弃意愿会出现爆炸式的增长。该惩罚系数的表达式反映了步行距离对用户使用意愿的影响。

在确定用户损失系数后,某单位区域的惩罚成本将表示为:

其中Penalty表示惩罚成本,p表示最高惩罚成本。

为了保证集群内部时间、空间属性的一致性,需要根据趋势指数将该地区划分成若干个需求变化特征一致的集群,在已有集群的基础上按照地理坐标的远近进行空间聚类。通过时空聚类产生的集群类似于传统共享单车系统中的基站,调度车将按照一定的顺序依次访问这些集群的质心,并完成期望数量的装卸任务。

2.2.3 需求预测

时空聚类产生的集群内部具有相似的需求变化趋势,可对此类区域进行集中预测。理想的共享单车预测数量应满足按正常趋势变化的需求,同时对可能出现的特殊情况有所准备,但趋势指数只反映了周期内需求变化的整体情况,需要对某些特殊需求情况进行处理。

令T表示集群的趋势指数,表示集群i内第j个单位区域在当前时段的需求,qt(i)表示集群i当前已有的共享单车,n表示集群包含的单位区域个数,dsp表示需求的特殊情况,那么集群i在下一时段的需求Dt+1(i)满足:

取其平均值:

在获得集群下一时段的总预测需求后,集群i的装卸数量表示为:

2.3 调度路径模型

调度路径模型的整体框架基于传统VPR问题的模型,但考虑到共享单车调度问题的独特性,在本文的调度模型中,调度成本增加了损失用户的惩罚成本。在实际操作中,运营商需要在规定时间内完成调度工作以即时满足用户的使用需求,因此模型对每辆车在每次调度任务中所能行驶的最长距离进行了限制。在聚类分析中,把每天划分成了7个时间段,而每个时间段之间的间隔将作为设定时间窗条件的依据。不同于基础的VPR问题,在共享单车调度问题中,每个节点不仅是需求方,也可以成为供给方。由于每辆调度车都有规定的容量上限,因此在调度过程中需要关注调度车的车载情况。

用Qv(i)表示调度车V在节点i的车载情况,车辆由节点i访问节点j,其中节点j需要装卸的单车数量为d(j),则调度车的车载量更新为Qv(j)=Qv(i)+d(j)。调度路径模型的目标函数和约束条件如下:

目标函数追求调度成本最低化。其中,调度成本由四部分构成:每辆调度车进行调度工作时的固定成本,本文假设所有调度车辆的车况相似,因此用统一的C0作为调度的固定成本;调度点之间的运输成本,该成本由调度车单位可变成本C1(燃料、车损等成本)和调度点之间的欧式距离决定;不合理的集群划分带来的惩罚成本,其中用户损失系数s的表示在聚类模型中已经说明;在集群内装卸共享单车的成本,每辆共享单车的装卸成本由C2统一表示。

约束条件:

公式(7)~(8)表示每次调度都必须由车场派车,且每辆调度车最终都必须回到车场。

公式(9)表示每个调度点只被分配一辆调度车。

公式(10)表示每个调度点一旦产生装卸需求,就必须被调度车访问以完成调度工作。

公式(11)表示在每个调度点完成装卸工作后,调度车都需要离开该调度点以继续调度任务。

公式(12)表示在调度过程中的任一时刻,调度车的装载量都必须在规定的合理限载范围内。

公式(13)表示进入某个需求点的调度车必定会从该点离开。

公式(14)保证调度路径中不会出现回路,避免无意义的重复调度。

公式(15)规定了每辆车在每日调度过程中的距离限制,该约束条件在一定程度上能避免不同工作组之间任务分配不一致而造成的公平问题,同时也能保证对调度车的合理使用。

公式(16)表示了调度车所载单车数量的变化。

公式(18)表示调度车分配情况的0-1变量,若yiv=1,则表示节点i由调度车v访问。

2.4 VPR优化算法

共享单车的调度问题本质上属于VPR(Vehicle Routing Problem)问题。作为一个NP-hard问题,VPR目前仍未找到有效的算法。为了找到可行的近似解,本文将采用贪心算法、遗传算法对前述模型进行求解。调度优化模型的目标是整体成本最小,其中惩罚成本、共享单车装卸成本是由聚类分析的结果决定的,因此在寻找优秀的路径时本节更关注的是决定调度可变成本的调度距离。两类算法的调度性能比较将在数值分析中进行详细说明。

2.4.1 可行性验证

对各算法选择的路径进行调度可行性验证,即是否满足调度车辆行驶距离限制和车容量限制的约束条件。为此,本文设计了流程如图4所示的RouteSort可行性校验,分为路径划分和车容量限制检测。提取测试路径集数据,输入总路径数组r、车容量限制threshold、各质心距离矩阵D、各质心到车场的距离DOF等信息,进行以下两类检测,最终输出该总路径的可行性与调度成本。

图4 RouteSort可行性校验Figure 4RouteSort feasibility check

1)路径划分。首先根据调度车行驶距离限制把每条路径分为若干部分,各部分即一辆调度车的访问路线,其次输出每组调度车访问调度点数量的索引。例如对于路径[6 5

3 2 1 4],划分产生的索引为[2 3 1],则第一辆调度车的调度路径为[6 5],第二辆车的调度路径为[3 2 1],第三辆调度车的调度路径为[4]。

2)车容量限制检测。模拟每条编码子路径的装卸活动进行判断。例如,当前调度车的初始容量为Q(0)=q,d(i)X表示在第i个节点的共享单车装卸量,则调度车在节点i的容量为:Q(i)=Q(i-1)+d(i)。如果Q(i)＞Qu,则退出该编码的检测,且设定该条编码的目标值为惩罚值INF。对于通过检测的合理编码,其成本可以通过目标函数计算获得。

3 数值分析

3.1 需求数据设计

为了模拟现实中共享单车需求变化的大致情况,本文设计了四种类型的需求情况来抽象反映不同功能区域的需求特性。在设计具体数据时,加入了一定的限制来使需求变化的特征更明显,虽然这与现实不完全符合,但本文更关注的是运营商如何利用需求的时空特征进行调度优化。以下是6:00至8 :30、9 :30至12 :00两相邻时间段的需求数据,通过两者的对比可以得出需求时间变化的趋势值。

3.1.1 工作日早高峰特征需求

由表2的数据可见,该类需求特征的区域在周一至周五的6 :00~8 :30时段有个明显的高峰值(不考虑节日与特殊情况的出现),而在9 :30~12 :00时段中,工作日单车需求则处于相对的低峰状态。与工作日不同,周末的需求状况表现出了截然不同的状况:用户需求在9:30~12:00迎来一个高峰状态。该需求模拟了城市中居民区的共享单车需求特征。在早高峰期间,大量用户选择使用共享单车以避免车辆拥堵,而到了上午的工作时间,留置在居民区的共享单车使用对象多数是非单车活跃用户的老人与幼儿。

表2 工作日早高峰特征需求表Table 2Demand with morning peak characteristics on weekdays

3.1.2 工作日午高峰特征需求

工作日午高峰需求表现出了与工作日早高峰需求完全相反的特征。如表3所示该类需求特征的区域在周一至周五的9 :30至12 :00时段有个明显的高峰值(不考虑节日与特殊情况的出现),而在6 :00至8 :30时段中,工作日单车需求则处于相对的低峰状态。在周末与节假日的时候,该类地区的需求处于持续的低峰状态。此类需求主要模拟了城市商业中心共享单车需求变化的特征。在工作日临近中午的时间段里,该区域办公的用户出于短距离外出办公、午间外出就餐等原因而产生了对共享单车的高峰需求。周末与假期的时候,大量用户因无工作任务安排而基本没有对共享单车的需求。

表3 工作日午高峰特征需求表Table 3Demand with noon peak characteristics on weekdays

3.1.3 平稳低峰特征需求

平稳低峰特征需求描述了类似于景区等共享单车平时需求较低的区域的需求特点。如表4所示,这些区域在平常的日期里人流量少,对共享单车的使用需求明显偏低。而到了节假日以及一些特殊的日子里,游客的大量涌入产生了高峰需求。

表4 平稳低峰特征需求表Table 4Demand with stable low peak characteristics

3.1.4 平稳高峰特征需求

如表5所示,该类地区平均需求高且在两个时段间的需求变化幅度小。此类特征的需求主要是对城市中人流集中区域情况的描述。持续的高需求也要求更高的用户服务水平,运营商需要对这些地区给予足够的重视与关注。

表5 平稳高峰特征需求Table 5Demand with stable high peak characteristics

3.2 聚类分析

3.2.1 共享单车网络模拟

进行调度前,需要确定每个区域现有的单车数量以及质心位置。本文通过MATLAB的随机函数模拟了一个大小为3 km×3km的地区的单车网络分布情况,将该地区划分成36个0.5km×0.5km大小的单位区域,图中的实心点代表了网络中单车的分布情况。在某些区域单车密布较为密集,而有些区域分布则较为稀疏,造成这种密度差异的重要原因是在当前时段用户使用单车的路径具有一定的指向性。如工作日午高峰需求特征的地区在6:00 - 8:30时间段主要是用户的目的地,因此单车的分布密度较大。图中的圆圈代表该地区单车分布的质心,它将代表该区域作为接下来时空聚类的输入。

图5 共享单车分布网络图Figure 5Distribution network of bike sharing

3.2.2 时间聚类

时间聚类的目的是将单车网络划分成若干个集群,且这些集群内部各区域的需求变化趋势相似。本文以各区域当前时段的需求以及趋势指数为指标,根据需求数据设计中不同特征需求的数量,采用k-means聚类的方法将对象地区划分成了4个集群。提取各区域时间特征并进行聚类后的具体结果如图6所示,Origin表示车场的位置,该区域聚类结果中共有4个集群,图中“∗”代表集群质心,不同形状点代表不同聚类类别,同时加以边缘线划分。在该聚类结果中,集群内部空间分散,且集群之间有较大面积重叠。显然,仅按照时间特性分类是不理想的,集群之间的重叠导致了各投车点(即集群质心)所服务区域的重复,造成了资源浪费。不仅如此,处于集群边缘区域的用户会因投车点过远而放弃使用共享单车,此类用户类型的流失对于运营商来说是不可原谅的,这也是上文强调惩罚成本的原因。考虑到上述因素,本文将在时间聚类的因素上进行空间聚类,从而使集群的分布更为合理。

3.2.3 空间聚类

现有的信息无法确定空间聚类的合理集群数量,因而本文提出通过在目标函数中加入惩罚成本的方法来确定最优集群数量。通过MATLAB编程,本文设计了一个以集群个数为条件的循环结构。为了减少运算量,本文认为每个集群区域的最小个数由α决定,因为当集群内部各区域到集群质心的距离小于该值时,惩罚成本将不再产生,且当该距离过小时将会增加调度的运营成本,因此当集群数量超过特定的值后,成本将增加。以集群数量为9的一种聚类结果为例,其具体聚类结果如图7时空聚类结果图所示,Origin表示车场的位置,图中共有9个集群。对比图6、图7,可以看出相较于仅使用时间聚类,时空聚类的结果重叠面积显著下降,每个集群内部各区域的时间趋势相似,且各集群区分明显。

图6 时间聚类结果图Figure 6Results of temporal clustering

图7 时间+空间聚类结果图Figure 7Results of temporal and spatial clustering

特别要说明的是,该聚类结果是遗传算法求解得出的收敛结果。前文2.2.2部分曾讨论过如何决定最佳的集群数量,这是运营商调度成本与用户服务水平之间的权衡,当集群数量过少时,不合理的取车距离会造成高昂的惩罚成本,而过多的集群数量则意味着更高的调度成本,从先前的推断来判断,该最优化结果显然是合理的。不仅如此,这也证明为了降低运算量而减少可能的聚类情况的做法是可行的。

3.3 调度路径模拟

3.3.1 参数设计

本文引入了贪心算法和遗传算法解决VPR问题,使用这两种算法分别对调度路径优化模型求解并进行对比。在求解最佳路径之前,需要整理出车场与节点、节点与节点之间的欧式距离矩阵。

表6展示了集群数量为8时的各节点之间的距离矩阵,其中O表示车场,节点1-8表示8个集群质心锁在的位置。为了避免各节点到自己的距离对搜索的影响,将这些距离设置为极大值INF,其他聚类结果的距离矩阵算法与表6一致。

表6 集群数量为8的距离矩阵Table 6Distance matrix of 8 clusters

在接下来的部分里,本文将对表7中的参数组合下贪心算法、遗传算法的求解结果进行详细地说明,并对各算法进行成本优化效果方面的对比。

表7 参数组合表Table 7Combination of parameters

3.3.2 实验结果分析

使用设计算法以模拟的数据为样本对调度优化模型进行求解,算法得到的VPR路线图结果如图8所示,表8则详细展示了算法收敛解的调度路径情况以及调度车载重量的变化。

表8 各算法调度路径结果Table 8Path results scheduled by various algorithms

图8 各算法调度路径图Figure 8Paths scheduled by each algorithm

(1)贪心算法

贪心算法(又称贪婪算法)是指,在对问题求解时,以追求当前最优解为目标。在调度优化模型中,目标函数追求整体成本最少,其中惩罚成本、共享单车装卸成本是由聚类分析的结果决定的,因此在寻找优秀的路径时更关注的是决定调度可变成本的调度距离。贪心算法在对问题进行求解时总是以到当前节点的欧式距离最短为依据寻找下一个访问节点,因此共享单车的调度路径将在对节点的搜索中直接形成而不存在优化的过程。

贪心算法所得解出现在[1,3,3,2]聚类结果中,最低的调度成本为213.6。运营商需要派出3辆调度车分别以[车场,5,3,车场],[车场,6,1,车场],[车场,8,7,9,2,4,车场]的路径访问共享单车网络。图8(a)详细展示调度车的路线图。在载重方面,三条路线的调度车载重量都在合理的范围内。其中访问8、7、9、2、4这五个节点的调度车需要从车场携带7辆共享单车来补充不足,访问6、1两节点的调度车则需要从车场携带6辆单车。

(2)遗传算法

不同于贪心算法,遗传算法的求解是个不断优化的过程,通过概率化的寻优方法,展现出强大的全局搜索能力。使用遗传算法,所得收敛解的调度成本为189.14,出现在集群数为9的聚类结果[1,4,3,1]中。运营商只需派出2辆调度车,调度车的调度路线图的结果如图8(b)。通过比较,可以发现遗传算法得到的最优调度方案的成本明显优于贪心算法得到的调度方案的成本,这与预想一致,贪心算法虽然每一步都做出了当前最优的选择,但却失去了全局优化的能力。结果显示,遗传算法在各个聚类情况下都得到了明显优于贪婪算法的调度路径收敛解,说明了全局优化算法在寻找最佳调度方案中的强大能力。

3.3.3 集群数量分析与算法比较

(1)集群数量分析

合理的集群的数量是调度成本以及用户服务权衡的结果。当集群个数过多时,用户到达单车投放点的平均距离减少,服务水平提高,但过多的集群将增加调度成本;当集群个数过少时,每个投车点需要服务的区域过大而导致用户则会因为投放点过远而放弃使用共享单车,转而选择其他交通出行方式。

为了探究集群数量的变化和不同聚类对调度结果产生的影响,本文设置了不同的K值进行数值模拟,具体的结果下表所示。表9所示是仅使用时间聚类和时空聚类产生的最低成本对比;表10中展示了不同集群数量划分情况下,重复进行k-means时空聚类分析并进行求解调度路径,取最优解和平均解。只考虑时间聚类的情况下,集群数量较少,由于服务区域内用户距离单车投放点位置较远,导致潜在用户的流失带来相应的惩罚成本,因此贪心算法总的调度成本达317.87,比最低成本高出48.82%;而当集群数量为11时,调度总成本为222.78,调度资源的浪费增加了约4.3%的成本。类似的,在遗传算法中,仅使用时间聚类方法,当集群数量为最小值4时,运营商需要付出的调度成本为313.97,比时空聚类后的最低成本高出66%;而当集群数量设置为最大值11时,成本则为206.14,更多的资源如调度车、工作人员的投入以及访问点的增加导致了8.99%的成本增加。

表9 不同聚类方法最优解比较Table 9Comparison of optimal solutions of various clustering methods

(2)算法性能比较

通过比较两类算法的调度方案结果及其所需总运营成本,虽然贪心算法求解方案明显不如遗传算法,但本文依然想探讨各种算法在求解不同聚类结果时最优调度路径时候的整体表现。

表10展示了两类算法在不同聚类结果中优化的成本情况。从总体表现来说,贪心算法对路径的优化明显不如遗传算法,但在某些情况下,贪心算法获得与启发式算法一样的优化结果,如集群数为7时,两种算法得到的最低成本相同。贪心算法在每一步做出的选择仅仅是当前最佳,但从全局来看并不一定最优,因此它虽然能在特定情况下获得与其他算法一样优秀的调度路径,但其整体效果有所不足。不同于贪心算法,遗传算法具有优秀的全局搜索能力,求解过程中该算法对解的构造与保留是概率性的,因此其收敛解与最优解的差异是可以接受的。

表10 基于时空聚类的算法调度路径结果分析Table 10Analysis of scheduling path results based on spatio-temporal clustering algorithm

在求解速度方面,由于贪心算法通过各阶段寻优即可得到最优解,因此求解速度明显快于遗传算法;在算法稳定性上,由图9与表10对比了两种算法在设置不同K值下平均解偏离的情况,K值即k-means聚类分析中预设的质心数,同时表示单车调度集群数量,K值设置过高将提高调度成本,过低将导致用户流失、收入降低。因此K值过高/过低情况下,使用不同算法求解得到的聚类分析结果中可行解成本普遍偏高,导致平均解偏离程度低。而K值设置适中情况下,聚类分析结果差异成为主要影响因素,较依赖于聚类中心初始化,多次聚类后的单车集群方案呈现较大差异,导致两类算法的平均解偏离程度均较高。另外,实验结果可以看出相对于启发式算法,贪心算法更容易受到聚类结果波动的影响。

图9 算法在不同聚类情况下的稳定性比较Figure 9Comparison of the stability of each algorithm under different clustering methods

此外,本文也使用模拟退火算法得到了不同的聚类结果优化后的调度成本情况,在求解质量与求解稳定性上,模拟退火算法的总体平均解为240.795,总体平均解偏差为7.394%,与遗传算法趋近,稍劣于遗传算法。但在求解速度上,遗传算法收敛迭代次数稳定在20次以内,而模拟退火算法需要约40次迭代才能找到收敛解,可见在本文的研究问题中遗传算法在其收敛趋势、收敛速度上展现出较大优势,优于模拟退火算法,因此本文仅展现遗传算法的结果。

4 结论与展望

本文利用共享单车需求的时间、空间特征,通过k-means聚类的方法构建了共享单车网络模型。在产生虚拟基站的基础上,共享单车调度问题转化成了有时间窗与载重量限制的VPR问题,提出在以成本最小的目标函数中增加了一项因集群划分不合理而产生的惩罚成本,构建了调度优化模型,并使用了贪心算法和遗传算法两类算法求解,并生成数据进行模拟实验,验证模型及算法的有效性。

本文所得的结论带来了如下管理启示:①合理的集群数量是用户服务水平与运营商调度成本权衡后的结果,如何确定调度时的访问对象是处理共享单车调度优化问题需要首先关注的问题。本文通过构建惩罚成本来寻找这个权衡的平衡点,通过一系列的比较得出最合理的集群聚类,相较于其他的聚类结果在成本上有明显的优化。共享单车运营商需要了解用户对于本公司提供的共享单车服务的粘性与满意度,确定合适的调度集群数量以通过降低调度成本来获得竞争优势。②启发式算法在优化调度路径时展现出了足够优秀的能力。贪心算法按照当前最佳选择的原则进行路径构建,能够在最短的时间内获得合理的调度路径。遗传算法则按照一定的规律对生成的初始解不断地进行构造,通过概率化的寻优方法来获得优秀的解。相比于另外启发式算法而言,贪心算法虽然在求解时间上具有很大的优势,但其整体优化的效果稍显不如,运营商在选择算法时需要做出时间与准确性之间的权衡。

现阶段国内外的研究重点集中在基于运营商的调度方案中,而对于激励用户的调度方案有所忽视。运营商派出调度车访问个节点在时间上已经有所滞后,对于调度期间的需求无法迅速做出反应,如果能通过一定的激励来引导用户的行为以保证资源的合理分配,会有更好的时效性。所以,未来关于共享单车调度优化的研究应该给予基于用户的调度更多的关注,研究定价、规则等在引导共享单车用户主动调配资源方面发挥的作用。