（交通运输规划与管理专业论文）物流配送车辆调度优化研究.pdf

武汉理工大学硕士学位论文 摘要 物流配送是物流活动中直接与消费者相连的环节。在物流的各项成本中，配 送成本占了相当高的比例。配送车辆调度的合理与否对配送速度、成本、效益 影响很大，特别是多用户配送车辆调度的确定更为复杂。采用科学、合理的方 法来进行配送车辆调度，是物流配送中非常重要的一项活动。因此，车辆调度 问题( v e h i c l es c h e d u l i n g p r o b l e m ，简记v s p ) 成为众多学者竟相研究的热门话题。 在高度发展的商业社会中，特别是随着i n t e m e t 的普及和电子商务的发展，消费 者对时间的要求越来越严格，以往的到货“日”已转换成到货“时”。 v s p 是一个典型的n p 难题，高效的精确算法存在的可能性不大，启发式 算法虽能快速求解大型问题，但对解的质量没有保证。近些年来，人们在用遗 传算法解决现实中的各种组合优化问题上进行了探索，如在生产调度问题中的 应用，但在车辆调度问题中的应用才m , n , j 开始。有专家断言遗传算法是用来解 决n p 完全问题和n p 难题的趋势。 本论文主要对有时间窗的非满载v s p 和供应商管理库存( v e n d o rm a n a g e d i n v e n t o r y ，简记v m i ) 管理思想下的v s p 进行了研究。 对于有时间窗的非满载v s p 问题，将货运量约束和时间窗约束转化为目标 约束，建立了v s p 模型，使用最大保留交叉、交叉率和变异率的自适应调整等 技术，设计了给予自然数编码的可同时处理软、硬时间窗约束的遗传算法，实 验分析取得了较好的结果。本论文丰富了遗传算法在组合优化中的应用，为继 续深入研究v s p 、j o b s h o p 和物流配送车辆调度优化的计算机实现等打下基 础。 对于v m i 下的v s p 问题，可以看作上述v s p 的问题的延伸。本文分析了 v m i 对于供应链物流配送系统优化的作用。在v m i 管理方式下，存在库存和配 送运输可以集成起来进一步优化配送系统成本这一实际情况。接着对此问题建 立了数学模型和迭代优化算法，实例证明该模型和算法能够起到较好的效果。 武汉理工大学硕士学位论文 物流配送车辆调度优化，是物流配送优化中关键的一环，也是电子商务活 动不可缺少的内容。对货运车辆进行调度优化，可以提高物流经济效益、实现 物流科学化。对货运车辆调度优化理论与方法进行系统研究是物流集约化发展、 建立现代调度指挥系统、发展智能交通运输系统和开展电子商务的基础。目前， 问题的形式已有很大发展，该问题以不仅仅局限于汽车运输领域，在水运、 航空、通讯、电力、工业管理、计算机应用等领域也有一定的应用，其算法 已用于航空乘务员轮班安排、轮船公司运送货物经过港口与货物安排的优化 设计、交通车线路安排、生产系统中的计划与控制等多种组合优化问题。 关键宇：物流配送，车辆调度，遗传算法，时间窗，v m i 武汉理工大学硕士学位论文 a b s t r a c t l o g i s t i cd i s t r i b u t i o ni s a no p e r a t i o nl i n k i n gw i t hc o n s u m e rd i r e c t l y ，a n dt a k e s a c c o u n tf o rc o n s i d e r a b l ep r o p o r t i o ni nv a r i a b l ec o s t si nl o g i s t i c s t h ep l a n n i n go f v e h i c l es c h e d u l i n gi nd i s t r i b u t i o nw i l lb et a k eg r e a te f f e c to nt h ee f f i c i e n c y ，c o s t ，a n d b e n e f i t ，e s p e c i a l l yi nd i s t r i b u t i n g f o rm u l t ic o n s u i n e r s as c i e n t i f i ca n dr e a s o n a b l e m e t l l o dt ov e h i c l e s c h e d u l i n gi s a n i m p o r t a n to p e r a t i o n i n l o g i s t i c d i s t r i b u t i o n s o ，v e h i c l es c h e d u l i n gp r o b l e mh a db e c o m ef o c u so fm a n ys c h o l a r st os t u d y i nt h e d e v e l o p e dc o m m e r c i a ls o c i e t y 。w i t hp o p u l a r i z a t i o n o fi n t e r a c ta n d d e v e l o p m e n t o f e l e c t r o n i cc o n l i i l e r c i , ，r e q u i r e m e n to fc o m s u m e rf o rd e l i v e r yt i m ei sh i g h e ra n dh i g h e r s ot h a td e l i v e r yd a y f o r m e r l yh a d t u r nt od e l i v e r yh o u rn o w v s pi sat y p i c a ls t r o n gn p h a r dp r o b l e m ，h i g he f f e c t i v ee x a c ta l g o r i t h mi s i m m p o s i b l e t oi t h e u r i s t i ca l g o r i t h mc a nr e s o l v el a r g e s c a l ep r o b l e m ，b u tc a n n o t e n s u r et h eq u a l i t yo ft h er e s o l u t i o n r e c e n t l y , g e n e t i ca l g o r i t h mh a sb e e nt y i e dt o r e s o l v ev a r i a b l ec o m b i n a t o r i a l o p t i m i z a t i o np r o b l e m s ，s u c h 鹊j o bs c h e d u l i n g p r o b l e m ，b u t b u th a s b e g a nj u s t n o wi nv s es o m ep e o p l ea s s e r t t h a t g e n e t i c a l g o r i t h m h a st e n d e dt on p h a d p r o b l e m t h i sp a p e ra t t e m p t st ot a k ev s pw i t ht i m ew i n d o wa n dv s pi nv l v l ia st h et o w c o r ep m b l e m sf o rf u r t h e rr e s e a r c h 。 o nt h ev s p w i t l lt i m ew i n d o w , w h i l et h er e s t r a i n t so f c a p a c i t ya n d t i m ew i n d o w s a r ec h a n g e di n t oo b j e c tr e s t r a i n t s ，am a t h e m a t i cm o d e l i se s t a b l i s h e d w eu s et e c h n i q u e s u c ha sm a x i m u m p r e s e r v e dc r o s s o v e ra n ds e l f a d a p t a b i l i t yc h a n g eo fp r o b a b i l i t yo f c r o s s o v e ra n dm u t a t i o n , a n dd e s i g ng e n e t i ca l g o r i t h mo nn a t u r en u m b e r , w h i c hc a l l d e a lw i t hs o f ta n dh a r dt i m ew i n d o w s t h ee x c e l l e n ts o l u t i o n sa r eo b r a i n e di n t h e a p p l i c a t i o n v s pi nv m im a yb el o o k e da st h es t r e t c ho ft h ev s p a b o v e o nt h ev s pi n v m i ，t h i sp a p e ra n a l y s e st h ec o n t r i b u t i o no f t h eo p t i m i z a t i o no fl o g i s t i cd i s t r i b u t i o n s s y s t e m b e i n ga i m e da tl o o k i n g f o rt h eo p t i m a ld i s t r i b u t i o np o l i c y , t h i sp a p e rp u t d e l i v e r yr o u t i n g a n di n v e n t o r yi n t oc o n s i d e r a t i o nj o i n t l y , a n db r i n g s f o r w a r da l l m a t h e m a t i cm o d e la n di t s a l g o r i t h m c o n s e q u e n t l y , r e s u l t sf r o mt h ec a s ep r o v e dt h e a v a i l a b i l i t yo ft h em o d e l a n di t sa l g o r i t h m i l l 武汉理工大学硕士学位论文 _ _ _ 一_ _ _ _ _ _ _ - _ _ _ _ _ _ _ - _ _ 一 v s pi sb o t h a p i v o t a l t a c b ei n l o g i s t i c d i s t r i b u t i o n o p t i m i z a t i o n a n d i n d i s p e n s a b l ei n e l e c t r o n i cc o l n l y l e r c e i tc a ni n c r e a s el o g i s t i ce c o n o m i cb e n e f i ta n d r e a l i z el o g i s t i cr a t i o n a l i z a t i o n t h es y s t e m i cs t u d yo nt h et h e o r ya n dm e t h o do fv s p i s t h eb a s eo nt h eg r o w t ho fl o g i s t i ci n t e n s i v i s m ，t h ee s t a b h s h m e n to fm o d e m c h a i no f c o m m a n d ，t h ed e v e l o p m e n to fi t s a n de c n o w , t h e p r o b l e m i sn o to n l ya p p l i e dt ot h e f i e l do fa u t ot r a n s p o r t a t i o n b u ta l s ot os h i p 、a v i g a t i o n 、c 0 衄u i l i c a t i o n 、e l e c t r i c i t y 、 i n d u s t r ym a n a g e m e n t 、c o m p u t e ra p p l i c a t i o n e t c t h ea l g n f i t h mh a sb e e n a p p l i e di n t o m a n yc o m b i n a t o r i a lo p t i m i z a t i o np r o b l e m ss u c ha st h et r a i n m a n ss h i f ta r r a n g e m e n t i na v i g a t i o n 、t h e o p t i m i z a t i o nd e s i g no f c a r g oa r r a n g e m e n t i ns h i pc o m p a n y 、t r a f f i c r o u t i n ga r r a n g e m e n t 、a n d t h e p l a n a n dc o n t r o li nt h ep r o d u c t i o n s y s t e m k e yw o r d s ：l o g i s t i cd i s t r i b u t i o n ，v e h i c l es c h e d u l i n gp r o b l e m ，g e n e t i ca l g o r i t h m ，t i m e w i n d o w s ，v m i 武汉理工大学硕士学位论文 1 1 研究背景 第1 章概述 在物流配送系统中，物流配送中心的成立可有效的简化配送程序与减少配 送的频率，以m 个供应商和n 个零售商为例，传统的配送模式是假设n 个零售 商的需求都是由m 个供应商自行配送，则一共有m n 次的运送，如图l 一1 所示。 假设零售商与供应商之间通过一个物流配送中心来配送，则只需m + n 次配送， 如图1 2 所示，如此一来即可减少( m x i l ，( m + ) ) 的配送次数，当供应商与零售 商数目越多，节省的配送次数也就会越多。 而物流配送中心作业的重点是如何将车辆有效的使用并决定其最经济的行 驶路线图，使商品能在最短的时间内送到顾客的手中。国外将此类问题称之为 车辆优化调度问题( v e h i c l es c h e d u l i n gp r o b l e m ) ，简称为v s p 问题。目前有关 v s p 的研究，多致力于单一车种或多车种优化调度问题，很少涉及结合时间窗 口的v s p 问题。所谓时间窗口是指配送车辆或顾客希望服务或被服务的时间范 围。由于消费者需求趋于多样化，对送货时间的要求日趋严格，尤其是运送有 时效性的商品，例如海产品、花卉、蔬菜等讲究新鲜度的货物，除了因缺货造 成的机会成本的损失外，由于配送不及时也会造成货物价值的大大降低。因此， 在配送运输上，时间因素显得越来越重要。 有时间窗的v s p 问题也称为v s p t w ( v e h i c l e s c h e d u l i n g p r o b l e mw i t h 面m e w i n d o w s ) ，根据时间约束的严格与否，分为软时间窗和硬时间窗的v s p 。由于 有时间窗的v s p 是典型的n p 难题，会随着节点的增加出现组合爆炸的现象， 因此求解的困难度及时效性会有影响，然而遗传算法具有随机与多点搜寻特性， 求解时不易陷入局部最优解，因此应用遗传算法求解v s p t w 问题是一种有效的 途径。 目前国外发达国家从实际上和理论上都认识到供应商管理库存( v m i ) 对于 整体供应链物流系统巨大优化作用，在v i v i i 管理方式下。存在库存和配送运输 可以集成起来进一步优化配送系统成本这一实际情况，对于v m i 下的v s p 也有 研究的必要。 1 2 论文研究的目的和意义 武汉理工大学硕士学位论文 本论文研究的目的为： ( 1 ) 构建以配送成本最小与顾客满意度最大为目标的车辆优化调度模型。 ( 2 ) 利用遗传算法的原理和其在组合优化方面的优点，为物流配送车辆调 度问题的求解提供一个切实可行的算法，求得一个较优的可行解，并说明其有 效性。 ( 3 ) 对v m i 下的v s p 问题进行初步研究，将运输成本与库存成本综合起 来考虑。 意义为：物流配送车辆调度优化，是物流配送优化中关键的一环，也是电 子商务活动不可缺少的内容。对货运车辆进行路径优化，可以提高物流经济效 益、实现物流科学化。对货运车辆路径优化理论与方法进行系统研究是物流集 约化发展、建立现代调度指挥系统、发展智能交通运输系统和开展电子商务的 基础。 近些年来，人们在用遗传算法解决现实中的各种组合优化问题上进行了探 索，如在生产调度问题中的应用，但在车辆路径问题中的应用才刚刚开始。有 专家断言遗传算法是用来解决n p 完全问题和n p 难题的趋势。本文丰富了遗传 算法在组合优化中的应用，为继续深入研究v s p 、j o b s h o p 和物流配送车辆 调度优化的计算机实现等打下基础。 1 3 物流配送v s p 的研究动态和水平 1 3 1 问题的提出 物流配送车辆优化调度问题最早是由d a n t z i g 和r a m s e r 于1 9 5 9 年首次 提出，自此，很快引起运筹学、应用数学、组合数学、图论与网络分析、物 流科学、计算机应用等学科的专家与运输计划制定者和管理者的极大重视， 成为运筹学与组合优化领域的前沿与研究热点问题。各学科专家对该问题进 行了大量的理论研究及实验分析，取得了很大的进展。 该问题一般定义为：对一系列装货点或卸货点，组织适当的行车线路，使 车辆有序的通过它们，再满足一定的约束条件( 如货物需求量、发送量、交发 货时间、车辆容量限制等) 下，达到一定的目标( 如路程最短、费用最少、使 用车辆尽量少等) 。 2 武汉理工大学硕士学位论文 国外对物流配送车辆调度问题作了大量而深入的研究，例如早在1 9 8 3 年 b o d i n 、g o l d e n 等人在他们的综述文章中就列举了7 0 0 余篇文献。在 c h r i s t o f i d e s ( 1 9 8 5 ) ，g o l d e n 和a s s a d ( 1 9 8 8 ) 编辑的论文集，以及a l t i n k e r n e r 和 g a v i s h ( 1 9 9 1 ) ，l a p o r t e ( 1 9 9 2 ) ，s a l h i ( 1 9 9 3 ) 等的综述文章中都进行了详尽的阐述。 该领域的代表人物有o d i n ，c h r i s t o f i d e s ，g o l d e n , a s s a d ，b a l l ，l a p o r t e ，r i n n o o y k a n ，i _ n s t r a ，d e s r o s i e r s 和d e s r o c h e r s 等人。 目前，问题的形式已有很大发展，该问题以不仅仅局限于汽车运输领域， 在水运、航空、通讯、电力、工业管理、计算机应用等领域也有一定的应用， 其算法已用于航空乘务员轮班安排、轮船公司运送货物经过港口与货物安排 的优化设计、交通车线路安排、生产系统中的计划与控制等多种组合优化问 题。 供应商( s ) 零售商( r ) 图卜l 传统的物流配送模式 武汉理工大学硕士学位论文 供应商( s )零售商( r ) 图1 - 2 以物流为中心的配送模式 国内对v s p 的研究相当少，主要研究对象是旅行商问题( t r a v e l i n g s a l e s m a np r o b l e m ，简称t s p ) 、中国邮递员问题( c h i n e s ep o s t m a np r o b l e m ， 简称c p p ) 、有向中国邮递员问题( d i r e c t e dc h i n e s ep o s t m a np r o b l e m ，简称 d c p p ) 等，系统性研究还尚未见到。李大为等( 1 9 9 8 ) 以t s p 的最近距离启 发式为基础，通过设置评价函数来处理时间窗约束，求解了简单的v s p 。张 鹱( 1 9 9 5 ) 针对单车场满载问题，提出了考虑运输行程约束的优化方法。遗 传算法和神经网络方法对简单t s p 的求解取得了一定成果。蔡延光等( 1 9 9 8 ) 应用并行表搜索法和模拟退火法针对简单情形对满载问题进行了求解。 对于v m i 下的综合考虑库存成本和运输成本的v s p 的问题，一些学者正 从理论上进行探索，往往将实际问题进行简化，用近似方法进行处理。 1 3 2v s p 问题的解法回顾 针对早期与现今的车辆配送问题模型，已有相当多的文献提出求解方法， 可分为以下四大 ( 一) 系统仿真法( s i m u l a t i o n ) 此方法最早由g o l d e n 和s k i s c i m 于1 9 8 6 年提出，主要应用于行车线路与物 4 武汉理工大学硕士学位论文 流中心区位的选择，优点在于可直接观察系统安排的效率与效果，但由于问题 的实际情况多变且具有不确定性，是否能将实际的配送情形系统逻辑化为仿真程 序，往往另人质疑。 ( 二) 人机互动法 此方法结合人类决策与计算机计算能力，在求解的过程中，通过高度的人 机交互模式，结合专家的决策信息，并据以计算出结果：优点是寻优的过程中， 决策者可以很清楚地看到各约束条件之间的替代关系，以及参数变化可能导致 的成本变化。 ( 三) 精确解法( e x a c tp m c e d u r e s ) 精确解法将车辆配送问题，通过严谨的数学模型或计算机数据结构规划， 利用数学法则或数据结构搜寻的方式，求得问题的解。由于两种方法都在所有 可行解集合( f e a s i b l es o l u t i o ns e t ) 寻找最优解，所以所求的解均为最优解。随 着变量的增加，车辆配送问题的解集合会有组合爆炸( c o m b i n a t o r i a le x p l o s i o n ) 的现象，求解时间也呈指数函数的趋势增长，不能在有限的时间( p o l y n o m i a l t i m e ) 给予决策者一个可行解，是这种方法最大的缺点。常见的精确解法有动 态规划法( d y n a m i cp r o g r a m m i n g ) 、分枝定界法( b r a n c h a n db o u n d ) 与切平面 法( c u t t i n g p l a n e s ) ，详细内容分述如下： ( 1 ) 动态规划法( d y n a m i cp r o g r a m m i n g ) 此方法的核心观念为最佳化原理，其运用数学逻辑来处理一连串相互关连 的决策问题，并采取系统化步骤以求得以整体最有利的策略。求解方法与步骤 如下所述： 步骤一：将整个问题分解为许多相互关联的局部问题，以便个别分析处理。 步骤二：从最后一个阶段的各种状态中，找出最有利的决策方案。 步骤三：利用“反策推算法”，自最后一个阶段逐步向前项阶段推进，直到 各阶段的最有利策略均找出为止。 h e l d 和k a r p 运用此法于求解巡回推销员问题，因其计算时间与计算机内 存空间均随变量的增加而呈指数增加，所以虽然此方法可求得最优解，但仅适 用于规模较小的问题。 ( 2 1 分枝定界法( b r a n c ha n db o u n d ) 此方法是组合优化问题的有效求解方法，其步骤如下所述： 步骤一：如果问题的目标为最小化，则设定目前最优解的值z ，。 武汉理工大学硕士学位论文 步骤二：根据分枝法则( b r a n c h i n gr u l e ) ，从尚未被洞悉( f a t h o m e d ) 节点 ( 局部解) 中选择一个节点，并在此节点的下一阶层中分为几个新的节点。 步骤三：计算每一个新分技出来的节点的下限值( l o w e rb o u n d ；l b ) 步骤四：对每一节点进行洞悉条件测试，若节点满足以下任意一个条件， 则此节点可洞悉而不再被考虑： 此节点的下限值大于等于z 值。 已找到在此节点中，具最小下限值的可行解；若此条件成立，则需比较 此可行解与z 值，若前者较小，则需更新z 值，燕以此为可行解的值。 此节点不可能包含可行解。 步骤五：判断是否仍有尚未被洞悉的节点，如果有，则进行步骤二，如果 已无尚未被洞悉的节点，则演算停止，并得到最优解。 k o l e na ta 1 曾利用此方法求解含时间窗约束的车辆巡回问题，其实验的节 点数范围为6 - 1 5 。当节点数为6 时，计算机演算所花费的时间大约1 分钟( 计 算机型为v a z l l h 8 5 ) ，当节点数扩大至1 2 时，计算机有内存不足的现象产生， 所以分枝定界法比较适用于求解小型问题。h e l d 和k a r p 指出分枝定界法的求解 效率，与其界限设定的宽紧有极大的关系。 ( 3 ) 切平面法( c u t t i n gp l a n e s ) 此方法与分枝界限法类似，也是在求解与整数规划相对应的线性规划上， 不断地增加新的约束，也就是另外加入线性约束条件，以切掉对应于非整数规 划的所有可行解的集合，以使问题可达到整数线性规划求解的形式，从而获得 最优解。 上述三种精确解法的优点在于可求得最优解，缺点在于求解时间过长。 ( 四) 启发式算法( h e u r i s t i c s ) 由于上述三种方法的求解效率较差，所以大部分的学者都致力于启发式解 法的发展。该方法在解题时可减少搜寻的次数，所以是一种容易且快速求解困 难问题的算法。s o l o m o n 曾提出数个时间窗约束车辆巡回问题的启发式解法，包 括节省法( s a v i n gm e t h o d ) 、最邻近法( n e a r e s tn e i g h b o r ) 、插入法( i n s e r t i o n ) 及扫描法( s w e e p i n g ) 。由于上述各解法起初都用于求解v s p 问题，如果应用于 求解v r p t w 问题时，则在求解过程中必须增加时闻可行性的检验的目的在于 确保配送行程能满足顾客的时间窗的要求；所以当顾客被排入路径时，需检验 该排入时点是否违反该顾客与其后影响的时间窗的限制。以下针对各启发式解 武汉理1 大学硕士学位论文 法进行探讨。 ( 1 ) 节省法 c l a r k e w r i g h t 于1 9 6 4 年提出该方法以求解车辆巡回问题，其思想在于按 节省值( 较短路径与原路径之差) 由大至小排序，在车辆容量限制下，依序将 对应的两顾客点排入路径中，直至所有顾客都被排入路径为止。s o l o m o n 于1 9 8 3 年将此法应用于求解时间窗约束的车辆巡回问题，关键在于当节省值较大的两 顾客点被排入路径时，除需考虑车辆容量限制外，更需要考虑到时间窗的限制， 也就是时间窗上界较早者，应优先被配送，并检验其时间可行性，此方法的优 点是提高车辆的利用率，而两节点间的节省值的计算公式与意义如下所示： s ( f ，j ) 一d ( f ，0 ) + 4 0 ，) 一d ( f ，) 其中d ( f ，o ) 代表顾客f 至场站的距离，d ( f ，) 则代表顾客f 至，的距离。计算 两节点f 与f 间的节省值j ( f ，f ) 时，应先计算原路径中各往返路径的总和，再以之 与较短路的总路径和相比较：两节点的原路径与较短路如图2 5 所示。 原路径较短路径 图1 3 节省法的图示 ( 2 ) 最邻近法 s o l o m o n 于1 9 8 3 年所提出的求解的v s p t w 的方法，该方法的思想如下所 述：出配送中心开始搜寻，若i 为离配送中心最邻近的节点( c 。最小) 则其优先 排入路径中，接着搜寻另一节点，以排入路径的下一位，且该节点加入后必须满 足以下条件，满足者称为可排入点； 1 之前尚被排入路径的节点 2 c 。最小者 3 车辆载量限制与时窗限制的时间可行性 7 武汉理工大学硕士学位论文 若其它尚未排入路径的节点中皆无法找到可排入点，则构造另一新路径， 直到所有顾客点都被排入所有路径为止。而决定节点是否为最邻近点的要素有 以下三点： 1 两顾客节点间的距离d ；， 2 两顾客节点间的运输时间t 。 3 配送下顾客时所需等待服务的时间c 在决定两节点间的最邻近法总成本时，场站应先评估对些三要素的权重组 合，且总和应为1 ，所以最邻近法总成本的计算公式如下所示： 。口一6 1 d f + c $ 2 t f + 6 3 u 其中6 l + 6 2 + 6 3t 1 且6 ，、6 ：、以为场站对该三要素的权重组合。 ( 3 ) 插入法 插入法原本是m o l e 和j a m e s o n 于1 9 7 6 年所提出，用于求解v s p 问题的方 法，其结合最邻近法与节省法的观念，依序将顾客点插入路径中以构建配送路 线。s o l o m o n 于1 9 8 3 年将此方法应用于求解v s p t w 问题，因为时间因素加入， 而使原问题的顾客的等待时间缩短。此方法包含二个步骤： 步骤1 ：选取距离配送中心最远的顾客点为起点，从其它剩余的顾客点中， 根据最邻近法决定下一个被插入的顾客点。 步骤2 ：以节省法决定该顾客点应被插入的位置，在车辆容量限制下，重复 进行选取与插入的步骤，当无法再扩大充路径时，则再建立另一路线，直至所 有顾客都被排入路径中。 ( 4 ) 扫描法 g i l l e t t 和m i l l e r 于1 9 7 4 年所提出的求解v s p 问题的方法，此方法属于先分 群再排路线的方式，此方法分为两阶段： 第一阶段：利用极坐标来表示各需求点的区位，然后任取一需求点为起点， 以车辆容量为分群的约束，再以该需求点为零度按顺时针或逆时针的方向，进 行顾客的扫描分群。 第二阶段：依据求解旅行商问题的算法，求解各顾客群的排程。 s o l o m o n 于1 9 8 3 年将此方法应用于求解v s p t w 问题，与原扫描法不同点 在于第二阶段的求解各顾客群排程，其以插入法进行各顾客群的排程，并检查 时间可行性若有顾客点无法满足时闻窗的约束，则先排除此顾客点。若所有 武汉理工大学硕士学位论文 的顾客群都以排入行程，则所有的顾客点都已被服服务，则完成路线的建构； 若有顾客点尚未被服务，则沿原扫描方向，将剩余的尚未服务的顾客点重复进 行扫描与插入的步骤，直到所有的顾客点都被服务。 综合上述四种启发法，求解时间窗限制车辆调度问题的关键在于掌握配送 时间与空间，并在时间可行性检验下有效解决车辆行使路线问题、行程问题与 装载问题。本文将上述的四大类求解时间窗约束的车辆调度方法的优缺点，整 理如表1 - 1 所示： 表1 - 1v s p t w 求解方法的优缺点 算法优点缺点 系统仿真可直接观察系统安装的效率与可能无法满足实际多变的配 法效果送环境 1 可适时地结合专家的意见1 相关的专门知识不易获得 人机互动 2 寻优的过程中，使用者可以很并整合 清楚地看到各限制条件之间的2 决策时间较长，虽然效果不 法 替代关系，以及参数变化可能错，但效率较差 导致的成本变化 1 受计算机内存容量的限制 精确解法可求得最优解 2 求解效率差 启发式算1 解题时可减少搜寻的次数无法确保求得最优，可能为 法2 可快速的求解困难的问题较优的可行解 1 3 3 本文的研究范围与假设 由于有时间窗约束的车辆调度问题所牵涉的因素相当多，本研究仅针对具 有普遍性的物流中心予以探讨，就研究范围与假设界定如下： ( 1 ) 仅考虑区位已知的单一物流配送中心和供应商 ( 2 ) 物流配送中心无缺货的可能，且商品种类单一 ( 3 ) 物流配送中心对顾客的基本配送资料( 需求量、地理位置、时间窗约 束等) 为已知 ( 4 ) 物流配送中心拥有一定数量同类车( 多辆) 的配送车辆，且每辆车的 载重量一定 9 武汉理工大学硕士学位论文 1 4 论文的主要工作 本文的主要内容包括： ( 1 ) 介绍了论文的研究背景和动机、研究目的和意义、国内外发展动态和 水平等。 ( 2 ) 阐述了物流配送的概念和业务流程，v s p 的相关概述等。 ( 3 ) 介绍了遗传算法的基本步骤和处理流程、遗传算法的特点、适应度函 数、基因操作及其控制参数等。 ( 4 ) 兼顾顾客对配送时间的要求，建立了比较切合实际的物流配送中心配 送车辆行驶路径优化模型。其中采用遗传算法作为主要优化方法，并证明了其 有效性。 ( 5 ) 分析了v m i 对于供应链物流配送系统优化的作用，将库存和运输结合 起来考虑，接着对此问题建立了数学模型和迭代优化算法，实例证明该模型和 算法能够起到较好的效果。 1 0 武汉理工大学硕士学位论文 第2 章物流配送及其v s p 随着社会主义市场经济的发展，作为“第三利润源泉”的物流对经济活动 的影响日益明显，越来越引起起人们的重视，成为当前“最重要的竞争领域”， 未来的市场竞争，物流将起着举重轻重的作用。 2 1 配送的概念 按照国家质量技术监督局发布的中华人民共和国国家标准“物流术语”，其 中关于配送的解释是这样的：在经济合理区域内，根据用户的要求，对物品进 行拣选、加工、包装、分割、组配等作业，并按时送达指定地点的物流活动。 一般来说，配送一定是根据用户的要求，在物流据点内进行分拣、配货等工作， 并将配好的货物适时的送交收货人的过程。它是物流中一种特殊的、综合的活 动形式。它将商流与物流紧密结合起来，包含了商流活动，也包含了物流活动 中若干功能要素。 2 2 配送功能要素 ( 一) 备货 备货是配送的准备工作或基础工作，备货工作包括筹集货源、定货或购货、 集货、进货及有关的质量检查、结算、交接等。配送的优势之一，就是可以集 中用户的需求进行一定规模的备货。备货是决定配送成败的初期工作，如果备 货成本太高，会大大降低配送的效益。 ( 二) 储存 配送中的储存有储备及暂存两种形态。 配送储备是按一定时期的配送经营要求形成的对配送的资源保证。这种类 型的储备数量较大，储备结构也比较完善，示货源及到货情况，可以有计划的 确定周转储备及保险储各结构及数量。配送的储备保证有时在配送中心附近单 独设库解决。 另一种储存形态是暂存，是具体执行日配送时，按分拣、配货要求，在理 货场地所做的少量储存准备。由于总体储存效益取决于储存总量，所以这部分 武汉理工大学硕士学位论文 暂存数量只会对工作方便与否造成影响，而不会影响储存的总效益，因而在数 量上控制并不严格。 还有一种形式的暂存，即是分拣、配货后，形成的发送货载的暂存，这个 暂存主要是调节配货与送货的节奏，暂存时间不长。 电子商务的发展，新的物流配送模式的出现，储存已不是必然的环节。 ( 三) 分拣及配货 分拣和配货是配送不同于其他物流形式及特点的功能要素，也是关系配送 成败的一项重要支持性工作。分拣及配货是完善送货、支持送货的准备性工作， 是不同配送企业在送货时进行竞争和提高自身经济效益的必然延伸，所以，也 可以说是送货向高级形式发展的必然要求。有了分拣及配货就会大大提高送货 服务水平，所以，分拣及配货是决定整个配送系统水平的关键因素。 ( 四) 配装 在单个用户配送数量不能达到车辆的有效载运负荷时，就存在如何集中不 同用户的配送货物，进行搭配装载以充分利用运能、运力的问题，这就需要配 装。 和一般送货不同之处在于，通过配装送货可以大大提高送货水平及降低配送 成本，所以，配装也是配送系统中有现代特点的功能要素，也是现代配送不同 于以往送货的重要区别之处。 ( 五) 配送运输 配送运输属于运输中的末端运输、支线运输，和一般运输形态主要区别在 于：配送运输是较短距离、较小规模、频度较高的运输形式，一般使用汽车做 运输工具。 与干线运输的另一个区别是，配送运输的路线选择问题是一般干线运输所 没有的，干线运输的干线是唯一的运输线，而配送运输由于配送用户多，一般 城市交通路线又较复杂，如何组成最佳路线，如何使配装和路线有效搭配等， 是配送运输的特点，也是难度较大的工作。配送线路合理与否对配送速度、成 本、效益影响很大。 ( 六) 送达服务 配好的货运输到用户还不算配送工作的完结，这是因为送达货和用户接货 往往还会出现不协调，使配送前功尽弃。因此，要圆满地实现运到之货的移交， 并有效地、方便地处理相关手续并完成结算，还应讲究卸货地点、卸货方式等。 武汉理：【：大学硕士学位论文 送达服务也是配送独具的特殊性。 ( 七) 配送加工 在配送中，配送加工这一功能要素并不具备普遍性，但往往是具有重要作 用的功能要素。主要原因是通过配送加工，可以大大提高用户的满意程度。 配送加工是流通加工的一种，但配送加工有它不同于一般流通加工的特点， 即配送加工一般只取决于用户的要求，其加工的目的较为单一。 2 3 配送的一般流程 配送的一般流程比较规范，但并不是所有的配送都按上述流程进行。不同产 品的配送可能有独特之处，如原料油配送就不存在配货、分放、配装工序，水 泥及木材配送又多出了一些流通加工的过程，而流通加工又可能在不同环节出 现。 2 4 物流配送的v s p 随着物流配送集约化、一体化的发展，常将配送的各环节综合起来，核心部 分为配送车辆的集货、货物配装及送货过程。进行配送系统优化，主要就是配 送车辆优化调度，包括集货线路优化、货物配装及送货线路优化以及集货、 货物配装和送货一体化优化。在国外，类似的工作已广泛地运用于生产、生活 的各个方面，如报纸投递及线路的优化、牛奶配送及送达线路的优化、电话预 定货物的车辆载货和线路设计、垃圾车的线路优化及垃圾站选纸优化、连锁商 店的送货及线路优化等等。 v s p 被提出后，l i n u s ( 1 9 8 1 ) ，b o d i n ，和g o l d e n ( 1 9 8 1 ) ，b o d i n ( 1 9 8 3 ) ，a s s d a ( 1 9 8 8 ) ，d e s r o c h e r s ，l e n s t r a 和s a v e l s b e r g h ( 1 9 9 0 ) 等许多学者对v s p 从不同角 度，按不同的标准进行了分类。 按任务特征分，有纯装问题或纯卸问题( p u r ep i c ku po rp u r ed e l i v e r y 车辆所有任务点装货或卸货，及集货或送货问题) 及装卸混合问题( c o m b i n e d p i c ku pa n dd e l i v e r y ，每项任务有不同的装货点和卸货点，即集货、送货一 体化问题) 。 武汉理工大学硕士学位论文 第3 章遗传算法基本理论 3 1 遗传算法的基本原理 遗传算法是一类借鉴生物界自然选择和自然遗传机制的随机搜索算法，它 由美国h o l l a n d 教授首先在自然结合人工智能系统的适应性一书中提出， 是利用生物进化的特性所发展的方法，由一群群体( p o p u l a t i o n ) 以随机配对 产生下一代，利用交叉( c r o s s o v e r ) 及变异( m u t a t i o n ) 等操作进行基因的进 化并经由选择( s e l e c t i o n ) 机能决定下一代相对的个数，使适应度越大的 解存活的机会越大；也就是“适者生存”的原则来选择随机的值域，最后留下 的就是最优解。 3 1 1 遗传算法的特点 同传统的寻优算法相比，遗传算法具有一下特点： ( 1 ) 算法对问题参数的代码集起作用，而不是对参数本身起作用。遗传算 法处理的对象是染色体，因而要求把所要优化问题的基本参数转化成定长度的 有限符号的染色体。 ( 2 ) 遗传算法是从初始群体开始搜索的，而不是从单点开始搜索的。许多 传统优化方法都是从搜索空间的单点出发，通过某些转换规则确定下一点。这 种点到点的搜索方法在多峰值优化问题中，容易误入局部最优解。遗传算法是 以点集开始的寻优过程，初始群体是随机地在搜索空间中选取的，覆盖面大， 利于全局寻优。 ( 3 ) 遗传算法在求解时只使用适应度函数的信息，而不使用导数及其他辅 助信息。对于不同类型的优化问题，传统方法需要使用不同形式的辅助信息， 没有一种优化方法能适应各类问题的要求。遗传算法在优化过程中放弃使用 这些辅助信息，具有广泛适应性。 ( 4 ) 算法具有极强的容错能力。 遗传算法的初始种群本身就带有大量与最优解甚远的信息，通过选择、交 叉、变异操作能迅速排除与最优解相差极大的染色体。 武汉理工大学硕士学位论文 ( 5 ) 算法具有隐含的并行性。 g o l d e b e r g 对g a 的处理并行性进行了合理的分析，指出了g a 对模式的处理效率 是d n3 ) ，h o l l a n d 称之为g a 的“隐式并行性”。 ( 6 ) 遗传算法中的选择、交叉、和变异都是随机操作，而不是确定的精确 规则。复制体现了向最优解的逼近，交叉体现了最优解的产生，变异体现了全