2019, Vol. 34
2. 中国人民解放军72465部队 济南 250022;
3. 国防科技大学 计算机学院, 长沙 410073
2. PLA 72465 Unit, Ji'nan 250022, China;
3. School of Computer Science, National University of Defense Technology, Changsha 410073, China
战场环境中的物资运输至关重要, 与普通物资运输具有明显区别.敌方火力打击对路网的破坏、对物资的损毁、对车辆通行速度的影响以及作战单元的物资需求变化等因素都对决策有重要影响.本文采用改进型蚁群算法, 对一假定案例进行建模和求解, 并采用仿真的方式验证路线选择的合理性和有效性.
1 改进型蚁群算法及其在VRPTW中的应用求解车辆路径问题的蚁群算法一般以总路程为目标函数, 以车辆载运能力、行驶速度、客户的物资需求数量、配送时间要求等为约束条件, 建立多约束目标优化模型[1].本文通过对信息素更新方式进行改进, 在一定程度上提高了计算效率.
1.1 带时间窗的战时物流配送车辆路径问题模型带时间窗的车辆路径问题简称VRPTW(Vehicle routing problem with time windows).设某一局部战场只有一个物资配送中心, 该配送中心对多个作战单元进行服务保障, 有多台型号相同的运输车辆可供调用, 车辆可以同时从配送中心出发, 各自按照一定次序完成对不同作战单元的服务保障.各配送车辆型号、容量(最大载重量)、平均行驶速度均相同, 各作战单元有相应的服务时间、物资需求量及卸货时间要求, 且每个作战单元只能接受一辆车服务一次.车辆需要在规定时间段内对作战单元进行服务, 配送中心及各作战单元间的距离预先给出, 目标函数为配送车辆总路程[2-4].
定义符号及其含义[5]如下.
V={Vi| i=0, 1, ..., n}:配送中心和作战单元, V0为配送中心, 其余为n个作战单元.
K={k=1, 2, ..., m}:可供调用的运输车辆.
Q:配送车辆的最大载重.
qi:第i个作战单元的物资需求量, i=1, 2, ..., n.
Dij:从出发点到目标点j的车辆行驶距离, i, j= 0, 1, ..., n.
tij:配送车辆由出发点i至目标点j的行驶时间, i, j=0, 1, ..., n.
ti:配送车辆为作战单元i提供服务所需要的时间(卸货时间), i=1, 2, ..., n.
Li:车辆实际依次经过的配送中心及作战单元, 车辆实际经过路线的配送中心及作战单元数量小于2n, i=1, 2, ..., 2n.
TRi:第i个作战单元接受服务的最早时间, i=1, 2, ..., n.
TDi:第i个作战单元接受服务的最晚时间, i=1, 2, ..., n.
xkij:车辆k的行驶线路是否包含由点i到点j的路段.
|
yki:车辆k是否为作战单元i提供服务.
|
问题的基本模型如下:
|
(1) |
|
(2) |
|
(3) |
|
(4) |
|
(5) |
|
(6) |
|
(7) |
|
(8) |
|
(9) |
|
(10) |
|
(11) |
|
(12) |
|
(13) |
|
(14) |
|
(15) |
|
(16) |
其中:式(1)为目标函数, 表示配送线路总里程最短, 即总费用最小; 式(2)表示任何一辆车完成服务的作战单元的物资需求量总和不大于车辆运载能力; 式(3)表示任何作战单元都只能被一辆车服务; 式(4)表示任意车辆都要返回配送中心; 式(5)表示所有车辆都应从配送中心出发, 且每次只能对一个作战单元服务; 式(6)表示配送中心是各个车辆完成配送任务的终点; 式(7)和(8)表示一个作战单元只能且必须有一个车辆对其服务; 式(9)表示每个作战单元接受物资配送的时间窗口; 式(10)表示车辆为作战单元服务的时间段; 式(11)和(12)表示配送车辆为作战单元完成服务后, 若对下一个作战单元进行服务, 则到达时间必须在相应时间窗内; 式(13)和(14)表示配送车辆为作战单元服务的开始时间、结束时间与该作战单元所需的服务时间及该作战单元允许的最晚到达时间的关系; 式(15)和(16)表示相应变量的取值范围.
1.2 VRPTW的改进型蚁群算法VRP问题已经被证明为NP-hard问题[6], 很难通过传统算法得到其最优解.遗传算法[7]、蚁群算法[8]、禁忌搜索法[9]等诸多启发式算法及其改进方法[10-12]被应用于求解该问题, 对搜索方式的改进以及不同方法的融合一直是研究热点[13-15].本文对传统蚁群算法的信息素更新方式进行一定改进, 在不采取其他优化方式的情况下, 很好地解决了Solomon测试数据中100个点的C类问题, 具有较好的应用前景.
蚁群算法的基本流程如下.
Step 1:初始化参数, m只蚂蚁同时从配送中心出发, 各自按一定条件选择第一个访问点.
Step 2:对每个蚂蚁列出全部未访问过的点, 设其个数为S1.
Step 3:判断S1的值.若S1=0, 则表示该蚂蚁已经完成全部配送任务, 应返回配送中心, 结束本条线路的配送; 若S1>0, 则从S1个未访问点中筛选出符合访问条件的未访问点为S2(S2≤ S1)个.若S2=0, 则表示没有可选点符合条件, 车辆返回配送中心; 若S2>0, 则在当前访问点一定距离范围内选取S=min(S1, S2)个候选访问点, 并将配送中心加入到候选访问点, 按照一定概率选取一个点作为下一个服务点, 返回Step 2.
Step 4:判断是否所有蚂蚁都已经完成配送任务, 若是, 则计算各蚂蚁所经过的总路线长度, 从中选出最短路线并记录, 按照规则更新信息素.
Step 5:计算每次运算中的各蚂蚁经过的路线最小值, 并记为Li(i=1, 2, ..., N), 经多次计算可得迭代最优解为min(Li).
1.3 信息素更新的改进方法经典模型中第k只蚂蚁从i到j所留下的信息素具体更新方式如下[1].
ant-quantity system:
|
(17) |
ant-density system:
|
(18) |
ant-circle system:
|
(19) |
受遗传算法中基因遗传、重组、变异等思想的启发, 本文提出一种新的信息素更新方式, 能够有效保留较好的路线片段, 并在不同路线片段之间合理组合, 以利于最优解的快速产生.第k只蚂蚁从i到j所留下的信息素改变为
|
(20) |
其中: w1 ~ w4为本文设置参数, 也是本文算法与其他算法的区别之处. w1、w2、w3、w4需要根据具体问题而定, 一般情况下w1为正数, w2、w3、w4为负数, 本文计算中采用w1=2.0, w2=w3=w4=-0.5.式(17) ~ (20)的取值依据为第k只蚂蚁是否经过i, j路段.
改进后需要补充定义新的符号如下.
Kkij:第k只蚂蚁所经过的点i到点j路段所在子线路的作战单元数;
Lkij:第k只蚂蚁所经过的点i到点j路段所在子线路的长度;
Rk:第k只蚂蚁所经过的线路总长度.
指标Kkij可以对优秀子路段上的信息素进行加强, 指标Lkij可以对访问点数目相同或相近的子路线进行区别, 指标体现了不同蚂蚁经过总路线的优劣.通过这样的信息素更新方式, 可以使得优秀的路段能够充分保留相对稳定性, 对于优秀路段内部的薄弱连接处则可能有较大的概率断裂, 从而产生更优秀的组合.在此基础上对所有路段信息素加一个较小的修正因子以保证一定的变异效果, 避免算法过早陷入局部最优.
|
(21) |
|
(22) |
|
(23) |
其中: α为残留信息的相对重要程度, β为启发式信息的相对重要程度, 本文令α=1, β=1; ρ为信息素挥发参数, 本文令ρ=0.5; τ0为信息素修正因子, 以增加不同路线的选择概率, 避免算法早熟, 本文令τ0=0.1.式(20)、(22)和(23)表示信息素的更新步骤; 式(21)表示第k辆配送车辆从作战单元i出发, 分别以不同的作战单元j为目标点的概率.
1.4 Solomon测试数据计算检验为验证算法的有效性, 采用Solomon标准测试数据中C1和C2类100个客户的共17组数据进行检验, 有15组计算结果达到了Marius个人网站上给出的Best Known Solutions[16], 其余2组结果也非常接近.为体现数据的真实性, 表 1和表 2给出了精确到小数点后4位的计算结果.
|
表 1 Solomon测试数据C1类问题计算结果 |
|
|
表 2 Solomon测试数据C2类问题计算结果 |
近年来, 军事物流配送问题得到关注, 研究人员开始探索战时物流配送的相关问题[17-20].文献[17-18]没有考虑敌方火力打击和需求变化问题; 文献[19]考虑了需求变化后的动态求解问题, 但案例数据变化太小, 仅增加一个需求点, 代表性不强; 文献[20]考虑了路网安全问题、道路对车速的影响等, 但并没有考虑物资损毁和需求变化.本文提出了敌方火力打击威胁下, 涵盖路网通行条件、车辆速度、物资损毁、作战单元需求变化等多重要素的战场物流配送案例假定, 建立了相应模型, 并给出合理的解决方案.
2.1 基本案例假定假定在一场局部战斗中, 某部队的一个物资配送中心需要对15个作战单元实施物资保障.配送车辆需节约使用, 各作战单元物资需求量已经明确.交战地域道路网络有一定损毁, 不同路段的车辆通行能力已经由情报侦查活动获知.有关部门对不同路段车辆遭受敌方火力打击的概率及遭受打击后物资损毁的概率进行了预测.希望在尽量满足作战单元需求的情况下, 减少车辆使用数目和车辆行驶总里程, 并尽可能减少物资损失.
配送中心及各个作战单元的具体位置如表 3所示.其中:序号0代表配送中心, 序号1 ~ 15代表需要提供配送服务的不同作战单元. 表 3给出了各作战单元对物资的需求量以及开窗、关窗时间.每个作战单元有一定的卸货时间, 车辆正常行驶的速度设为60.0 km/h, 车辆最大载运量为8.0 t, 车辆运行最大距离和最长时间不作限制, 车辆完成配送任务后返回配送中心.
|
|
表 3 战时物流配送案例基本数据 |
为定量确定路网受损情况对车辆运行速度产生的影响, 本文采用0 ~ 1之间的实数表示路网受损对车辆通行速度的影响程度, 如通行能力为0.8表示车辆在某受损路段的通行速度为正常速度的80 %.在前期交战过程中, 4、5、6、12、14号作战单元所在区域附近交火比较激烈, 该区域的道路交通网络受到敌方火力的重点打击, 产生了较大的损毁, 具体指标如表 4所示.
|
|
表 4 战时物流配送案例基本数据 |
假定路网中各路段受敌方火力打击的概率服从二项分布, 且不同路段相互独立.假定编号7、8、9、11、15几个作战单元所在的地域运输车辆受敌方火力打击概率较大, 编号4、5、14几个作战单元所在地域受到敌方火力打击的概率稍大, 其他作战单元受到敌方火力打击概率较小. 表 5给出了运输车辆通过路网中不同路段时遭受敌方火力打击的概率.
|
|
表 5 不同路段受敌方火力打击的概率 |
在实际作战问题中, 车辆经过不同路段遭受敌方火力打击后物资损失的概率可能会受到敌我双方兵力分布、作战目的、武器有效作战半径等多种因素的共同影响, 表 6给出了路网中车辆被打击后的物资完好率.
|
|
表 6 受到敌方火力打击后的物资完好率 |
下面分析车辆通过某一路段, 到达下一个作战单元时物资完好的概率pij. pij与该段路线被敌方火力打击概率paij和受打击后物资完好率pbij有关.本文在paij与pbij相互独立的前提下进行分析.
根据条件概率相关知识, 车辆通过某一路段后物资的完好率可以表示为
|
(24) |
以从第4个作战单元到第5个作战单元为例, 将pa45=0.4, pb45=0.6代入式(1)中, 可得
|
(25) |
通过这个方法可以计算出所有路段车辆通过后的物资完好率.
3 路径优化 3.1 问题的基本模型为解决考虑敌方火力毁伤和道路通行条件的战时物流配送车辆路径问题, 需要对该蚁群算法模型进行适当调整.主要有3项内容, 一是将路况通行条件对车辆运行速度的影响加入模型, 二是将敌方火力打击造成的概率损失加入模型, 三是目标函数不再是路线总长度最短, 而应是在确保完成任务、减少使用车辆数目的前提下使物资损失尽量减少.
为解决问题, 需要运输车辆在装载物资数量及运输时间上有一定的预判, 本文通过多次仿真计算得出的经验性目标函数及相应限制条件如下:
|
(26) |
|
(27) |
|
(28) |
式(26)为新的目标函数, 该目标函数充分考虑了受到敌方火力打击的物资损毁情况; 式(27)充分考虑了车辆选择从作战单元对作战单元服务所需要的物资载有量; 式(28)表示车辆从作战单元向作战单元所需要的行驶时间.
3.2 基本模型的求解分别对考虑敌方火力打击损失和不考虑敌方火力打击损失两种情况, 通过本文设计的蚁群算法进行计算, 得出的最优路线如图 1和图 2所示.其中:数字0 ~ 15表示配送中心和各个作战单元的坐标, 箭头表示车辆行驶方向.
|
图 1 不考虑敌方火力打击损失的最优路线 |
|
图 2 考虑敌方火力打击损失的最优路线 |
为进一步说明两条线路的不同效果, 采用仿真的方式对两条路线的线路长度、平均完成任务率、平均未完成的任务量(少交付最后一个被服务的作战单元的物资量)进行计算, 计算结果如表 7和表 8所示, 仿真次数为1 000次.
|
|
表 7 不考虑敌方火力打击损失的最优路线 |
|
|
表 8 考虑敌方火力打击损失的最优路线 |
由表 7和表 8可以看出:在不考虑敌方火力打击影响的前提下, 以总路线最短为目标函数, 得到的路线总长度为2 245.4 km, 使用车辆数目为4辆; 而考虑敌方火力打击时, 以物资损失最少为主要目标, 以线路总长度、车辆数目为次要目标的模型中, 得出的路线总长度为2 628.7 km, 使用车辆为5辆.虽然后者的路线长度和车辆数目都没有优势, 但完成任务的概率远远大于前者, 能够在很大程度上满足作战单元的需求, 这说明本文设计的算法模型达到了理想效果.
3.3 采用排队策略解决需求变化的实时路径优化考虑到在战斗进行中不同作战单元对物资的需求可能出现一定的变化, 下面对作战单元需求变化的情况进行建模和仿真计算.问题设置如下:运输车辆按照预定路线出发之后, 第4辆车运输过程中遭到地方火力打击, 其余车辆正常.敌方火力打击对运输线路造成了一定毁坏, 致使作战单元2、3之间及作战单元4、5之间的路段被毁, 无法通行.作战单元4、5、12、13、14、15的物资需求、时间窗、卸货时间等都分别发生了变化, 具体需求变化如表 9所示.
|
|
表 9 更新后的需求数据 |
只有第4辆车在第一段路程受到敌方火力打击, 由于该路段受到火力打击后物资完好率为0.9, 认为第4辆车到达目的地时已经损耗了0.8吨物资.将0.8吨计入到作战单元6的物资需求, 将其原需求量2.3吨修改为3.1吨; 作战单元2、3之间以及作战单位4、5之间的道路无法通行, 则将其对应的路线长度设为无穷大.
针对这种情况, 可以采用一种排队策略完成路线优化, 该方法的基本思路为:首先建立一个队列, 元素都设置为0, 代表配送中心.将已经确定为配送目标并开始实施配送活动的作战单元放在队尾, 依次从队尾取出一个作战单元放入队列, 选取符合约束条件的队列之外的作战单元作为下一个目标, 并依次完成路线搜索.待没有可选作战单元时返回配送中心, 再从队尾选取下一个作战单元放入队列, 这样既保证了已经发生的事实不再改变, 又能够在此前提下得出最优路径, 具体流程如图 3所示.
|
图 3 需求改变后求解模型的排队策略 |
通过这种方法, 用Matlab软件完成算法程序编写, 得出后续最优路线如图 4所示.
|
图 4 需求更新后的最优路线 |
为便于比较, 采用仿真检验的方法对该线路的运输效果进行检验, 表 10给出了对该路线的仿真检验结果, 仿真次数为1 000次.
|
|
表 10 需求更新后的后续最优路线 |
从仿真结果可以看出, 在已经确定运输路线并开始执行配送任务的情况下, 如果作战单元需求发生变化, 本文算法依然能够及时给出调整路线, 且调整后的路线能够有效完成配送任务.但本文算法也有一定的局限性, 在数据更新的情况设置中, 数据变化幅度较小, 且仅对部分数据进行了更新, 如果大量数据出现变化则很可能当前车辆无法满足要求, 需要另外派出运输车辆共同完成任务.
4 结论本文对蚁群算法信息素更新方式进行了一定改进, 并通过算例检验了所提算法的优越性.采用改进的算法对战时物资配送问题进行研究, 综合相对重要的影响因素建立模型, 并对假定案例进行求解, 通过仿真计算的方式验证相应算法的有效性和得出配送路线的合理性, 是对战时物资配送问题的有益探索.当问题规模较大时, 所提方法的求解时间比较长, 从而应在下一步工作中通过并行计算技术[21-22]加速战时物资配送问题求解.
| [1] |
段海滨. 蚁群算法原理及其应用[M]. 北京: 科学出版社, 2005: 33-38. (Duan H B. Ant colony algorithms: Theory and applications[M]. Beijing: Science Press, 2005: 33-38.) |
| [2] |
Paolo Toth, Daniele Vigo. The vehicle routing problem[M]. Beijing: Tsinghua University Press, 2011: 127-153.
|
| [3] |
伯克, 肯德尔. 搜索方法论[M]. 北京: 清华大学出版社, 2014: 271-280. (Burke, Kendall. Search methodology[M]. Beijing: Tsinghua University Press, 2014: 271-280.) |
| [4] |
蔡自兴, 王勇. 智能系统原理、算法与应用[M]. 北京: 机械工业出版社, 2014: 205-212. (Cai Z X, Wang Y. Principles, algorithms and applications of intelligent systems[M]. Beijing: Mechanical Industry Press, 2014: 205-212.) |
| [5] |
吕游, 杨波. 一种改进型蚁群算法在带硬时间窗的战场物资配送车辆路径问题中的应用研究[J]. 物流科技, 2015, 38(10): 123-126. (Lv Y, Yang B. Vehicle routing problem with hard time windows in battlefield resources distribution based on omproved ant colony pptimization[J]. Logistics Sci-Tech, 2015, 38(10): 123-126. DOI:10.3969/j.issn.1002-3100.2015.10.030) |
| [6] |
Amine Dhahri, Anis Mjirda, Kamel Zidi. A VNS-based heuristic for solving the vehicle routing problem with time windows and vehicle preventive maintenance constraints[J]. Procedia Computer Science, 2016, 80: 1212-1222. DOI:10.1016/j.procs.2016.05.473 |
| [7] |
Djamalladine Mahamat Pierre, Nordin Zakaria. Stochastic partially optimized cyclic shift crossover for multi-objective genetic algorithms for the vehicle routing problem with time-windows[J]. Applied Soft Computing, 2017, 52: 863-876. DOI:10.1016/j.asoc.2016.09.039 |
| [8] |
Viktor Danchuka, Olena Bakulichb, Vitaliy Svatkoa. An improvement in ant algorithm method for optimizing a transport route with regard to traffic flow[J]. Procedia Engineering, 2017, 187: 425-434. DOI:10.1016/j.proeng.2017.04.396 |
| [9] |
Michael S, Fabian S, Daniele V. Designing granular solution methods for routing problems with time windows[J]. European J of Operational Research, 2017, 263(2): 493-509. DOI:10.1016/j.ejor.2017.04.059 |
| [10] |
Emilio Zamorano, Raik Stolletz. Branch-and-price approaches for the multiperiod technician routing and scheduling problem[J]. European J of Perational Search, 2017, 257(1): 55-68. |
| [11] |
Claudia Archetti, Nicola Bianchessi, Grazia Speranza M. A branch-price-and-cut algorithm for the commodity constrained split delivery vehicle routing problem[J]. Computers & Operations Research, 2015, 64: 1-10. |
| [12] |
Tunchan Cura. An artificial bee colony algorithm approach for the team orienteering problem with time windows[J]. Computers & Industrial Engineering, 2014, 74: 270-290. |
| [13] |
Yong Shi, Toufik Boudouh, Olivier Grunder. A hybrid genetic algorithm for a home health care routing problem with time window and fuzzy demand[J]. Expert Systems With Applications, 2017, 72: 160-176. DOI:10.1016/j.eswa.2016.12.013 |
| [14] |
Errico F, Desaulniers G, Gendreau M, et al. A priori optimization with recourse for the vehicle routing problem with hard time windows and stochastic service times[J]. European J of Operational Research, 2016, 249: 55-66. DOI:10.1016/j.ejor.2015.07.027 |
| [15] |
Ng K K H, Lee C K M, Zhang S Z, et al. A multiple colonies artificial bee colony algorithm for a capacitated vehicle routing problem and re-routing strategies under time-dependent traffic congestion[J]. Computers & Industrial Engineering, 2017, 109: 151-168. |
| [16] |
Marius Solomon M. VRPTW Benchmark problems[EB/OL]. (2005-3-24)[2017-11-16]. http://w.cba.neu.edu/msolomon/home.htm.
|
| [17] |
苏涛, 王庆斌, 孙聪, 等. 蚁群算法的军事物流配送路径优化[J]. 海军航空工程学院学报, 2012, 27(3): 342-346. (Su T, Wang Q B, Sun C, et al. Research on the military logistics delivery routing optimization problem based on ant colony algorithm[J]. J of Naval Aeronautical and Astronautical University, 2012, 27(3): 342-346.) |
| [18] |
张锦, 聂伟, 沈军, 等. 大规模作战物流配送VRP模型及求解[J]. 军事交通学院学报, 2015, 17(11): 59-63. (Zhang J, Nie W, Shen J, et al. Logistics distribution VRP model and its solution in large-scale combat[J]. J of Military Transportation University, 2015, 17(11): 59-63. DOI:10.3969/j.issn.1674-2192.2015.11.014) |
| [19] |
郝瑞卿, 闫莉. 军事配送式后勤车辆路径问题研究[J]. 西安工业大学学报, 2015, 35(1): 63-69. (Hao R Q, Yan L. Research on military distribution logistics vehicle routing[J]. J of Xi'an Technological University, 2015, 35(1): 63-69.) |
| [20] |
甄义林.基于遗传算法的战区弹药保障技术研究[D].天津: 南开大学信息技术科技学院, 2013: 47-50. (Zhen Y L. The ammunition support technology research in the military theater based on the genetic algorithm[D]. TianJin: Department of Information Technology and Science, Nankai University, 2013: 47-50.) |
| [21] |
Chunye Gong, Jie Liu, Lihua Chi, et al. GPU accelerated simulations of 3D deterministic particle transport using discrete ordinates method[J]. J of Computational Physics, 2011, 230(15): 6010-6022. DOI:10.1016/j.jcp.2011.04.010 |
| [22] |
Chunye Gong, Weimin Bao, Guojian Tang. A parallel algorithm for the riesz fractional reaction-diffusion equation with explicit finite difference method[J]. Fractional Calculus and Applied Analysis, 2013, 16(3): 654-669. |