阎庆 鲍远律 (中国科学技术大学 自动化系,安徽 合肥 230039) 摘 要:论文建立了物流配送路径优化问题的数学模型.因为遗传算法的交配 算子操作可能会使最好解遗失. 同时常用的一些停止准则不但无法保证算法所得 的最终解必定是最优解, 甚至无法保证最终解是整个搜索过程中曾经达到的最优 解.这些不足都严重影响了整个算法的性能.针对这些情况本文提出了将遗传算 法和模拟退火算法结合,并加入了记忆装置.根据这种想法设计了一种有记忆功 能的遗传模拟退火算法,并进行了试验计算.试验结果表明:用这种有记忆功能 的遗传模拟退火算法求解物流配送路径优化问题, 可以在一定程度上解决上述问 题,从而得到较高质量的解. 关键词:物流配送;遗传模拟退火算法;遗传算法;模拟退火算法;路径优化
中图分类号:TP319:F25 文献标志码:①
The new Genetic Simulated Annealing Algorithm Solve the VRP Problem
YAN Qing BAO Yuan-lv
(Department of Automation, USTC, Hefei Anhui 230027,China)
AbStract:This paper establishes the optimizing model on physical distribution routing problem.,because the Crossover operator of the Genetic Algorithm may be losing the best result,the common stop rule cannot ensure the result is the best of all the result,even cannot ensure it is the best one of all the result received from the whole search procedure.these weakness affect the performance of the algorithm.On the basis of the situation,this papar bring forward let the genetic algorithm and the simulated annealing algorithm combinated,and let it has a remembering function.thus we get a new hybrid algorithm, called remembered genetic simulated annealing algorithm.we make some experimental computation,the result demonstrate this algorithm can overcome the weakness above,and the high quanlity solutions obtained. Key words:Physical Distribution; genetic simulated annealing algorithm;the genetic algorithm;the simulated annealing algorithm;the optimation of the routing problem
1
引言
在竞争日益激烈的现代商业社会, 企业只有以市场为核心去适应不断变化的 环境并及时对市场做出发应,才能在竞争中立于不败之地.物流管理正是以实 现上述要求为目标的.而物流配送是现代化物流管理中的一个重要环节.它是指 按用户的定货要求,在配送中心进行分货,配货,并将配好的货物及时送交收货 人的活动.在物流配送业务中,存在许多优化决策的问题.本文只讨论物流配送 路径优化问题.合理选择配送路径,对加快配送速度,提高服务质量,降低配送 成本以及增加经济效益都有很大影响.物流配送路径优化问题最早是在 1959 年 由 Dantzig 和 Ramser 首先提出的,即所谓的车辆路径问题(Vehicle Routing Problem)VRP(1).它也是目前在物流系统中较受关注的一个方面.它是指在客
户需求位置已知的情况下,确定车辆在各个客户间的行程路线,使得运输路线最 短或运输成本最低. VRP 问题已经被证明是一个 NP-hard 问题. 也就是说当问题 的规模较大时,很难得到全局最优解或满意解.而且随着问题规模的增大,算法 的计算时间将以指数速度增加.因此研究的重点就转移到各种启发式算法上. 求解物流配送路径优化问题的方法有很多, 常用的有旅行商法, 动态规划法, 节约法,扫描法,分区配送法,方案评价法等.而遗传算法的出现为求解物流配 送路径优化问题提供了新的工具.遗传算法(Genetic Algorithm,GA)是由美国 Michigan 大学 Holland 教授发展起来的(2).遗传算法作为一种非数值并行算法, 其思想起源于生物遗传学适者生存的自然规律.它对优化对象既不要求连续,也 不要求可微,尤其适合求解 NP-hard 问题.到目前为止,已经有很多人都曾利用 遗传算法求解物流配送路径优化问题并取得了一些研究成果. 郎茂祥还尝试采用 新的编码方法和遗传算子构造了求解配送路径优化问题的遗传算法, 并进行了试 (3) 验计算 .计算结果表明:尽管用遗传算法可以求得物流配送路径优化问题的可 行解或满意解,但总体上解的质量不是很高.有时其结果甚至比爬山算法还差. 究其原因,主要是由于遗传算法局部搜索能力不强造成的(4).因此我们考虑用一 种局部搜索能力强的算法和遗传算法相结合, 构造一种混和遗传算法来求解物流 配送路径优化问题.郎茂祥选择了爬山算法而我们尝试用模拟退火算法.模拟退 火算法是一种局部搜索算法的扩展.它不同于一般局部搜索算法之处在于:它以 一定的概率选择邻域中费用值大的状态.在模拟退火时齐算法中,每两个温度之 间的状态点是无关的.从理论上说,任何一个温度的马氏链都可逐渐达到平稳分 布. 即从一个状态到另一个状态随着迭代步数的增加渐渐不依赖于起点状态且在 每一个状态的概率服从平稳分布. 这种特性就可以用来克服遗传算法因为仅强调 两代之间的进化关系而在其交配操作中可能使最好解遗失的缺点. 在此基础上我 们又设置了一个记忆装置以记住算法进行过程中出现的最优解. 这样就保证了最 终解至少是整个搜索过程中曾经出现的最优解. 至此我们就构造了求解物流配送 路径优化问题的一种有记忆功能的遗传模拟退火算法. 在本文中将对其步骤详细 叙述并通过实验计算证明该算法的良好性能.
2
物流配送路径优化问题的数学模型
物流配送路径优化问题一般可以这样描述:从某物流配送中心用多辆配送 车辆向多个客户送货.每个客户的位置和货物需求量一定,每辆车的载重量一 定,其一次配送的最大行驶距离一定.要求合理安排车辆配送路线,使目标函 数得到最优.并满足以下条件: (1)每条配送路径上各客户需求量之和不超过 配送车辆的载重量; (2)每条配送路径的长度不超过配送车辆一次配送的最大 行驶距离; (3)每个客户的需求必须满足,且只能由一辆配送车送货. 设配送中心需要向 k 个客户送货,每个客户的货物需求量是 gi (i=1, 2,…..k) ,每辆配送车的载重量是 q,且 gi
得到的数学模型如下所示:
min Z = ∑∑∑ c ijxijs
i = 0 j= 0 s =1 k k m
(1)
∑
i =0 m
k
giyis ≤ q
s=1,2,…..,m
(2)
∑y
s =1
is
1, i = 1,2,..., k = m, i = 0 j=1,…,k;s=1,2,..,m
(3)
∑x
i =0 k
k
ijs
= yjs
(4)
∑x
j=1
ijs
= yis
i=0,1,…,k;s=1,2,…,m
(5)
xijs=0 或 1 i,j=0,1,…,k;s=1,2,…m (6) 上述模型中,式(2)为汽车容量约束;式(3)保证了每个客户的运输 任务仅由一辆车完成,而所以运输任务则由 m 辆车协同完成;式(4)和式(5) 限制了到达和离开某一客户的汽车有且仅有一辆.
3 物流配送路径优化问题的有记忆的遗传模拟退火算法
针对遗传算法的一些不足,作者将模拟退火算法与之结合,并加入了记忆 装置,从而构造了物流配送路径优化问题的一种有记忆功能的遗传模拟退火算 法.该算法的特点是扩大了原有遗传算法的搜索邻域,在一定概率控制下暂时 接受一些恶化解.同时利用记忆装置保证了在一定终止条件下所得的最终解至 少是搜索过程中曾得到所有解中的最优解. 该算法通过在常规的遗传算法基础上 加入模拟退火算子和记忆装置而得到. 下面首先介绍此有记忆功能的遗传模拟算 法的步骤.然后再对遗传算法中染色体的结构,其常规算子的构造以及模拟退火 算子中的邻域结构和温度衰减函数的选择加以具体介绍. STEP1 给定群体规模 maxpop,k=0;初始温度 tk=t0,产生初始群体 pop(k);对初 始群体计算目标值 f(i), 找出使函数 fi(tk)最小的染色体 i 和这个函数值 f,记 i*=i,f*=f; 其中,fi(tk)为状态 i 在温度为 tk 时的目标值.i ∈ pop(k),即当代群体中的一个染 色体. STEP2 若满足结束条件则停止计算,输出最优染色体 i*和最优解 f*;否则, 在群体 pop(k)的每一个染色体 i ∈ pop(k)的邻域中随机选一状态 j ∈ N(i), 按模拟退火中的接受概率
fj ( tk ) fi (tk ) Aij (tk ) = min{ 1, exp }, tk
接受或拒绝 j,其中 fi(tk), fj(tk)分别为状态 i,j 的目标值.这一阶段共需 maxpop 次迭代以选出新群体 newpop1. STEP3 在 newpop1(k+1)中计算适应度函数 fi (tk ) f min fi (tk ) = exp{ }, tk 其中,fmin 是 newpop1(k+1)中的最小值.由适应度函数决定的概率分 布从 newpop1 中随机选 maxpop 个染色体形成种群 newpop2 STEP4 按遗传算法的常规方法对 newpop2 进行交叉得到 crosspop,再变异得 到 mutpop. STEP5 令 pop(k+1)=mutpop,对 pop(k+1)计算 fi(tk),找出使函数 fi(tk)最小的染色体 i 和这个函数值 f,如果 f
k k m m k Z= ∑∑∑ cijxijs + M ∑ max ∑ giyis q,0 i = 0 j= 0 s = 0 s =1 i =0
其中 M 为一很大的正数,表示当一辆车的货运量超过其最大载重量时的惩 罚系数.M 应趋向于无穷大.考虑到计算机处理的问题,参考文献[6],取 M 为 1000000.将此运输成本函数作为我们的目标函数.适应度函数采用一种加速适 fi (tk ) f min 应度函数 fi (tk ) = exp{ }. 这种适应度函数加速性能比较好, 可以迅速 tk 改进适应度的值,缩短算法运行时间. 3.4 交叉算子 将每代种群的染色体中适应度最大的染色体直接复制,进入下一代.种群 中其他染色体按其适应度的概率分布,采用轮盘赌的方法,产生子代.这样既 保证了最优者可生存至下一代,又保证了其余染色体可按生存竞争的方法生成 子代,使得算法可收敛到全局最优.选中的染色体按一定的概率—交叉率,产 生子代.文献[7]认为交叉率在 0.6～0.8 之间,算法进化效果较好. 由于车辆路径问题的条件约束,如果采用简单的交叉算子,将可能产生 大量的不可行解.因此这里采用文献[6]的交叉算子,这种改进的交叉算子, 避免非可行解的产生,具体做法如下: ⑴随机产生交叉位,如果在交叉位的外侧两端的父代基因都是 0 的话,则 对父代进行简单交叉;如果交叉位的外侧两端的父代基因不为 0 的话,则将左交 叉位向左移,直至移动到左交叉位的左端基因为 0 时停止.以左交叉位为起点, 继续向右移动右交叉位,直至右交叉位的右端基因为 0 为止.这样就保证了父代 染色体都用 1 条子路径来进行交叉. ⑵经过第 1 步操作,子代中仍会产生访问同一客户 2 次的情况,需要对 子代进行整理.在子代中选择那些具有重复情况的自然数,如果该自然数并非 在交叉位内的话,则删除之.子代如存在未访问到某一客户的情况,则在染色 体的交叉位外补上该客户对应的自然数. ⑶经过第 2 步的操作,如果产生了某一子路径为空的情况,即染色体中含 有 2 个连续的 0,须继续进行第 3 步操作.将其中的 1 个 0 与染色体其它位上 的客户自然码进行交换.对该客户自然码的要求是该码的前一位与后一位均不 为 0.本步操作可放在对子代的变异后进行. 如有父代 1:015604027680,父代 2:071086402350.使用上述算法,对 父代 1 选定交叉位 8,11,对父代 2 选定交叉位 5,7.经过第 1 步计算,得子 代 1:01560408640 和子代 2:0710273802350.使用算法的第 2 步,整理子代 1 和子代 2.得到子代 1;012537008640 和子代 2:014027380560.子代 1 中存 在 2 个连续的 0,对其进行第 3 步操作.最后得到子代 1:012507308640 3.5 变异算子 交叉产生的子代依一定概率—变异率发生变异.变异的策略是随机交换 2 个基因的位置.在变异后,需要用交叉算子的第 3 步操作整理子代,以保证 可行性. 3.5 结束条件 当算法的当前进化代数大于预先设定的 N 时,算法结束. 3.6 邻域结构 每个染色体的邻域包括任意交换其两个基因所产生的所有染色体. 3.7 衰减函数 tk+1=α×tk,
4 实验分析
实验初始数据取自参考文献[6] 实验 1,随机生成 1 个有 8 个门店的 VRP 问题,初始数据如下:
实验 1 初始数据 门店 配送中 心 位置 需求 量 仓库 位置 需求 量 仓库 7 (29,90) 2.54 仓库 8 (10,60) 2.39 (31, 9) (76,38) 0 2.46 (77,16) 0.41 (90,82) 2.16 (60,74) 2.27 (76,86) 1.83 (11,31) 3.76 门店 1 门店 2 门店 3 门店 4 门店 5 门店 6
根据各仓库的需求量, 计算出需要的汽车数: m=[17.82/(0.85*8)]+1=3 文献 [6]采用传统的遗传算法的各算子,并对其中的交叉算子进行了改造,取群体规 模为 20,进化代数为 50,应用此程序他费时 3s 得到的结果为: 子路径 1:0 8 7 4 0 子路径 2:0 6 0 子路径 3:0 5 1 2 0 运输距离成本:476.29 而我们的算法在上面的算法中加入了一个模拟退火算子,取初始退火温度 为 10,衰减系数取 0.85 使用第三节所述算法步骤,在奔腾四的计算机上计算, 耗时 2s,得结果如下: 子路径 1:0 6 0 子路径 2:0 2 1 3 5 0 子路径 3:0 8 7 4 0 运输距离成本:476.290507 进化代数为:20 实验 2,随机生成 1 个有 20 个门店的 VRP 问题,初始数据如下:
实验 2 初始数据 门店 位置 需求量 配送中心 (52,4) 0 门店 1 门店 2 门店 3 门店 4 门店 5 门店 6
(15,49) (0,61) 1.64 1.31
(51,15) (25,71) (38,62) (35,45) 1.43 3.38 1.13 3.77
门店 位置 需求量
门店 7
门店 8
门店 9
门店 10
门店 11
门店 12
门店 13
(100, 41) (10,52) (26,79) (87,7) 3.48 0.39 0.24 1.03
(24,89) (19,25) (20,99) 2.35 2.60 1.00
门店 位置 需求量
门店 14
门店 15
门店 16
门店 17
门店 18
门店 19
门店 20
(73,91) (100, 95) (7,73) 0.65 0.58 2.56
(69,86) (24,3) 1.27 2.69
(66,14) (9,30) 3.26 2.97
计算得:需 6 辆车.用文献[6]的算法取群体规模 100,进化代数分别设为 20,50,100,得到的结果不同:
实验 进化代数 运输成本 1 20 1153.12 2 50 964.48 3 100 908.44
而采用本文的算法,初始退火温度取 10,衰减系数取 0.85,在奔腾四的计 算机上计算,则结果如下:
实验 进化代数 运输成本 1 20 997.96 2 50 958.67 3 100 901.29
从以上两个实验可以看出:采用本文中所述的算法,要得到相同的结果可以 缩短进化代数,从而节约运算时间.而要增加进化代数必然得到更好的结果.
5 结束语
本文使用文献[6]中比较合理的交叉算子和变异算子,采用自然数编码将模 拟退火算法与传统的遗传算法相结合,用来求解物流系统中车辆路径问题.这种 算法所需的进化代数明显减少, 因此在时间特性上有了比较好的改善, 耗时较短, 获得了较好的结果.实验结果表明此算法在解决诸如车辆路径问题这类 NP_hard 问题确实可行,并有较好的性能.而且随着问题规模的增大,这种对时间性能的 改善效果将更加明显. 参 考 文 献 1 郭耀煌,李军著 车辆优化调度.成都:成都科技大学,1994 2 邢文训,谢金星编著 现代优化计算方法.北京:清华大学出版社,1999.140 3 郎茂祥,物流配送车辆调度问题的模型和算法研究[D].北京:北方交通大学, 2002 4 郎茂祥,胡思继,用混和遗传算法求解物流配送路径优化问题的研究,中国管 理科学,2002,10(5):51—56 5 李军,谢秉磊,郭耀煌,非满载车辆调度问题的遗传算法.系统工程理论与实 : 践,2000,20(3) 235—239 6 唐坤 车辆路径问题中的遗传算法设计.东北大学学报(自然科学版)2002, 28(1):66—70 7 姜大立,杨西龙,杜文等 车辆路径问题的遗传算法研究[J].系统工程理论与实 践,1999 19(6):40—45 作者简介:阎庆(1978-),女,安徽六安人,硕士研究生,主要研究方 向:地理信息系统在物流管理系统中的应用;鲍远律(1947-) ,男,安徽 六安人,教授,硕士生导师,主要研究领域:控制理论与系统集成,全球 定位系统GPS应用,交通矢量地图GIS,移动目标监控专用数字通讯. 附注:本文感谢其研究基金项目来源如下,如若发表,请在正文中注明. 基金项目:国家自然科学基金(60272040)资助项目.