摘要：本文针对省级电网公司电能计量装置的大规模配送路径问题，构建了车辆配送路径优化模型，提出了一种基于贪心算法、禁忌搜索的启发式算法。研究结果表明，基于贪心算法、禁忌搜索的启发式算法不仅能够解决多车、多用户点、多产品的配送需求下成本最优的车辆分配和路线规划问题，还能够为省级电网公司计量装置的大规模配送任务分解和资源调度提供了科学的依据。

　　关键词：能计量装置;配送路径优化;贪心算法;禁忌搜索

　　1.引言

　　目前随着物流业的快速发展，电网行业对电网工作中的相关物流工作越来越关注，电网行业的物流工作涉及许多，其中配送路径优化问题(Vehicle Routing Problem，VRP)是公司关注的重中之重[1]。

　　2. 文献综述

　　VRP问题一直以来就是研究的热点问题，从理论研究方面来看，物流配送路径优化问题已被证实是NP-hard问题，它求解复杂度较高，计算量较大[2]。近年来，已经有大量的学者对电网物资配送路径优化问题进行了研究。张巍结合电网公司物流配送的具体问题，提出使用蚁群算法来解决电网物资配送问题，大大提高了物资配送效率[3]。陈国勇基于物联网技术，采用遗传算法对电网物流配送问题进行了研究，研究结果显著减少了配送车辆的行驶路程[4]。齐心设计了基于遗传算法和模拟退火算法的综合启发式算法，结果证明该算法大大提升了计算的效率[5]。

　　上述文献在电网公司配送路径问题上都取得了很好的成绩，但是目前的应用范围还都仅限于配送数十个用户点，对于上百个用户点的配送需求研究还较少。众所周知，配送路径问题的复杂度是随着用户点数量增加呈指数上升的。对此，本文提出了一种基于贪心算法、禁忌搜索的启发式算法，该算法能够在较短时间内解决较大规模的用户点配送需求。

　　3.模型构建

　　3.1问题描述

　　河北电网公司想要通过其下属各用户点每月的需求提交情况直接得出该月的配送计划，该配送计划要能得出在配送成本最小时的配送路线。该电网公司的具体情况如下：

　　(1)该电网公司有1个配送中心，N个配送用户点;

　　(2)该电网公司共有K辆车，每辆车有固定的最大容量、最远行驶里程和额定工作时间，并且不同车型有一定的使用比例，每辆车都是从配送中心出发，配送完成之后回到配送中心;

　　(3)对于需求量很大的用户点先采用整车运输，余下的需求量再跟其他用户点需求拼车运输。

　　3.2问题假设

　　为了方便计算，先对以下几点进行假设：

　　(1)计量中心在配送前所有表计的库存都是能满足配送需求的;

　　(2)各用户点的电能计量装置需求量、相互的配送距离等都是已知的，并且为了方便计算，各用户点的计量装置需求量已经提前转化为各种箱子的需求量;

　　(3)每辆车的最大容量、平均车速、最远行驶里程以及各种车型的使用比例都是确定的;

　　(4)当用户点的需求量较小时，一辆车可以配送多个用户点。

　　3.3模型构建

　　(1)参数说明

　　K1：大车的集合;

　　K2：小车的集合;

　　K：所有型号的车集合，k∈K(k1∪k2) ;

　　N：用户点的集合;

　　C：配送中心(只有一个，C={0});

　　A：所有点的集合，A=N∪C;

　　Fk：车辆k的固定成本，即车辆每启动一次的成本;

　　Pk：车辆k的单位变动成本;

　　Vk：车辆k的平均速度;

　　T：车辆的额定工作时间;

　　S：车辆的最大行驶距离;

　　L：车辆的平均装载率下限;

　　U1：大车的最大储位，这里归一化处理为1;

　　U2：小车的最大储位，这里归一化处理为1;

　　m：箱子类型，m∈{1、2、3、4、5}

　　Qim：用户i对箱子m的需求量;

　　Gkm：箱子m在车辆k中所占的储位比率;

　　ti：车辆在用户点i的卸货时间i∈N;

　　dij：点i到点j的距离，i∈A，j∈A;

　　g1：大车与小车的使用比例系数(下限);

　　g2：大车与小车的使用比例系数(上限);

　　Xkij：车辆k从i点到j点，值为1，否则为0;

　　Yki：车辆k经过点i，值为1，否则为0;

　　(2)模型构建min■■■Xkij*dij*Pk+■■Fk*Yki (3-1)

　　■■■*Xkij+■Yki*ti≤T ?坌k∈K (3-2)

　　■Xkij=■Xkji ?坌k∈K，?坌i∈A (3-3)

　　■Xkij≤1 ?坌k∈K，i∈C (3-4)

　　■Xkij=Yki ?坌k∈K，?坌i∈A (3-5)

　　■Yki =1 ?坌i∈A (3-6)

　　■■Qim*Yki≤U1 ?坌k∈K1 (3-7)

　　■■Qim*Gkm*Yki≤U2 ?坌k∈K2 (3-8)

　　■■■Qim*Gkm*Yki≥L*(U1*■Yk0+U2*■Yk0) (3-9)

　　■■Xkij*dij≤S ?坌k∈K (3-10)

　　■Yki≥g1*■Yki ?坌i∈C (3-11)

　　■Yki≤g2*■Yki ?坌i∈C (3-12)

　　■■Xkij≤R-1 ?坌R?哿N(R≠Φ)，k∈K (3-13)

　　目标函数(3-1)表示所有车辆的变动成本和固定成本之和最小;约束(3-2)表示车辆的行驶时间与卸货时间之和小于等于额定工作时间;约束(3-3)表示对于用户点i，车辆的流入量等于流出量;约束(3-4)表示车辆k给用户点i送货的次数小于等于1;约束(3-5)表示车辆k从用户i到用户j，意味着车辆k一定经过了用户i;约束(3-6)表示每个用户点只能被服务一次;约束(3-7)、(3-8)分别表示大车与小车的装载要小于等于其最大储位;约束(3-9)表示所有车辆的平均装载率要达到一定的标准;约束(3-10)表示每辆车的行驶距离不能超过车辆的最远行驶距离;约束(3-11)、(3-12)表示大车和小车的使用比例要在一定区间范围内;约束(3-13)表示子回路消除约束。

　　3.4模型求解

　　从配送需求来看，要求解的问题规模较大(上百个点的需求)，同时希望算法能收敛到最优解，因此禁忌搜索算法相比于其他算法更为合适。考虑到单一的禁忌搜索算法特存在一定的局限性，因此，这里提出了一种基于贪心算法及禁忌搜索算法结合的混合启发式算法来对该问题进行求解，具体的算法流程如下：

　　首先，定义Solution类的成本函数cost(), 这个成本包含Vehicles引出的路径长度成本、单相表使用纸箱进行装箱的额外倒箱成本和车辆固定使用成本。

　　其次，GreedySolution()将节点引入初始解中。基本原则是：在最大容量约束的前提下，暂时不管路径长度和工作时间，尽量使装载率越大越好。此外，建议将每辆车的行车路径用TSP算法优化重排。

　　然后，InterRouteLocalSearch()将遍历每辆车，如果它的路径长度或者所用时间超过限额，则将它与其他车的路径进行交互。

　　最后，IntraRouteLocalSearch()将所得解进一步优化。考虑将现有解中的大车换为小车，装单相表的纸箱换为周转箱，如果所有约束仍都满足且能减低配送成本，则更新方案。

　　4.大规模算例

　　4.1算例介绍

　　河北电网公司只有一个配送中心，需要配送105个用户点的电能计量装置的需求，每个月计量中心供使用的车共有120辆，其中编号1~60号为大车，61~120号为小车。所有车辆的额定工作时间是8小时，单程最远行驶里程是350公里，平均行驶速度是90公里/小时，车辆的最低平均装载率为0.8，其中大车的固定成本为300元/天，单位变动成本为2.5元/公里，小车的固定成本为260元/天，单位变动成本为2元/公里，每辆车在用户点的卸货时间为0.5小时，各种箱子占用不同车型的储位率见下表2

　　表2 各箱子占用不同车型的储位率

　　4.2结果分析

　　本算例使用基于Java的启发式算法进行求解，只花了不到1分钟，得到最优的配送成本为62678.80元，共使用车辆70辆(其中拼车运输车辆为33辆)，平均装载率为94.55%。得到最优配送方案如下表3所示：

　　表3 最优配送方案

　　由于配送路径较多，在此选取其中的33辆拼车运输的配送路径展示如下图1：将优化方案运行得到的配送结果与7月份的实际配送情况进行比较，比较结果展示如下表4：

　　图1 最优配送方案的部分配送路径图

　　表4 7月份实际配送情况与优化方案配送结果的对比

　　由上表可以很直观地看出，优化方案比目前的实际运行结果更优。

　　5.结论

　　本文采用基于贪心算法、禁忌搜索的启发式算法对多车辆、多用户点的配送需求进行车辆分配和路径优化，该模型能够在较短时间内解决较大规模的用户点需求，求解结果表明本文算法不仅能够提高车辆的装载率，降低车辆的行驶里程，还能够大大降低配送成本，这对于国网公司来说具有很好的现实意义。同时，本文也存在一定局限性：本文假设计量装置的库存完全能满足配送计划的需求，但实际情况中，配送无法按照计划完成往往是因为配送计划与库存不匹配，所以建议未来的一个研究方向是将需求计划、生产检定、存库和配送结合起来安排配送计划。C

　　(作者单位：北京物资学院信息学院)

　　参考文献

　　[1]史春燕,黄辉.车辆路径问题:研究综述及展望[J].物流科技,2014,37(12):75-77.

　　[2]张勇. 基于改进蚁群算法物流配送路径优化的研究[J].控制工程,2015,22(2): 252-256.

　　[3]张巍.电网企业物流配送路线优化与应用研究[D].

　　华北电力大学(北京),2016.

　　[4] 陈国勇. 电网物流配送优化模型构建及仿真研究[J].自动化技术与应用,2018,37(12):141-144.

　　[5] 齐心. 基于综合启发式算法的物流配送路径优化研究[J].物流科技,2017,40(1):102-105.