（系统工程专业论文）基于MMAS的配送线路规划研究与应用.pdf

山东大学硕士学位论文 摘要 物流配送是现代化物流系统的重要环节。在企业内部，物流配送主要发生在 区域配送中心( r d c ) 、前端配送中心( f d c ) 和中转站( c d ) 之间。在实际运作 过程中，物流配送网络存在两种模式：一种是“一级配、一级送”模式( d s d ) ； 一种是“一级配、两级送 模式( t 1 j | d ) 。两种不同的模式下的路径规划，将造成 不同的运输成本，同时将直接影响企业物流系统的总费用，因此车辆配送线路规 划以及配送模式的选择对于降低运输成本具有重要的意义。在实际应用中，许多 行业的迅速发展，受到了企业物流网络现状的制约，因此根据企业的资源现状、 客户需求分布以及实际交通路网分布等情况，进行车辆路线规划( v r p ) ，从而选 取总成本较低的网络运输方案成为亟待解决的问题。 d s d 和t w d 可分别抽象成具有容量限制的v r p ( c v r p ) 和多车场v r p ( 佃v r p ) 两种模型，均为n p 难题，随着客户数量的增加，可选的配送线路方案数量将以 指数速度急剧增长。因此，用启发式算法求解该问题就成为人们研究的一个重要 方向。本文针对实际应用中的中等规模网络布局问题相关特点，在不改变模型复 杂程度的前提下采用一阶段法( 整体法) 进行求解，使得算法能够在更大的空间 内进行解的搜索。在算法设计上采用最大一最小蚂蚁系统( m m a s ) ，并根据求解问 题的特殊性，对m m a s 的初始蚁群的分布、信息素更新规则以及蚂蚁的转移方式 进行了改进。 为验证算法的有效性，选取具有代表性的f 企业作为案例。通过案例中c v r p 和m d v r p 的求解，获得了较为满意的收敛时间和结果，并根据求解结果得到每个 r d c 在两种模式下的运输成本，对比后作出r d c 模式决策，得到各r d c 的最佳送 货路线和车辆调配方案。仿真结果表明，采用一阶段m m a s 可为f 企业每年节约 运输成本9 9 6 。 关键词：配送线路规划；最大最小蚂蚁系统；多车场车辆路径问题；一阶段法 山东大学硕士学位论文 a b s t r a c t p h y s i c a ld i s t r i b u t i o np l a y sa l li m p o r t a n tr o l e i nm o d e ml o g i s t i c ss y s t e m s i n s i d ea l le n t e r p r i s e ，t h ec o m m o d i t ym u s tb ep i c k e da n ds o r t e di no n eo ft h er e g i o n a l d i s t r i b u t i o nc e n t e r s ( r d c s ) f r o n td i s t r i b u t i o nc e n t e r ( f d c ) l i k e sah u b ，c o n n e c t s r d ca n ds o m eo ft h ec r o s sd o c k i n g s ( c d s ) a n dl o g i s t i c sm a i n l yo c c u r sa m o n g r d c ，f d ca n dc d t h e r ea r et w ok i n d so fl o g i s t i c - n e t w o r k - m o d e ，o n ei sc a l l e dd s d m o d e ，w h i c hm e a n sd i r e c ts t o r ed e l i v e r y , a n dt h eo t h e rc a l l e dt w d ，w h i c hm e a n s t r a n s i tw a r e h o u s ed e l i v e r y c o s t su n d e rt w om o d e sa r ed i f f e r e n t c l i e n t s d e m a n d s a n dt h er o a dn e t w o r ks h o u l d b ec o n s i d e r e dd u r i n gt h ed e s i g n r o u t i n gd e s i g nt a k e sa l l i m p o r t a n tr o l ei nt h et o t a ll o g i s t i c sc o s t s oo p t i m i z i n gt h ed e l i v e r yr o u t i n gi sn e e d e d f o rc u t t i n gd o w nt h et r a n s p o r t a t i o nc o s t i nm a n ye n t e r p r i s e s ，t h el o w c o s ts o l u t i o n s w o u l db et h ec h o i c e s ov e h i c l er o u t i n gp l a n n i n gi st h eb u r n i n gq u e s t i o n a c c o r d i n gt o t h ed i f f e r e n tf e a t u r e s ，t h ed s dm o d ea n dt w dm o d ea l e a b s t r a c t e da sc v r pa n dm d v r p v r pi san o n - d e t e r m i n i s t i cp o l y n o m i a lp r o b l e m t h ed i f f i c u l t ya n dt h en u m b e r so fs o l u t i o n sg r o we x p o n e n t i a l l yd u et on o d e - a d d i n g h e u r i s t i ca l g o r i t h mb e c o m e sa ni m p o r t a n td i r e c t i o ni nt h i sf i e l d i nt h i sp a p e r , t h e m a x m i na n ts y s t e m ( m m a s ) i su s e dt os o l v et h ec v r pa n dm d v r p a n da n u n u s u a la n t c o l o n yi n i t i a ld i s t r i b u t i o na n dr u l e sf o ru p d a t i n gt h ep h e r o m o n et h a t d i s t i n g u i s h e df r o mo t h e rr e s e a r c h i td e v e l o p sag l o b a la p p r o a c hf o rm d v r p w h i c h d i d n te n l a r g et h em o d e l sc o m p l e x i t y i nt h i sp a p e r , t h et r a n s p o r t a t i o nc o s to ft h es o l u t i o n sh e l p st om a k ed e c i s i o n sf o r ac e r t a i np r o j e c tc a s e n u m e r i c a ld a t ae x h i b i t st h a tt h er e s u l t so fm m a sa r ef e a s i b l e a n dl o w e rc o n v e r g e n c et i m e s 。a sar e s u l t ，e a c hr d ck n o w si t sd e l i v e r yr o u t e s ， s e r v i c ea r e a , a n de v e r yv e h i c l e ss c h e d u l e t h es o l u t i o no ft h em o d e l sw o u l dg i v et h e p r a c t i c a la p p l i c a t i o nas a v i n go f9 9 6 o ft h et r a n s p o r t a t i o nc o s t se v e r yy e a r k e y w o r d s ：d i s t r i b u t i o nr o u t i n gd e s i g n ；m m a s ；m d v r p ；g l o b a la p p r o a c h i i 山东大学硕士学位论文 符号说明 v r p 模型中符号说明： g 连通有向图； vc v r p 模型中g 的顶点集； 么 g 的边集； ，。配送中心或者车场； c 【( + 1 ) ，( + 1 ) 】c v r p 模型中与弧集相关的运输费用矩阵； 勺与之间的运输费用； g f k q x 爹 每个客户的非负的货物需求； c v r p 模型中配送中心具有的车辆总数； 每台车辆的车载能力； c v r p 模型中边( f ，) 是否由车辆七服务的决策变量； m d v r p 中车场v 。的车辆七是否由客户e 到的决策变量； c v r p 模型中客户点e 是否由车辆k 服务的决策变量； m d v r p 模型中的点集，由客户点集和车场集组成； 客户点集，含个客户； 车场( 配送中心) 集，有m 个车场； m d v r p 模型中第聊个车场拥有的车辆数； c ( + m l ( + m ) 】m d v r p 模型中与弧集相关的运输费用矩阵； 三妇总运输成本最低的目标函数值。 i l l y 匕 如 山东大学硕士学位论文 m m a s 算法设计中符号说明： m 6 。o ) d p m = 以o ) ，蚁群中蚂蚁的数量； i = 矗 t 时刻位于客户i 的蚂蚁的个数； 客户i 与客户歹之间的距离； 边( f ，j ) 的能见度，反映由客户f 转移到客户j 的启发程度，一般取 叼玎 q q = 、 d 口； 乃边( f ，) 上的信息素轨迹强度； f 驴蚂蚁七在边o ，) 上留下的单位长度轨迹信息素量； 芹 蚂蚁后的转移概率，j 是未被访问的客户； a 在路径( f ，歹) 上残留信息的重要程度； 芦为启发信息的重要程度； t a b u 。 禁忌表，用以记录蚂蚁七以前走过的客户列表； 瓦第七只蚂蚁走过的路程之和； ( r a i n ，f 一】信息素轨迹量的值域范围； f 一 轨迹量上限，同时也是信息素初始值； f 曲 轨迹量下限； p 为信息素挥发系数； s 驴 从实验开始以来最优解全局最优解； s 曲当前循环中最优解迭代最优解； 三；耐 总运输成本最低的目标函数值。 i v 山东大学硕士学位论文 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究做出重要贡献的个人和集体，均己在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名：砬遂竺 日期：塑墨：尘：垒 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文 论文作者签名： 山东大学硕士学位论文 1 1 课题意义 第1 章引言 现代化物流配送是社会化大生产、国民经济发展的客观要求，它的发展状况 对经济发展、商品流通和大众消费起着重要的促进或制约作用。伴随着世界经济 的快速发展和全球经济的一体化，现代物流作为一种先进的组织方式和管理技 术，正受到世界各国政府、企业以及学术界的高度重视。现代物流是流通不断向 高度化、纵身化发展的必然产物，同时也是企业提升绩效、塑造核心竞争力的源 泉。现代物流的发展水平已逐渐成为衡量一个因家现代化程度和综合国力的重要 标志；在发达国家和地区，物流产业已经成为国民经济发展的重要组成部分。 在销售型企业内部，物流配送线路的路线安排直接影响着企业物流系统的总 费用。因此优化车辆配送线路对于降低运输成本具有重要的意义。应根据具体企 业的客户需求的分布以及实际交通路网的分布情况，选取网络运输总成本较低的 方案。 在进行配送中心网络布局与线路规划决策中通常要全面考虑众多影响因素， 这使得此类问题一般都非常复杂，难以手工计算解决，通常需要将定性和定量技 术结合起来以寻求最合适的解决方梨1 1 。 1 2v r p 求解的国内外研究现状 车辆路径问题是由d a n t z i gg b ( 1 9 5 9 ) 【2 】首先提出，用于解决大型汽油存储 中心与大量加油站之间的运输车队线路安排的实际问题。 当把服务每个客户的时间做出限制，则称其为带有时间窗的v r p ( 廿t w ： v r p 、) i ，i mt i m ew m d o w s ) 。还有一些学者对其它的扩展问题进行了研究： g e n d r e a um 等人( 1 9 9 9 ) 用禁忌搜索求解了多车型车辆线路问题例；m i n g o z z ia 等 人( 1 9 9 9 ) 研究了一种精确算法用于解决具有回程运载的v i 冲( v r p b ：v r p 丽m b a c k h a u l s ) 【4 】；集送货一体化的v r p ( v r p p d ：v r pw i t hp i c k v pa n dd e l i v e r i n g ) ， c o r d e a uj - f 和l a p o r t eg ( 2 0 0 1 ) 研究了具有场地特性和时间窗的v r p 的禁忌搜索 山东大学硕士学位论文 算法，即部分车辆不能够到达某些特定的场地【5 1 ，c o r d e a uj - f 等j k ( 1 9 9 7 ) t 6 】研究 了多车场、周期性v r p ( p v r p ：p e r i o d i cv r p ) 复合问题的禁忌搜索算法，还 有的情况是某个客户可能由多个车辆服务：d r o rm 等人( 1 9 9 4 ) 研究了这种情况 ( s d v r p ：s p l i td e l i v e r yv r p ) 【7 】o 在现实生活中车辆都有负荷限制，如未经专门说明，则所讨论的都是带能力 约束的v r p 问题；确定性v r p 是现实中最常见的类型。它针对的背景是：已知 客户或结点的确切需求信息，以及客户结点的位置。以下仅讨论确定性v r p 。 1 2 1 国外研究现状 ( 1 ) v r p 的精确式求解现状 p a o l ot o t h 和d a a i e l ev i g o ( 2 0 0 2 ) i s 】的论文阐述了v l 冲问题的模型、松弛 和精确式算法，文中回顾了多年来分支定界法求解具有车辆容量约束的基本v r p ( c v i 冲) 的发展情况，即使是解决费用矩阵是非对称矩阵的情况下，分支定界 法仍然是精确式算法中最有效的算法，迄今为止这种最有效的精确式算法能够得 出具有5 0 个客户点的c v r p ，只有某些特殊的更多客户点的c v r p 能够精确求 解；在实践当中，一般会使用一些启发式算法。 g l a p o r t e 和y n o b e r t 等人( 1 9 9 2 ) 【9 】【1 0 】撰写了关于v r p 问题的精确式算法 的综述，在此之前的1 9 8 5 1 9 8 7 年每年均撰写l 至2 篇关于c v r p 问题的精确式 解法和近似算法的综述【1 1 】【1 2 】；g l a p o r t e 等人( 1 9 9 2 ) 1 3 1 在撰写的关于分支定界 法解决几类v r p 问题的论文中，发展出能够解决多达4 0 个结点的具有能力约束 的v r p 的精确式算法。可以说，g ；l a p o r t e 等人在上述综述中将上世纪8 0 年代 发展到极致的精确式算法作了完整和详尽的分析。这个时期，最有效的是采用了 基础松弛和最小生成树的分支定界法；后来又出现了采用拉格朗日松弛法及其附 加算法的分支定界法，这种方法扩大了问题的规模，但仍可以取得最优解。 除分支定界法以外，还有几种精确式算法被用作v r p t w 或c v r p 问题的 求解，如整数规划法( i n t e g e rp r o g r a m m i n g ) 1 4 1 ；切平面法( c u t t i n g - p l a n e a l g o r i t h m ) ；分枝裁减法( b r a n c h a n d c u t a l g o r i t h m ) 1 6 1 1 7 】；分枝定价算法( b r a n c ha n d p r i c ea l g o r i t h m ) 1 8 】【1 9 】，或者是其中两种或多种的复合算法【2 0 】【2 1 1 。 ( 2 ) v r p 的启发式求解现状 2 山东大学硕士学位论文 v r p 问题是极其复杂的组合优化问题，只有相当少数的例子可以解出最优 解。至今为止，任何精确式算法都很难解决超过5 0 个客户点的v r p 问题，原因 是诸如分支定界法或者动态规划等精确式算法会由于准确的下限值很难确定而 造成收敛速度( 率) 很慢( 低) 。正是由于精确式算法的这些不足，启发式算法 在实践中被广泛的研究和应用1 2 2 1 。 早期的启发式算法强调的是快速的找到可行解，并将其进行事后最优化，这 类的算法有著名的节约法( c l a r k e 和w r i g h t ，1 9 6 4 ) 、扫描法( g i l l e t t 和m i l l e r ， 1 9 7 4 ) 、广义指派法( f i s h e r 和j a i k u m a r ，1 9 8 1 ) 。 上世纪9 0 年代，亚启发式算法发展起来，其间的研究主要应用了两大方面， 即局部搜索( l o c a ls e a r c h ) 和群体搜索( p o p u l a t i o ns e a r c h ) 。 局部搜索方法中，对于解空间的搜索是通过对当前解的临域的搜索得到下一 个可能的解，这类亚启发式算法的代表是最早由k i r k p a t r i c k ( 1 9 8 3 ) 提出的模拟 退火算法( s a ：s i m u l a t e da n n e a l i n g ) 2 3 】和最早由g l o v e r ( 1 9 8 6 ) 提出的禁忌搜 索算法( t s ：t a b us e a r c h ) 【2 4 1 。模拟退火算法适用的领域较多，可人为地控制 迭代次数反复求解，然而所得解的好坏与初始状态、温度函数等都有很大的联系， 但就其运算过程和解的情况来说不如遗传算法的效果好。禁忌搜索是对局部邻域 搜索扩展后的一种全局逐步寻优算法，由于该算法的搜索速度快、效率高，适用 于大规模的优化计算，因此随着v r p 复杂性的提高和问题领域的延伸，近些年 来很多复杂的问题都用该算法解决。但禁忌搜索算法具有对初始解有较强的依赖 性和搜索过程中只能对一个解操作的缺陷，所以往往需要使用其它启发式方法先 获得一个较好的初始解。 群体搜索的主要原理是将父辈将优秀的基因( 解) 传给下一代，代表性的是 遗传算法( g a ：g e n e t i cs e a r c h ) 。g a 通过多个个体间的选择、交叉等的遗传操 作，相互协力进行解的探索，与以前的算法中对单纯的并列的解的探索相比，容 易发现更好的解。b e r g e r 和b a r k a o u i ( 2 0 0 4 ) 2 5 】用g a 解决带有时间窗的v r p ； 然而在运用该方法的过程中，该算法所得结果的好坏，主要依赖于遗传代数和解 的规模，问题的遗传因子型的表现亦依赖于设计者的能力。在实际应用中只能根 据具体要求，在合理的时间内对问题进行求解，若所得解不能令人满意，就要以 计算时间为代价增大解组规模或遗传代数，从而有希望得到问题的全局最优解。 山东大学硕士学位论文 k r z y s z t o ff l e s z a 等( 2 0 0 7 ) 2 6 1 运用变动邻域搜索( v n s ：v a r i a b l en e i g h b o r h o o d s e a r c h ) 解决开放式v r p ( o v r p ：o p e n v e h i c l er o u t i n gp r o b l e m ) 。在此之前的 b r a n d a o ( 2 0 0 4 ) 1 2 7 j 用t s 解决o v r p 。 c o l o r n i ，d o r i g o 和m a n i e z o ( 1 9 9 1 ) p s l 使用蚁群算法解决配送优化问题，可 能是最早利用蚁群寻找食物的过程原理解决v r p 问题的鼻祖。b u l l n h e i m e r ，h a r t l 和s t r a u s s ( 1 9 9 7 ) p 9 1 用改进的蚁群算法求解v r p ，其算法的主要思想是：每一 只蚂蚁通过连续的寻找下一结点来建立一条行驶路线，当所有结点遍历完毕，该 蚂蚁结束本次循环。蚂蚁主要根据其车辆的载重容量限制并结合各个可选结点的 路径与信息素综合概率来选择下一个结点。当每一只蚂蚁在走到下一结点后，即 对刚才所走过的路径进行局部信息素的更新。当全部蚂蚁结束一次循环后，从中 找出最优的蚂蚁，对其走过的每一条边进行全局信息素的更新，初始蚂蚁群的分 布：分布在各个结点上，而本文采用了与其不同的初始蚁群分布方式和信息素的 更新方式，具体见第2 章。m a z z e o 和l o i s e a u ( 2 0 0 4 ) 3 0 】用蚁群算法解决c v r p 。 k a r led o e m e r 等人( 2 0 0 4 ) 3 1j 把并行的a s 运用于求解c v r p ，文章分析了运 用于c v r p 问题的三个主要蚂蚁优化算法：r a n kb a s e da s 、m m a s 和a c s ，然 后提出一种并行计算策略来提高计算效率，发现在提高解的质量方面，r a n k b a s e d a s 和m m a s 优于a c s ，而m m a s 略优于r a n kb a s e d a s ，可见在运用蚂 蚁算法进行c v r p 问题的求解中，m m a s 的效果最好。2 0 0 6 年澳大利亚阿德莱 德大学的a a r o nc z e c c h i n 等人【3 2 】将m m a s 用于水配给问题的求解并用实验数 据证明m m a s 较a c 优。这些均是本文直接采用m m a s 进行算法设计和求解计 算的主要原因和重要依据。 最近，f u e l l e r e r 和d o e m e r 等( 2 0 0 7 ) 3 3 】又发展到使用蚁群算法全局优化二 维装载与v r p 相结合的综合问题。 ( 3 ) 多车场v r p 的研究现状 gl a p o r t e 等( 1 9 8 4 ，1 9 8 8 ) 3 4 1 1 3 5 1 发展了用于解决多种m d v r p 的精确式算 法：分支定界法，但其特点是仅能解决部分小规模的问题。 关于启发式算法求解m d v r p ，早期的研究多为构造算法和其改进算法，如 f a t i l l m a n 和t m c a i n ( 1 9 7 2 ) 、w r e n 和h o l l i d a y ( 1 9 7 2 ) 【3 6 】、r a f t 等( 1 9 8 2 ) 3 7 】；近期的有c h a o 等( 1 9 9 3 ) 3 8 1 提出了一种结合了d u e c k 【3 9 1 的r e c o r d t o - r e c o r d 4 山东大学硕士学位论文 局部法的搜索过程，将客户点重新分配给不同的车辆线路，然后用2 - o p t 法改进 每个单独的车辆线路；r e n a u d 等( 1 9 9 6 ) 4 0 】用禁忌搜索解决m d v r p ，过程是 将客户分配给距离其最近的车场作为初始解，利用4 o p t 的子集来优化每条线路， 交换线路同车场或非同车场内的客户点，或者是三条线路间客户点的交换。 c o r d e a u 等( 1 9 9 7 ) 4 1 】用改进的禁忌搜索算法解决m d v r p 时，同样是首先将客 户分配给距离其最近的车场作为初始解，各车场的v r p 的求解采用扫描算法， 改进之处是：将客户点转移到同车场的另一条线路中，或者将一个客户重新放置 到另外一个车场当中。再次插入点时，采用了g e n i 4 2 】算法，这种启发算法的主 要特点是：搜索过程中，非可行解也被允许存在，这种持续的多样化是由对频繁 移动的惩罚实现的。b e n o i tc r e v i e r 等( 2 0 0 7 ) 【4 3 】扩展了一种新的带有中途补给 的m d v r p 模型：( m d v r p i ：m u l t i d e p o tv e h i c l er o u t i n gp r o b l e mw i t hi n t e r - d e p o t r o u t e s ) ，同样使用了禁忌搜索及其改进算法，在此不再赘述。 2 0 0 7 年香港理工大学和阿斯顿大学的w i l l i a mh o ，g e o r g et s h o ，p i n gj i 等 人畔】使用两种混合遗传算法求解m d v r p 。 p o l a c e k ( 2 0 0 4 ) 等人采用变动邻域搜索【4 5 】( v n s ：v a r i a b l en e i g h b o r h o o d s e a r c h ) 解决带有时间窗的多车场v r p ( m d v r p t w ) 。该文章第一次将v n s 用于解决m d v r p ，结果表明，其v n s 算法在解的质量和计算机时两方面均比 现今的禁忌搜索算法更优。 b l h o l l i s 等( 2 0 0 6 ) 【4 6 】用通过使用列生成法( c o l u m ng e n e r a t i o n ) 求解 m d v r p 模型解决澳洲邮局的车辆路线安排和人员工作排程的实际问题。该实际 问题的模型具有时间窗的约束、而且同时具有集货和送货两种情况( v i 心p b ) ； 同时用三种不同的集覆盖方式进行建模；利用三组实际的数据进行了计算，最后 得出三种建模方式以及求解算法对路线求解结果的影响，在实际应用背景下，其 优化结果为澳洲邮局年节约成本量达1 0 。 1 。2 2 国内研究现状 ( 1 ) v r p 的国内研究现状 国内学者早期的研究多集中于对目前用于解决v r p 的各种启发式算法的改 进，比如节约算法、遗传算法等。如：李军( 1 9 9 6 ) 4 7 1 用节约算法实现了有时 山东大学硕士学位论文 间窗的车辆路径安排；李军等人( 2 0 0 0 ) 4 8 】使用自然数编码的遗传算法求解非 满载车辆调度问题；檀庭方( 2 0 0 7 ) 4 9 】在传统遗传算法的基础上，加入自适应 算子，并引入了免疫算法的思想，实验结果表明该算法具有更好的全局和局部搜 索能力和收敛速度。 另外，将近年发展起来的群智能算法及其与其它启发算法或思想结合求解各 类v i 冲成为国内主要的研究方向。吴曙莉等( 2 0 0 4 ) 5 0 1 将遗传算法和禁忌搜索 算法的混合策略应用于求解有时间窗的车辆路径问题。 林国玺等( 2 0 0 6 ) 5 1 1 提出将模拟退火算法中的m e t r o p o l i s 接受准则引入到遗 传算法的群体更新策略中，将其应用于c v r p t w 。郝会霞等( 2 0 0 7 ) 1 5 2 1 使用改 进的粒子群算法( p s o ：p a r t i c l es w a r mo p t i m i z a t i o na l g o r i t h m ) 求解经典v r p 问题，并将其改进的p s o 的实验结果与标准g a 、基本p s o 相比，具有较好的 全局收敛性。 崔雪丽等( 2 0 0 4 ) 5 3 】利用蚂蚁搜索算法求解了经典的v r p ，同类的研究还 有沈矗( 2 0 0 6 ) 5 4 1 等；吴建军、刘军( 2 0 0 4 ) 【5 5 】利用蚁群算法产生基本可行解， 然后再利用遗传算法进行二次优化，以求得问题最优解；同类的文献还有胡卉等 ( 2 0 0 6 ) 1 5 6 】。王则林等( 2 0 0 6 ) 【5 7 】使用最近邻居选择、信息素动态更新和局部 启发搜索法对m m a s 算法进行优化，此算法运用于解c v r p 问题时，取得了较 好的效果。关于m m a s 求解v i 冲相关问题的还有万旭等( 2 0 0 5 ) 【5 8 】使用改进 m m a s 在求解c v r p t w 。 ( 2 ) 多车场v r p 的国内研究现状 洪联系等( 2 0 0 7 ) 5 9 1 提出了一种用于求解带有时间窗的多车场v i 冲问题的 聚类和迭代混合遗传算法。该算法采用三阶段过程：客户聚类分配、路径规划和 路径改进；该算法采用混合遗传算法进行路径规划，竞争一插入进行路径改进， 且路径规划与路径改进有机结合形成迭代路径规划过程，c o r d e a u 标准算例的运 算表明其算法能够在可以接受的计算时间内得到可接受的较好解。 迄今关于m d v r p 的文献中，几乎所有的多车场问题都转化为单车场来处 理，即对每个车场首先确定它所服务的任务。但是这种启发式算法并没有把各个 车场以一个整体来考虑，而只是以一定的方法来划分各个车场的管辖范围，因此， 很难得到整体最少费用。钟石泉等人( 2 0 0 5 ) 6 0 1 在研究m d v s p 时，提出了两种 6 山东大学硕士学位论文 所谓智能算法解决多车场车辆调度问题：一种是设置虚拟车场，把各个配送点和 实际车场都看作虚拟车场的配送点，然后让所有的配送车辆都从这个虚拟车场出 发，去各个配送点完成配送任务，虚拟车场到实际车场的过程中是零费用，从虚 拟车场发出的车辆，只能先到达实际车场，然后再去完成配送任务，完成任务后 再回到实际车场，另一种方法是让各个车场同时选择配送点，强制让第一个点为 车场，达到约束限制之后再插入一个车场，且车场的插入必须成对。这两种方法 从根本上说也相当于转化为单车场求解，但这两种方法可以用一条路径表达多个 车场的配送任务，从多车场的整体进行优化。本文将采用最大最小蚂蚁系统 ( m m a s ：m a x - m i na n ts y s t e m ) 构建一种启发式算法一阶段求解m d v r p ，不 将客户先分派给某个车场，具体见第三章。 辛达( 2 0 0 6 ) 6 h 采用蚁群算法来解决m d v s p 问题，同时结合分解法和整体 法给出了蚁群算法解决多配送中心车辆调度问题的算法模型和实现过程，其对于 多车场的处理，同样采用了虚拟车场的思想。 1 3 本文内容安排 课题的核心内容是采用最大一最小蚂蚁系统对c v r p 和m d v r p 进行了算法设 计，并对实际应用案例进行了求解。本文所采用的案例，来自实际企业物流配送 网络规划工程项目。使用所设计的m m a s 算法求解了应用背景下两种配送网络模 式下的路线规划结果，并对两种模式进行了比较和选择。其间，利用c v r p 模型 对“一级配、一级送”配送网络模式进行了模拟和运算，利用m d v r p 模型对“一 级配、两级送 配送网络模式进行了模拟和运算，经m a t l a b 程序的设计和实验， 得到了较为满意的结果，解决了配送网络规划的实际目的。 过程中，采用真实交通路网作为数据基础，同时区别对待各等级公路进行费 用的计算，通过目标函数为费用最低来优化求解得到反映现实运营情况的路线方 案。 具体的章节安排如下： 第一章阐述了课题的意义和c v r p 与m d v r p 在国内外的研究现状； 第二章介绍了相关原理、模型和方法； 第三章是m m a s 求解c v r p 与如v r p 的算法设计； 7 山东大学硕士学位论文 第四章介绍了案例所在的应用背景和需求、解决思路和步骤；以及具体求解 过程、求解结果和网络运营模式的选择； 第五章是结论与展望，内容是论文在算法设计和实际应用两方面的主要创新 和意义，同时提出了下一步研究的方向。 8 山东大学硕士学位论文 第2 章模型与算法 2 1 两种配送网络模式 货品自生产者到消费者( 客户) 的实物流动过程，是商品流通的重要内容之 一。如图2 1 所示：上游供应商或生产厂直接或间接生产的产品，一般需经由区 域配送中心( r d c ：r e g i o n a ld i s t r i b u t i o nc e n t e r ) 进行商品的收货、检验、仓储、 拣选和分拣活动，根据实际需要，r d c 再将处理完毕的货品按照一定的顺序将 其运送到前端配送中心( f d c ：f r o n td i s t r i b u t i o nc e n t e r ) 进行暂存，再由f d c 向其辖区中转站( c d ：c r o s sd o c k i n g ) 进行配送。在某些行业的供应链中，c d 有可能是某些更低级别的中转中心，也有可能企业客户。 上游供应商 区域配送中心 前端配送中心 客户 图2 - 1 物流网络流动示意图 物流网络规划设计就是确定产品从供货点到需求点流动的结构，包括决定使 用什么样的结点、结点的数量、结点的位置、如何给各结点分派产品和客户、结 点之间应使用什么样的运输服务，以及如何进行服务【6 2 】。 作为c d ，其货品的来源，可能直接来源于r d c ，也可能是f d c ，这将取 决于整个干线配送网络的运作模式。换句话说，对于销售型企业来讲，其配送网 络中是否应设置f d c 进行二级中转? 这就存在模式选择的问题。“一级配、一级 送 模式( d s d ：d i r e c ts t o r ed e l i v e r y ) 是指，r d c 直接负责辖区c d 的干线配 送，如图2 2 所示；“一级配、两级送 模式( t w d - t r a n s i tw a r e h o u s ed e l i v e r y ) 是指，r d c 先将货品送至f d c ，由f d c 再向部分c d 进行配送，如图2 3 所示。 9 山东大学硕士学位论文 图2 - 2d s d 模式下的配送关系图2 - 3t w d 模式下的配送关系 模式选择的主要影响因素，一是c d 的地理分布位于r d c 经济配送里程； 二是c d 需求量的与车辆额定载重的差别情况所导致的装载率。如图2 _ 4 所示： 圆圈表示c d ，圈内数字表示该c d 的货品需求量，车辆装载能力为1 5 吨。在 d s d 模式下，r d c 负责直送所有c d ，而地理上与r d c 相距较远的c d 点，将 耗费较多的单车日工作时长，若采用最大里程约束，将增加所使用车辆数；若采 用t w d 模式，距离r d c 较远的部分c d 将由f d c 负责进行配送。是否存在f d c 中转，是由具体问题中的网络节点分布的特殊性决定的。 图2 - 4 两种配送网络模式下的某物流节点网络 对于配送中心和客户的数量和位置已经确定的实例当中，d s d 模式下的物 流网络规划可抽象成c v r p ( c a p a c i t a t e dv e h i c l er o u t i n gp r o b l e m ) 模型；t w d 模式下的物流网路规划可抽象成m d v r p ( m u l t i d e p o t v e h i c l er o u t i n gp r o b l e m ) 。 通过分别对这两种v r p 模型的求解得到每个r d c 两种模式下的运输成本，经过 对比后作出决策，同时得到各r d c 的送货路线和车辆使用，以及各配送车辆的 工作时段。 1 0 山东大学硕士学位论文 2 2 车辆路径问题 2 2 1 有容量限制的v r p 模型 车辆路径问题是提出之初是用于解决大型汽油存储中心与大量加油站之间 的运输车队线路安排的实际问题。通常在v r p 问题中，在客户网络里，已知待服 务的客户和出发点的位置、车辆的最大负荷和客户需求的前提下，设计车辆路径， 使运输成本最小化。 c v r p 可以描述为：连通有向图g = 缈，4 ) ；顶点集y = 轧，1 ，) ；边集 彳= 如，j ) ：哆，v 矿，icj ；顶点，。代表配送中心或者车场，圪= ， 代表 个客户点。与弧集相关的是一个运输费用矩阵c 【( + 1 ) ，( + 0 1 ，其中y ，与v ，之 间的运输费用是c 妒。如果这个矩阵均是对称的，则定义在g = 缈，彳) 上的v r p ， 可以用边集e = 如。，v j ) ：1 ，1 ，j y ，f q ，) 。车辆的数目既可以是事 先给定的，也可以是决策变量。目的是求得至多为必条配送或者集货线路，使 得运输成本最低。 c v r p 的数学模型为： 决策变量： 如果边g ，油车辆瑚艮务 否则 如果客户点v ，由车辆明艮务 否则 置 l 。耐= r a i n 勺x ； k = lt e v ，矿 s j r 巧k = 1 j e vk = l ，圪) c 叮 f ，歹 么，k = 1 ，k ) ( 2 1 ) ( v i 屹，k = l ，k ) ( 2 2 ) ( 2 - 3 ) ( 2 - 4 ) 器暴瞰 = = 标 苟 矿 目 山东大学硕士学位论文 x ；= y ； 似圪，k = l ，k ) 旭矿 x ；= y ； f 圪，七= 1 ，k ) j e 矿 ( v f k ) x ； g 。) 的车辆k 。辆。费用矩阵 c 【( + 竹) ，( + 膨) 】记录矿中_ 与_ 之间的费用系数c l ，。 1 2 l = 七，y r 蹦 k 一o 砖 成 譬料 = o 峨 鬈蹦 山东大学硕士学位论文 m d v r p 的数学模型为： 决策变量： x 严= 0 喜盖的车辆七从客户q 到客户巧 目标函数： ( 2 - 1 1 ) ( 2 - 1 2 ) s t nx 等：n m k 1 v me + 1 ，+ 2 ，+ m ) ，尼 1 ，2 ，k 。) ( 2 - 1 3 ) v i l ，2 ，n v j l ，2 ，n ( 2 - 1 4 ) ( 2 - 1 5 ) n+ m g ，x - q m e + 1 ，n + 2 ，n + m , ke 1 ，2 ，k m ( 2 1 6 ) i = l j - n + m x 茄：n + m x 筹： + 1 ， ，m 1 “2 一k 。)(2170 v m en + 2 n + m , k e k1 7 ) x 茄= x 筹= + 1 ， ， 1 “一。) ( 一 v m + 1 ，n + 2 ，+ 肘 ( 2 1 8 ) x l s l - xv s 圪，i s j 2 ，m 圪，k 1 ，2 ，k 。) ( 2 1 9 f ，j e s 其中，公式( 2 - 1 2 ) 为总运输成本最低的目标函数；公式( 2 1 3 ) 表示每辆 车均须从各自车场出发并回到原车场；公式( 2 1 4 ) 和( 2 1 5 ) 表示每个客户能 且只能被一辆车服务一次；公式( 2 - 1 6 ) 定义了车辆的容量限制；公式( 2 1 7 ) 表示车辆不能够从车场到车场；式( 2 - 1 8 ) 各车场派出车辆的数目不能超过该车 场所拥有的车辆数；公式( 2 - 1 9 ) 是防止求解线路结果中出现独立的闭环。 磅勺 k 黼m 删 一 m 脚 mm i i 耐聪 = 兮 岛黼 一 闩 = 砖 k 料 一 曲 肿 k 一 础哪 x b 腻 一 山东大学硕士学位论文 2 3 最大最小蚂蚁系统佟3 】 蚁群优化算法是一种结合了分布式计算、正反馈机制和贪婪式搜索的算法， 具有很强的搜索较优解的能力。正反馈能够快速地发现较优解，分布式计算避免 了早熟收敛，而贪婪式搜索有助于在搜索过程中早期找出可接受的解决方案，缩 短了搜索时间。可以不通过个体之间直接通信而是通过信息素进行合作，这样的 系统具有更好的可扩充性。由于随着系统中个体增加而增加的系统通信开销在这 里将非常小。而最大最小蚂蚁系统是对普通蚁群的改进，且是目前国际上公认的 用于解决v r p 问题效果最好算法，因此本文采用m m a s 进行算法设计。 2 3 1 生物界的蚂蚁觅食行为 觅食行为是蚁群一个重要而有趣的行为。据昆虫学家的观察和研究发现，蚂 蚁有能力在没有认识可见