基于蚁群算法的战时运输路径优化模型

摘要： 针对多式联运，必经点等战时维修器材供应运输中的现实问题，考虑当各路段通行时间和运输方式转换时间为随机变量时，建立起了给定时间的最大置信水平约束下，以最小时间和费用为优化目标的随机机会约束模型，然后根据所建模型特点，基于随机模拟方法，设计了的模型求解的蚁群算法。算例结果表明：该模型和和算法具有有效性，能为确定战时交通运输路径提供有效的决策支持。

关键词： 多式联运；时间；费用；置信水平；蚁群算法

中图分类号：E8文献标识码：A文章编号：1006-4311（2012）04-0319-030引言

后勤保障过程中的军事运输行为，需要实现军事效益与经济效益的统一[2]，战场情况复杂多变，实现军事效益要求在规定运输时间内，找到最大置信水平的运输路径；实现经济效益则要求在规定运输费用内，找到最大置信水平的运输路径。此外，现代战争中的交通运输包括众多运输方式的组合，多式联运是指采用两种或者两种以上的运输方式，把物资从起始地运送到目的地。因此，研究多式联运的运输路径优化更加贴近于实际，也更有意义。

笔者基于多式联运，考虑当各路段通行时间和物资中转时间为随机变量时，在给定的时间和费用指标约束下，建立时间和费用的最大置信水平的多目标优化模型。

1战时交通运输路径优化模型

1.1 路网建立根据战时的军事运输任务，建立从运输起点到终点的网络图G=（V,A,D,T1,T2,K），其中：V代表节点集，设节点总数共计n个，节点序号采用自然数序列编码，起点编为“1"，终点编为“n”，即节点的总个数，A代表弧的集合，即路段集合，D代表各路段的距离集合，d■■∈D，表示路段（i，j）之间第k种运输方式的距离，T1代表各路段的时间权集，T2代表运输方式转换时间权集，K表示运输方式集合（公路、铁路、航空等）。

在战时的军事运输中，必须考虑必经点和禁止点、必经路段和禁止路段问题。对于禁止点和禁止路段的处理，在赋权图中可将与禁止点和禁止路段相连的路段以及自身从网络图中删除，因此最后得到的节点集合V应该是除去了禁止点和禁止路段包含节点的路网节点集合，而弧集A则是除去禁止路段和与禁止点、禁止路段相连路段的整个路网路段集合。对于必经路段，可将路段的起、止点转化为必经点，这样与原有的必经点一起构成必经点集合，设为VM。此外，设Vk表示所有可能存在运输方式转换的节点集合。

1.2 时间的确定运输分队通过各路段的时间变量，以及运输方式转换时间变量可能服从某种分布函数，可以为正态分布、均匀分布等等，则时间权集集合定义为T1=t■■（i，j）∈A，k∈K，t■■表示节点（i，j）之间，以k种运输方式通过该路段的时间；T2=t■■i∈VK，m，n∈K；，t■■表示在阶段i从第m种运输方式转换到第n种运输方式的转换时间，节点i前后运输方式相同时，t■■=0。如当通过某一路段的时间变量服从正态分布时，可以记为t■■~N■，?滓■■2■，其中■表示节点（i，j）之间，以k种运输方式通过该路段的时间均值，?滓■■为时间的均方差；某一运输节点运输方式转换的时间变量服从均匀分布时，可以记为在t■■~U（ta，tb），其中ta和tb分别为时间的上、下界。另外一些情况下，以各种时间通过某路段或完成维修器材从一种运输方式转换为另一种运输方式的的时间可能无法获得它的准确分布函数，只能根据先前经验获得估计时间变量的概率（或称为频率）。

1.3 模型建立设X=x■■（i，j）∈A，k∈K表示起点到终点一条路径，其中x■■∈{0，1}。如果x■■=1，则表示运输分队经过（i，j）这条路段，且采用的运输方式为k，否则x■■=0，则表示弧（i，j）不在这条路上或未采用第k种运输方式。假设维修器材在两个节点间只能选择一种运输方式和一条运输路径。

结合各路段的通行时间和维修器材运输方式转换时间，可以得到运输分队通过该路径的总时间函数定义：T=■■t■■x■■+■t■■

多式联运下的运输费用由各路段运输费用和节点运输方式转换费用两部分构成。

设c■■表示采用第k种运输方式时，单位维修器材的单位运输距离的资金耗费，则当采用第k种运输方式时，路段（i，j）间进行单位维修器材器材运输所需的费用C■■可表示为：C■■=c■■×d■■

设C■■表示在节点i，单位维修器材从第m种运输方式转换到第n种运输方式的转换费用， 则可建立从运输起始点到运输终点之间，多式联运下的运输总费用函数C可表示为：

C=■■x■■×C■■+■■C■■=■■x■■×c■■×d■■+■■C■■

这样，当运输路径决策同时考虑运输时间和运输费用目标时，就可以建立起随机机会约束优化模型。

min Tmin min C s.t.

P{T?燮Tmin}?叟?琢 （1） ■■x■■=1 （2）

■■x■■-■■x■■=0，?坌j=2，3，…，n-1（3）

■■x■■=1（4）

■■x■■=1，■■x■■=1，?坌m=VM（5）

x■■∈{0，1} ?坌（i，j）∈Ak∈K（6）

其中：（1）式中T为运输分队的运输总时间函数、?琢为置信水平、Tmin为优化目标，即T的?琢悲观值；C为运输分队的运输费用函数。上述优化的含义是运输分队以时间T不低于置信水平?琢，在时间Tmin内到达终点，且费用要尽可能低。（2）式为起点约束方程表明运输分队从起点出发，只能选择一条运输路段和一种运输方式作为运输道路。（3）式为中间节点约束方程，该约束符合中间节点的流量平衡要求，即运输分队进入某一中间节点必须还要从该节点出发，不能停留或消失。（4）式为终点约束方程，该约束表明，运输分队最后到达了终点。（5）式为必经点约束方程，该约束方程表明运输分队出行的路径中必须包含每一个必经点。（6）式为0-1约束。

通过求解所建立的模型，就可以搜索出给定运输时间要求下，运输费用最小的最大的置信水平路径。

2基于蚁群算法的模型求解

2.1 模拟求解方法各种分布随机数的产生参见文献[12]，假定已得到了一条路径，路段总数为m，途经了n次运输方式转换，由该路径包含的各路段通过时间和维修器材运输方式中转时间所得到m+n个随机时间变量记为t1，t2，…，tm+n。则有模拟求解算法为：

Step1：给定模拟的总次数N，置i=1；

Step2：分别依据第j个时间变量的概率分布函数或经验分布，产生满足需求的0-1之间的随机数，进而得到对应的通行时间tj，其中j=1，2，…，m+n，计算；Ti=■tj

Step3：令i=i+1，如果i?燮N，转Step1，否则对得到的T1，T2，…TN,按降序排列，取第[?琢N]个，“[]”表示四舍五入，即为所求。

2.2 适应度函数建立根据所建立的模型，有在给定?琢置信水平时，随机机会约束模型的目标函数为：opt.min Tminmin C

首先，对目标函数进行无量纲化处理。分别以时间和费用为对象，从当前代种群中选取最大者和最小者，记为Tmax、Tmin和Cmax、Cmin，然后对每只蚂蚁搜索所得路径的时间和费用进行无量纲化处理。