基于混合遗传算法的带容量约束的车辆路径问题研究

基于混合遗传算法的带容量约束的车辆路径问题研究

随着国内b2电子商务的快速发展，负责货物运输的第三方物流公司面临着越来越大的挑战。如何合理组织公司的团队，并在规定的期限内将货物发送给不同的客户。并且,城市道路交通外部环境在不断恶化。例如,一些大城市的主干道在每天的固定时段“必定”交通堵塞,车辆的道路通过时间是非繁忙时段的几倍甚至十几倍。因此,在安排车队的行驶路线时,目标不仅是车队的行驶总距离/总成本最小,还需要避开交通高峰期和拥塞道路,即车辆的行驶/运营时间最短。在物流管理研究领域,这类问题属于带容量限制的车辆路径问题(CapacitatedVehicleRoutingProblem,C-VRP),即如何设计运输车队中每辆车(每辆车的载货容量有限)的行驶线路,在满足顾客需求的前提下实现运营成本最低。C-VRP问题实际上包含2个著名的组合优化问题:装箱问题和旅行商问题,并已经被证明是一类NP-Hard问题。当前,C-VRP问题的研究工作侧重于:(1)考虑实际应用背景,对标准C-VRP问题进行数学模型扩展;(2)设计更加高效的求解算法。文献中考虑了一个2级C-VRP问题,即货物先从分销中心运送到多个仓库,再由仓库对最终顾客进行配送;文献中在标准C-VRP问题基础上,考虑顾客的货物需求具有周期性特点,即C-VRP问题与周期性车辆路径问题的交叉问题;文献中在标准C-VRP问题基础上,考虑顾客的货物需求是随机函数,并且限制每辆车/每条路线的行驶时间;文献中也分析了当顾客的货物需求为随机函数,且具有时间窗约束情景下的C-VRP问题;文献中放宽了C-VRP问题中“1个顾客只能由1辆车来服务”的约束条件;文献中不要求车辆在服务完顾客后返回出发点,即C-VRP问题与开方式VRP问题的交叉问题;文献中将车辆的容量限制从1维的约束扩展为2维的空间约束;文献中将车辆的容量扩展到3维。而C-VRP问题的求解算法也从传统的精确算法,发展为各种启发式算法,以及智能算法等。但是,很少有人研究道路拥塞对C-VRP问题求解的影响,其源于行驶路线的时间成本为非常复杂的非线性函数,传统数学方式的表达和计算非常困难。因此,本文采用计算机建模的方法建立评价行驶方案各项指标的计算机模型,应用计算机算法计算得到不同行驶方案的各项指标值。并且,对于行驶方案的多目标综合评价并非采用简单的加权和形式进行汇总和排序,而是给出问题的最优Pareto集合。同时,为了提高求解效率,本文还提出一个遗传算法与模拟退火算法相结合的混合遗传算法。本文的特色之处在于:(1)研究问题为复杂的C-VRP问题。交通网络中每条道路有不同的交通拥挤时段,且具有方向性,因此,车辆在不同时刻或者从不同方向通过相同道路,其通过时间不相同;问题的决策变量不仅包括车队的规模(参与运输的车的数量)和每辆车的行驶路线,还包括每辆车的出发时间。(2)决策目标为多目标决策。决策目标不仅是车队行驶的总距离最短,还包括车队行驶总时间最短、每辆车的负荷(行驶距离和行驶时间)最均衡等多目标。(3)问题求解算法更加高效。针对具体问题,设计一种遗传算法和模拟退火算法相结合的混合遗传算法,计算效率高于标准算法。1车辆通过时间是时间的非线性函数本研究的C-VRP问题可以概括为:设计一个车队的行驶路线方案,包括每辆车的出发时间和访问顾客点的顺序(从起点出发,依次访问各个顾客点,并最后返回起点);要求每辆车装载的顾客货物需求总量不能超过车辆的最大容量,且每辆车必需从配送中心出发,并最终返回配送中心;评价一个车队行驶路线方案的指标包括车队的总行驶距离和总行驶时间,以及每辆车行驶距离和行驶时间的均衡度指标。具体描述和符号定义如下:(1)交通网络包括n+1个节点,其中,1个配送中心节点作为特定货物的供应方,n个顾客节点作为货物的需求方。在平面直角坐标系中,n个顾客节点的坐标分别为(xi,yi),i=1,2,…,n;配送中心的坐标为(x0,y0)。假定配送中心到顾客,以及顾客之间的距离(km)计算公式为(2)n个顾客的货物需求量确定,分别为di,(i=1,2,…,n)(箱)。假定配送中心能够满足所有顾客的需求,不会出现因为缺货导致的顾客需求不能够被满足的情况。(3)配送中心调度具有相同容量C(箱)的车辆负责货物的运输,每辆车辆装载的货物总量不能超过容量C。车辆的数量不受约束,即不会因为缺少车辆而导致顾客的需求得不到满足。(4)配送中心的车辆在配送中心装货后按照指定的线路访问顾客,并最终返回配送中心。每个顾客只能被1辆车访问1次,即每个顾客的需求被1辆车一次性满足。并且,假定单个顾客的货物需求量小于1辆车的车容量C,即di<C,i=1,2,…,n。(5)每辆车都可以从z个时间点中任意选择一个作为车辆的出发时间,即车辆j从配送中心出发的时间可以为tjs(k),k=1,2,…,z。(6)车辆在不同时间,从不同方向经过相同的道路(顾客i和j之间的道路),其行驶速度受到当时道路车流量大小的影响而不能保持为常数,即dvi,j(t)/dt≠0且vi,j(t)≠vj,i(t),(i,j=0,1,…,n)。因而,车辆的通过时间是时间的非线性函数。(7)车辆在第i个顾客处花费的时间,即卸货时间tiu,是货物需求量di的函数。(8)每辆车的运行时间包括从配送中心出发,访问顾客,并返回配送中心的道路行驶时间,以及在顾客处花费的卸货时间之和。本问题的决策变量包括每辆车的行驶路线rj,j=1,2,…,m,以及每辆车的最佳出发时间tjs*,j=1,2,…,m。对于本问题的一个可行解A-m辆车,每辆车的出发时间为tjs(k),j=1,2,…,m,行驶路线分别为rj,j=1,2,…,m,每辆车的行驶距离为l(rj),j=1,2,…,m,运行时间为t(rj,tjs(k)),j=1,2,…,m(运行时间包括道路运输时间和顾客处的卸货时间两部分)。本问题的决策目标定义为:(1)所有车辆的行驶总距离最短,即(2)所有车辆的运行总时间最少,即另外,本文引入统计学中的变异指标来反映每辆车行驶距离和行驶时间的离散程度,并选用标准差形式来计算具体的变异系数。假定车队中每辆车行驶距离的平均值la(rj),j=1,2,…,m,标准方差每辆车运行时间的平均值ta(rj,tjs),j=1,2,…,m,标准方差定义车辆的行驶距离均衡度指标θl和运行时间均衡度指标θt分别为:因此,所研究问题的目标函数还包括每辆车行驶距离的均衡度最高,即max(θlA),以及每辆车运行时间的均衡度最高,即max(θtA)。由于研究问题的多目标特性,本文设计算法用于寻找问题的Pareto优化解集,即Pareto非支配解集。结合本文的4个评价指标/目标,定义可行方案A、B之间支配关系:定义1如果方案A的4个指标与方案B的4个指标值满足关系LA≤LB,TA≤TB,θlA≥θlB,θtA≥θtB,并且其中至少包含1个严格不等式,则称方案A绝对优于方案B,同时方案B绝对劣于方案A。定义2如果方案A不能绝对优于方案B,方案B也不能绝对优于方案A,则称方案A非支配方案B,方案B非支配方案A。基于以上2个定义,对于所研究问题的Pareto优化集合定义如下:定义3集合中的可行方案两两之间都为非支配关系,而不属于Pareto优化集合的可行方案都是绝对劣于集合中的一个或多个可行方案。综上所述,本文所研究的问题可以概括为以带容量限制的车辆路径问题为基准问题,研究当车辆在不同时间通过相同道路所需时间不同的情景下,综合考虑车辆行驶的总距离、总时间,以及每辆车行驶的距离和时间的均衡性,问题的最优Pareto集合。2混合遗传算法求解本文提出一种基于模拟退火和遗传算法的混合遗传算法,即在标准遗传算法基础上,对于每次迭代中的可行方案采用模拟退火算法进行局部搜索,从而减少迭代次数,提高求解效率。算法中染色体的编码采用n个顾客编号的排列形式,即c1,c2,…,cn。解码则是从c1开始依次向车辆的行驶路线中加入顾客(节点),直到加入顾客ci+1后车辆的运输货物总量超出了车辆的容量限制。此时,重新增加一条行驶路线,并以顾客ci+1为第1个访问的顾客。例如,假定编号由1~7的7位顾客,他们各自的货物需求量为5,4,5,3,7,8,2(箱),则给定1条染色体编码“3,1,4,2,7,6,5”,其解码为2条车辆行驶路线:第1辆车(容量限制为20箱)的行驶路线为从配送中心出发,首先到达编号为3的顾客处,然后依次到达顾客1,4,2和7,最终返回配送中心;第2辆车的行驶路线为从配送中心出发,依次访问顾客6和5,最终返回配送中心。车辆tci时刻从顾客ci处出发,到达顾客ci+1的时间tci+1由下式计算得到。对于问题的一个可行解A,遗传算法的适应度函数定义为:式中:ωi为可行解A的4个目标的权重取值;L0,T0、θl0和θt0分别为初始时给定的任意一条染色体所表示的行驶路线的4个评价指标值。在实际应用中,权重可以由决策人员或决策小组共同确定。混合遗传算法的求解过程。(1)设定遗传算法的算法参数(种群数目Ng、交叉概率Pc、变异概率Pm、迭代次数Mg、适应度函数F(·)中指标权重ωi等),模拟退火算法的算法参数(温度参数T0、温度下降参数λ、循环参数Ns和Ms),以及Pareto优化集合的集合参数(集合元素的数量Np);随机生成1条染色体,对染色体进行解码,得到所需车辆的数量m,以及每辆车的行驶路线rj,(j=1,2,…,m)。任意给定一个统一的车辆出发时间tjs(k),j=1,2,…,m,计算得到其4项目标值,并将其总行驶距离值和总运行时间值作为L0和T0;(2)生成初始种群(Ng条染色体)。针对每条染色体,解码后采用穷举的方法计算得到每辆车的最佳车辆出发时间tjs*,以及相应的4项目标值。进而计算得到每条染色体的适应度函数取值;(3)根据种群中每条染色体的适应度函数值,应用锦标赛选择法选择得到遗传算法下一代的染色体;(4)以交叉概率Pc从下一代染色体中随机选择2条染色体执行顺序交叉操作;(5)以变异概率Pm从下一代染色体中随机选择1条染色体执行移位变异操作;(6)对种群中每条染色体进行解码,采用穷举法重新计算得到最佳车辆出发时间tjs*,以及相应的4项目标值;(7)对种群中的每条染色体,采用模拟退火算法局部调整车辆的行驶路线;(8)重新计算种群中每条染色体的适应度函数值。如果遗传算的迭代次数小于最大迭代次数Mg,则重复(3)~(8);否则,转(9);(9)从最终种群中选出Pareto优化集合的元素,并输出。由于算法中染色体的解码方式是顺序累加染色体中的顾客节点的货物需求量,直到计算得到的货物需求总量超过车辆的容量限制C时,再考虑增加一条车辆路线。这种车辆服务顾客的划分算法虽然简单易实现,但是对于染色体中顾客节点的排列顺序依赖程度较高,一般不能够快速搜索到问题的最优解。因此,本文在标准遗传算法的算法基础上,应用模拟退火算法对顾客的划分进行局部调整。基于模拟退火算法的局部调整思路为:任意选择一辆车的行驶路线,减少其服务的顾客数量。然后再对剩下的顾客重新按照标准方法进行划分。以上文介绍的7位顾客的例子为例,初始化分的结果是第1辆车顺序访问顾客3,1,4,2,7,第2辆车则顺序访问顾客6,5。假定模拟退火算法随机选择第1辆车,并随机减少1为顾客,那么结果是:第1辆车顺序访问顾客3,1,4,2,第2辆车顺序访问顾客7,6,5。相比之下,如果不采用局部搜索算法,染色体“3,1,4,2,7,6,5”难以快速通过遗传算法的交叉操作和变异操作变换为“7,6,5,3,1,4,2”。假定染色体A解码后由m辆车/行驶路线组成,计算得到最佳的车辆出发时间为tjs*,j=1,2,…,m,4项目标的取值分别为(LA,TA,θlA,θtA),适应度函数计算值为Qt=F(A),t=0。模拟退火算法局部调整计算步骤如下:(1)从m辆车中随机选择一辆车x,1≤x≤m,并从该车行驶路线rx=(c1x,…,cux)(共服务u位顾客)中随机选择顾客y,1≤y<u,作为调整点;(2)保持车辆x之前各辆车的行驶路线不变,即r′i=ri,1≤i<x;第x辆车服务顾客减少到y,即r′x=(c1x,…,cyx);对于染色体从cxy+1开始,到最后一位顾客,重新按照标准解码方式进行解码,得到调整后的车辆行驶路线;(3)重新计算调整后车辆路线的4项目标值,以及适应度函数计算值;(4)如果调整后车辆路线的适应度函数值Qt+1>Qt,则接受调整后的车辆路线;否则,按照概率接受调整后的车辆路线Qt+1=Qt;(5)调整模拟退火算法中的温度参数Tt+1=λ·Tt,并重复(1)~(4)Ns次;(6)重复(1)~(5)Ms次,并选择其中最佳适应度函数值,以及对应的车辆路线作为局部调整的最终值。3混合遗传算法测试在前期工作的基础上,以Java为编程语言,在J2SE1.5平台上实现了混合遗传算法的原型系统。并以网络上公开发布的C-VRP问题测试数据集和最优解为基准(/VRP/data/),测试了算法的有效性。首先,在文献的基础上,假设车辆在每条道路上的行驶速度(km/h)是以24h为周期的时间函数,并且为下面所示的4个速度函数之一(服从概率为25%的离散随机分布):式(5)描述在1天的24h内,车辆的行驶速度比较稳定,保持在40km/h;式(6)表示车辆的行驶速度在每天的14:00(交通高峰时段)时最慢,仅达到大约28km/h的速度,而非繁忙时段则达到40km/h。类似式(6);式(7)表示车辆的行驶速度在每天的12点和18点时最慢,而其他时段恢复到40km/h;式(8)表示车辆的行驶速度在每天的7:00、13:00和19:00时最慢。由于车辆行驶速度是时间的非线性函数,故在实际计算时采用文献中的近似算法计算得到(算法中积分步长S=0.20和s=0.05)。假定车辆在顾客处的停留时间/卸货时间与顾客的货物需求量成比例关系,即另外,假定每辆车可以选择在早上8:00、8:30、9:00、9:30或10:00出发,即定义混合遗传算法中主要参数:遗传算法中种群数目Ng=100,交叉概率Pc=0.7,变异概率Pm=0.2,迭代次数Mg,模拟退火算法中温度参数T0=1.05×Q0,温度下降参数λ=0.50,循环参数Ns=5和Ms=20,以及Pareto优化集合的数量Np=20。为了测试混合遗传算法的有效性,本文首先设定遗传算法适应度函数F(·)中指标权重ω=(1.0,0.0,0.0,0.0),即将所研究问题简化为单目标-所有车辆/车队的行驶总距离最短。表1给出了标准遗传算法(最大迭代次数为500次)和本文提出的混合遗传算法求解标准C-VRP问题的结果对比。由表1数据可以看出,在500次的迭代计算中,本文提出的混合遗传算法多数情况下能够取得问题的最优解(部分问题因为计算精度的影响导致算法计算结果小于理论值,例如表中问题B-N35-K5、B-N45-K5、P-N40-K5的数据结果)。并且,对于问题E-N30-K,由于设定目标函数仅为最小化车队的行驶总距离,使得本文算法计算结果优于理论值(车辆的行驶总距离小于理论值,但是车辆的数量多于理论值)。而相比较而言,多数情况下标准遗传算法并不能够在给定的最大迭代次数中收敛到最优解。因此可以得到初步结论:相比标准遗传算法,本文提出的混合遗传算法计算效率更高(由于增加了模拟退火算法的局部调整,从算法执行时间角度上,本算法并无优势)。接下来,以问题A-N45-K6为测试问题,在给定不同的目标函数权重系数组合下,对比单目标-车队行驶的总距离最短目标函数与多目标目标函数下的计算结果(为了保证结果数据的可比性,这里以单目标最优解的4个目标值作为多目标求解过程中的基准解),如表2所示。表2中的第1、2组权重组合分别表示C-VRP问题的目标为单目标,即车队行驶总距离LA最短或车队运行总时间TA最短。对比这两组数据,可以发现,算法结果差异并不大:当目标为车队运行总时间TA最短时,计算得到的车队行驶总距离增加了5.77%,但是行驶总时间缩短了0.76%。表2中的第3~6组权重组合分别表示C-VRP问题的主要目标为车队行驶总距离LA最短或车队运行总时间TA最短,但是同时也在一定程度上关注各辆车行驶距离和/或行驶时间的均衡性,即指标θlA和θtA。由表中的数据可以看出,当各辆车行驶距离和行驶时间的均衡性目标权重之和越大,车队行驶总距离和总时间都越大,即运营的总成本越高。表2中的第7~10组权重组合表示C-VRP问题的主要目标为包括车队行驶总距离LA最短和车队运行总时间TA最短,并且在一定程度上关注各辆车行驶距离和行驶时间的均衡性。由表中数据可以看出,综合考虑行驶距离和时间时,车队行驶总距离LA指标