战区内战时军事运输路径优化研究

杨文索　姚金凯　王　耀

摘要：军事运输路径优化研究，是军事物流系统优化的重要内容，特别是在运输网络密度程度比较高的战场，合理选择运输路径，可以提高军事运输的安全性、时效性和经济性，从而能够极大地增强军事运输的保障效率与效益。文章立足战场实际，分析了战时交通网络的特征，在综合权值基础上运用经典的Di jkstra算法，探寻最优路径。

关键词：战时；军事物流；路径优化

中图分类号：U116.2文献标识码：A

Abstract: The research of military transportation route optimization is an vital part of military logistics optimization. Especially in war field which has dense transportation network, choosing transportion route reasonably can improve military transportation's timeliness, safety and economy, for which strengthening supportability rate and benefit. The thesis is based upon practice of war field, analyzing the characteristics of transportation network in war, using classical Dijkstra arithmetic on the basis of integrate parameter poporation, exploring the optimal route.

Key words: wartime；military logistics；optimal path

0引言

军事物流的组织实施过程，既是一个创造军事效益的过程，也是一个创造经济效益的过程。为使军事物流能够提供最佳的价值效能，必须保证在实施军事物流的各阶段、各环节的实施过程都达到最优，从而保证军事物流的过程通畅迅速，适应军事物流组织优化的要求。所以，要运用科学的方法，选择合理的运输方式，确定最佳的运输路线，制定最优的运输计划，力求以最低的运输成本、最快的运输速度、最少的运输时间、最短的运输距离，达到最佳效果、最高效率和最大能力，使军事运输各个过程、各个阶段和各个环节都达到合理优化。其中，运输路径优化是制定运输计划的基础，也是当前军事物流领域研究的热点问题。目前，边权值为常量的静态交通网络最短路问题研究已非常成熟，这些研究多少与战时的多权值的动态交通运输网络有些不符。本文就是从战场的实际情况出发，运用经典的Di jkstra算法，求解多目标、多约束的交通运输网络的路径优化问题。

1战时交通网络的路径优化模型

战时条件下交通网络路径优化有其自身的特殊性：一是运输路径的优化，在达到军事目标的同时，相应的也要注意经济效益的提高，不但要求运行时间最短，运行速度最快，而且还要求运费最省，追求的目标体现在综合性上。二是影响路径选择的因素和约束条件大大增多，具有多边权、多因素、多要求的特征；三是由于战时交通环境条件的恶劣性，导致交通网络的结构特征、功能不断发生变化，路网动态特征更为明显。

战时条件下的军事运输路径优化仅考虑路网中的单边权是不够的，路径的优化应该受到多边权的影响。路边权应该是和运输时间、交通条件（如交通流量、运输距离）、道路条件（如道路类型、道路等级、道路通行能力等）、运输风险（气候条件、受敌威胁程度和隐蔽程度）、运输经济性（运费、燃料消耗、后勤保障消耗）等多方面的限制因素有关，与之同时，还要贯彻落实上级首长或运输指挥决策者的主观意图，在综合各种影响因素的基础上才能做出路径优化决策。因此，需要综合考虑上述各方面因素对路径优化的影响，并采用某种科学方法将这些因素加以集成，进而再确定出最优运输路径。为此，我们提出了运输线路综合权的概念，既综合考虑了战时影响路径优化的各种因素，又适合运用经典的Di jkstra算法进行求解。

2战时交通网络路径优化算法分析

2.1Di jkstra算法简介

Di jkstra算法将路网节点分为未标记点、临时标记点和永久标记点三种。算法过程就将路网所有节点初始化为未标记点，搜索过程中把与起点相连通的节点标记为临时标记点，每次循环都是从临时标记点中搜索出距起点权值最小的节点作为永久标记点，直至找到终点成为永久标记点来结束算法。其算法的基本思想，就是设置永久标记点集合并不断做贪心选择来扩充这个集合，将节点V插入L中当且仅当从起点Vs到v的最短路径长度已知。执行过程中，每一节点Vi都对应一个两元组di，pi，其中di是从起点Vs到Vi的最短路的长度，pi则是从Vs到Vi的最短路径中Vi的前一点。

用Di jkstra算法求解从起点Vs到终点Vn的最短路径的具体步骤：

①从起点开始，令d1=0，di=∞，pi为空，L={Vs}，并令k=1。

②考察所有Vk∈L到与其直接连接的未标记点vi的距离，并设置，di=min{di,dk+Wki}其中Wki是从Vk到Vi的权重。

③从所有未标记的节点中选取di最小的节点Vi，将其设置为已标记节点，即L=L+{Vi}。

④从已标记的节点中找到与Vi直接连接的节点Vj*，作为Vi的前一点，即pi=Vj*。

⑤如果Vn已标记，则算法终止；否则，令k=i，转入②。

2.2模型转化求解

首先确定运输线路上的几个最重要的边权，在综合考虑多个边权的基础上，将每条运输线路的情况用线路矩阵D表示。假定：Tij、Cij、Qij、Dij分别代表第i点到j点之间线路的运行时间、运输费用、交通条件恶劣程度和运输风险。

A= TCQD T C QDi

对线路矩阵进行标准化处理。令T＝max{Tij}，C=max{Cij}，Q＝max{Qij}，D=max{Dij}，则可得到标准化矩阵。

=i

根据运输决策指挥人员的主观意图，确定权系数矩阵为M＝｛MT,MC,MQ,MD｝，其中MT+MC＋MQ+MD＝1，分别代表运输决策指挥人员认为运行时间、运输费用、通行能力与安全系数影响运输线路决策的重要程度。

将权系数矩阵与标准化矩阵相乘，便可得到各线路的综合权B矩阵。

B=MMMM=B,B,…,B i＜j

确定了运输线路的综合权之后，就将多权值的交通网络路径优化问题转化为确定最小综合权的单权运输线路优化问题。因此，可运用经典的Di jkstra算法探寻其最优运输路径。

2.3含特殊要求的运输路径优化算法

对于必经点和禁行路段的处理问题，算法的基本思想是以运输网络中的必经点为界，将原运输网络分成两个子网络，必经点作为前一运输子网络的终点，同时作为后一运输子网络的起点，分别求算两个运输子网络的最短路径，两个子网络的最短路径相连，便是经过该必经点运输网络的最优路径。

对于含有必经路段的运输路径优化问题，算法的基本思想是将必经路段看作一个点，这样就简化为必经点问题。以必经路段为界，将原运输网络分成两个子网络，必经路段的起点作为前一运输子网络的终点，必经路段的终点作为后一运输子网络的起点，分别求算两个运输子网络的最短路径，两个子网络的最短路径相连，便是经过该必经路段运输网络的最优路径。

对于含有禁行点或禁行路段运输网络路径优化问题，算法的基本思想是将禁行点或路段从原运输网络中去掉，再探寻原运输网络的最优路径。

另外，战区运输路径优化还会遇到为部队提供多条最优运输路径问题，对于这一问题，算法的基本思想是首先运用经典最短路算法，求出一条最优路径，然后通过消除替换最优路径中的部分路段以寻求备选路径。选择的消除路段可以考虑战时易遭到敌人破坏的路段，或交通不便的路段等。这一算法的突出优点是它的简便性——备选路径可以像最优路径一样很容易被确定出来。

3实例分析

以战时条件下东南沿海某一公路网段为例：

有一批保障物资要从战役后方基地V1（起点）经过此公路运输网络运输到前沿需求点V7（终点）。在此公路网络中，V2～V5公路段中唯一可通行的桥梁已被敌方破坏，短时间内已经无法通车。V6是此网络运输点的重要的指挥保障点，所有的运输物资都要在此通过，然后运往V7。因此，V2～V5路段已成禁行路段，在运输网络优化中可以去除。而V6是必须要经过的节点（如图1所示）。

（1）如果各权值取值范围为1～15，图1利用加乘同余法随机生成各段线路的权值，可以得到线路矩阵：

A=

（2）对线路矩阵进行标准化处理。可知T＝max{Tij}=13，C=max{Cij}=12，Q＝max{Qij}=14, D=max{Dij}=14, 则可得到标准化矩阵;

=

对于运行时间、运输费用、交通条件恶劣程度和运输风险影响运输线路决策的重要程度，根据运输决策指挥人员的主观意图并结合专家评分，得出权系数矩阵为M＝｛MT,MC,MQ,WD｝={0.2,0.1,0.3,0.4}。