单纯形蚁群算法对带时间窗车辆路径优化问题的研究

李永亮，王玉富，向长城

(1．湖北民族学院 理学院，湖北 恩施445000:2．郑州测绘学校，河南 郑州450015)

车辆路径问题研究的是车辆的运输优化问题，通常会利用启发式算法求解此类问题，并且在一定的搜索时间范围内获得问题的近似解，再根据解的合理性，制定出合适的配送方案．在建模的过程中，不仅要使运输的成本最低．而且能够尽可能的满足客户的需求(在这里主要是满足客户的时间需求)．带时间窗车辆路径问题是在原来的车辆路径问题基础之上融入了时间窗的限制，即多了约束条件．目前大多是在理论上对VRP问题进行的研究，而且研究的主要是站点较少的VRP 问题，但在现实世界中，站点数目往往比较多，现有的方法难以很好地解决大规模车辆路径问题，不能得到满意解，处理这些问题时往往就不再适用了．如何有效解决大规模VRP 问题，寻求满意的配送方案，成为如今物流企业着重需要解决的难题，对它进行研究，具有极其重要的理论意义和现实意义．

1 带时间窗的车辆路径优化问题的分析与建模

研究带时间窗的优化问题实质就是在含有运输容量约束的车辆优化路径问题的基础上，增加了时间窗的约束，则带时间窗的车辆路径问题描述为:车辆从仓库出发去满足每个站点的需求，完成站点的需求后依旧返回仓库，规定每个站点只能被其中一辆车服务而且仅被服务一次，而且对站点的服务时间必须控制在站点事先规定的时间窗约束条件下进行，从而问题就是怎样去选取合适的行车路线，使得在满足时间窗和需求量的要求下，完成全部需求花费的总成本最小．

带时间窗车辆路径问题数学建模符号表示为:令G=(V，E)为一个无向图，V表示顶点集，E为边集．顶点v0表示配送中心，顶点v1，v2，v3，…，vi表示客户位置，dij表示i，j两点之间的距离长度，tij表示车辆从vi行驶到vj的所用的时间，运输费运为cij，车辆容量为Q，所需车辆为k，客户i的需求量为qi，客户i的时间窗为［ETi，LTi］，车辆到达客户i的时间为si，在时间窗的约束条件下，必须要满足ETi≤si≤LTi．为此可以构造数学模型，定义变量如下:

则可得到带时间窗的车辆路径问题的数学模型如下:

模型中，cij表示为从点i到j的距离运输成本量，它是根据问题情况来确定，可以表示为距离、费用、时间等．式(1)表示目标函数使得所用费用最少;式(3)表示表示车辆k服务的所有客户的需求量之和不大于车辆的载重量;式(2)表示客户i只能被一辆车来服务;式(4)表示时间窗约束．

2 改进单纯形蚁群算法

2．1 单纯形算法的简介

单纯形法在运算过程中，不仅仅计算量小、而且无需求导、优化速度快等优点的传统的局部搜索算法，并且在运行时，不会有复杂的矩阵运算，因此它在运算的过程中内存的消耗较小;但利用单纯行算法进行计算时，由于初始值的不同，它会得到不同的搜索结果，急欲陷入局部收敛，很难保证得到全局最优解．单纯形法的基本原理是在n维空间中用n+1 个顶点构成一个单纯形，再根据单纯性的相应规则，不断改变单纯形的迭代的顶点，使它向适应度函数最小的方向移动，直至找到函数最优的近似解的值．求解过程为:首先需要找到适应度函数值的最差点xh、次差点xd、最好点x1，其适应度函数值分别为fh，fd，f1，然后需要求出除最差点外的其他的n个顶点的重心xg，则它的适应度值为fg［1］．如果它的反射点的适应度函数的值为frrx1的函数值f1，就这样进行扩展，如果它的反射点的函数值大于xd的函数值，则需要在该方向上执行一次向内收缩，从而得到它的收缩点xn，使单纯形更接近最优点的值．单纯形则在每一次迭代中进行反射、扩展、收缩的条件如下所示:

①如果f1＜fr＜fd，则xc=xg+∂(xr+xh);②如果fr＜f1，则xr=xg+β(xg+xh);

③如果fd＜fr＜fh，则xn=xg+o(xg－xr);④如果fr＞fh，则xn=xg－φ(xg－xh)．其中，∂为反射因子;β 为扩张因子;o 为正向收缩系统;φ 为反向收缩因子．

2．2 蚁群算法简介

蚁群算法是根据自然界蚂蚁在寻找地址的过程中，每一条蚂蚁能够在它所经过的路径上留下叫信息素的物质来进行信息的传递，当其他的蚂蚁在经过此路径的时候，能够感知这种信息素和信息素的量，并且根据这条路径上的信息素的量来判断选择这条路径的概率，随着蚂蚁经过这条路径的数量越来越多，则这条路径的信息素的量就越来越多，蚂蚁选择这条路径的概率就会逐渐大．式(5)～(7)为蚁群算法的基本模型为:

式(5)p为蚂蚁的转移概率．m为蚂蚁的总的数量;n表示的是迭代的次数;i表示蚂蚁当时所在位置;j为蚂蚁接将要到达的位置;Λ 为蚂蚁可以到达的所有的位置的集合;η 为启发性的信息;式(6)τ 为由i到j的路径中蚂蚁释放出的信息素的强度;式(7)Δτ 为蚂蚁k由i到j的路径上，蚂蚁所留下的信息素的数量;L为路径的长度;α，β 为启发性的信息的权值;ρ 为路径上信息素的蒸发系数;Q为信息素的质量的系数［2］．

2．3 改进的单纯形的蚁群算法

对于N维向量的空间优化问题，需要N+1 个单纯形的顶点来产生一个N维空间的单纯形．算法的基本流程为:

1)首先需要求出目标函数值最小顶点、次小顶点和最大顶点;并且还要计算出最小顶点之外的N个顶点的形心点的值;

2)计算出最大顶点关于形心点的反射点的值;在计算出反射点的目标函数值，如果大于次小顶点，则需要在该方向上向下执行一次收缩运算;如果小于最大顶点值，则需要执行一次扩张运算;

3)如果单纯形整体收敛与最低点，则执行下一次迭代，目的是为了利用单纯形算法的局部搜索和蚁群算法的全局搜索能力，在蚂蚁初始化时，采用单纯形算法来进行初始生成，从而避免算法在初始化时的均匀生成的缺点．

为了利用单纯形算法的局部搜索和蚁群算法的全局搜索能力，在蚂蚁初始化时，采用单纯形算法来进行初始生成，从而避免算法在初始化时的均匀生成的缺点．在算法进入迭代搜索的时，首先要利用蚁群算法对目标函数进行优化，对相应的迭代次数进行设置，当蚁群算法运行并且搜索到后期时，需要每隔10 代需要进行一次单纯形的搜索，从而可以避免搜索所需要的时间过长，当单纯行搜索完成后再继续进行蚁群搜索［1－5］，图1 为该算法的流程图．

图1 单纯形的蚁群算法流程图Fig．1 A simplex search－ant colony optimization algorithm flow chart

3 带时间窗车辆路径问题求解

3．1 容量约束的车辆路径问题

首先考虑容量约束的车辆路径问题，随机生成一组坐标数据和容量限制，如图2 所示．

图2 站点坐标分布图Fig．2 Coordinates of site map

利用了改进后的单纯性蚁群算法进行了求解，用Matlab 软件编程，得出如下结果如图3 所示，图4 为最优收敛的路径图．

从结果得知总共需要5 辆车，才能满足各个站点的需求，5辆车的路线如下表1．

表1 优化路线结果排列Tab．1 Route optimization results

此时最佳路径长度为642．294，由图4 可知，该算法对多站点车辆路径问题也有较强的适应性．

3．2 带时间窗车辆路径问题求解

首先在带时间窗车辆路径问题数据库中，找得一组数据源，用Matlab 画出各个站点分布图(图5)．由图5可知，共有26 个站点，其中包括一个车场0，同理，用Matlab 软件基于最大最小蚂蚁系统求解，取定参数α=1，β=2，ρ=0．02，蚂蚁数目n为26，得出车辆路线行驶图(图6)．

图3 站点路线优化结果Fig．3 Optimization results of site map

图4 平均和全局最短路径长度Fig．4 The average and best path

图5 站点坐标分布图Fig．5 Coordinates of site map

图6 站点路线优化结果Fig．6 Optimization results of site map

从结果得知总共需要7 辆车，才能满足各个站点的需求，七辆车的路线如表2．

表2 优化路线结果排列Tab．2 Route optimization results

由程序结果可知，最短路径为5 937．2，由此可知，单纯形蚂蚁系统对带时间窗车辆路径问题也有较好的适用性．将此结果和带容量约束的车辆路径问题相比，带时间窗的车辆路径问题所用车辆明显多于带容量约束的车辆路径问题，因为加入时间窗的约束后，每辆车的行驶路程就会改变，这与实际中遇到的情况是吻合的．

［1］ 刘建，王益群，姜万录，等． 引入单纯形算子的粒子群优化算法在板形模式识别中的应用［J］． 中国机械工程，2007，18(23):2977－2880．

［2］ 田明杨，周永杰，王媛 基于蚁群算法转移概率的研究［J］． 硅谷，2010(3):95－95．

［3］ 李舟，向长城． 非线性单纯形蚁群算法在垃圾运输问题中的应用［J］湖北民族学院学报:自然科学版，2011，29(3):271－273．

［4］ 汪祖柱，程家兴，方宏兵，等．车辆路径问题的混合优化算法［J］．运筹与管理，2004，13(6):48－52．

［5］ 王进，周绍梅．一种基于MMAS 的具有奖罚机制的分组蚁群算法［J］．计算机应用与软件，2009，26(3):237－238．

［6］ 段海滨，王道波．一种快速全局优化的改进蚁群算法及仿真［J］．信息与控制，2004，33(2):241－244．

［7］ 张曦煌，李岩，李彦中．求解VRP 问题的改进蚁群算法［J］．计算机工程与设计，2007，28(23):5694－5696．

［8］ 胡俊鹏．基于双向选择的蚁群相遇算法的优化［J］．湖北民族学院学报:自然科学版，2013，31(1):60－64．

［9］ 杜衡吉，李勇．蚁群算法中参数设置对其性能影响的研究［J］．现代计算机，2012(9):3－7．

［10］ 张建秋．基于蚁群算法的TSP 的算法与研究［J］．科技信息，2010(25):71－71．

［11］ 冷画屏，王明慧，余永权．最大－最小蚂蚁系统及K－TSP 问题的求解［J］．计算机应用与软件，2008，25(2):242－244．

［12］ Stutzle T，Hoos H H．Improving the ant system:a detailed report on the MAX－MIN ant system［J］．Technical report AIDA－96－12，1996(32):309－314．

［13］ Stutzle T，Hoos H H．The MAX－MIN ant system and local search for the traveling salesman problem［C］//Proceedings of the 1997 IEEE International Conference on Evolutionary computation(ICEC'97)，1997:309－314．

［14］ 匡正，王智杰．解决二次分配问题的改进蚁群算法［J］．计算机工程与应用，2006，42(16):89－91．