基于双层禁忌搜索算法的共享单车再平衡问题

吕 畅，张超勇+，张道德，任亚平，孟磊磊

(1.华中科技大学 数字制造装备与技术国家重点实验室，湖北 武汉 430074；2.湖北工业大学 机械工程学院，湖北 武汉 430068；3.聊城大学 计算机学院，山东 聊城 252059)

0 引言

共享单车系统(Bike Sharing System, BSS)1965年起源于荷兰，是一种低碳环保的出行方式。国内近10年发展势头猛烈，由其衍生而来的共享电动车，共享汽车也开始进入人们的视线。但无论如何变化，共享单车的再平衡问题(Bike Sharing Rebalancing Problem, BSRP)，即如何解决各个共享站点供需平衡﹑降低再平衡作业成本提升作业效率，是BSS亟需解决的关键问题之一。与一般的路径规划问题相比，BSRP需要在每一个站点处进行放置或取走多少数量货物的决策，由于调度货车载量的限制，该决策又势必影响到访问站点的选择，极大增添了问题的复杂度。Ho等[1]在2014年已证明BSRP属于NP-hard问题，由于该问题具有重要的理论和实际应用价值，受到社会以及学术界的广泛关注。

实际的BSS通常规模大、站点数量多、仓库不唯一，所需调度车辆较多，但若减少调度车辆，由于车载上限，将导致多次往返，增加行驶路程。因此，允许站点临时停靠以及多次访问，极大增添了再平衡作业模型的灵活性，Chemla等[2]建立了允许站点的临时停靠以及多次访问的共享单车再平衡问题的数学模型，并获得了不错的效果；Erdogan等[3]所提出的模型也允许多次访问和临时停靠，并通过精确算法获得60站点内的最优解。

站点分组访问的思想源于Baldacci等[4]所提出的集群车辆路径(Grouping Vehicle Routing Problem, GVRP)模型，在该模型中站点被分为不同的站点族，每辆调度货车必须访问每个族内的至少一个站点。Battarra等[5]2013年提出CVRP模型，将其访问形式作了调整，规定调度货车必须将该站点族内所有站点全部访问后才能进行下一个族的访问。Forma等[6]将该分组思想成功应用到了BSRP中，3-step中的第一步便是根据站点的距离以及库存特性生成站点族，其模型以及解决方案能获得125站点以内的较优解。国内学者叶锦程等[7]也提出了类似的分组访问模型——子群划分，较好地减少了调度点数量以及调度路程。类似于站点的分组访问，分类访问则是根据站点实际库存和目标库存之间的关系将其分为不足﹑过饱和和平衡站点。2014年Ho等[1]将该分类访问方式应用于BSRP，通过禁忌搜索(Tabu Search, TS)求解取得了不错的效果，并在2016年[8]结合站点之间路径的相关性提出了基于贪婪随机自适应搜索(Greedy Randomized Adaptive Search Procedure, GRASP)的求解模型，2017年[9]对该访问模式进行了少许改进，规定并非所有过饱和站点都必须访问，并结合混合大邻域搜索(Hybrid Large Neighborhood Search, H-LNS)进行求解，效果显著。

成本是衡量一个运作系统好坏的重要指标。在BSS再平衡作业中，单车的库存成本对整个作业成本的贡献不亚于运输成本。Lin等[10]提出针对交通共享系统的中心位置库存(Hub Location Inventory, HLI)模型，在解决实际案例时能较好地降低作业总成本，同时大大提升了BSS的服务水平。RAVIV等[11]也给出了关于BSS的库存模型设计，通过数学建模求解验证了其可行性。Lin等[12]将系统的服务水平加入了模型的约束中，提出了结合服务水平的目标函数。除了效率和成本，Caggiani等[13]还将客户满意度加入到了目标函数中作为衡量标准。2016年，Alvarez-Valdes等[14]提出了针对BSS系统服务水平的评价体系，并通过该评价结果进行了相应的再平衡作业调度，获得了低成本高满意度的调度方案。王涵霄等[15]提出了考虑共享单车临时故障的调度模型，并结合调度满意度概念，通过蚁群算法求解，获得了不错的效果。

近几年BSS规模不断扩大，对应的再平衡作业规模也随之扩大，针对大规模问题，研究者们也提出了适应性的新算法与新思路。Raidl等[16]通过变邻域搜索(Variable Neighborhood Search, VNS)算法结合最佳装载(Optimal Loading Operations, OLO)策略给出了不错的站点结合性邻域结构，局部优化效果显著。Gaspero[17]通过新型约束规划结合蚁群算法，Rainer-Harbach等[18]通过VNS结合变邻域下降(Variable Neighborhood Descent, VND)，Chemla等[2]通过Branch-and-Cut结合TS，分别对该问题进行了求解，均获得了不错的效果。Dell’Amico等[19]将分支定界结合整数规划应用于解决该问题，并测试了众多标准实例，验证了其可行性。更进一步，Nair等[20]将“瓶颈”的思想融入了大规模BSS的运作中，将各个站点的不平衡通过双向流的作用形成互补，极大地降低了调度作业的成本。陈桂英等[21]通过一种资源应急调度方法对BSS模型进行改善，并将模拟退火机制引入遗传算法对该问题进行求解，获得低成本应急调度方案，有效提升了BSS服务水平。

由于大规模BSRP需要进行调度的站点较多，调度货车数量与周转库存均显著增加，导致作业成本大幅上升，且线路规划复杂。已有研究大多基于求解算法的创新，在求解模型的改进方面研究甚少。因此，在解决大规模问题时，多数已有模型与相应算法明显乏力。本文面向大规模共享单车问题，提出一种基于站点供需状态的分块策略及其相应双层禁忌搜索算法(Double-Layer Tabu Search, DL-TS)。在提出策略中，基于站点供需的配对模式有效降低了周转库存，基于调度货车载量上限的线路规划方式有效减少了作业所需车辆，严格的分块访问模式极大地简化了调度线路规划的复杂度。对分块后的站点集进行内外两层的禁忌搜索，并在其中加入一个变异算子用于两层之间的信息交流。

1 共享单车再平衡问题描述及建模

1.1 问题描述

该问题的物理模型描述如下：规定区域内有若干共享单车取用站点(station)，用集合S={0,1,2,…,n}表示，其中S0为车库。根据规划时的数据统计和调查，每个除S0以外的站点Si都有预先设定的目标需求量qi，经过一天的客户随机取用归还后，每个站点的自行车数量pi会与目标需求量qi有所差异(demand)，用di表示，di=pi-qi。di>0，则Si站点过饱和，需要移出di辆自行车；di<0，则Si站点不足，需要补充di辆自行车。进行调度作业的是标准运输货车(vehicle)，用集合V={0,1,2,…,m}表示。每辆货车的载量上限Q已知。在整个调度作业过程中，每辆作业货车的实时载量e必须满足0≤e≤Q。站点i到站点j之间的运输距离Dij已知。单位运输成本包括路费﹑燃油费等，与路程成正比，用C1表示，C2为自行车的单位库存成本，C3为货车的单位使用成本。再平衡作业就是通过货车从车库S0出发经过有需求的站点，使其达到供需平衡，最后回到车库，同时将运输和库存费用降至最低。本文不考虑多次访问和临时停靠等问题，每一个站点只能被一辆货车访问一次，且尽可能使该站点达到平衡，没有需求的站点(di=0)禁止访问。

1.2 问题模型

首先定义一个0-1变量：Aink：当站点i是货车k的第n个访问站点时(n∈P)，Aink=1；否则，Aink=0。其中P为访问路段，P={0,1,2,…,N+1}，0为起始路段，N+1为返回路段，N是该货车该次访问的站点数。

多辆标准调度货车同时作业，每个有需求的站点仅访问一次，在不使货车超载的条件下尽可能使该站点达到目标需求qi。目标函数以及相关约束可表示如下：

min

C2ek)+C3K。

目标函数(1)中第一项为行程消耗成本，第二项为库存成本，第三项为货车调用成本，通过对站点和路段的依次求和，对满足AinkAj(n+1)k≠0的路段，即实际作业行驶路段，进行成本计算求和，ek表示货车k初始载量。约束(2)保证了每一个站点只能被一辆货车访问一次；约束(3)保证了一辆货车在一个时间段中最多只能出现在一个站点；约束(4)保证了每辆货车在尚未访问紧前站点之前不允许访问其下一站点，即不允许跳过访问，这是多车模型中避免遗漏访问的约束手段；约束(5)和约束(6)保证了每辆货车从车库S0出发，之后还要返回车库S0一次；约束(7)保证了每一辆货车在整个调度作业过程中的载量不超过上限Q；约束(8)和约束(9)分别对ek和Aink进行了说明。

1.3 目标函数

本文通过站点的需求状态进行站点分组，生成站点族，并且通过所设计的分块算法使得生成的站点族内部可以自给自足，因此将每一个站点族称为“零需”站点集，用xdpi表示，下一节将对其生成方式进行详细介绍。对于每一个“零需”站点集xdpi，保证其由一辆调度货车完成作业，因此只需对“零需”站点集xdpi进行访问路线生成。

单车作业成本函数：

(10)

多车作业成本函数：

(11)

本文对“零需”站点集xdpi的提出，使得∑ek趋近于“0”，库存成本不用考虑；同时，单车﹑多车作业均是以xdpi为单位展开的，∑D不会有较大差异。因此，最终导致两者成本较大差异的就是多车中的货车调度成本C3K。若只考虑成本函数(11)，显然调度车辆数K越多，成本越高，因为式(11)没有考虑调度作业的时间成本。很多调度项目，不仅对作业成本有要求，还对作业时间有要求，而多车作业在本文所给出的算法中显然能降低作业时间，因此在作业时间较为紧张时采用多车同时作业模式。

2 基于站点供需的分块策略

本文通过站点需求配对策略所生成的“零需”站点集，有效地避免了每一个站点处进行放置或取走多少数量单车的决策，极大地降低了问题的复杂度。具体思想是在站点分类访问的基础上，将分类后的站点进行需求配对，形成“零需”站点集。在该站点集内，通过相互调度达到每个站点的目标需求而无需外界干预。因此，在理论上，调度货车在对该站点集进行再平衡作业时无需携带单车，作业完成后也不会有剩余单车携带，从而可以直接进行下一个站点集的访问。该种分类访问的理论依据是：系统运行之初，各个站点均处于供需平衡状态，理想状况下，整个BSS的单车数量是不会变化的，有站点不足必定有站点过饱和，而总的供需关系是平衡的，由此将整个系统划分为一个个可以自给自足的“零需”站点集，调度货车只需搬运，无需提供或移出单车，这就使得理想状况下，周转库存可以设置为零。但考虑到实际系统运作中，存在部分共享单车未按库停放以及报废等意外情况，应结合实际数据统计设置一个根据系统总规模按一定比例生成的安全周转库存，保障意外情况下系统的正常运作，由于安全周转库存对总成本影响极小，本文不对其作具体设置。标准案例求解结果显示，在该策略下，原库存量减少达80%以上。

2.1 解的表达方式

分块算法中，解的表达较为简单，采用基于调度货车和站点的编码方式，例如：调用编号为1的货车V1依次访问站点3﹑站点2﹑站点5﹑站点4﹑站点1，则解x={V1|S3，S2，S5，S4，S1}，其中第一位为货车编号，后面为按访问顺序依次排列的站点编号。在算法部分将进一步详细介绍本文编码和解码方式。

2.2 分块策略算法步骤

分块策略算法具体步骤如下：

(1)根据调度作业开始时各个站点的状态将站点分为3类：piqi，即需要移出(pick-up)共享单车站点集合Sp；pi=qi，即供需平衡(balanced)的站点集合Sb，无需访问，如图1所示。

(2)分别对站点集合Sd和Sp内所有站点随机选择起始站点S1，通过基于距离的贪婪搜索算法进行旅行商问题(Traveling Sales-man Problem, TSP)求解，生成单条总链Xd和Xp,如图2所示。

(3)对Xd(Xp)进行切断操作。从每条链的起始站点S1开始，依次计算访问站点需求度之和T，当访问下一站点将导致T>Q时，由此处切断Xd(Xp)，T初始化为0，继续访问下一站点，直到单链Xd(Xp)被分割成一系列需求度近似为Q的子链xdi(xpi)，如图3和图4所示。

(4)计算每条子链xdi(xpi)的站点几何中心(center)坐标xdic(xpic)(式(12))，即每条子链xdi(xpi)内站点坐标的均值作为其几何中心坐标，如图5所示。

(12)

(5)用几何中心坐标xdic(xpic)代表子链xdi(xpi)进行一一配对，每一个xdic选择距离自己最近的xpic配对，xdic+xpic=xdpic，即xdi+xpi=xdpi，由xdpic所代表的站点集xdpi即为“零需”个体集(生成i个“零需”个体集)，如图6所示。

每一个通过该方法生成的“零需”站点集均可仅由一辆标准作业货车完成再平衡作业，即在整个作业过程中车载不会超过载量上限Q。因为|Txdi|≤Q,|Txpi|≤Q，而Txdi,Txpi异号，所以在“零需”站点集xdpi内的任一访问次序的实时需求度之和Txdpi都将满足|Txdpi|≤Q。

3 双层禁忌搜索算法(DL-TS)求解共享单车再平衡问题

较大规模的BSRP站点数量一般在100个以上，其调度作业货车和仓库数量一般不唯一。由于该问题的NP-hard特性，其决策复杂度和计算复杂度急剧上升。本文所提算法针对较大规模问题，主要思路便是将整个优化问题划分为许多各自相互独立的子问题，即本文所提出的“零需”站点集xdpi，利用TS高效的局部搜索能力，最优化每个子问题，获得每个“零需”站点集xdpi内部的最优调度路线；再对优化后的“零需”站点集xdpi进行访问排序，从而给出整体调度路线的最优解。所设计的双层禁忌搜索，内层针对“零需”站点集内部调度路线的优化，外层针对“零需”站点集访问路线的优化；设计的变异算子用来提升各个子问题之间的交互作用，根据当前解的实际情况对之前的“零需”站点集分块进行微调，以获得最优解。该改进算法类似分治思想，化大规模问题为相互独立子问题，将子问题和总问题分别分配给相互独立的两层算法同时由变异算子进行联系，极大地降低了原问题的计算复杂度。

3.1 编码

本文提出的双层禁忌搜索算法解的编码分为内层和外层，即“每个零需站点集xdpi内部站点”和“所有零需站点集xdpi”两层，均采用自然数编码。

(1)内层 针对每个“零需”站点集xdpi内部站点访问排序，采用基于调度货车和站点的编码方式，即如果编号为1的调度货车V1需要访问编号为1～5的所有站点，访问的顺序为站点4、站点1、站点3、站点5、站点2，则可得到解x={V1|S4，S1，S3，S5，S2}，其中第一位为货车编号，后面为顺次排列的站点编号，当未确定访问货车编号时，首位置为0。解码过程为编码的逆过程，即如果获得解x={V2|S7，S9，S6，S8}，则表示编号为2的调度货车V2顺次访问站点7、站点9、站点6、站点8。

(2)外层 针对全部“零需”站点集xdpi访问排序，采用基于调度货车和“零需”站点集xdpi的编码方式，即如果编号为1的调度货车V1需要访问编号为1～5的“零需”站点集xdpi，访问顺序为xdp3、xdp2、xdp1、xdp5、xdp4，则可得到解X={V1|xdp3，xdp2，xdp1，xdp5，xdp4}，其中第一位为货车编号，后面为顺次排列的“零需”站点集xdpi编号，当未确定访问货车编号时，首位置为0。解码时，如果获得解X={V2|xdp7，xdp9，xdp6，xdp8}，则表示编号为2的调度货车V2顺次访问“零需”站点集xdp7、xdp9、xdp6、xdp8。

3.2 初始解生成

内层初始解x0i生成方式为：对于每一个站点集xdpi，在其内部进行基于距离的贪婪搜索生成内部站点的访问序列作为初始解。外层初始解X0生成方式为：以每一个站点集xdpi中心坐标xdpic代表其地理位置，进行基于距离的贪婪搜索生成站点集xdpi的访问序列作为初始解。

3.3 算法设计

(1)邻域结构

1)2-opt算子。“零需”站点集xdpi内相邻顺次访问的两个站点之间(Sa，Sb)交换访问次序，如图7所示。

2)贪心移位算子。随机选择xdpi内一站点Srand，将xdpi中距离该站点最近的站点Snear移位至Srand的紧邻访问站点位置(Srand，μ)，包括紧前(Srand，-1)或紧后(Srand，+1)，如图8所示。

(2)禁忌对象

将移动属性作为禁忌对象，对于2-opt算子，禁忌对象为(Sa，Sb)；对于贪心移位算子，禁忌对象为(Srand，μ)。

(3)特赦准则

1)当前邻域中的被禁移动将产生历史最好解时，破禁。

2)当前邻域中所有移动均被禁时，选择剩余禁忌步长最短的移动进行破禁。

(4)禁忌列表和禁忌长度

禁忌列表长度指被禁忌解的个数以及被禁忌的步长，该长度设置直接影响到算法跳出局部最优和快速收敛的能力。因此，本文将根据xdpi的规模和特性动态的设置禁忌表长度。

(5)变异算子

本文设计的变异算子作用于两个不同的“零需”站点集，对满足变异条件的站点集进行内部站点随机交换操作，生成两个新的“零需”站点集。具体内容如下：

(13)

(6)评价函数

对于每个xdpi通过TS生成解的评价由评价函数式(14)计算，即生成解所对应访问线路长度之和的倒数：

(14)

3.4 算法流程

(1)“零需”站点集xdpi作业优化流程

1)由式(15)计算每一个“零需”站点集xdpi的几何中心坐标xdpic，即每个“零需”站点集xdpi内站点坐标的均值作为其几何中心坐标：

(15)

2)以xdpic坐标代表xdpi，通过本文所提出的TS对所有xdpi进行访问线路求解生成其最优访问路线XB。

3)在每个“零需”站点集xdpi内部，通过本文所提出的改进TS进行求解，生成内部最优访问路线xBi。“零需”个体xdpi内部起始站点通过遍历每一个内部站点S从中选择使得内部访问总线路di最小的点作为最优随机起始站点SS，由此产生的结束站点为Se，通过SS生成的访问路线作为xBi。

4)由式(13)进行变异操作判断，满足则进行变异操作，产生较优解则替换原有解，否则不变异。

5)实际线路解Xa生成。将由XB确定的“零需”站点集xdpi间的连接路线换成xdpi内部站点SS与Se之间的路线，根据每个xdpi个体内部最优访问路线xBi，计算最终总体实际线路解Xa长度之和LXa(如式(16)所示)及该线路下作业总成本W。

(16)

“零需”站点集xdpi作业优化实现伪代码如下：

算法2改进TS生成的访问顺序

输入：由分支定界算法获得的W的下界WLB和w的下界wLB

1：Construct XB

Calculate all xdpic

X0=GreedySearch,W0=W(X0),X*=X0,W*=W0

While W*>WLB

End if

End while

Return XB

2：Construct xBi

Set i=1

While i

Do x0=GreedySearch,w0=w(x0)

Set x*=x0,w*=w0

While w*>wLB

End if

End while

End while

Return xBi

(2)算法总体流程

本文所提出的双层禁忌搜索算法可分为两部分：

1)基于供需关系对站点进行分块形成“零需”站点集xdpi。

2)基于DL-TS算法的各个站点族内部访问线路生成以及针对xdpi个体的总路线规划。

步骤1基于站点供需的分块算法生成“零需”站点集xdpi。

步骤2以xdpic坐标代表xdpi，对所有xdpi进行求解生成其初始访问路线X0。

步骤3在xdpi内部选择随机初始站点，依据基于距离的贪婪搜索算法生成xdpi内部初始解x0i。

步骤4根据式(14)计算解的适值函数，判断是否满足终止条件，满足则转步骤8，否则转步骤5。

步骤5对每一个xdpi的初始解x0i采用本文所设计的TS算法进行内部优化使其达到内部最优解xBi。

步骤7计算变异后的xdpi和xdpic，并对变异后的xdpi进行求解，生成其改进访问路线Xi，返回步骤4。

步骤8算法结束。

4 实验结果及分析

本文测试实例采用国外标准案例——法国巴黎的Vélib共享单车系统。本文选取了其中150个常用站点，获取其相对地理位置﹑站点容量以及平均供需量等必要信息。该标准案例为大规模BSRP实例，其调度货车及车库均不唯一，且该实例已经过国外众多学者测试，其中近五年来较为成功的有文献[4]和文献[9]等。

在实验中，目标函数下界采用分支定界获得，在CPLEX 12.7软件运行；双层禁忌搜索算法采用C++语言进行编译，在Microsoft Visual Studio 2013上运行，计算机处理器Intel(R)Core(TM)i5-4200H CPU @2.80 GHz,RAM8.00 GB。本文测试的样本分类如下：站点规模n：20/40/60/80/100/125/150；货车载量Q：15/25/45；货车数量K：1/2/3。

双层禁忌搜索算法参数设计如下：相关参数设计依赖于具体问题规模n0，在内层搜索中n0为每个站点集内所含站点的个数；在外层搜索中，n0为站点集的总个数。根据本文具体问题规模和货车载量Q的实际情况，供需策略分组后生成的n0范围均在30以内，因此设计最小禁忌步长Lmin=3，最小迭代总次数Itermin=1000，无改进最大迭代次数Iterno=100。动态参数设计，禁忌步长L=Lmin+[n0/5]，迭代总次数Iter=Itermin+100[n0/5]，其中[x]表示不超过x的最大整数。

4.1 实验结果分析

如表1～表3所示分别为单车实验测试、多车实验测试和综合实验测试结果，具体内容包括分支定界算法获得的目标函数下界(LB)、DL-TS算法获得的目标函数值及其与LB之间的Gap值、DL-TS算法的Cpu平均计算时间，并且给出了对比算法GA-TS求解相同案例获得结果的Gap值以及Cpu平均计算时间。其中目标函数下界(LB)是通过分支定界算法在2 h内给出的，当站点规模n超过100时，分支定界在2 h内已无法给出最优解，而提出DL-TS算法能在100 s以内获得较优解。

表1 单车实验求解结果(C1=0.001，C2=0.5，C3=10/15/20)

续表1

表2 多车实验求解结果(C1=0.001，C2=0.5，C3=10/15/20)

表3 单车和多车实验结果综合比较(C1=0.001，C2=0.5，C3=10/15/20)

续表3

表中参数说明如下：

n为站点规模即站点数量；

Q为度作业货车载量上限；

K为调度作业货车数量；

LB为分支定界在CPLEX上运行2 h内获得的目标函数下界Lower Bound；

W为目标函数值；

Gap为W与LB的百分差；

Cpu为算法求解时间，单位:s。

影响目标函数以及Cpu耗时的自变量包括站点规模n、货车载量Q、调度货车数量K。站点规模对目标函数以及Cpu的影响是显而易见的，由表1～表3均可看出，n越大，W以及Cpu越大，且由于该问题的超NP-hard特性，普通算法在解决该问题上消耗的Cpu与n呈指数级别的增长(如分支定界，线性规划等)。本文在启发式算法基础上，进一步利用供需关系将大规模问题进行分块求解，使得Cpu随问题规模增加而急速上升的指数型增长趋势转化为了线性型增长趋势，大大提高了算法的效率。对于100以内的站点，能在较短的时间内获得解，并通过与分支定界下界的求解(LB)比较，能证明其为最优解；当n超过100时，分支定界已无法在2 h内给出结果，将其在2 h内获得的LB与DL-TS算法获得结果进行比较，Gap均小于5%，DL-TS算法消耗Cpu始终在100 s以内。如图10所示显示了作业规模n对算法Cpu的影响。

对于调度货车载量上限Q，许多学者在该问题的求解上并没有过多考虑其对调度作业的影响，如Forma等[6]仅考虑一种标准作业货车，也是有一定道理的，毕竟同一地区的作业货车一般为同一型号。本文将其作为一个重要自变量，并分为15/25/45三种载量上限，一是由于本文站点的分块与Q关系紧密，二是调度所用货车的载量上限Q对于调度作业确实具有较大影响，大致可概述为Q越大，成本目标函数W越小，当在大规模作业时(n>80)尤为明显；但在小规模作业时(n<60)反而会出现Q越大，成本目标函数W越大的情况，尤其是多车作业(如表2)。这是由于Q增大，货车在调度过程中不易达到载量上限而不用返回车库，在本文的分块算法中表现为“零需”站点集xdpi规模更大，个数更少，减少了货车往返次数。但Q增大意味着调用成本C3更大，因此需要根据问题的规模选择适当载量的货车，能很好地降低作业成本。其次，在对算法性能的影响上，由于Q增大，导致xdpi个数减少，减少了计算量，使得Cpu降低。如图10显示了车载上限Q对算法Cpu的影响。

对于调度货车数量K，由于本文的分块模式，一个xdpi仅由一辆调度货车进行作业，不会出现像其他算法中对多车调度线路分配的问题，因此调度货车的数量K越多，调度作业时间越短。表3中，为了体现比较的客观性，在目标函数中没有加入时间换算而来的成本，因为时间成本是一个较为主观的成本，工期越紧迫，时间成本自然就越高。可以发现，随着调度货车数量增多，W普遍减小，规模较大时较为明显，但也会出现反例(n=80，Q=45；n=100，Q=15)。Cpu的情况则较为简单，随着K增多，Cpu增加，如图11所示。

4.2 实验结果比较

本文提出的DL-TS算法与已有GA-TS算法详细对比如表1﹑表2和表3。首先，单独分析GA-TS算法结果，可以发现其与DL-TS在算法特性上极为相似，3大变量(n，Q，K)对其获得的目标函数值以及Cpu消耗影响几乎与DL-TS算法一样，在该条件下进行两种算法性能比较更为合理客观。通过两种算法获得结果对比可以发现，GA-TS算法无论在目标函数求解结果还是在Cpu消耗上均不及本文所提出的DL-TS算法。GA-TS在n=60时，部分案例已不能获得最优解，并且在求解大规模案例n=150时，Gap值已达10%左右，为DL-TS算法的两倍以上。分析其原因，在Cpu的消耗上，GA-TS算法在模型优化上未能有效解决规模增大所带来的计算复杂度呈指数形式上升的问题；在目标函数值上，DL-TS是在结合了供需关系模型的基础上进行算法设计的，模型与算法的有机结合，相互能较好地适应与配合，达到目标函数中库存单项成本显著降低的效果。以上对比均体现了本文算法与模型在针对该问题时的优越性。

为进一步验证本文所提模型与算法的有效性，选取两位前人研究成果进行对比分析。本文提出的DL-TS算法与Chemla等[2]提出的BC-TS(brunch-and-cut & tabu search)算法比较如表4所示，BC-TS算法未采用分块访问，直接通过分支定界结合禁忌搜索获得的结果。显然，本文的分块策略在改善计算复杂度上具有显著效果，大大缩短了相同规模问题的计算时间，并且由于增添变异算子，使得目标函数更接近函数下界，显著提高了最优解的获得概率，充分体现了本文采用的供需分块模型的有效性。

本文提出的DL-TS算法与Forma等[6]提出的3-step算法比较如表5所示，3-step与本文所提出的分块访问类似，其第一步是将站点进行分块，但分块方式是基于距离主导的形式，需求次之，其结果同样可以证明分块访问对解决该类问题的有效性，但其结果略逊于本文所提出的基于供需关系的分块模式，他将各个站点的库存水平分为3种：Light/Real/Heavy，3种情况下的求解结果平均Gap普遍大于本文所提算法，如图12所示，充分体现了本文所提算法与供需分块模型有机结合的效果显著。

表4 DL-TS算法与BC-TS算法结果对比

表5 基于供需的分块与基于距离的分块结果对比

5 结束语

共享单车系统近几年在国内逐步兴起，发展势头迅猛。然而，国内期刊针对共享单车再平衡问题进行深入研究的论文甚少，并且求解算法陈旧，模型创新性严重不足。本文提出一种结合供需关系的站点分类策略模型，并设计了相应的双层禁忌搜索算法解决大规模共享单车再平衡作业问题。其中，供需关系的站点分类策略是通过过饱和站点和不足站点之间的配对，形成能自给自足的站点集，对这样的站点集进行再平衡作业，能有效避免一般模型中调度货车在各个站点进行取走或放置单车数量的决策过程，同时由于站点间的自给自足，使单车的库存成本降低了80%以上；在算法上，采用改进的双层禁忌搜索算法，分别基于分块站点集合和站点集合内部进行禁忌搜索，并通过一个嵌套变异算子，增强两层搜索间的信息交流，在提高算法搜索能力的同时增添了解的多样性。经过标准案例测试，能在Cpu消耗100 s内获得150站点以内较优解，同时保证了较低的作业成本，证实了该策略针对较大规模再平衡作业的有效性。未来考虑将LNS以及VNS结合的分治思想，使更大规模再平衡作业中所涉及的多个NP-Hard问题能转化为一个NP-Hard问题，降低其计算复杂度和时间复杂度。