赵玉苹 张惠珍

（上海理工大学　　管理学院，上海，200093）

带柔性时间窗车辆路径问题的混沌蚁群算法*

赵玉苹 张惠珍

（上海理工大学管理学院，上海，200093）

带柔性时间窗的开放式车辆路径问题（Opening Vehicle Routing Problemwith Flexible Time Windows，OVRPFTW）对物流配送中的延迟或者提早具有一定程度的容忍.本文首先建立了OVRPFTW的数学模型，然后分别将Sine映射，Chebyshev映射和Logistic映射引入基本蚁群算法，构建了三种混沌蚁群算法，并将其用于求解OVRPFTW.算例测试表明：Sine映射和Chebyshev映射能够明显地改进基本蚁群算法的优化性能，基于Sine映射和Chebyshev映射的混沌蚁群算法的求解性能优于基本蚁群算法和基于Logistic映射的混沌蚁群算法.

车辆路径问题 柔性时间窗 混沌优化 蚁群算法

1　引言

开放式车辆路径问题（Opening Vehicle Routing Problem）和带时间窗的车辆路径问题（Vehicle Routing Problem with Time Windows，VRPTW）是组合优化问题中应用相当广泛的模型［1］，它们是车辆路径问题（Vehicle Routing Problem，VRP）的扩展.在物料运输、邮政快递以及校车路径规划中都可以看到VRPTW的应用，它要求为顾客提供服务的时间必须在此顾客的时间窗内，允许车辆在顾客服务时间窗开始之前到达，并且在等待期间不产生成本，但是不允许车辆在顾客服务时间窗结束之后到达.带软时间窗的车辆路径问题（Vehicle Routing Problem with Soft Time Windows，VRPSTW）假定可以违背顾客服务时间窗，但必须要为车辆的早到或者迟到接受适当的惩罚［2］.对于开放式车辆路径问题（Opening Vehicle Routing Problem，OVRP）来说，不要求车辆完成配送任务后返回原出发点，若要求返回原出发点，则沿原路线返回［3］.目前，用于求解开放式且有时间要求的物流配送问题的启发式算法主要包括：模块启发式算法［4］，混合粒子禁忌搜索算法［5］，变邻域搜索算法［6］，蚁群算法［7］，遗传算法［8-10］等等，这些算法主要用于解决带硬时间窗或软时间窗的开放式车辆路径问题.

带柔性时间窗的开放式车辆路径问题（Opening Vehicle Routing Problem with Flexible Time Windows，OVRPFTW）表示客户对配送时间具有一定程度的容忍，容忍度是根据配送物品的特点以及顾客的时间弹性来确定，允许配送时间窗的违反［11］.国内外关于带柔性时间窗的车辆路径问题的研究并不多见，而对于多配送中心、开放式的带柔性时间窗的车辆路径问题更是鲜有研究.本文首先建立带柔性时间窗的多配送中心、开放式的车辆路径问题的数学模型，然后分别将基于Sine映射，Chebyshev映射和Logistic映射的混沌策略引入基本蚁群算法，构建了三种不同的混沌蚁群算法，并将其用于求解OVRPFTW，最后通过测试算例分析了三种混沌蚁群算法和基本蚁群的求解性能.

2　带柔性时间窗的多配送中心开放式车辆路径问题

2.1问题及描述符号定义

带柔性时间窗的多配送中心开放式车辆路径问题可以描述为：车辆k从配送中心D出发，一次为多个顾客配送货物，配送完成之后返回就近的配送中心.其中，每个顾客i只能被一辆车服务且只能被服务一次.假设顾客i的服务时间窗为［li，ui］，考虑到该时间窗对早到或晚到具有一定的容忍度后的时间窗为［l′i，u′i］，车辆k超出这一限定区间到达要受到一定的惩罚，即若车辆k早到，则必须等到最早开始服务时间l′i才能服务；若车辆k晚到，则必须在最晚开始服务时间u′i之前到达.该问题的目标是求解从所有配送中心出发的车辆对所有顾客配送服务的最小运输总成本，这里的运输成本包括固定成本和可变成本，固定成本为车辆启动费用，可变成本只考虑车辆的行驶距离.

为便于问题描述，现将变量及符号定义如下：

G=（V，E）：运输网络；V：节点集，包括客户集C=1，2，…，A｛

｝和配送中心集D= 1，2，…，B｛

｝，任意一个配送中心车辆的集合；o：油耗费用系数；r：调用一辆车的固定启动费用系数；W：每辆车的最大装载量；［li，ui］：客户点i的时间窗；pli：违背客户i时间窗早到的最大容忍度；pui：违背客户i时间窗晚到的最大容忍度；：考虑客户i 最大容忍度的时间窗，其中；tik：车辆k到达客户点i的时间；tij：每辆车从节点i到节点j的行驶时间；t0：每辆车在客户点的服务时间；hij：节点i到j之间的距离；dl：车辆在原时间窗之外，最大容忍时间窗之内早到的惩罚系数；du：车辆在原时间窗之外，最大容忍时间窗之内晚到的惩罚系数；P：惩罚函数，

决策变量：

2.2数学模型

上述模型中，式（1）为目标函数，表示车辆运行总成本最小；约束（2）表示每个客户必须被服务且只能被服务一次；约束（3）和（4）确保客户仅被访问一次，且从客户点离开的车辆仅有一辆；约束（5）保证每辆车不会从一个配送中心不经过客户直接到达另一个配送中心；约束（6）为车容量约束；约束（7）表示到达客户点i的车辆数与离开客户点i的车辆数相同且均为1；约束（8）为时间窗约束；式（9）为计算车辆k到达节点j的时间公式；约束（10）保证车辆行驶的先后顺序；约束（11）为消去支路约束，排除不完整线路.

3　混沌蚁群算法

蚁群算法是模拟蚁群觅食行为的一种基于种群的模拟进化算法，其在求解组合优化难题和连续优化问题中取得了较好的结果［12］.近年来，越来越多的学者利用蚁群算法求解物流配送中的车辆调度和路径优化问题［13］.相比于其他智能优化算法，蚁群算法具有较强的鲁棒性，易与其他方法结合的优点.首先，蚁群算法对初始路线的要求不高，即蚁群算法的求解结果不依赖于初始路线的选择，而且在搜索的过程中不需要进行人工调整.其次蚁群算法的参数数目少，设置简单.但蚁群算法也具有一定的不足之处，如：容易陷入局部最优，搜索速度比较慢等.

本文针对基本蚁群算法收敛速度慢和易陷入局部最优等缺点，分别将Sine映射，Chebyshev映射和Logistic映射三种混沌映射方法与蚁群算法结合，设计不同的混沌蚁群算法，以便有效抑制算法的早熟现象，跳出局部最优.

3.1混沌扰动策略

混沌是一种普遍的非线性现象，其表面上是混乱的，但实际上却含有内在规律性，规律性、随机性和遍历性是混沌的特点.混沌优化的基本思想是：将优化变量通过混沌映射规则映射到混沌变量空间的取值区间内，利用混沌变量的遍历性和规律性寻优搜索，最后将获得的优化解线性转化到优化空间.

当蚁群算法循环迭代中最优解的值（最小费用）连续重复出现多次时，即可认定算法进入早熟、停滞的状态.蚁群算法进入早熟、停滞状态后，可利用混沌扰动策略帮助其跳出局部最优.不同的混沌映射产生的混沌效果不同，本文分别利用Logistic混沌映射、Chebyshev混沌映射和Sine混沌映射（三种混沌的参数、映射表达式和区间表达式如表1所示）调整蚂蚁算法中蚂蚁的信息素含量，构建了三种不同的混沌蚁群算法.

表1　三种混沌扰动策略

表1中，g表示选出的需要混沌的路径个数；n表示混沌迭代次数；xn为第n次混沌迭代的数值；τg为第g个要进行混沌的蚂蚁信息素含量；τmax表示所选蚂蚁路径上信息素含量的最大值；τmin表示所选蚂蚁路径上信息素含量的最小值.

混沌优化过程为：假设进入混沌迭代时各路径的信息素含量为τi（0＜i≤m，m为蚂蚁数），首先利用映射空间计算表达式将信息素含量转换到各混沌策略的映射空间上；然后用映射表达式对得到的x1进行混沌扰动，得到混沌序列x=x1，x2，…，xn（

），最后将混沌序列通过逆映射表达式映射到解空间.若混沌迭代过程中更新了全局最优解或达到最大混沌迭代次数仍未更新最优解，则停止混沌扰动.

3.2混沌蚁群算法的设计

3.2.1转移规则

式（12）中，Nki代表蚂蚁k可以访问的客户点集；τij为边（i，j）的轨迹强度；ηij为边（i，j）的能见度，一般表示为路径长度的倒数；μij为边（i，j）的节省量，即uij=hib+hbj-hij（b ∈D），节省量的值越大表示蚂蚁越应当在访问完节点i之后访问节点j.α，β和γ分别表示τij，ηij和μij的相对重要性.

蚂蚁构造路径时，遵循以下的伪随机规则：q为0到1之间的随机数，当q＞q0（q0=0.05）时，根据式（12）计算出的转移概率并按照轮盘赌的方法确定下一个访问客户；否则，取转移概率最大的点为下一个要访问的客户点n，即

3.2.2信息素更新

当所有蚂蚁完成一次循环迭代后，各边上的信息素强度由式（14）-（16）进行更新：

3.3算法

求解带柔性时间窗、多配送中心、开放式车辆路径问题的混沌蚁群算法的步骤如下：

步骤1 初始化各参数，输入所有客户及配送中心的数据，最大迭代次数Nc_max=200；

步骤2 将m只蚂蚁随机均匀地放到B个配送中心，初始化蚂蚁k已走的客户点集tabuk，以及候选点集Nki（包括配送中心）；设置完成任务的蚂蚁数量l=0；

步骤3 对蚂蚁k，当车辆剩余载重量能满足至少一个客户时，按转移规则确定下一个访问节点j，并更新tabuk，Nki以及车辆的剩余载重量；

步骤4 如果Nki≠Ø，并且至少有一个候选点的需求量小于车辆的剩余载重，则转步骤3；否则转步骤5；

步骤5 若Nki≠Ø，并且车辆剩余载重不能满足所有候选点的需要量，则增加一辆车，令其载重量为W，并转步骤3；否则，转步骤6；

步骤6 若Nki=Ø，且当前蚂蚁的最后一个访问点不是配送中心，则令其返回到离其最近的配送中心，l++.若l≤m，转步骤3；否则，转步骤7；

步骤7 所有蚂蚁遍历一次后，按照公式（14）-（16）对所有路径的信息素进行更新；Nc ++；

步骤8 由各蚂蚁的tabuk得到路径集L=L1，L2，…，Lm｛

｝，根据约束条件计算每个可行解的罚函数以及目标函数值，记录本次迭代的最优解，同时更新全局最优解（全局最优解为迭代至今求得的最优解）；

步骤9 若同一全局最优解连续出现Nbest_max 次，则转步骤10，否则转步骤11；

步骤10 利用混沌映射改变路径上信息素含量，求出可行解的目标函数值并与当前全局最优解比较，若混沌过程中得到了优于当前最优的解，则更新全局最优解，并跳出混沌迭代；若在混沌迭代过程中未找到优于当前最优的解，直接跳出混沌过程.

步骤11 若Nc=Nc_max ，则算法终止，并输出全局最优解L*；否则，Nc++，转步骤2.

4　算例及分析

本文利用文献［10］中的算例来测试算法的求解性能，其中客户点、配送中心的位置坐标以及需求量等数据如表2所示.设1-24为客户编号，25-27为配送中心编号，它们分布在不同的地方.所有车辆的装载容量为4t，车辆在顾客点的服务时间t0为定值20.

算法运行环境为Windows7平台，32位操作系统，Intel处理系统，3.40GHz，4 GB内存；仿真软件为MATLAB2010a.

表2　算例数据

为了确保算法之间的可比性，使它们在相同的起点上进行比较，计算过程中对三种混沌蚁群算法和基本蚁群算法共有的参数设定了相同的值：蚂蚁数m=60，轨迹的相对重要性α=1，能见度的相对重要性β=1，节省量的相对重要性γ=2，初始信息素总量Q=10，时间窗容忍度ρli=ρui=0.2，算法迭代次数Nc_max=200.对三种混沌迭代中的共有参数设定如下：达到混沌标准的最优解重复次数Nbest_max=30，最大混沌迭代次数Tc=10.三种混沌蚁群算法和基本蚁群算法各运行20次，求解结果如表3所示.

表3　基本蚁群算法与混沌蚁群算法计算结果

由表3不难看出，虽然基本蚁群算法的计算效率以及计算结果的稳健性要高于几种混沌蚁群算法，但基于Sine映射的混沌蚁群算法和基于Chebyshev映射的混沌蚁群算法的优化结果明显优于基于Logistic映射的混沌蚁群算法和基本蚁群算法，且Sine映射的混沌蚁群算法的计算结果更优，Chebyshev映射的混沌蚁群算法稳定性更好.与基本蚁群算法相比，带Logistic映射的混沌蚁群算法并没有改善问题的最优解，且计算时间更长.

图1　满意解图示

基于Chebyshev映射和Sine映射的混沌蚁群算法求得相同的满意解（如图1所示），配送总成本为162472.50，车辆数为7.每辆车的配送路线如下，车辆1：25-16-11-8-22-7-25；车辆2：25-14-3-18-23-25；车辆3：25-9-5 -27；车辆4：27-20-6-19-27；车辆5：27-4 -15-24-17-27；车辆6：27-2-10-21-26；车辆7：26-13-12-1-26.

5　结论

本文首先建立了带柔性时间窗的开放式车辆路径问题（OVRPFTW）的数学模型，然后将Sine映射，Chebyshev映射以及Logistic混沌映射分别与基本蚁群算法融合，提出了三种求解OVRPFTW的混沌蚁群算法.测试算例结果表明：基于Sine映射的混沌扰动对蚁群算法在解决带柔性时间窗的开放式车辆路径问题中产生了很明显的优化作用，混沌优化后的最优解平均值171046远远优于基本蚁群算法得到的结果174019；利用Chebyshev映射的混沌扰动策略也能够改进最优解的质量，且稳定性要高于基于Sine映射的混沌蚁群算法；利用Logistic映射的混沌扰动策略对解决此类问题的优化效果却并不明显.

［1］A D López-Sánchez，A.G.Hernández-Díaz，Vigo D，et al.A multi-start algorithm for a balanced real -world Open Vehicle Routing Problem［J］.European Journal of Operational Research，2014，238（1）：104-113.

［2］Beheshti A K，Hejazi S R.A novel hybrid column generation-metaheuristic approach for the vehicle routing problem with general soft time window［J］.Information Sciences，2015，316：598-615.

［3］杨进，马良.蜂群优化算法在带软时间窗的车辆路径问题中的应用［J］.预测，2010，29（6）：67-70.

［4］Rahimi-Vahed A，Crainic T G，Gendreau M，et al.Fleet-sizing for multi-depot and periodic vehicle routing problems using a modular heuristic algorithm［J］.Computers&Operations Research，2015，（53）：9-23.

［5］Escobar J W，Linfati R，Toth P，et al.A hybrid granular tabu search algorithm for the multi-depot vehicle routing problem［J］.Journal of Heuristics，2014，20（5）：483-509.

［6］王征，张俊，王旭坪.多车场带时间窗车辆路径问题的变邻域搜索算法［J］.中国管理科学，2011，（2）：99 -109.

［7］Reed M，Yiannakou A，Evering R.An ant colony algorithm for the multi-compartment vehicle routing problem［J］.Applied Soft Computing，2014，15（2）：169-176.

［8］孙宾松，符卓.求解带软时间窗的车辆路径问题的改进遗传算法［J］.系统工程，2003，21（6）：12-15.

［9］潘震东，唐加福，韩毅.带货物权重的车辆路径问题及遗传算法［J］.管理科学学报，2007，10（3）：23-29.

［10］钟石泉，杜纲，贺国光.有时间窗的开放式车辆路径问题及其遗传算法［J］.计算机工程与应用，2007，42（34）：201-204.

［11］Duygu Taş，Ola Jabali，Tom Van Woensel.A Vehicle Routing Problem with Flexible Time Windows［J］. Computers and Operations Research，2014，52：39-54.

［12］Dorigo M，Bonabeau E，Theraulaz G.Ant algorithms and stigmergy［J］.Future Generation Computer Systems，2000，16（8）：851-871.

［13］李娅，王东.基于混沌扰动和邻域交换的蚁群算法求解车辆路径问题［J］.计算机应用，2012，02：444 -447.

The Chaos Ant Colony Optimization Algorithm for Solving Vehicle Routing Problem with Flexible Time Windows

Zhao Yuping Zhang Huizhen
（School of Business，University of Shanghai for Science and Technology，Shanghai 200093，China）

Opening Vehicle Routing Problemwith Flexible Time Windows（OVRPFTW）allows vehicles to serve customers ahead of schedule or behind schedule by a given tolerance.In this paper，the mathematical model of the OVRPFTW is formulated firstly，then three chaos Ant Colony Optimization（ACO）algorithms for solving the OVRPFTW are proposed by combining ACO with Sine mapping，Chebyshev mapping and Logistic mapping，respectively.Numerical results show that Sine mapping and Chebyshev mapping can significantly improve the ACO algorithm，and comparing with the basic ACO algorithm and the chaos ACO algorithm based on Logistic mapping，the chaos ACO algorithms based on Sine mapping and Chebyshev mapping have better optimization performance.

Vehicle routing problem Flexible time window Chaos optimization Ant Colony Optimization

国家自然科学基金项目（71401106）；高等学校博士学科点专项科研基金联合资助课题（20123120120005）；上海市教育委员会科研创新项目（14YZ090）资助

2016年03月19日