货物不相容车辆路径问题的优化

汤雅连 蔡延光 刘宏玉 江泽东

(广东工业大学 自动化学院,广州 510006)

货物不相容车辆路径问题的优化

汤雅连 蔡延光 刘宏玉 江泽东

(广东工业大学 自动化学院,广州 510006)

考虑现实生活中每个客户定制的货物不可用同一辆车混装，或者多个客户的货物不可混装的问题，建立了基于车辆载重、行驶里程、多种车型等约束条件的货物不相容的多车型车辆路径问题的数学模型，应用基于精英选择、混沌变异及模拟退火机制的混合遗传算法求解。将该算法应用到benchmark算例上，并与分支定界算法求解的结果比较，结果表明提出的算法优于分支定界算法。

货物不相容的多车型车辆路径问题；混合遗传算法；模拟退火机制；3-opt局部搜索；混沌变异；分支定界算法

在货物配送过程中,会经常出现多个客户需要的货物不可混装的情况,比如易腐产品和日用品,危险品和食品等。在合理安排车辆装载及货物分配的条件下,研究货物不相容的多车型车辆运输调度问题(heterogeneous vehicle routing problem with incompatible goods,HVRPIG)有一定的研究意义。车辆路径问题(vehicle routing problem,VRP)是HVRPIG的基础,VRP[1-3]自1959年Dantzig和Ramser首先提出以来就引起了人们的高度重视。VRP的实用性强,应用广泛。车辆路径问题一般定义为:对一系列送货点和收货点,组织适当的行车路线,使车辆有序地通过它们,在满足一定的约束条件(如货物需求量、发送量、送发货时间、车辆容量限制、行驶里程限制、时间限制等)下,达到一定的目标(如路程最短、费用极小、时间尽量少、使用车辆数尽量少等)。货物相容和不相容HVRP示意图如图1所示。

图1 货物相容和不相容HVRP示意图

在过去的几十年中,有不少学者研究了VRP。郑丽英等人[4]为了保证染色体的多样性和尽可能地降低问题求解复杂度,提出了五类遗传交叉算子,求解单车场多车型VRP问题;杨浩雄等人[5]采用自适应多态蚁群算法求解基于空驶成本、运输成本和时间成本这三个维度的VRP;王晓博等人[6]为满足电子商务客户多样化和个性化的需求,建立了多车型的装卸混合车辆调度模型,对混合遗传算法求得的精英种群进行禁忌搜索,提高了搜索效率;陶胤强等人[7]考虑了车型与任务的相容性,建立了带时间窗约束的多车型多费用非满载车辆路径问题数学模型,应用启发式算法求解;陈萍等人[8]基于变邻域搜索,设计了变邻域搜索中的“抖动”以及局部优化过程的邻域结构结合,提出一种启发式算法求解多车型车辆路径问题。葛显龙等人[9]采用量子比特位设计染色体结构,改进遗传算法中交叉与变异算子,避免优秀基因被破坏,设计快速寻优机制与最优保留机制,求解基于车辆使用优先原则的多车型车辆路径问题。陈美军等人[10]提出了一种自适应的最大-最小蚁群算法,算法结合自适应方法和最大-最小蚁群算法的优点,适时地控制蚁群算法中的信息素更新过程,扩大搜索范围,避免了基本蚁群算法的早熟现象,并克服了求解速度慢的缺点,基于该改进算法求解基于客户优先级、路况影响、多车型、时间窗和容量等多约束条件下的多车场车辆路径问题。但是对研究HVRPIG的相关文献还没发现,所以研究HVRPIG具有非常重要的意义。

1 建立数学模型

1.1 问题描述

HVRPIG是指某车场有多种不同类型的车辆,为多个客户送货,每个客户需要的多种货物或客户与客户需要的货物不相容,不可用同一辆车配送,组织适当的配送计划及行车路线,在满足一定的约束条件下(客户需求量、车辆载重等),使配送距离最短。不考虑装卸货时间。

1.2 数学模型

1)优化模型符号。

客户编号:i=1,2,…,l;客户i的需求量:gi(i=1,2,…,l);车辆类型:h(h=1,2,…,H);货物类型:n(n=1,2,…,N);每种类型货物的重量:gn(n=1,2,…,N);车辆载重:qh,gi＜qh,gn＜qh;车辆最大里程约束:Dh;每种类型的车辆数量:Kh;客户i与j之间的距离:dij;客户i与j的平均速度:vij;车辆服务的客户数量:Cnh;中心车场的编号:0;货物相容系数:Cpq(1≤p,q≤N), Cpq=1,则可以混装;否则,不可以混装。

2)定义变量。

3)建立数学模型

目标函数:

约束条件:

目标函数式(3)表示总距离最短;式(4)表示车场派出的车辆数不能超过该车场的车辆总数;式(5)表示车辆从所在的车场出发,完成配送任务后,回到原车场;式(6)和式(7)表示每辆车的载重限制;式(8)为车辆里程约束;式(9)消除了车辆不是从车场出发的现象;式(10)表示车辆服务的顾客数不小于1,则参与配送,否则没有参与。

2 算法设计

2.1 产生初始种群及编码

采用文献[2]的方法,染色体表示为基因序列(G1,G2,…,Gm),Gi由三部分构成,车场编号DepotNum、车辆编号VehicleNum和排序值SortValue,表示客户i由n车场h类型的车辆服务,根据车辆所有客户的SortValue决定客户在路径中的位置。DepotNum、VehicleNum和SortValue随着初始群体的产生而生成。

2.2 适应度值计算

计算相应的目标函数值以及适应度函数值fj,j=1,2,…,m。我们用当前群体中最佳染色体的目标函数值z与当前染色体的目标函数值zi的比值作为适应度值,如式(11)所示。

2.3 精英选择策略

精英选择[11]是群体收敛到优化问题最优解的一种基本保障。如果下一代群体的最佳个体适应值小于当前群体最佳个体的适应值,则将当前群体最佳个体或者适应值大于下一代最佳个体适应值的多个个体直接复制到下一代,随机替代或替代最差的下一代群体中的相应数据的个体。对于给定的t代规模为n的群体P(t)=｛a1(t),a2(t),…,an(t)｝,一般描述为

2.4 自适应交叉

交叉算子[1]主要用于产生新个体,实现算法的全局搜索能力。考虑到整个种群的变化趋势及每个个体的变异机会,本节设计了与进化代数相关而与个体适应度无关的交叉概率计算公式,如式(12)所示。t为当前进化代数,Tgen为预设的最大进化代数,pcmax为预设最大概率,pcmin为预设最小概率,pc(t)为当前种群的交叉概率,采取均匀交叉的方式进行交叉操作。假设两个父代为A和B,均匀操作如下。

1)随机产生一个与个体编码串长度等长的染色体C,C=c1c2…ci…cl,l为染色体编码长度;

2)若ci=0,A′在第i个基因座上的基因值继承A的基因值,B′在第i个基因座上的基因值继承B的基因值;

3)若ci=1,A′在第i个基因座上的基因值继承B的基因值,B′在第i个基因座上的基因值继承A的基因值。

2.5 混沌变异

采用混沌变异策略[1],混沌变异形式如式(13)所示。K(0,1)为(-2,2)按混沌规律变化的序列。根据Logistic映射[1],如式(14)所示。式中,u表示种群序号,u=0,1,…,n;β表示混沌变量, 0≤β≤1;μ表示吸引子,当μ取0～4时,Logistic映射为[0,1]间的不可逆映射,μ=4时,完全处于混沌的状态,此时产生的混沌变量β(u)具有很好的遍历性。β(u)经过放大和平移可得K(0,1)。变异算子的变化尺度对算法的性能有一定的影响。既要达到精度,又要搜索到全局最优解,所以在进化初期应采用逐渐缩小的变异尺度,利用文献[2-3]提出的变异策略,如式(15)所示。kc为当前代数, Gen为最大迭代次数,δ为当前群体中某个体的某分量的变异尺度,α,β,γ为控制尺度收缩参数。

2.6 引入模拟退火机制

退火初始温度为T0,终止温度为Tend,温度冷却系数qcool。以fi为当前解,计算每一个个体的适应值fi′。若f′i＞fi,则以新个体替换旧个体;否则,以概率exp(fi-f′i)T接受新个体,舍弃旧个体。

2.7 终止条件

当算法运行达到最大迭代次数或者Ti＜Tend,算法终止。

2.8 3-opt局部搜索

采用3-opt局部搜索[12]方法,可以增强遗传算法的局部搜索能力。

步骤1从路径中删除3条边,并在路径的其他地方加上3条新的边,使路径保持完整。如果更换之后使路径长度变短,保留切换结果;否则,通过删除添加不同的边,并尝试其他更换方式。

步骤2重复步骤1,直到尝试了所有可能的更换方式,且不能再提高解的质量,则输出最优路径,退出算法。

3 仿真

3.1 实例

Benchmark算例可从http://www.bernabe.dorronsoro.es/vrp/上获得,主要以Solomon中C101的25客户和50客户的数据作为测试对象。坐标位置不变,某类型的车辆只能配送相应类型的货物。车辆信息如表1所示。客户所需货物信息如表2所示。

表1 车辆信息

表2 客户所需货物信息

本实验是在SONY i5-4200U CPU2.6GHz、内存为4.0G、安装系统为win7的PC机上采用Matlab R2010b编程实现的。混合遗传算法参数设计:种群规模为size pop=50,最大迭代次数TGen=300,pcmax=0.4,pcmin=0.004,变异概率pm=0.005,均匀交叉,单点变异,尺度收缩参数为α=1,β=10, γ=0.6,δ=0.6,T0=100,Tend=0,qcool=0.8。运行算法20次,取最好的结果。

3.2 结果分析

Solomon-25客户和Solomon-50客户的最优行驶网络如图2和图3所示。Solomon-25客户和Solomon -50客户的配送计划表如表3和表4所示,最优值分别为309.49和572.10。本文算法与分支定界法的算法比较如表5所示,可见两种算法都能获得最优值,但是当问题规模增大时,分支定界算法寻优的能力就开始减弱了,且寻优时间比本算法长,进一步说明了本算法在寻优能力和寻优时间方面都优于分支定界法。

图2 Solomon-25客户的最优行驶网络

图3 Solomon-50客户的最优行驶网络

表3 Solomon-25客户配送计划表

表4 Solomon-50客户配送计划表

表5 算法比较

4 结语

HVRPIG问题实质上是一个多任务的VRP问题。应用基于精英选择策略、自适应交叉、混沌变异,并引入了模拟退火机制的HGA求解,最后应用3-opt局部搜索策略对解进行调整,得到最优解。本算法的优点在于:分析不同客户所需货物的类型,专车配送相应的货物类型,简化了问题模型;考虑到收敛精度与进化代数的关系,混沌变异结合了“尺度收缩”思想,并采用了避免近亲繁殖的策略,引入模拟退火机制能有效克服传统遗传算法易早熟的现象;3-opt局部搜索对解的调整,从而提高算法的性能。下一步将要探讨的问题是考虑更为复杂的问题模型,如规模更大、道路因素、客户需求紧急程度、个性化送货时间窗、周期性、开放式、客户随机性需求等,以及研究如何改进算法,使算法的性能更优。

[1] 汤雅连,蔡延光,郭帅,等.单车场关联物流运输调度问题的混沌遗传算法[J].广东工业大学学报,2013,30:53-57.

[2] 汤雅连,蔡延光,赵学才.关联物流运输调度问题的改进遗传算法[J].微型机与应用,2012,31(17):69-71.

[3] 汤雅连,蔡延光,章云,等.易腐产品运输调度问题的优化[J].计算机系统应用,2013(8):136-140.

[4] 郑丽英,贾海鹏.全局搜索聚类的多车场多车型调度算法研究[J].兰州交通大学学报,2009,28(6):19-22.

[5] 杨浩雄,胡静,何明珂.配送中多车场多任务多车型车辆调度研究[J].Computer Engineering and Applications,2013,49(10):243-246.

[6] 王晓博,李一军.多车场多车型装卸混合车辆路径问题研究[J].控制与决策,2009,24(12):1769-1774.

[7] 陶胤强,牛惠民.带时间窗的多车型多费用车辆路径问题的模型和算法[J].交通运输系统工程与信息,2008,8(1):113-117.

[8] 陈萍,黄厚宽,董兴业.求解多车型车辆路径问题的变邻域搜索算法[J].系统仿真学报,2011,23(9):1945-1950.

[9] 葛显龙,许茂增,王伟鑫.多车型车辆路径问题的量子遗传算法研究[J].中国管理科学,2013,1:125-133.

[10] 陈美军,张志胜,史金飞.多约束下多车场车辆路径问题的蚁群算法研究[J].中国机械工程,2008,19(16):1939-1944.

[11] 汪勇,杨海琴,张瑞军.基于强基因模式组织算法的VRPTW研究[J].控制与决策,2011,26(4):606-610.

[12] 王华秋,曹长修.一种结合O3-opt局部优化的智能蚂蚁算法研究[J].计算机应用与软件,2010,27(10):89-91.

The Optimization of Vehicle Routing Problem with In compatible Good s

TANG Ya-lian CAIYan-guang LIU Hong-yu JIANG Ze-dong
(School of Automation,Guangdong University of Technology,Guangzhou 510006,China)

Considering the incompatibility of the many goods of every customer’s or many customers’in the real life,we establish the heterogeneous vehicle routing problem with incompatible goods(HVRPIG)mathematical model based on vehicle load, vehicle mileage constraints,heterogeneous vehicles etc.Using hybrid genetic algorithm(HGA)based on elite selection,chaotic mutation and simulated annealing mechanism solves the model.By measuring the performance of the algorithm by the simulation research of benchmark examples,and comparing the results between the HGA and branch and bound algorithm(BBD),the results show that the proposed algorithm is better than BBD.

heterogeneous vehicle routing problem with incompatible goods;hybrid genetic algorithm;simulated annealing mechanism;3-opt local search;chaotic mutation;branch and bound algorithm

TP301

A

1009-0312(2015)01-0019-06

2014-04-01

国家自然科学基金(61074147,61074185);广东省自然科学基金(S201101000505983510090010000 02);广东省教育部产学研结合项目(2012B091000171,2011B090400460);广东省科技计划项目(2012B050600028,2010B090301042)。

汤雅连(1986—),女,湖南常德人,博士生,主要从事物流信息技术及智能算法研究。