多次需求的特殊路段限容量弧路径问题研究

李坤阳

摘 要：限容量弧路径问题在城市生活当中具有一定的普遍性，引起广泛的关注。本文所关注的焦点是针对CARP问题的一种拓展问题：考虑了特殊路段的多次需求情况下的路径优化问题。首先提出了此类问题的背景和意义，然后针对该问题中的容量约束和需求次数两个方面进行了分析，最后建立模型，并用模拟退火算法进行求解，然后对结果进行分析。

关键词：多次需求;弧路径问题;路径优化

DOI：10.16640/j.cnki.37-1222/t.2019.02.199

0 引言

限容量弧路径问题（Capacitated Arc Routing Problem， CARP），是一种把研究对象设置为道路或路段的问题，主要的应用方面是城市的服務车辆，例如城市道路的洒水车、垃圾收集车、冬季除雪车等，均是服务道路或路段的车辆。我国的城市建设一直在发展，以南京为例，2012年的城市道路长度为6615公里，而在2016年时城市道路长度为8012公里。城市建设的同时，会使得城市道路网发生变化，而这也对服务车辆的运营提出的新的要求。关于CARP问题，国内外学者进行了一些研究，Li J Q等[1]根据澳大利亚的矿场中道路信息，结合运煤车的运行模式，考虑了动态的洒水车根据需求改变服务方案，并解决了该矿场洒水车场的选址问题。Lacomme P等人[2]则考虑了周期性的问题，考虑多目标的情况下，并设计了一种改进的遗传算法进行求解，并且得到了较好质量的解。刘洁等人[3]考虑了垃圾收集车的问题，并结合了城市中的转向限制和单行道的情况，将弧路径问题转换成了节点路径问题。朱征宇等人[4]对洒水车的问题设计了一种改进后的双层遗传算法，并且在单个车场的基础上考虑了多个补水场的问题。很多学者对CARP问题进行了研究，但多数研究只考虑了一次服务需求，而对于一些特殊路段，在实际的应用中可能会需要不止一次的服务。因此，研究这些特殊路段的多次需求对于改善城市道路环境、提高服务车辆的运营和管理水平、减少成本的耗费是有帮助的。

1 问题分析

考虑需求次数的特殊路段弧路径问题可以这样来对问题进行描述：在城市道路网络中，有一组具有不同服务需求次数的路段（可称作“任务”）需要服务车辆进行服务，而在某一节点处，存在一个车场，车场内有一个由多辆相同的服务车辆所组成的车队。现需要将任务分配给车队中所有的服务车辆，并且确定服务车辆的路径，保证所有的任务都能够完成，也即所有有服务需求的路段均需要被服务车辆服务到，并且满足路段的服务需求次数的要求。如何安排车队中服务车辆的路径问题，使得总的成本耗费或行驶距离耗费最小，是本问题需要重点考虑的内容。

考虑特殊路段的多次需求问题，实际上是在CARP问题的基础上加以多次需求因素，它与CARP问题的不同点在于，将某些特殊路段考虑了多次需求。而在该问题中，除了服务车辆的服务对象是城市道路的边以外，还有两点重要因素：容量限制和服务需求次数，是本问题着重考虑的部分，也是构建模型和算例求解时，主要围绕的部分。

1.1 容量限制

城市的服务车辆在对城市的路段进行服务时，是需要考虑容量的影响。洒水车的水箱是有容量的，除雪车能承载的除雪剂也是一定的，垃圾收集车的容量同样有限制，服务车辆的容量限制了服务车辆不能无限制的服务下去，当服务了一定的时间或者一定长度的路段后，会因为容量限制的原因无法继续作业。而本问题所研究的需求是不可拆分的，也即服务车辆对路段进行服务时，只能选择将路段的需求完全满足，或者完全不服务，不能出现服务车辆服务路段的部分需求的情况。

因此，从容量限制的角度来看，本问题中，城市道路网络中路段的平均长度越短，则服务车辆出行一次所能够提供服务的路段数量也越多，并且返回车场时所剩余的容量也越少，利用率相对较高;而若路段的平均长度越长，则服务车辆出行一次所能够提供服务的路段数量也越少，并且返回车场时所剩余的容量也越多，利用率相对较小。

1.2 服务需求次数

一般的城市路段只需要一次服务即可，如洒水车一天时间内对一个路段洒水一次，垃圾收集车辆早上对路段上的垃圾箱进行清理。但是有一些情况需要多次对路段进行服务，如施工现场附近被渣土车经常驶过的路段等情况，可能会需要多次服务才能满足要求，而不仅仅是一次。

服务需求次数的要求，使得服务车辆的运营模式对比仅仅服务一次情况时，要复杂一些。因为这将会对服务车辆的连续性造成影响，在考虑一次服务需求次数的情况下，服务车辆可以考虑连续的服务若干条相互接续的边，以减少空驶距离;如果考虑了多次需求的情况下，当第一次服务时，连续的服务若干条相互接续的边后，第二次的需求则会使之前服务过的、只有一次需求的边成为空驶而不服务，这样会增加空驶距离。而实际运营中，应当尽可能减少空驶距离，以降低成本。

2 模型建立

在模型建立前，对该问题进行假设条件的设置：（1）所有的服务车辆是相同的，并无任何区别;（2）服务车辆需要从车场出发，完成任务后最终返回车场;（3）服务车辆进行服务时，任务的需求不能拆分;（4）不考虑服务车辆在交叉口经过时的行驶距离和服务容量的消耗。

在图中，为顶点集，节点0为车场所在，为弧集，弧的长度为、需求量为、服务次数，有个容量为的服务车辆对图中的路段进行服务，确定每个服务车辆的路径，使得总的行驶距离最小。

在模型中，需要两个0—1变量对服务车辆的路径问题进行描述：

——当服务车辆的对弧只途径不服务则为1，否则为0;

——当服务车辆的对弧服务则为1，否则为0。

模型建立如下：

 目标函数（2.1）是要求总的行驶距离最短;约束式（2.2）表示车辆服务的所有任务的需求量之和不超过容量;约束式（2.3）表示满足弧的服务次数要求;约束式（2.4）表示车辆对弧的选择只有服务、途径不服务和不途径三种情况;约束式（2.5）表示服务车辆的车场约束，从车场出发最终必须返回车场;约束式（2.6）表示道路网络中的节点流量平衡约束;约束式（2.7）和（2.8）表示0—1变量的取值约束。

3 算例求解

现有一个局部城市道路网络如图3.1所示，为了便于计算，将该网络转换为表格形式，将路段的服务需求和车辆容量转换成若干个单位长度表示，如表3.1所示，其中节点1为车场，编号3、8、11、12的路段需求次数为2次，其余路段的需求次数均为1次。另有服务车辆4辆，容量均为12，需要计算出服务车辆的总行驶耗费的最小值。由于长度和需求正相關，因此考虑设置为相同的值。

需要说明的是，0—1变量是确定服务车辆路径的主要参数，但是在对算例进行求解的时候，为了方便求解，将问题转化成直接安排任务分配给服务车辆的计算。

选择模拟退火算法对上述问题进行求解，相关参数为：初始温度100，温度下限1，降温系数为0.95，迭代次数为100次。通过随机方法确定初始解：1号车为（1，3，8，13），2号车为（5，2，7，8，12），3号车为（4，6，11，3，9），4号车为（10，12，11，14）。该初始解总耗费为79，耗费的计算除了任务本身的需求，还要加上相邻任务之间的最短路径的长度耗费以及从车场出发和返回车场的长度耗费。新解的产生方法为随机互换任务弧，并同时检验约束条件是否符合。

经过计算后得到新的优化方案：1号车为（1，8，3，7），2号车为（2，8，14，13，12），3号车为（6，12，11，10，9），4号车为（5，11，4，3），总的耗费为49。

由算例的结算结果可知，在多次服务的考虑下，对于洒水车的运营是有所影响，同时所建立的模型在模拟退火算法的计算下，能得到满意解，说明该方法对于此类问题的求解比较有效。

4 总结

考虑了多次需求的服务车辆路径问题，会使得服务车辆的路径任务安排变得更加复杂。本文在解决问题时，引用了图论中的建模基础，建立模型并且运用启发式算法进行求解，从而得到满意解。

参考文献：

[1]Li J Q，Mirchandani P，Knights P.Water truck routing and location of refilling stations in open pit mines[C]. Proceedings of 2008 Australian Mining Technology Conference. The Australian Institute of Mining and Metallurgy，2008：141-156.

[2]Lacomme P，Prins C，Ramdane-Chérif W.Evolutionary algorithms for multiperiod arc routing problems[C].Proc.9th Int.Conf.Inf.Process.Manage.Uncertainty Knowl.-Based Syst，2002：845-852.

[3]刘洁，何彦锋.城市垃圾收集车辆弧路径问题研究[J].成都大学学报（自然科学版），2013，32（04）：423-426.

[4]朱征宇，刘建辉，杨永，谢志华.多车场洒水车路径问题的双层遗传算法[J].微型电脑应用，2008（06）：1-4.