改进的遗传算法在战时油料运输车辆路径问题中的应用研究

蒋敬东　周庆忠　李　凌　杨　方

摘要：文章首先对战时油料运输车辆路径问题（VRP）进行了分析，阐述了战时油料运输车辆路径问题的优化目标，并建立了多目标的优化模型；接着简介了遗传算法的优缺点，并设计了一种改进的遗传算法运用到问题的求解中；最后举例进行了计算和分析，验证了模型和算法的有效性。

关键词：战时油料运输；车辆路径问题；遗传算法

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

Abstract: In this paper, the author firstly analyses the vehicle routing problem of POL transporting during wartime, states the optimization goals of VRP and build a multi-object optimization model. Then the author briefly introduces the genetic algorithm and constructs an improved genetic algorithm which is used to solve the problem. At last, an example is given to prove the efficiency of the model and the algorithm.

Key words: POL transporting during wartime; vehicle routing problem; improved genetic algorithm

1问题分析

战时油料运输车辆路径问题（VRP），是指在战时一个油料供应点保障多个部队用油的情况下，寻找一条最优的巡回路径。传统意义上的最短路程巡回路线在战时并不具有很大的实际意义，决策者需要的是能够在规定时限内完成任务，且运输代价（主要指损失、时间和路程）最小的方案。

2模型的建立与求解

2.1遗传算法简介

遗传算法是模拟生物在自然环境下的遗传和进化过程而形成的一种自适应全局优化概率搜索方法。它首先对问题的可行解进行编码，组成染色体，然后通过模拟自然界的进化过程，对初始种群中的染色体进行选择、交叉和变异，通过一代代进化来找出最优适应值的染色体，它具有很强的全局搜索能力和较强的自适应性，适合解决连续变量函数优化问题和离散变量的优化组合问题[1]。

然而，遗传算法仍具有很多问题，如早熟、收敛慢等，本文对遗传算法进行一定的改进，并将其运用到战时油料运输车辆路径问题中。

2.2模型的建立

将油料运输网络抽象，构建网络图G=V，E，W。权重集W=T，L，D，其中，T表示时间集，tij表示路段i，j通过时间，L表示损失集，lij表示路段i，j油料运输损耗率，D表示路程集，dij表示路段i，j的路程。

根据优化目标，可以建立模型如下：

minC=•YLx+•Dx+•Tx

s.t.Y=Y•1-Lx≥T=Tx≤x∈0,1

式中：

（1）Yi、Ti表示到达第i个节点时的油料运输量和经历的时间；

（2）、、分别表示损失率和路程在优化目标中所占的权重；

（3）i、i分别表示第i个节点处的指定的运输量和时限；

（4）xij是0-1变量，当路段i,j在所选路线上时，xij=1，否则，xij=0。

2.3模型的求解

（1）、的值可由决策者根据战时要求并参考专家意见确定。

（2）为简化计算和统一量纲，对数据进行归一化处理。设起点的运输量为1个单位，即Y1=1；设Dmax=maxD=1，则Dij∈0,1。

（3）采用改进的遗传算法求解。

3改进遗传算法的设计

3.1染色体编码

根据油料运输车辆路径问题的特点，本文采用简单直观的自然数编码方式构造染色体，染色体的基因表示油料运输网络中的节点，基因的排列顺序即表示由起点到终点的路线。

设油料运输网络中有一个供应点和n各保障点（用油部分队），用0表示供应点，1,n之间的自然数表示保障点。若供应点有m个运油分队参与油料运输, 则需要寻找m条巡回路线，即一种路线选择方案。如染色体0120345607890表示的路线选择方案是：0-1-2-0、0-3-4-5-6-0、0-7-8-9-0。

3.2种群初始化

种群初始化是产生表示起始搜索点的初始群体数据。随机生成1,n之间n个自然数的一个全排列，再将m+1个0随机插入到生成的排列中，排列的头部和尾部都必须有且只有一个0，这样就构成了需要的染色体。

3.3适应度计算

遗传算法中以个体适应度的大小来评定各个个体的优劣程度，从而决定其遗传机会的大小。在本问题中，是以求函数最小值为优化目标且目标函数C非负，故可用目标函数的倒数作为个体的适应度，即：

F==

3.4染色体选择

选择运算是把当前群体中适应度较高的个体按某种规则或模型遗传到下一代群体中。常用的方法是轮盘赌选择法，但轮盘赌的选择方式使每个个体都有被选中的机会，降低了进化的效率。本文对算法进行了改进，采用依个体适应度比例选择的方法，使适应度高的个体有更多的机会遗传到下一代种群中。具体算法是先求出某个体的适应度占种群中全部个体适应度总和的比例，则此比例与种群数目的乘积即是该个体在下一代种群中复制的数量。

3.5染色体交叉

交叉运算是遗传算法中产生新个体的主要操作过程，它以某一概率相互交换某两个个体之间的部分染色体。常用的交叉方法有很多种，不同的方法适用于不同的情况。针对本问题的特点采用类OX法[2]。其算法基本操作过程是：

（1）生成随机数，若随机数小于交叉概率，则进行下面的步骤；

（2）对种群中的个体进行随机配对；

（3）随机选择两个交叉点的位置（不包括0基因），两交叉点之间的部分称为匹配区域段；

（4）将匹配区域段分别加到另一个个体的前面；

（5）删除每个个体中的重复基因。

为了加快种群的进化速度，本文对上述交叉算法进行了改进，即按照上述的算法将每对配对个体进行多次交叉，从产生的多个新个体中选择两个最优个体遗传到下一代种群中。

3.6染色体变异

变异运算是对个体的某一个或某一些位置的基因值按某一较小的概率进行改变，它也是产生新个体的一种操作方法。

本文采用的染色体变异方式有两种：

（1）随机选择某个个体的两个基因，将其调换位置；

（2）随机改变0基因的插入点。

同时比较变异前后染色体适应度的变化，若适应度提高，则将变异后的染色体保留到种群中，否则，保留原来的染色体。

3.7参数的选择

遗传算法中的控制参数包括种群规模、染色体长度、交叉概率、变异概率和进化代数等。参数的选择非常关键，过大或过小都会对算法的性能产生不良的影响。一般来说，种群规模取20～100、交叉概率取0.4～0.9、变异概率取0.001～0.01、进化代数取100～500比较合适[2]。

4实例分析

某油料供应点A负责对其周边的8个部队进行油料保障，已知该供应点到各部队之间的路程、行驶时间、可能的损失率以及各部队的油料需求量（见表1～表4），有2支运油分队可以使用，要求24小时之内完成对所有用油部队的油料补充，试选择最优的运输路线[3]。

（1）求解。取种群规模为20，交叉概率为0.8，变异概率为0.01，进化代数为100。通过模拟计算，在第65代时得到最优结果（表5所示为搜索寻优过程）。最优路线为：A-8-2-1-A、A-4-3

-7-5-6-A，两只运油分队分别承担0.30和0.70的任务。方案适应度为0.9871，损失为0.4438，时间为16小时，路程为82公里。

（2）结果分析。下面对2支分队共同参与油料运输的情况做以分析，得出在不同任务量下不同的最优路线，这些路线的适应度差别不大，在战时遇到敌人袭击或其他突发事件时可以作为备用路线替换。

5结束语

本文建立的模型和改进的算法较好地解决战时油料运输车辆路径问题，得到了既能按时完成任务又能使损失尽量小的方案，在实际应用中具有一定的参考价值。

参考文献：

[1]陈国梁, 王煦法, 庄镇泉,等. 遗传算法及其应用[M]. 北京: 人民邮电出版社, 1996.

[2]王小平, 曹立明. 遗传算法——理论、应用与软件实现[M].西安: 西安交通大学出版社, 2002.

[3]姜大力, 王丰, 张剑芳.军事物流系统模型及应用[M]. 北京: 中国物资出版社, 2006.