基于自适应遗传算法的联合投送路径优化设计研究

张恩泽, 高 毅， 张 辉

(1.95486部队；2.96756部队；3.火箭军工程大学 基础部，陕西 西安 710025)

1 问题描述与分析

现代大型军事行动中采取联合投送[1-5]的方式进行运输传送，但由于联合投送具有距离远、任务多、道路约束强等特点，在投送方案的选取上具有较大的挑战性。现考虑通过铁路和公路两种方式对多个编组进行投送，每个编组由若干梯队组成。计划编成若干个梯队，对梯队进行编组，通过公路、铁路两种方式运输。联合投送规则如下：

1)在运输的过程中，编组不允许在中间路段、节点停留，同一个编组只能选择同一条投送线路，如果需要进行线路转换，只允许存在铁路转公路的情况，并且最多转运一次。设有A、B、C三种编组类型，若目的地相同，规定必须B型编组全部梯队都到达后才允许其他编组进入，而对于A型编组而言，优先考虑铁路运输。

2)一个编组的投送时间应当保持连续，如果该编组当天未完成投送任务，则第二天继续进行该编组的投送，直到该编组投送完毕再进行下一编组的投送。

3)每一个路段都有相应的最大投送能力，每天通过各节点进入该路段的总梯队数不能超过其最大投送能力。一旦超过最大投送能力则立即关闭，第二天再开启投送通道。

4)投送起点和终点、从铁路转运到公路时分别要进行装卸载，整个装卸载的耗时忽略不计。铁路上每天的装、卸载最大梯队数为15梯队，公路为10梯队。

假设投送方式的转换只能发生在节点，且节点处的场地、设施满足运输方式转换的要求，不考虑实时路况对联合投送过程中的影响，不考虑车辆损坏、交通事故等意外事件的发生，不考虑恶劣天气等自然因素对联合投送的影响，同时道路负荷不会引起道路中断。根据任务设计合理的联合投送方案，在设计投送方案的时候需要考虑到总任务完成时间、各编组投送时间、总投送里程、道路负荷等因素。

由于作战物资的投送分为三种编组类型，每种编组类型包含若干出发节点和目的节点不同的编组，而每个编组又包含若干梯队。由于每个路段的最大投送能力不同，每个节点装、卸载梯队数也不尽相同，而且每个节点有多个可供选择的下一路段，因此总任务完成时间由各编组投送时间决定，总的投送里程由各编组投送里程决定，道路负荷则受到各编组路径选择的影响。需要解决的问题是：综合考虑总任务完成时间、各编组投送时间、总投送里程以及道路负荷等因素，给出最优的投送方案。

对于此问题，首先将物资的联合投送问题抽象为由节点以及连接节点的弧(即节点之间的路段)构成的有向虚拟网络图，该网络图的每条弧上都赋予了非负的权值；其次建立路径优化模型，然后将每段路的最大投送能力看作是容量，而得到最优投送方案需要考虑的总任务完成时间、各编组投送时间、总投送里程等因素则看作是费用，因此可以采用最小费用最大流算法进行求解。当不同编组路径发生冲突时，则采用排队论思想或次优解的方法进行求解，最终将其转化为一个带有时间约束、里程约束和容量限制的最短路径优化问题。在对不包含负权环路的情况下，可以先构造邻接矩阵，再利用Warshall-Floyd算法[6]求解出单个编组的最优解，然后利用自适应遗传算法[6]对所有找到的单个编组的解进行优化，最终得出综合所有因素后的全局最优解，求解流程图如图1所示。

图1 问题求解流程图Fig.1 Flow chart of problem solving

2 路径优化设计模型与算法

由联合投送要求及对问题的分析，采用Warshall-Floyd算法和自适应遗传算法对投送方案进行求解。要遵循一些原则从而达到提高联合投送的效率、降低投送成本的目的，具体包括充分利用道路资源原则、时间和里程综合最优原则、任务需要原则等。这是一个多式联合投送问题，需考虑运输方式对最优解的影响，如图2所示。A、B、C三种编组出发时路径、投送方式、每天发出的梯队数均可以不同，且起点、终点也可以不同，所以在对其建立模型时要分层次进行，用约束条件分别对不同编组进行模型建立，然后再综合优化进而得出全局最优解。

图2 多式联合投送路径图Fig.2 Multi-type joint delivery path graph

由于交通信息复杂，可抽象简化将投送路线网看作是一个虚拟网络，交叉路口、车站或城市看作是节点得到投送路线网络图，投送过程中每个编组有不同的起点和终点以及中间点。

建立多个编组联合投送的数学模型要求解的路径较多，且要综合考虑到运输方式的选择、投送时间及道路负荷等影响因素，同时不同编组可能在同一路段上发生冲突，因此在求解过程中要划分层次，逐个解决。单个编组考虑的最优路径是局部最优，但现在需要综合考虑不同编组路径的组合是全局最优。由于局部最优解的线性组合无法代表综合最优解，所以首先得到排名靠前的十组次优解，然后利用自适应遗传算法在这些次优解中优化得出综合最优解。

2.1 A型编组的路径最优模型

单个编组在投送过程中的最优方案与路段的最大投送能力、投送时间、投送里程有着密切的关系。将影响投送的因素作为求解最优路径的权值赋给每条路段，建立模型

惩罚因子为

若选择公路，ω将会使得出的解变大，不满足最优的思想，这样就可以将优先走公路的路径筛除；而选择铁路时，不会对求解最优路径造成影响，惩罚因子ω用来保证A型编组优先选择且充分利用铁路。

根据实际需要，里程和时间指标的重视程度需要进行分配，取α=0.45，β=0.55。因为不同权重的量纲和数量级有所差异，为屏蔽数值量纲差异，确保求解结果的可靠性，需将里程d和时间t进行归一化处理,得模型

约束条件为

约束条件1)～ 3)分别表示网络中起点、中间点及终点为满足得到一条从起点到终点的完整路线；约束条件4)是用来筛选得到的解中满足只能由铁路转为公路，且至多转运一次；约束条件5)表示从任意节点vi出发只能选择一种运输方式，对同一编组只能选择同一条投送路线进行了限制；约束条件6)可以保证单个编组在运输方式上的连续性。

2.2 B、C型编组的最优路径

在求解B、C型编组的最优路径中，求解思路与A型编组的方法类似，且同样要进行归一化处理，但B、C型编组没有充分利用铁路的要求，因此对于B、C型编组的求解不需要利用惩罚因子ω对运输方式筛选，模型为

C型编组在求解过程中的约束条件与A型编组基本一致，故可直接利用上述A型编组的约束条件对B、C型编组进行约束，然后根据模型解得B、C型编组的10组次优解。

2.3 综合优化所有次优解，得出全局最优解

在得出所有次优解后，综合所有编组，考虑到总投送时间要最短，建立如下模型(如图3)：

满足的约束条件为

11)∑i,jktsBijvij≤∑i,jktsAijvij；

12)∑ijktsBijvij≤∑ijktsAijvij,

其中决策变量为

约束条件7)～9)保证投送过程中通过起点、终点和转运点的梯队数不超过节点每天允许的装卸载梯队数；约束条件10)保证每天通过节点进入路段的总梯队数不超过该路段的最大投送能力；约束条件11)和12)保证多个编组目的地相同时，所有B型编组全部到达后，其他编组才能进入。

图3 随机次优解路径图Fig.3 Path table of stochastic suboptimal solution

3 模型求解

假设有29个铁路节点和29个公路节点，共计58个节点。对于不包含负权环路，先构造58×58的邻接矩阵，再利用Warshall-Floyd算法求解出单个编组的最优解，然后利用自适应遗传算法对所有找到的单个编组的解进行优化，最终得出综合所有因素后的全局最优解。

3.1 Warshall-Floyd算法求解局部最优解

对于58×58邻接矩阵，对于其中实际不存在的节点，令其与剩余任何节点的里程距离和时间距离都为无穷大，对于实际存在连接关系的公路与公路节点，铁路与铁路节点，它们间的距离和时间按照实际里程距离和实际时间距离构造。考虑到公路不能转铁路而铁路可以转公路，则令铁路到公路里程距离和时间距离为0，令公路到铁路的里程距离和时间距离为无穷大。再根据带权重的时间距离和里程距离，采用Warshall-Floyd算法求解最短路径，为了避免局部最优无法代表全局最优，现对每一个编组保留较短的10条路径，作为后续算法的输入参数。

3.2 用自适应遗传算法求解全局最优解

现采用自适应遗传算法，以每个编组保留的10条路径为对象，综合考虑所有约束条件，对所有编组进行全局优化，最终得出最优解，如图4～图7所示。

染色体编码：每一个染色体作为一个可行解，存储在一个元胞数组Chorm中，Chorm{:,1}存储21个编组的路径信息，Chorm{:,2}存储21个编组的投送出发时间，出发时间以及每天投送量依据各段道路的承载能力和各个路段耗时情况，按照避免拥塞和超过载荷的原则，对每天的投送量按短板效应原则分配，Chorm{:,3}存储对应21个编组得选择方案来自于Top_10的索引位置。

图4 最优解示意图Fig.4 Schematic chart of optimal solution

图5 优化过程1Fig.5 Optimization process 1

图6 优化过程2Fig.6 Optimization process 1

图7 各个路段利用甘特图Fig.7 Gantt table of each section used

优先级计算：考虑到目的地相同的有四组，其中每组中都有一个B型编组，并且当多个编组的目的地相同时B优先级最高，然后根据冲突数量衡量编组优先级，冲突多的为了不影响其他编组的投送，故冲突多的优先级高。所以先给B进行优先级排序，对每一个染色体的21个编组进行冲突预运算，计算每一个编组中所有路段在其他的重复情况，并以重复量作为编组出发顺序的依据。

适应度计算：建立一个118×N的路段容量记录器，按照计算的优先级顺序投送编组，并实时更新路段容量记录器的容量，在投送下一个编组时，也按照前段投送原则，如果路段拥堵不能投送，则推迟发送时间，当超过预设的时间后则不再投送，按优先级顺次到邻近编组进行投送，并将二者优先级对调，每执行完一次投送都要清空编队未投送标志。当所有标志位都清空时，此时的所得值就是最终的投送时间消耗量，该时间消耗量就可以代表适应度。

交叉操作：获取Chorm{:,3}的所有编组代号，根据编组适应度值自动选取合适的交叉概率Pc对相邻的两个染色体相同位置的编组号进行交叉，交叉长度随机生成。

变异操作：根据编组适应度值自动选取合适变异概率Pm对每一个染色体编码随机选择位置进行变异操作。

选择操作：按照设定的代沟GGap将新产生的个体和原种群中适应度高的插入到原种群中得到新的种群。

最后根据上述算法，利用MATLAB编程求得A、B、C型编组的最优路径设计方案，如表1所示。

表1 联合投送最优路径设计求解结果

4 小结

本文研究了联合投送最优联合投送路径规划方案问题，提出基于协同进化的自适应遗传算法进行模型求解，较好地解决了易陷入局部最优解、收敛速度慢的问题。对整个联合投送作战地域进行划分，充分考虑总任务完成时间、各编组投送时间、总投送里程、道路负荷等因素，引入带有混合时间窗的惩罚函数，建立联合投送路线管理模型，优化联合投送路径安排，逐步优化了联合投送路径。考虑到任务需要，指挥员可能对时间或对车辆行驶里程重视程度不同，故用相对权重α和β对其进行了分配，可以灵活地改变它们的取值来对投送方案进行重新制订，具有较强的战场适应能力。事实上，该问题也可应用于运输网络等诸多领域，如民用海港口集装箱航线运输等，进一步研究可用于未来战场中“陆—海—空”联合作战的物资投送，提高模型的精确程度后可为我国国防领域提供理论支撑与技术支持，具有较强的理论价值与现实意义。