智能电表周转箱回收车辆路径规划研究

程昭立，郝悦辰，周丹妮，张艳馥

(华北电力大学经济与管理学院，北京 102206)

智能电网建设步伐的加快对智能电表的配送提出了更高的要求。与智能电表的正向配送相比，周转箱回收由于发生的时间、地点、数量等存在不确定性，其回收车辆路径规划更为复杂。通常情况下，回收物流车辆路径规划分为回程回收和纯回收两类路径规划[1]。回程回收适合于正逆结合的逆向物流网络，主要分为先配送后回收(VRPB)、混合的配送回收(VRPBM)、配送与回收同时发生(VRPSPD)三类[2]。国内外对回程回收中的VRPSPD的研究是近几年才兴起的。有的学者以车辆行驶路程限制为基础展开研究，如文献[3]提出了配送车辆有最大行程约束的VRPSPD数学模型，文献[4]从单车型、有载重量限制，需求量己知等限制条件展开，构建混合整数规划模型，文献[5]对该问题具体的定义、条件、具体标准进行详细叙述。有的学者在时间约束的基础上展开研究，如文献[6]从单类型、载容、需求确定展开粒子群算法对该问题进行求解，文献[7]针对单配送中心在文献[5]的基础上提出硬时间窗约束条件，并对有时间窗的和无时间窗的仿真结果进行比较，文献[8]则从是模糊时间窗限制的角度开展研究。在模型算法上，主要有禁忌算法、蚁群算法、启发式算法、粒子群法、遗传算法等。基于此，本文针对同时满足缓存库中两种需求的回程回收车辆路径规划(VRPSPD)进行研究，并采用遗传算法对其进行分析。

1 构建数学模型

为将现实中同时具有智能电表配送及周转箱回收的车辆路径规划抽象为数学模型，本文对VRPSPD作如下假设:

1)只有省电网公司计量中心一个车场，每辆车均从省计量中心出发，完成本车路径上的智能电表配送和周转箱回收任务后返回省计量中心。

2)只有一种车型，每辆车的载容已知，单个地市缓存库的配送量和回收量不能超过单车载容。

3)通过计量管控一体化平台，省计量中心可以获取各地市缓存库的智能电表配送需求和周转箱回收需求。

4)省计量中心、地市缓存库的地理坐标已知，即省计量中心与地市缓存库之间的距离已知。

5)每个地市缓存库的智能电表配送需求和周转箱回收需求只能由一辆车服务。

6)配送的智能电表和回收的周转箱可以混装。

7)开展智能电表配送和周转箱回收的车辆最大行驶距离已知，不能超过该路程。

8)车辆在地市缓存库处可以同时完成智能电表配送和周转箱回收任务。

9)智能电表的配送需求量以周转箱为单位，每地市缓存库的需求为整数个周转箱。

10)车辆运输成本与行驶路程呈正比例关系，车辆行驶路径决定车辆行驶路程，当路径距离最短时运输成本最优。

11)每条行驶路径上的车载智能电表配送数量和周转箱回收数量之和小于或等于车辆的载容。

根据上述描述和相关假设，以车辆行驶路程最小为目标建立同时具有智能电表配送和周转箱回收需求的车辆路径规划数学模型为

式中:s为各库的集合，s={0，1，2，．．．，s}，其中 S0为省计量中心;v 为车辆集合，v={1，2，．．．，v};R为车辆的载容;Cij为省计量中心、地市缓存库之间的距离，且有 Cij=0，∀i=j，i，j∈s;Di为地市缓存库i的智能电表配送需求量，i∈s;Pi为地市缓存库i的周转箱回收需求量，i∈s;Xijv为车辆从节点i到节点j时，是否由车辆k服务，当Xijk=1时表示车辆k服务于节点i与节点j之间，否则Xijk=0;Yijv为车辆k从缓存库i到缓存库j行驶时承载的已回收周转箱数量;Zijv为车辆k从缓存库i到缓存库j行驶时承载的装有尚未配送的智能电表周转箱数量;MD为车辆最大行驶距离;Uiv为缓存库i是否由车辆v服务，当Uiv=1时表示车辆 k服务于节点 i，否则Uiv=0。

函数目标式(1)表示目标函数为所有车辆的行驶路程之和最小化.在约束式中:式(2)表示驶进驶离每个缓存库的车辆为同一辆车，且每库只由一辆车服务;式(3)表示省计量中心是所有车辆必须服务，而每个缓存库只能由一辆车服务;式(4)保证每辆车的行驶路程不超过最大距离;式(5)表示车辆k从缓存库i直接到缓存库j时车辆取货物量的变化;式(6)表示车辆k从节点i直接到节点j时车辆送货物量的变化;式(7)表示任何一条车辆的行驶路径上的配送量和需求量之和都必须小于或等于车辆的最大载容;式(8)表示配送车辆在任何行驶路径上承载的周转箱回收量或未送智能电表量都满足车辆最大车容的限制;式(9)表示每辆车离开省计量中心时的车载量为该路径上各个缓存库智能电表的配送需求量之和;式(10)表示每辆车回到省计量中心时的装载周转箱的数量为该路径上各个缓存库回收量之和。

2 求解数学模型的遗传算法设计

应用遗传算法来解决智能电表配送及周转箱回收的车辆路径，就是要根据各市级缓存库提出的配送和回收需求，在满足车辆载容、路程等约束条件下，以成本最小化为目标来规划回程回收车辆路径。通过对目标函数的大小评价各路线的优劣，获取适应性强的方案并将其优秀特征遗传到下一代，获得最优解，规划出最优的车辆回程路径。遗传算法的具体流程如下:

1)参数编码。应用自然数对参数进行编码，对各缓存库用1到n表示，形成排列S1，S2，…，Sn，每个数出现一次且仅一次。在求解数学模型时，运用搜索空间限定法处理其中的约束条件。比如对于车辆路程限制和车载容量的条件约束，通过对已构成的缓存库序列，按照路程和容量限制两个约束条件，依次将各客户划入各条配送及回收路径中，限定其搜索空间，以提高遗传算法的效率。

2)初始回程回收路径方案。通过编码产生的n个缓存库，群体规模为npop，则通过随机产生npop个这样的个体，并按路程和车载容量限制的约束条件插入0，即可形成初始回程回收路径方案群。

3)计算每个个体适应度值。适应度是评价个体优劣和进行遗传操作的依据，度量个体适应度的函数称为适应度函数。基本遗传算法按与个体适应度成正比的概率来决定当前种群中个体遗传到下一代种群中的机会。根据所研究个体的实际情况，拟通过以下公式计算个体适应度值:

其中 average Cost为所有个体总成本的平均值，Cost(i)为第i个体的总成本。

4)遗传操作设计。各车辆路径规划方案的适应度值是遗传算法中衡量方案优劣的一个准则，遗传算法的优化过程是在适应度的指引下，通过各种遗传操作(即遗传算子)来逐代进化。同时对产生的新一代种群进行遗传操作，直至满足收敛结束条件。遗传算法的算子包括选择算子、交叉算子、变异算子[9-11]。

3 实证分析

在构建模型和选择应用遗传算法后，可通过matlab工具对上述问题进行计算。假设某省计量中心坐标为(0，0)，各市缓存库坐标，配送及回收需求如表1所示。

表1 各仓库坐标、智能电表需求量、周转箱回收需求量

设选择概率为0.9，交叉概率为0.3，变异概率为0.01，最大迭代次数为200，最优个体保持数为100，S∈(0，1，2…，30)，车辆最大行驶距离 MD=10×80=800(km/d)，单车载容为300，计量中心与各库之间的距离采用直线距离，通过以下公式计算:

由计算程序计算得到的最优车辆路径方案如表2所示。

表2 最优车辆路径方案

经分析，在本案例中，计量中心只需派出6辆车，并按照上述最优路线行驶，就能同时满足18个地市缓存库和12个典型县直配库的智能电表配送和周转箱回收需求。总行驶路程为3 566.1 km，智能电表配送量为1 735，出发时车辆平均满载率为96%，周转箱回收量为1 719，返程时车辆平均满载率为95.5%。

4 结语

从智能电表配送和同时回收周转箱的的角度，研究了车辆路径最优方案。为了方便求解对其进行了假设，即在此基础上，建立了符合实际的数学优化模型，并基于遗传算法的工作流程对该优化方案进行了解释。通过案例及运用matlab工具的计算验证，构建的最优回收车辆路径方案能满足实际工作需求。

[1]胡天军，程文科.带回程取货的逆向物流车辆路径建模及其蚁群算法[J].交通运输系统工程与信息，2010，10(3):110-114.

[2]刘洋.逆向物流车辆路径问题的研究现状和发展趋势[J].商业文化，2007，8:200-201.

[3]MONTANE F A T，GALVAO R D.A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service[J].Computer ＆ OperationResearch，2006，33:595-691.

[4]张涛，田文馨，张杰，刘士新.带车辆行程约束的VRPSPD问题的改进蚁群算法[J].系统工程理论与实践 .2008，(1):132-140.

[5]EMMANOUIL E，CHRISTORS D，CHRIS T.A hybrid metaheuristic algorithm for the vehicle routing problem with simultaneous delivery and pick-up service[J].Expert Systems with Applications，2007(5):152-161.

[6]AI T J，KACHITVICHYANUKL V.A particle swarm optimization for the vehicle routing problem with simultaneous pickup and delivery[J].Computers ＆ Operations Research，2009，36:1693-1702.

[7]马庆国，孟丽君.基于混合算法的具有硬时间窗口约束的VRPSPD问题[J].西安电子科技大学学报:社会科学版，2009，19(3):41-46.

[8]李华，赵冬梅.具有同时配送和回收需求的车辆路径问题研究[D].成都.西南交通大学，2010.

[9]宋远清，李水生，梁慎清，等.需求随机车辆调度问题的遗传算法研究[J].计算机技术与发展，2009，19(2):230-233.

[10]李军，谢秉磊，郭耀煌.非满载车辆调度问题的遗传算法田[J].系统工程理论方法应用，2000，9(3):235-239.

[11]钟石泉，王雪莲.多车场集送一体化车辆调度问题及其遗传算法研究田[J].西安电子科技大学学报:社会科学版，2009，19(1):63-68.