（管理科学与工程专业论文）物流配送车辆路径问题模型及算法研究.pdf

博上学位论文 摘要 物流企业为了节约成本和保护环境，必须将先进的物流理论和物流技术引入 企业的生产和经营管理中，作为实现物流合理化的重要内容和手段，研究车辆路 径问题有助于企业降低物流成本、提高运作效率、提高客户满意度。车辆路径问 题将运筹学理论与管理实践紧密地结合在一起，是近半个世纪以来运筹学领域最 成功的研究之一。以往对车辆路径问题的研究都是将前向物流和逆向物流中的车 辆路径问题分开考虑，而实际中的企业或客户为了节约成本和保护环境需将两者 结合起来运作。本文研究几类物流配送车辆路径问题的模型和算法，在分析其理 论和实践背景的基础上，提出其数学模型，并构造了几种有效的亚启发式算法求 解相关问题。其中同时送货和取货车辆路径问题有效整合了前向物流和逆向物流 的车辆路径问题，本文在不确定性信息条件下，研究了同时送货和取货车辆路径 问题的三种特殊情形，建立了相关的不确定性模型，给出了求解算法，并用数值 实验检验了模型和算法的有效性。本文的主要研究内容和创新成果如下： ( 1 ) 基于改进差分进化算法的同时送货和取货车辆路径问题研究 现有的车辆路径问题的模型不能完全描述同时送货和取货车辆路径问题的特 征，提出同时送货和取货车辆路径问题的整数规划数学模型；同时运用改进差分 进化算法求解该问题；并用数值实验检验该算法的有效性。 ( 2 ) 基于改进遗传算法的带时间窗的同时送货和取货问题研究 首次提出并建立了带时间窗的同时送货和取货车辆路径问题( v i 冲一s d p t w ) 的混合整数规划数学模型，可以将其转换为其它经典的车辆路径问题，同时采用 改进遗传算法( i g a ) 求解该问题，数值实验结果表明该算法可以有效地求解 v r p s d p t w 。 ( 3 ) 基于复合最优模型微粒群算法的车辆数目不确定的带时间窗的车辆路径 问题研究 车辆数目不确定的带时间窗的车辆路径问题是带时间窗的同时送货和取货车 辆路径问题的一种特殊情形，运用复合最优模型的微粒群算法求解该问题，并用 数值实验检验该算法的有效性，同时与遗传算法、分派算法等启发式算法进行比 4 4 牧o ( 4 ) 多车型随机需求车辆路径问题研究 在客户需求为随机条件下，研究具有多种车型、每种车型有多辆车的车辆路 径问题，提出该问题的随机规划数学模型，在客户服务不可分割的前提下，研究 了区别于重新优化策略的预优化策略，并分析了预优化策略的渐近性，结果表明 物流配送车辆路径问题模型及算法研究 预优化策略可以在节约大量计算资源的前提下能获得该问题的高质量解，并以预 回路的期望成本作为目标函数，分别设计了改进的遗传算法和差分进化算法求解 该问题，通过大量数值实验验证了算法的有效性。 ( 5 ) 模糊需求车辆路径问题研究 模糊需求车辆路径问题是对传统的确定性车辆路径问题的拓展。在引入决策 者主观偏好概念的基础上，对于基于模糊可能性的模糊机会约束规划模型，提出 了一种基于随机模拟的混合遗传算法；对于基于模糊可信性的模糊机会约束规划 模型，提出了一种基于随机模拟的混合差分进化算法。同时，分别在两种混合算 法中，采用随机模拟的数值实验研究了决策者主观偏好值对最终决策目标的影响， 在最小化总行驶距离的目标下，得出了运用上述两种混合算法时的决策者的主观 偏好值的最佳取值范围。 关键词：逆向物流；车辆路径问题；不确定性；随机性；模糊性；遗传算法；差 分进化算法；随机模拟 博l j 学位论文 a b s t r a c t w i mt h ei n c r e a s i n gf o c u so ne n v i r o m e n t a lp r o t e c t i o na n dc o s td e c r e a s e ，m a n y e n t e r p r i s e sr e a l i z et h a tl o 西s t i c si sa ni m p o r t a l l tm e a s u r et oi m p r o v et h ea b i l i t yo f m a r k e tc o m p e t i t i o n ，a l l da d v a n c e d1 0 9 i s t i c a lt h e o r ya i l dl o 百s t i c a l t e c h n i cs h o u l db e u s e dn e c e s s a r i l yi nm a n u f a c t u r a t i o na n dm a n a g e m e n t a sa ni m p o r t a n ta p p r o a c ht o r e a l i z el o 西s t i cr a t i o n a l i z a t i o n ， r e s e a r c ho nv e h i c l er o u t i n gp r o b l e m sw i l lh e l p e i l t e r p r i s e st or e d u c e1 0 百s t i c a lc o s t ，i m p r o v eo p e r a t i o ne f ! e i c i e n c y ， a n de n h a n c e c u s t o m e rs a t i s f a c t i o nc o m p r e h e n s i v e l y s i n c ev e h i c l er o u t i n gp r o b l e m st i 曲t l yc o 衄e c t t h e o r yo fo p e r a t i o nr e s e a r c hw i t hp r a c t i c eo fm a n a g e i l l e n t ，w h i c hw a sn 锄e d a so n e o ft h em o s ts u c c e s s 如1a r e a si no p e r a t i o nr e s e a r c hi nt h ep a s th a l fc e n t u r y i i lt h e c l a s s i c a lv e h i c l er o u t i n gp r o b l e m s ，t h er e l a t i o n so fv e h i c l er o u t i n gp r o b l e m sb e t 、) l ，e 饥 f o n a r da 1 1 dr e v e r e s el o 西s t i c si ss 印a r a t e ，b u ti nm a n yd i s t r i b u t i o r e d i s t r i b u t i o n s y s t e m s ，o p e r a t i n gt h ef o r w a r da i l dr e v e r s ec h a n n e ls 印a r a t e l ym a yr e s u l ti n 觚 u n n e c e s s a 巧 v e h i c l eu t i l i z a t i o n ， a j l d e 1 1 t e 叩r i s e s o rc u s t o m e r sh o p et oo p e r a t e s i m u l a n t e o u s l ym ef o r w a r da r l dr e v e r s el o 舀s t i c s f o rr e d u c i n gc o s ta n dp r o t e c t i n g e i l v i r o i 吼e n t w ec o n s i d e rt h em o d e l s锄da l g o r i t l l i i l s o fs o m ev e h i c l er o u t i n g p r o b l e m si nd i s t r i b u t i o n 1 0 昏s t i c s t h ev e h i c l er o u t i o n gp r o b l e mw i t hs i m u l t 锄e o u s d e l i v e wa i l dp i c k 。u p ( v r p s d p ) t h a te 矗e c t i v e l yi n t e 乒a t et l l ev e h i c l er o u t i n gp r o b l 锄 b e t w e e nf 0 九a r d1 0 百s t i c sa n dr e v c r s el o g i s t i c s ，w ep r e s e n ti t sm a t h e m a t i cm o d e l sb y 肌a l y z i n gi t st h e o r ya n dp r a c t i c a lc o n t e x t ， a n dc o n s t r u c ts e v e r a lm e t a l l e u r i s t i c s a l g o 订t h m st os 0 1 v et h er e l a t i v ep r o b l e m s a n dw ec o n s i d e rt l l r e es p e c i a lp r o b l e i t l s a b o u tv r p - s d pi nu n c e i r t a i n t ys i t u a t i o n ，w ea l s op r o p o s ec o r r e s p o n d m gu n c e n a i n t y m o d e l sa 1 1 dp r e s e n tr e l a t i v ea l g o t sf o rs 0 1 v i n gt h e s ep r o b l 锄s ，a tl a s tt h em o d e l s a n da lg o r i t h m sa r ec h e c k e db yt h en u m e r i c a le x p e r i m e n t a t i o n s t h em a i nc o n t e n t sa 1 1 d i n n o v a t i o n so ft h i sm e s i sa r eo u t l i n e da sf 0 1 1 0 w s ： ( 1 ) r e s e a r c ho nt h ev e h i c l er o u t i n gp r o b l 锄w i t hs i m u l t a l l e o u sd i v e r ) ra n dp i c k 。u p b a s e do ni m p r o v e dd i a j b 代n t i a le v 0 1 u t i o na l g o t h m t h ee x i s t i n gm o d e l sa b o u tv e h i c l er o u t i n gp r o b l e mc 觚n o td e s c r i b l et 1 1 e c h a r a c t e r i s t i co fv r p s d p w ep r o p o s et l l ei n t e g e rp r o 黟a m m i n gm o d e la b o u t v r p s d p ，a n da d o p ta i li m p r o v e dd i a e r e n t i a le v 0 1 u t i o n ( i d e ) t os o l v et h i sp r o b l 锄， t h en 啪e r i c a le x p e r i m e n t a t i o n ss h o wt h ev a l i d i t ya b o u tt h em o d e la n da l g o r i o t l l i l l ( 2 ) r e s e a r c ho nt h ev e h i c l er o u t i n gp r o b l e mw i t hs i m u l t a n e o u sd i v e r y a n d p i c k u pa n dt i m ew i n d o w s b a s e do ni m p r o v e dg e n e t i ca l g o r i t w ec o n s t m c tam i x e di n t e g e rp r o g r a m m i n gm a t h e m a t i cm o d e lo fv r p s d p t w 物流配送车辆路径问题模型及算法研究 i nd e t a i l ，i tc a nb et r a i l s f o 锄e di n t oo t h e rc l a s s i c a lv e h i c l er o u t i n gp r o b l e m sb ys e t t i n g d i f r e r e n tp a r 锄e t e r s a ni i n p r o v e dg e n e t i ca l g o r i t l u l l ( i g a ) i sp r o p o s e df o rs 0 1 v i n g t h i sp r o b l 锄，锄dm en u m e r i c a le x p e r i m e n t a t i o n ss h o wm ev a l i d i t ya b o u tm o d e la n d a l g o o t h l t l ( 3 ) r e s e a r c ho nv a r i a b l ef l e e tv e h i c l er o u t i n gp r o b l e mw i t ht i m ew i n d o w sb a s e d o nc o m p o u n do p t i m u mm o d e lp 砌i c l es w a 肋o p t i m i z a t i o n t h ev e h i c l er o u t i n gp r o b l e mw i t ht i m ew i n d o w su n d e ru n c e r t a i nv e h i c l en 啪b e r i sa i le s p e c i a lc a s ea b o u tv r p s d p t w w ep r o p o s ei t sm i x e di n t e g e rp r o 伊锄m i n g m a m e m a t i c a lm o d e l w ed e s i g nac o m p o u n do p t i m u l nm o d e l p a r t i c l es w 锄 o p t i m i z a t i o n ( c o m p s o ) a l g o t h mt os o l v et h i sp r o b l e m n u m e r i c a le x p e r i m e n t sa r e u s e dt oc o l n p a r et h ep e r f o m a n c eo ft h ep r o p o s e dm e m o dw i mg e n e t i ca l g o r i t h m ( g a ) a 1 1 da s s i 印m e n ta 1 9 0 r i t h m e x p 甜m e l l t a lr e s u l t si n d i c a t et h a tt h ec o m p s oi sb e t t e r m 锄t h eo t h e ra l g o r i m m s ( 4 ) r e s e a u r c ho nt h eh e t e r o g e n o u sf l e e tv e h i c l er o u t i n gp r o b l 锄w i t hs t o c h a s t i c d e m a n d w es t u d yt h eh e t e r o g e n o u sf l e e tv e h i c l er o u t i n gp r o b l 锄 ( h f v r p ) w i t h s t o c h a s t i cc u s t o m e rd e m a l l d w es u p p o s et l l a t 也ec u s t o m e r sd e m a n dc a nn o tb e d i v i d e d w ep r e s e l l tap r i o ro p t i m i z a t i o ns t r a t e g yd i 虢r e i l tf r o mr e o p t i m i z a t i o n ，a 1 1 d 锄a l y z eu p p e rb o u n d 、l o w e rb o u n da 1 1 d 嬲y m p t o t i cp r o p e r t yo f t h ep o l i c i e s a n db 嬲e d o nt o t a le x p e c t a t i o nc o s to fp r i o rt o u e r 舔o b je c t i v e 如n c t i o i l w ed e s i g ni m p r o v e d g e n e “ca l g o d m ma n dd i 丘e r e n t i a ie v o l u t i o na l g o r i t l l l l lt os o i v et h ep r o b l e m ，a n dt i l e m n e n c a le x p 耐m e n t a t i o n ss h o wm e v a l i d i t ya _ b o u tm o d e la n da l g o r i o t h m ( 5 ) r e s e a r c ho nv e l l i c l er o u t i n gp r o b l 锄w i t hi 记z yd e m a i l d s t h ec l a s s i cv e h i c l er o u t i n gp r o b l 锄i se x p a n d e dt ot h es i t u a t i o nt h a tc u s t o m e r s d e m a n di sf u z z y w bd e v e l o pa 向z z yc h a n c ec o n s t r a i n e dp r o g r a n l l i l i n gm o d e lb a s e do n f h z z yp o s s i b i l i t yt l l e o r e mb yi n t r o d u c i n gd e c i s i o n m a k e r sp r e f 钉e n c e 姐dt h el a t e s t t h e o r e mo fm z z ym a t h 啪a t i c s w ep r o p s eam i x e dg e n e t i ca l g o r i t h mt os o l v et l l i s p r o b l 锄b a s e do n 如z z ) rs i m u l a t i o n a n dw ep r o p o s eam i x e dd i 伍玎e n t i a le v o l u t i o n a l g o r i t h mt os o l v et l l e 向z z yc h a n c ec o n s t r a i n e dp r o 伊a m m i n gm o d e lb a s e do nm z z y c r e d i b i l i t y f i n a l l xt h ei n n u e n c eo ft h ed e c i s i o 啪a 1 ( c r sp r e f e r e n c eo nt h ef i n a l o b j e c t i v eo ft h ep r o b l e mi sd i s c u s s e du s i n gt h em e l m o do fs t o c h a s t i cs i m u l a t i o n ，a n d 廿l er a t i o n a l 啪g eo ft h ep r e f 醯e n c en u m b e ri so b t a i n c d k e yw o r d s ： r e v e r s e l o 百s t i c s ； v e h i c i er o u t i n gp r o b l e m ； u n c e r t a i n t y ； s t o c h a s t i c i n f o 肌a t i o n ；如z z yi n f o n n a t i o n ；g e n e t i ca l g o r i t h m ；d i f f e r e n t i a le v o l u t i o n ； s t o c h a s t i cs i m u l a t i o n v 物流配送车辆路径问题模型及算法研究 插图索引 图1 1v r p b 示意图3 图1 2v r p b m 示意图4 图1 3p d p 示意图5 图1 4v i 冲s d p 示意图5 图1 5 论文研究内容的结构关系2 5 图2 1经过2 0 0 次迭代后的运行结果3 5 图2 21 0 0 0 次迭代的随机实验运行结果3 6 图2 3算法比较结果3 6 图3 1标准遗传算法流程图4 2 图3 2 交叉操作5 0 图3 3互换操作5 0 图3 4 逆转操作5 1 图3 5 经过3 0 0 次迭代后的运行结果5 2 图3 6 经过5 0 0 次迭代后的运行结果5 2 图3 71 0 0 0 次迭代的随机实验运行结果5 4 图4 1微粒群算法流程图6 2 图4 2进化2 0 0 代的c o m p s o 运行结果7 1 图4 3 c o m p s o 优化【1 8 7 】中算例的计算结果7 2 图5 12 0 个客户时的i g a 进化结果8 5 图5 22 0 个客户时的i d e 进化结果8 5 图6 1随p 值变化的各类行驶距离变化趋势图9 5 图6 23 0 个客户时各类行驶距离随c ：值变化的趋势图1 0 2 图6 31 0 0 个客户时各类行驶距离随c ：值变化的趋势图1 0 3 博 ：学位论文 附表索引 表1 1 不同学者关于送货和取货问题的研究情况比较6 表1 2 车辆路径问题的分类9 表2 1 任务的特征及需求3 4 表2 2 配送中心与各客户之间的距离3 4 表2 3l o 次实验的平均计算结果3 5 表2 41 0 次随机实验的计算结果3 6 表3 1客户间及客户与配送中心的距离5 1 表3 2 任务的特征及需求5 2 表3 3 运行5 0 0 次的平均计算结果5 3 表3 41 0 次随机实验的计算结果5 4 表4 1客户间及客户与配送中心的距离7 0 表4 2 任务的特征及需求7 0 表4 3运行2 0 0 次的平均计算结果。7 0 表4 4 本文算法与其它优化算法的最好结果比较。7 l 表5 1i g a 和i d e 的参数设置8 4 表5 2改进遗传算法和改进差分进化算法计算结果。8 4 表6 1模型参数及改进遗传算法参数设置。9 4 表6 2 不同p 下的运行结果9 4 表6 33 0 个客户时模型参数及差分进化算法参数设置l o l 表6 43 0 个客户时不同c ：下的运行结果1 0 1 表6 51 0 0 个客户时模型参数及差分进化算法参数设置1 0 2 表6 61 0 0 个客户时不同c ：下的运行结果1 0 2 x 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取 得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何 其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献 的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法 律后果由本人承担。 佟着签名：麓7 ，2 7 ，缸 j 日期：胖月阳日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学 校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被 查阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编入 有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编 本学位论文。 本学位论文属于 l 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“”) 作者繇膨 导师签名： 网 篷p 溺； 、- _ _ - - 一 日期：蝣，月协日 日期：矿峰，月如日 夕平 博 ? 学位论文 1 1 选题背景及意义 第1 章绪论 本研究来源于国家“十五 重大攻关项目“小城镇现代流通业关键技术研究 与开发”【2 0 0 3 b a 8 0 8 a 1 3 】、国家“十五 科技攻关重大专项“奶业重大关键技术 研究与产业化技术集成示范”中的课题“区域内奶制品物流配送关键技术研究与 开发 2 0 0 2 b a 5 18 a 2 7 】以及国家科技支撑计划项目“现代村镇服务业关键技术研 究与示范”中的课题“村镇连锁经营与配送关键技术研究” 2 0 0 6 b a j 0 7 8 0 3 的研 究。上述课题需要解决的一个主要技术难点和关键点是设计物流配送管理需要的 车辆路径优化算法。本文是其中物流配送车辆路径优化算法理论研究的重要组成 部分。 随着社会主义市场经济的发展，作为“第三利润源泉”的物流对经济活动的 影响日益明显，越来越得到了人们的重视，成为当前“最重要的竞争领域”，未来 市场竞争，物流将起着举足轻重的作用，而配送是物流中一个重要的直接与消费 者相连的环节，物流术语n 】中对配送的定义为：在经济合理区域范围内，根据 用户要求对物品进行拣选、加工、包装、分割、组配等作业并按时送达指定地点 的物流活动。配送实际上个局部物流，是大物流在小范围内的整合，配送是物 流系统的终端，是直接面对服务对象的物流活动，配送功能完成的质量好坏极其 达到的服务水平，会直接影响到客户对整个物流服务的满意程度。配送的核心部 分是配送车辆的集货、货物分拣及送货过程，而车辆配送路径的合理优化，对于 整个物流运输速度、成本、效益影响至关重要。根据中国仓储协会对1 4 6 个企业 的调查显示，用于运输的费用占整个物流费用的比例分别为：在生产企业原料物 流中占5 8 ，在生产企业成品物流中占7 3 ，在商业物流中占5 2 。作为物流 系统优化中关键的一环，物流配送车辆路径问题( v e h i c l er o u t i n gp r o b l e m ，v r p ) 的研究受到了人们的广泛关注，各国学者对其理论和应用进行了大量的研究工作， 取得了许多研究成果，使v l 冲研究成为“最近半个世纪运筹学领域是成功的研究 一，【2 】 一 o “逆向物流 是物流过程的相反活动，是指为了重新获取产品的使用价值或 正确处理废弃产品，而将原材料、半成品、制成品及相关信息由供应链下游的消 费一端返回上游生产一端的过程。实际上逆向物流的工作在欧美发达国家己经卓 有成效。例如1 9 9 4 年，欧洲纸制品的回收量达到了2 7 7 百万吨，占整个纸制品 消费的4 3 ，且以每年7 的速度增长。欧洲玻璃的回收量达到7 百万吨，占整 物流配送车辆路径问题模型及算法研究 个玻璃产品消费总量的6 0 ，德国的商业包装材料的重复利用率达到6 0 7 5 ， 在荷兰，1 9 9 4 年有4 6 的工业废物被重复利用，这个数目还在增长。美国逆向物 流委员会的调查表明，2 0 0 3 年的美国逆向物流成本达到4 0 0 亿美元，从事再制造 的企业在美国有7 3 0 0 0 家，年销售额超过5 3 0 亿美元。而在我国，资源与产品的 重复利用工作还很滞后。矿产资源的总回收利用率为3 0 5 0 ，比世界平均水平 低1 0 2 0 ，单位产品能耗为世界平均水平的2 3 倍，主要用能产品单位能耗比 世界先进水平高4 0 ，每年可综合利用的固体废弃物和可利用的再生资源，没有 利用其价值的高达5 0 0 多亿元。我国工业中产品能源、原材料的消耗占企业生产 成本的7 5 左右，若降低1 则可以取得1 0 0 多亿元的效益【1 2 】。 许多企业认为物流是企业的第三利润源泉，而逆向物流也许是企业在降低成 本中的最后一块处女地，管理好逆向物流可以帮助企业提高物流效率，获得消费 者信赖，赢得市场份额。显然，西方发达国家在发展逆向物流、循环经济上已经 占得先机。我国发展循环经济，就必须重视发展逆向物流。在新的竞争形式下， 企业需把逆向物流提上日程，实施逆向物流战略，进一步挖掘“第三利润源泉”， 提高企业在新环境下的竞争能力。研究逆向物流，对于加强我国企业在物流方面 的竞争力，提高我国国民经济可持续发展的质量具有极其重要的现实意义。在逆 向物流中也涉及到很多复杂的规划问题，逆向物流的车辆路径问题( v e h i c l e r o u t i n gp r o b l 锄，v r p ) 即是其中最为突出的一个。基于前向物流和逆向物流的不 同关系，延伸出了许多不同种类的v r p ，如v i 冲b ( v e h i c l er o u t i n gp r o b l e mw i t h b a c l ( 1 l a u l s ) m 1 、v r p b m ( v e h i c l er o u t i n gp r o b l e mw i t hb a c k h a u l so fm i x e d l o a d s ) m 1 、p d p ( p i c k u pa n dd e l i v e r yp r o b l e m ) 阴0 1 等。 电子技术和信息技术的发展促进了物流业的发展，人工智能、数据通讯传输 技术、电子传感技术、电子控制技术和信息处理技术已广泛应用于物流领域，企 业迫切需要利用这些先进技术来开发先进的车辆路径系统。然而在以往的研究中 通常将前向物流和逆向物流分别加以考虑，这并不符合企业物流的实际情形，而 在现实的应用中受到一定的限制，因为在许多配送系统中，将前向物流和逆向物 流分开来单独考虑往往会导致一些不必要的浪费，而将两者结合起来考虑可以节 省成本和保护环境。另外，在许多实际情形中，客户可能会有同时的送货和回收 需求。此外，在许多国家颁布了环境保护的法律，企业必须对其生产的产品进行 回收处理，尤其是可能污染环境的产品，企业对其产品的使用和处理要负重要责 任( 如军工企业弹药筒的处理) h 1 1 。故将前向物流和逆向物流同时加以考虑，对企 业和社会都存在诸多的好处，这种v r p 被称为带同时送货和取货的车辆路径问 题( 、，c h i c l er o u t i n gp r o b l e mw i t hs i m u l t a n e o u sd e l i v e r ya n dp i c k u p ，v r p s d p ) ， v r p - s d p t w 问题则是客户根据自身的实际情况，为了节省人力资源和其它成本， 要求配送企业在一定的时间窗口内开始送货和取货任务，该问题有效考虑了配送 企业和客户的双向成本，更加符合实际情况。v r p s d p 需要考虑的参数比通常情 形下的车辆路径问题要复杂得多，是典型的n p 难题，因此需要研究和设计与之 2 博f j 学位论文 相对应的理论和方法。 1 2 物流配送车辆路径问题的研究动态 有关同时送货和取货车辆路径问题的研究比较少，但是存在着大量的有关送 货和取货车辆路径问题的研究，这些问题与同时送货和取货车辆路径问题存在着 理论联系，同时送货和取货车辆路径问题可以转化为其它经典的车辆路径问题。 为了不引起表述和理解的混乱，我们指出所谓送货、取货任务是相对于配送中心 ( 或配送企业) 而言，配送货物是指在配送中心将客户需要的货物装车，然后按 照每个客户的要求将货物送给客户，该服务过程相对于配送中心是送货任务 ( d e l i v e r v ) ：返回货物是指在每个客户处卸货后将配送中心需要带回的货物装车 送达配送中心，该服务过程相对于配送中心是取货任务( p i c k u p ) 。s a v e l s b e 咄和 s o l 【9 1 定义了广义送货和取货问题( g p d p ) ，并给出了相应的文献综述。与之关系 密切的是如下三种在每个客户非同时送货和取货的车辆路径问题： 若在配送时，车辆装满客户需要的货物从车场出发，先完成所有的送货任 务，然后再在其他客户处进行取货任务，最后返回车场，该问题要求所有的送货 任务都必须在取货任务之前完成。显然送货路线和取货路线是不同的，每条路径 可分为两部分，前面部分是纯配送货物路线，后面部分是纯回收货物路线，此种 配送问题是带回程的车辆路径问题( v c ：i l i c l er o u t i n gp r o b l e mw i t hb a c l ( 1 1 a u l s ， v i 冲b ) p 呻1 ，如图1 1 所示。当只需一辆车完成服务时，该问题就成为带回程的旅 行商问题( t r a v e i i n gs a l e s m a l lp r o b l e mw i t hb a c l 【h a u l s ，t s p b ) 阡m 】。g e i l d r e a u 等人 【1 5 1 6 1 用两阶段算法研究了只有一辆车情形( t s p b ) ；d e i f 和b o d i n p l 研究了v r p b ； g o l d e n 等人7 1 、c a s c o 等人【1 8 】、t o t h 和g o p l 以及m i n g o z z i 和g i o 哂1 9 】研究了 v i 冲b 的数学模型，并用精确算法求解了该问题；g e l i n a s 【2 0 】等人研究了带时间窗 的情形即v i 冲b t w ；d u h 锄e l 【2 l 】等人用禁忌搜索算法求解了如b t w 。 图1 1v l 冲b 示意图 其中圆圈代表送货点，三角形代表取货点，长方形代表配送中心，实线代表送货路线， 虚线代表取货路线，显然v i 冲b 要求先完成所有送货服务，然后再进行取货服务。 若在配送时，送货任务并不一定要先于取货任务，每条线路都是送货和取 货的混合情形，此种配送问题为混合送货和取货车辆路径问题( v 曲i c l er o u t i n g 物流配送车辆路径问题模型及算法研究 p r o b l e mw i t hb a c l ( h a u l so f m i x e dl o a d s v r p b m ) ，如图1 2 所示。g o l d e n 1 等人 运用插入启发式算法求解了v r p b m ，该算法将送货的客户插入到取货客户形成 的路径中，插入准则是考虑与插入某点后路径中的送货点数量有关的惩罚因子； m o s h e i o v u 副研究了只有一辆车服务的情形r t s p b m ) ，随后又研究了送货和取货都 是单位需求的特殊情形；a n i l y 和m o s h e i o v 叫运用最小分割树求解了t s p b m ； 近年来，s a l h i 和n a g y 睁改进了c a s c o u 引等人提出的插入启发式算法，通过允许 多个送货点同时插入到取货点形成的路径中，不再是单个点的插入，该改进的插 入启发式算法适当地改进了计算结果，但需花费更多的计算时间，同时指出该算 法也能求解同时送货和取货车辆路径问题。 图1 2v r p b m 示惹图 其中粗黑线代表送货和取货混合服务路线，其它图形代表的意义同图1 1 ，v l 冲b m 的送 货服务并不一定先于取货服务。 若在配送时，运输任务包括成对的取货点和送货点，取货点在送货点之前， 要求将取货点的货物运送到送货点，且每对取货和送货任务需同一辆车去完成， 一般任务量不大，一辆车可以同时完成几个任务。此种配送问题为取货和送货问 题( p i c k u pa n dd e l i v e wp r o b l 锄，p d p ) ，如图1 3 所示。特别的，当只需一辆车 就能完成服务时，该问题为招拨问题( d i a l - a r i d ep r o b l e i n ，d r p ) 。p d p 也可以考虑 最大距离约束和时间窗口约束，考虑的目标函数一般是最小化总的车辆数或总的 行驶距离。p s a u r a 衔s 等人阱2 3 j 运用动态规划算法求解了静态的p d p ，同时运用该 方法求解了时间窗口变化的动态p d p ；随后s e x t o n 等人【2 4 _ 2 6 1 ，d e s r o s i e r s 等人提 出了启发式算法求解时间窗口变化的p d p ；近年来v 缸d e r 等人【2 8 】提出了模拟退 火法求解该问题；m a d s e n 等人【2 9 1 运用平行插入启发式算法求解该问题：r o y 等 人【3 0 - 3 1 1 、j a w 等人【3 2 1 、d u m a s 等人3 3 1 运用启发式算法求解了更复杂的带时间窗 的多辆车的p d p 。 4 博十学位论文 图1 3p d p 示意图 图形代表的意义同上，在p d p 中，车辆先进行取货服务，再进行送货服务，取货点对应 的送货点总出现在其后。 同时送货和取货车辆路径问题最早由m i n h p 叫于1 9 8 9 年提出，但是随后近 1 0 年没有这方面的相关研究，直到本世纪人们开始重视逆向物流，并将逆向物流 看作是同时送货和取货的一种重要形式，许多学者才开始研究同时送货和取货车 辆路径问题。d e t h l o f f p m 结合逆向物流研究了同时送货和取货问题，提出了关于 v r p s d p 的数学模型，并用四种不同原则的插入法求解了该问题；s a l h i 【1 0 l 运用 四种插入启发式算法研究了该问题；近年来，根据求解经典车辆路径问题的方法， 一些学者提出了局部搜索算法求解该问题。t 觚g p 首先运用路径分割启发式算法 和扫描法求解了只有一辆车进行服务的t s p s d p ，然后求解了v r p s d p ； a n g e l e l l i 【3 引用分枝定界算法求解了冲s d p ；t a l l g 等人3 9 1 研究了同时送货和取 货车辆路径问题的数学模型，考虑了最大行驶距离约束，运用禁忌搜索算法求解 了该问题。 图1 4v i 冲s d p 示意图 v i 冲s d p 要求在每个服务点进行同时的送货和取货服务。 5 物流配送乍辆路径问题模型及算法研究 表1 1不同学者关于送货和取货问题的研究情况比较 问题规模 ( d 代表车场数目，r 代 作者( 时间)问题类型求解方法表路径条数( 若未知或 变化用 表示) ，c 代表客 户