变邻域搜索求解公共交通乘务调度问题

变邻域搜索求解公共交通乘务调度问题彭琨琨;沈吟东【摘要】Publictransportcrewschedulingisaprocessofpartitioningblocksofvehicleworkintoasetoflegalshifts,whichisNPhard.Theefficiencyofmanysolvingapproachesiscloselyrelatedtoshiftevaluation.Inthispaper,aTOPSISshiftevaluationmethodisproposedbytailoringTOPSIS(TechniqueforOrderPreferencebySimilaritytoanIdealSolution).Moreover,acrewschedulingapproachbasedonVariableNeighbourhoodSearch(VNS)ispresented,whichtailorsVariableNeighbourhoodSearchtosovlecrewschedulingproblem.IntheVNS,theTOPSISshiftevaluationmethodisembeddedtoserveforshiftevaluationdaringtheschedulingprocess,andtwocompoundneighbourhoodstructureswithprobabilityaredesigned,whichconsiderablyenhancessearchdiversificationandhelpstoescapefromlocalminima.Inaddition,SimulatedAnnealingisemployedforlocalsearchintheVNS.Computationalexperimentsbaseson11real-worldcrewschedulingproblemsinChinashowthattheVNSoutperformstworecentlyproposedsolvingapproaches,andachievesresultsclosetothelowerboundsintermsofshiftnumber.%公共交通乘务调度问题是一^将车辆工作切分为一组合法班次的过程，它是NP难问题，许多求解方法的效率都与班次评价密不可分,本文通过裁剪TOPSIS方法(TechniqueforOrderPreferencebySimilaritytoanIdealSolution)设计了TOPSIS班次评价方法•此外，通过裁剪变邻域搜索算法使之适合求解乘务调度问题，提出了基于变邻域搜索的乘务调度方法(CrewSchedulingApproachBasedonVariableNeighbourhoodSearch,VNS),其中,并入了TOPSIS班次评价方法在调度过程中进行班次评价，设计了两种带概率的复合邻域结构以增加搜索的多样性，帮助跳出局部最优，在VNS中利用模拟退火算法进行局部搜索•利用中国公共交通中的11组实例进行了测试,测试结果表明,VNS优于两种新近提出的乘务调度方法,且其结果关于班次数接近于下界.期刊名称】《交通运输系统工程与信息》年(卷),期】2017(017)001【总页数】7页(P164-170)【关键词】城市交通;乘务调度;变邻域搜索;复合邻域结构;班次评价【作者】彭琨琨;沈吟东【作者单位】华中科技大学自动化学院,武汉430074;华中科技大学自动化学院,武汉430074【正文语种】中文【中图分类】U491乘务调度问题(CrewSchedulingProblem,CSP)是公共交通运营与规划的重要组成部分［1］，即安排一组乘务员来完成一天内全部车辆运营工作且要满足一系列复杂劳动法规约束•有效的调度方案能为公共交通企业节约大量运营成本.CSP是NP难问题［2］，其复杂性主要在于大规模，多目标，同时被一系列复杂劳动法规约束.从19世纪60年代开始，CSP受到了广泛研究［2］•至今已有很多求解方法，主要可归类于早期启发式，传统整数线性规划方法，列生成方法［3］和元启发式方法［2,4-8］等•其中元启发式方法由于其快速及有效性，得到了广泛关注，主要包括遗传算法［2,4-5］，禁忌搜索［6］和贪婪随机自适应搜索方法［7］这3种，同时，还有变邻域搜索［8］等•尽管已有很多元启发式方法，但CSP的NP难特性及复杂性决定着对该类方法的研究仍有很大发展空间，特别是如何将CSP的问题特征与元启发式有机地结合值得深入研究，这是元启发式方法设计的关键•此外，在很多乘务调度方法中，班次评价是基础，一个班次的有效性往往受制于多个属性，可视为多属性决策问题•现有的多属性决策班次评价方法很少，仅有模糊班次评价方法［2］和灰关联分析班次评价方法［5］.本文基于CSP的问题特征，首先通过裁剪逼近理想解排序法(TechniqueforOrderPreferencebySimilaritytoanIdealSolution，TOPSIS)，设计一个TOPSIS班次评价方法，随后提出基于变邻域搜索的乘务调度方法(CrewSchedulingApproachBasedonVariableNeighbourhoodSearch，VNS)，其中，嵌入了TOPSIS班次评价方法，设计了两种带概率的复合邻域结构，并以模拟退火算法(SimulatedAnnealing,SA)为例说明如何在VNS中进行局部搜索.在车辆运营任务中的站点，乘务员可换班，相应的站点和时间称为换班机会；两个连续换班机会之间的工作称为小驾驶段；一个车辆运营任务中的若干连续小驾驶段称为连续值乘段•乘务员一天的工作称为班次，它包含乘务员在车场签到和签退，执行若干个连续值乘段，其中可能会包含休息.满足全部劳动法规的班次称为合法班次•一组能够覆盖全部小驾驶段的可行班次称为一个“方案”，即CSP的解.给定一个CSP:假定已事先给定了小驾驶段集合P二{p1,p2,...,pm},且已根据劳动法规约束事先生成了所有合法班次，记为S={s1,s2,...,sn},其中每个班次覆盖若干个小驾驶段，CSP的目标是找到一个具有最小班次数和班次总成本的方案，其中优先最小化班次数，模型可描述为式中：cj为班次sj的成本；若sj覆盖pi,记aij=1,否则记aij=0•式⑴最小化班次数和班次总成本，其中C为一很大的常数以优先最小化班次数；式(2)保证每个小驾驶段至少被一个班次覆盖；式(3)是0-1决策变量.TOPSIS方法是一个框架性方法，需要适当剪裁以评价班次，基本思想是：一个好的班次应该距离理想班次最近、离最劣(负理想)班次最远.根据CSP的问题特征，一个有效班次通常工作时间更长，工资成本更低，小驾驶段更多，松弛线性规划解中的值更大，且含有两个连续值乘段的班次更为有效［2］.因此，本文考虑将工作时间(C1)，工作时间与工资成本的比例(C2)，小驾驶段的数目(C3)，连续值乘段的数目(C4)，松弛线性规划解中的值(C5)作为5个评价准则•对于任意班次sjeS,相应的评价值记为Xj=(Xj1，Xj2，Xj3，Xj4，Xj5),因此S中包含的n个班次对应一个nx5矩阵X=(xjk)nx5,称为决策矩阵•接着，对该矩阵进行正则化，得到正则化决策矩阵，然后定义理想班次V+和负理想班次V-,并计算每个班次与理想班次和负理想班次的距离，最后计算班次与理想班次的相对贴近度•由于上述5个评价准则只与一个具体班次的属性相关，因此称为静态评价准则；该评价方法称为静态评价方法•最后，还将考虑班次间的相关影响(如重覆盖)设计综合评价方法.2.1静态评价正则化决策矩阵.首先将决策矩阵中的元素Xjk转化在［0,1］之内，即正则化决策矩阵，记为V=(vjk)nx5.本文利用Li等［2啲模糊隶属度函数进行正则化•当k=1,2,3时，使用式(4),当k=4,5时，分别使用式(5)和式(6).2.2综合评价—个班次覆盖的小驾驶段可能被方案中的其他班次所覆盖，称为重覆盖•这会使方案需要更多班次•本文使用重覆盖的惩罚g(sj)［2］来作为动态评价函数.式中：|sj|表示sj中所含有小驾驶段的数目；tkj为sj中小驾驶段pk的工作时间.基于静态评价和动态评价，进—步设计综合评价为式中：a,阻［0,1］,反映了静态评价和动态评价的相对重要性.变邻域搜索算法是一种基于多邻域结构的元启发式算法，已被成功用于求解多个困难组合优化问题.其主要思想是定义多个邻域结构，在搜索过程中系统地改变当前使用的邻域结构，使得搜索过程能够探索对应于不同邻域结构的搜索空间.变邻域搜索算法只提供了求解问题的一般框架，在求解CSP时需要专门进行裁剪，它有两个重要组成部分：(1)邻域结构的设计，这是基础和关键；局部搜索的设计，以对每个邻域结构进行有效探索.本文通过裁剪变邻域搜索算法提出了VNS•首先，根据CSP的领域知识，设计了两种带概率的复合邻域结构，将概率引入到邻域结构中：邻域结构中的每个复合动作有两个动作构成，每个动作会根据概率执行不同操作，这保证搜索能覆盖一定的解空间，极大地增加了搜索的多样性，提升了VNS跳出局部最优值的能力•此外，整合了TOPSIS班次评价方法到VNS中作为调度过程中班次评价的求解器，从而能够选择合适班次以构建或者破坏方案•随后，给出了VNS的算法框架，最后以SA为例展示了如何设计有效的局部搜索.3.1带概率的复合邻域结构N1N1由一个复合动作集合构成，每个复合动作由带概率的删除动作probRemovel和带概率的插入动作probinsert构成.probRemovel以一定概率执行不同操作，根据这些操作从当前方案X1中删除若干(如R1)班次；在班次删除之后，会有一些小驾驶段现在不被X1覆盖，需要再选择一些班次进入X1,probinsert以一定概率执行不同操作，根据这些操作从班次集合中选择班次进入X1.给定小概率pl(如0.2)和p2(如0.2)及整数R1,probRemovel和probinsert设计如下.probRemovel:分别以概率pl和1-p1执行以下操作：⑴从X1中随机删除R1(如|X1|・10%)个班次；(2)对X1中班次使用TOPSIS班次评价方法进行评价，并按评价值升序排列，随后从X1中选择R1个班次从X1中删除，其中排名第i的班次被选择的概率为其中，第(1)种操作使得每个班次有相同机会从当前方案中删除，第(2)种操作使得TOPSIS评价值低的班次以较高概率被删除，评价值高的班次以较低概率被删除.probInsert分别以概率p2和1-p2执行以下操作：(1)将P中目前未被覆盖的小驾驶段按覆盖其班次数从小到大排列，得到小驾驶段列表U.(2)首先将被删除的班次按TOPSIS班次评价方法的评价值升序排列，将它们所覆盖的小驾驶段(除去目前被覆盖的小驾驶段)依次排列，得到U.对U调用使用TOPSIS的贪婪算法来选择班次，直到其中的小驾驶段都被覆盖•使用TOPSIS贪婪算法的主要思想是对一个小驾驶段，分别以概率Prob(如0.95)和1-Prob选择具有最大、第二大TOPSIS评价值的班次来覆盖它•这不同于用于乘务调度的传统贪婪算法(对每个小驾驶段都选择具有最大评价值的班次)，这样设计目的是增强多样性.3.2带概率的复合邻域结构N2N2由一个复合动作集合构成，每个复合动作由带概率的复合删除动作probRemove2和probinsert共同构成.probRemove2是以一定概率执行不同的操作，根据这些操作从当前方案X1中删除R2个(R2>R1,如|X1|・40%)班次；在班次删除之后，再利用probinsert选择班次进入X1以保证小驾驶段全部被覆盖.给定整数R2,probRemove2设计如下：分别以概率pl和1-p1执行以下两种操作：从X1中随机删除R2个班次；对X1中所有班次使用TOPSIS班次评价方法进行评价，并按评价值升序排列，随后根据一定的概率分布从X1中选择R2个班次从X1中删除，其中排名第i的班次被选择的概率Pi如式(14)所示.N1和N2的区别N1和N2中的主要区别在于：与N1中的删除动作相比，N2删除的班次更多，因此，N2会对当前解造成更大破坏，然后使用带概率的插入动作来选择班次，增强了对解空间的搜索，在一定程度上防止了搜索被限制在某个局部区域，增强了算法的多样性•而N1能在一定程度上细致地探索局部区域，使得算法具有一定集中性.算法框架给定VNS的最大迭代次数I,VNS的算法框架如下：Step1设计两个复合邻域结构N1和N2，设置在每个邻域结构内执行局部搜索的迭代次数分别为n1和n2(n1>n2).Step2构建一个初始解X0,设置最优解Xb=XO,当前解X1=X0.Step3设置k=1,i=0,其中k和i分别表示第k个复合邻域结构和第i次迭代.Step4设置Nk为当前的邻域结构，对X1执行迭代次数为nk的局部搜索，在每次迭代中，设置i二i+1,如果得到的解优于Xb,则更新Xb,设置k=1,转Step6;否则，继续下一次迭代.Step5设置k=k+1,如果k>2，则设置k=1.Step6若ivI,转Step4;否则，对Xb执行文献⑸的局部搜索策略，输出Xb.局部搜索在给定邻域结构Nk后，需要在VNS框架内嵌入局部搜索方法以对当前解X1在Nk内进行探索，任何局部搜索方法都可执行这一任务.本节以SA为例进行说明.SA中的接受准则非常重要，在很大程度上影响SA的搜索能力•本节使用了文献[9]中的改进接受准则,它能在保证解质量的前提下,接受“被破坏的”解,同时又不丢失随机性：给定当前解X1和其邻域解X2,实数PE[0,1](如0.5)和一个很接近于1的实数b(如1.0002),当前代温度T，改进接受准则描述如下：在［0,1］内生成一个随机数r,如果r>P,以概率min(1,exp(-(E(X2)-E(X1))/T))接受X2;否则，当且仅当E(X2)<bE(X1)时接受X2.给定邻域结构Nk,SA在Nk内的最大迭代次数nk，每个温度下的最大迭代次数L,初始温度T0,当前解X1,SA的算法框架如下：Step1设置m=0,T=T0.Step2设置1=0.Step3从Nk内随机选择一个动作，对当前解X1执行该动作得到邻域解X2.Step4利用文献［5］中的局部搜索策略来改进X2.Step5使用改进接受准则判断X2是否能够取代X1.Step6设置1=1+1;如果内循环终止条件已达到(l>L),转Step7;否则，转Step3.Step7设置m=m+1,T=cT;如果终止条件已达到(mL>nk),终止程序；否则，转Step2.为验证VNS的性能，采用我国城市公交中的11组实例进行实验，表1给出了它们的基本特征：即每个实例所包含的车辆数，小驾驶段数，班次数，同时也给出了VNS独立运行10次的平均结果，随后将VNS与著名数学规划软件CPLEX(12.4版本)、两种较新的乘务调度方法，即AECS［4］和EGRA［5］，进行对比，详细结果如表2和表3所示.VNS用C++编写，在具有3.30GHz和4G内存的计算机上运行，CPLEX在具有2.13GHz和2G内存的计算机上运行.VNS的参数设置为：I=55,n1=40,n2=10,c=0.9,T0=100丄=10,(a,p)二(1.0,1.0),(w1,w2,w3,w4,w5)=(0.15,0.15,0.15,0.15,0.4),这5个wi的值是由LI和KWAN［2］得到的一组好的参数组合.从表2可看出，CPLEX只能求出前8个实例的最优解，在班次数和班次总成本方面，VNS关于CPLEX的平均RPD分别为0.79%和11.63%，注意到在CSP中，最小化班次总数优先于最小化班次总成本，因此可以认为VNS可以获得非常靠近CPLEX的高质量解•对于剩余3个实例，利用CPLEX求出班次数的下界，VNS相对于11个问题的班次数下界的平均RPD仅为0.73%，这说明VNS可获得非常接近班次数下界的高质量方案.从表3可看出，VNS优于AECS和EGRA:与AECS相比，关于班次数和班次总成本，VNS分别在9个和10个实例上更优，平均RPD分别为-2.01%和-3.19%,这充分说明了VNS优于EGRA;与EGRA相比，在班次数方面,VNS在4个实例上更优，在剩余实例上与EGRA相同，在班次总成本方面,VNS在7个实例上更优，平均RPD分别为-0.57%和1.56%，在CSP中，最小化班次数是最主要目标，因此VNS优于EGRA•以上分析表明VNS是一种求解CSP的有效算法.本文研制了TOPSIS班次评价方法和VNS方法，其中，设计了两种带概率的复合邻域结构，较大地增加搜索空间的多样性，将TOPSIS班次评价方法嵌入到VNS中，并以SA为例展示了如何在VNS中并入局部搜索•实例测试表明了VNS的优越性.TOPSIS班次评价方法和复合邻域结构具有通用性，可用于其他乘务调度方法中,VNS是一个求解框架，其他班次评价方法，邻域结构及局部搜索都可并入.【相关文献】SHENY,XUJ,ZENGZ.PublictransitplanningandschedulingbasedonAVLdatainChina[J].InternationalTransactionsinOperationalResearch.2016，23(6):1089-1111.LIJ,KWANRSK.Afuzzygeneticalgorithmfordriverscheduling[J].EuropeanJournalofOperationalResearch,2003(147):334-344.JUTTES,THONEMANNUW.Divide-and-price:Adecompositionalgorithmforsolvinglargerailwaycrewschedulingproblems[J].EuropeanJournalofOperationalResearch,2012,219(2):214-223.SHENY,PENGK,CHENK,etal.Evolutionarycrewschedulingwithadaptivechromosomes[J].TransportationResearchPartB,2013(56):174-185.PENGK,SHENY.Anevolutionaryalgorithm