（控制理论与控制工程专业论文）车辆路径问题的粒子群算法研究与应用.pdf

浙江工业大学博士学位论文 车辆路径问题的粒子群算法研究与应用 摘要 物流被称为“第三利润源泉”，越来越受到人们的关注，日益成为国民经济的 基础产业。运输是物流中的重要环节，占物流成本的6 0 以上。车辆路径问题主 要研究物流配送中车辆线路优化以降低运输成本。该问题是运筹学和组合优化领 域中的著名n p 问题，在航班调度、列车编组等众多领域都有应用。由于n p 问题 求解的复杂性，目前车辆路径问题的求解方法主要使用各种智能优化算法。本文 主要研究了以下四种模型的车辆路径问题：有能力约束的车辆路径问题，开放式 车辆路径问题，基于客户满意度的开放式车辆路径问题，开放式动态网络车辆路 径问题。研究了粒子群及其改进算法对上述模型的求解。具体的研究内容如下： ( 1 ) 首先介绍了论文的研究背景及意义，给出了车辆路径问题的定义，分 析了车辆路径问题的组成要素。然后在对国内外大量文献总结提炼的基础上，从 车辆路径问题的模型和求解算法两方面，深入分析了车辆路径问题的国内外研究 现状。 ( 2 ) 系统研究了基于粒子群算法的有能力约束车辆路径问题( c a p a c i t y v e h i c l er o u t i n gp r o b l e m ，c v r p ) 。提出了整数编码、实数编码两种求解c v r p 的 方法。在整数编码中，以交换数为基础，对粒子的速度重新定义，并对速度的加、 减等操作进行了定义，提出了“换位减”算子作为整数编码的速度计算方法；针 对整数编码算法存在的问题，提出了一种实数编码方法求解c v r p ，用实数的整数 部分表示客户所在的车辆，小数部分表示在该车辆中配送的次序，融合遗传算法 的思想，引入交叉算子以增加种群的多样性，详细讨论了粒子群算法的各个参数 对算法结果的影响为了与其他智能优化算法比较，研究了遗传算法、人工鱼群 算法在c v r p 中的应用。将双种群遗传算法用于c v r p 的求解；提出了人工鱼群 算法在c v r p 中的应用，针对车辆路径问题的特点，定义了鱼群的距离、领域等 概念，提出了人工鱼根据自身在鱼群中的排序，自适应选择移动算子的策略。 ( 3 ) 通过引入虚拟配送中心的概念，建立了开放式车辆路径问题的三下标 数学模型。提出了开放式车辆路径问题的粒子群求解方法，将最邻近插入，最远 要 插入、2 - o p t 、3 - o p t 等启发式算法作为再优化过程引入粒子群算法，通过这些启发 式算法调整线路内和线路间的客户来改进解，从理论上分析了这些算法的计算复 杂度。通过实验分析，找出合适的启发式算子，并和其他的算法进行了比较。 ( 4 ) 以客户满意度为首要优化目标，建立了基于客户满意度的开放式车辆 路径问题的数学模型，使用梯形模糊数表示客户满意度。综合考虑距离、等待时 间、客户的满意度等因素，定义了广义的距离和节约费用的概念，提出了改进的 最邻近法和最廉价插入法，将这两个算法作为初始化和改进算子结合粒子群算法 进行优化求解。分析了算法的复杂度，对算法的各个参数进行了讨论，通过实验 仿真对这几种方法进行了分析比较 ( 5 ) 动态网络车辆路径问题目前研究的热点和难点问题，将动态网络与开 放式两个因素结合起来研究车辆路径问题还未见报道。本文针建立了开放式动态 网络车辆路径问题的数学模型，提出了一种连续时间依赖函数模型。提出了自适 应惯性权重调整的粒子群算法，定义了粒子的“位置比”概念，充分利用粒子的 已有知识，动态的调整惯性权重。在算法中，引入公告板策略，根据粒子适应度 的高低分类更新粒子状态，对于优秀粒子使用一种新的状态更新公式，以使其跳 出局部极值点。对于适应度低的粒子，通过统计其在公告板中出现的频率，用新 的粒子替换以保持种群的多样性。通过实验讨论了算法的参数设置，对几种惯性 权重方案进行了分析比较，实验结果证明了算法的有效性 ( 6 ) 在上述理论工作的基础上，针对第三方物流在国内的迅速发展，而相 应的车辆调度软件功能不够完善，开发了智能车辆调度系统。该系统包括智能车 辆调度、承运单的管理、电子地图的显示等功能。该系统可以处理有时间窗、有 能力约束等多种情况的车辆调度问题，提供遗传算法、粒子群算法等多种优化算 法供用户使用。系统在杭州某物流公司应用，取得了良好的效果。 最后，对全文研究工作进行了总结，展望了车辆路径问题的模型和算法研究 的前景 关键词：车辆路径问题粒子群算法遗传算法人工鱼群算法客户满意度 开放式动态网络第三方物流组合优化 浙江工业大学博士学位论文 p a r t i c l es w a r m o p t i m i z a t i o nf o rv e l a i c l er o u t i n gp r o b l e m a n di t sa p p l i c a t i o n l o g i s t i c s ，w h l e hi s 陀铲r d e da s t h et h i r dp r o f i ts o i , i i ”，h 硒o b v i o u si m p a c to n e c o n o m i ca c t i v i t yo f t h ew o r l dd a yb yd a y , a n dc 勰p e o p l e sm o r ea n dm o r ea t t e n t i o n t o o t r a m p o r t a f i o na n dd e l i v e r yi st h ek e yp a r ti nt h el o g i s t i c s ，6 0 * , 4o fa l lt h el o g i s t i c s c o s t v e l a i e l er o u t i n gp r o b l e m ( v r p ) ，w l a i e l ai sr e s e a r c ho nh o wt op l a nt h ev e l a i e l e s r o i l t c si no l d e rt os a v et h e i t d l l l s p o l 倒o nc o s t , i st l a ew e l lk n o w nn pp r o b l e mi nt h ef i e l d o f o p 剃o r e s e a r e l aa n dc o m b i n a t i o no p t i m i z a t i o n i th a sb e e na p p l i e dt om a n yf i e l d s s u c h 翘n i 班s e h e c i 1 i n g ，i r a i n 伽鲫l i z i 唱 rh a v em a n ym o d e l sb e c a u s eo fi 乜m a n y e o , s t r a i n t 乳s ha l lc u s t o m , n e t w o r ka n dv e l a i e l et y p e f o rn pc o m p l e x i t y , t h e p o l y n o m i a lm e t h o dh a sn o tb e e nf o u n dn o w , s om o s tr e s e a r c h e r sc o n e e l m l l t eo nt h e r e s e a r c ho f h e u r i s t i cm e t h o d 1 kc i f l f l 删o l lm a i n l ys t u d i e df o u rv r pm o d e l s ：c a p a c i t yv e h i c l et o u l i n g p r o b l e m ( c 啦) ，0 | p e 虹v e l a i e l er o u t i n gp r o b l e m ( o 啦) ，t h ec u s i o m a s a t i s f a c t i o n v d a i e l er o u t i n gp r o b l e m ( c s v e d ) a n dt l a ct i m ed e l 瑚x d c l a tv e l a i e l er o u t i n gp r o b l e m f m v e a , ) t h em a i ne o n l r i b u t i o mo f t l a ep a p e r 锄a sf o l l o w s ： ( 1 ) f i r s tt h et 陀- s e a r e l ab a c k 伊叫n da n ds i g n i t i e a e eo ft h et h e s i si si n t r o d u c e d , a n d t h ed e f m i l i o no f v e l a i e l el p o u l j n gp r o b l e mi sg i 慨t h e c o m p o s i t i o nd e m e n t so f v e l a i e l e r o u t i n gp r o b l e mi sa n a l y z e d t h e nb a s e do ns t a i n i n gl l pa 姆n u m b e ro fd o m e s t i c a n df o l 呛i g nl i t e r a t m s u r v e yt l a es t a t u so fv e h i c l er o u t i n gp r o b l e md 。e p l yf r o mt h e m o d e la n da l g o r i t h m s 0 p e nv e l a i e l er o u t i n gp r o b l e ma n dt i m ed e p e n d e n tv e l a i e l e r o u t i n gp r o b l e ma sh o ti s s u e s 玳d i s c u s s e dd e t a i l e a t l y ( 2 ) mc v r pi sd e e p l ya n ds y s t e m a t i c a l l ys t u d i e db a s e do i lp a r t i c l es w a r m o p t i m i z a t i o n t w oe n c o d i n gm e t h o d s ：i n t e g e re n c o d i n ga n dr e a li l u m b e re n c o d i n ga p r e s e n t e d i nt h ei n t e g e rn u m b e re n c o d i n g , b a s e do n 恤 e x c h a n g en u m b e r ，t h e v d o e i t yo ft h ep a r t i c l e si sr e d e f i n e d , a n dv a l - i o u so p e r a t o ro fv e l o c i t yi sd e f i n e d 要 e x e l m g ei n i n u so p e 删i sc 0 1 1 8 1 1 u c i e dt oc o m p l l t cp a r t i c l e sv e l o c i t y i nt h er e a l n u m b e re n c o d i n g ，t h ev e l a i e l ei sm a p p e di n t ot h ei n t e g e rp a r to f t l a er e a ln u m b e r ；a n dt h e s e q u e n c eo fc u s t o m e r si nt h ev e h i c l ei sm a p r ，e di n t ot h ed e c i m a lf l l l c t i o l lo f t i l er e a l n u m b e r t h ec i o s s o v e i o p e r a m ri si n d u c t e dt oi m p r o v et h ed i v e r s i t yo ft h ep o p u l a t i o n t h ei m p a c to fv a r i o u sp a r a m e t e r sf o rt h er e s u l ti sd i s c u s s e dd e t a i l e d l y f o rt h es a k eo f c o m p a r i n gw i t ho t h e ri n t e l l i g e n ta l g o r i t h m s g 黜6 ca l g o r i t h ma n da r t i f i c i a lf i s h $ e l a o o la l g o r i t h ma s t u d i e d d o u b l ec - e n c t i ca l g o r i t h mi sp r e s e n t e df o rc v r p , a n d t w op o p u l a t i o n si si n i t i a l i z a t i o n , e a e l ah a si t sp r o b a b i l i t yo fc r o s s o v e ra n dm u t a t i o n , a n d t l a et w op o p u l a t i o n se x c h a n g et h eb e t t e re l a r o m o s o m e i t 啪b r e a kt h eb a l a n c eo f i n t e r - p o p u l a t i o ni nt h el o c a lm i n i m i z a t i o n , i n c r e a s et h ed i v e r s i t yo ft h ep o p u l a t i o n , e s c a p et h el o c a lm i l l i n l i 盟t i o n f o ra r t i f i c i a lf i s hs c h o o la l g o r i t l m l , s o i i i ed e f i n i t i o n s a n dr u l e sw h e nt h ea f s a a l g o r i t h mi sa p p l i e di n t oc o m b i n a t i o no p t i m i z a t i o np r o b l e mi s p r e s e n t e d t h eo p e r a t i o nr u l e so fa f s af o rv r pa 聆p r e s e n t e d , m e t h o do fe n c o d i n g , b e h a v i o re v a l u a t i o na n ds oo n t h ec o m p u t a t i o n a lc o m p l e x i t yo ft l a e s ea l g o r i l a t m sa 咒 a n a l y z e da n dt h ep a r a m e t e r so f a l g o r i t l a m s 骶d i s c u s s e dt l a r o u g he x p e r i m e n t s ( 3 ) t h em a t h e m a t i c a lm o d e lo fo p e nv c l a i e l er o u t i n gp r o b l e mi sf o u n d e d , a n d p a r t i c l es w a r mo p l i m j 础o nc o m b i n e dt l a eg l o b a ls e a r c ha n dl o c a ls e a r c ha l g o r i t h m s 雠p r e s e n t e d s c v o r a l h e u r i s tm e t h o d s 玳a p p l i e di n t ot l a cp o s t - o p t i m i z a t i o n p l o c l ：d u t e s u c ha s2 - o p t , 3 - o p t , n e a r e s ti n s 酬d o na l g o r t i l a m t h e ya 他u s e dt oo p t i m i z e t h ei n n e ro ro u t e rr o u t e sa n dm o d i f yi l l e g a ls o l u t i o n s t h ec o m p u t a t i o n a lc o m p l e x i t yo f t h e s ea l g o r i l a l 卫a sa 托锄i a l y z e d i nt h e 币e r i i n e n 协，t h ep e r f o r m a n c eo ft h ep r o p o s e d p o s t - o p t i m i z a t i o na l g o r i t h mi sa n a l y z e da n dt h ep 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 i se o m l a e dw i t ho t h e rh e u r i s t i cm e t h o d s ( 4 ) t h em u l t i - o b j e c t i v ev e l a i e l em u t i n gp r o b l e mt oo p l j l l l i z e b o t hc u s t o m e l s a t i s f a c t i o na n dt h em m s p o r t a t i o nc o s ti sp r o p o s e d t h ec u s t o l n 盯s a i l s f a c t i o ni sd e n o t e d b yu - a p e ：z i af i l 2 珂n u m b e r t h ei m p r o v c m e a tn e , 衄e s tn e i g h b o ra l g o r i t h ma n dc h e a p e s t h a l g o r i t h ma 地p i 馏缸c e d t h eg e n e r a lc o s ti s 出血d w h i c hi si n c l u d e d c u s t o r n e l s a t i s f a c t i o n , d i s t a n c e ，w a i t 血gt i m ea n do t l l e tf a c t o r s 1 h et w oa l g o r i t h m s h y b r i dp s oi sp r o p o s e dt os o l v et h ep r o b l e m t h ec o m p l e x i t yo f t h ea l g o r i t h ma n dt h e a l g o r i t h m sp a r a m e t e r sa 地d i s c u s s e d f i n a l l y , i nt h ee x p e r i m e n t s t h e s ea l g o r i t h m sa r e i v 浙江工业大学博士学位论文 a n a l y z e da n dc o m p a r e d ( 5 ) t u n ed e p e n d e mv e h i c l er o u t i n gp r o b l e mi sm o r ec o m p l e xt h a no t h e rv r p s , b e c a u s ei t sw a v e lc o s tc h a n g e dw i t ht h et i m e mt h ep 印t h em a t h e m a t i cm o d e lo f t h e p r o b l e mi sf o u n d e d , a n dac o n t i n u o u sf f l n 甜o f ii sp r e s e n t e df o rt h et i m ed e p e n d c a t n e t w o r km o d e l t h ea u t o - a d a p t p a r a m e t e ro fp s oi sp r e s e n t e c le a c hp a r t i c l e s p a r a m e t e r w 啪a u t o - a d a p tr c g u l a 把a c c o r d i n gt ot h ef i m e s sc h a n g i n g a tt h es a m e t i m e ，c a l l b o a r dp o l i c yi si n 打o d u c e di nt h ea l g o r i t h m , a n dt h ep a r t i c l eu p d a t ei t sp o s i t i o n a c c o r d i n gt ot h ef i t o e s s f o rt h eb e t t e rp a r t i c l e an 绷u p d a 衄f o m u l a i sa p p l i e d , a n df o r t h ei n a c t i v i t yp a r t i c l e t h e ya 地d i s p l a c e db yt h en e wp a r t i c l e s i nt h ee x p e r i m e n t , t h e p a r a m e t e r so ft h ea l g o r i t h ma r cd i s c u s s e dd e t a i l e d l y , a n dt h er e s u l ts h o wt h ea l g o r i t h m i se f f i c i e n c y ( 6 ) b a s e do nt h ea b o v et h ea c , a d e m i cr e s 骶h , a ni n t e l l i g e n tv e h i c l er o u t i n gs y s t e m b a s e df i l lt h e3 “p a r t yl o g i s t i c s 岫呻i sd e v e l o p e d t h es y s t e mi n c l u d et h ef o l l o w i n g f l m c t i o u s , s u c h 勰v e h i c l es c h e d u t m gm u t ep l a n n i n g , d e l i v e r i n go r d e rb i | i l d i n 吕 e l e c t r o n i cm a pd i s p l a y , a n db a s i ci n f o r m a t i o nm 麟e r t h es y s t e ms u p p o r t st h em o d e l s o fc v r p , v r p t w a n dp r o v i d e st h eg e n e t i ca l g o r i t h m , p a r t i c l e 翱f 蛐o p 血n i = 蜘a n d s oo n t h es y s t e mh a sb e e na p p l i e di na 3 州p a r t yl o g i s t i c sc o m p a n y , a n dh a v e f a v o u r a b l ee c o n o m i cb e n e f i t k e yw o r d s ：v e h i c l er o u t i n gp r o b l e m , p a r t i c l es w a r mo p t i m i z a t i o n , g e n e t i c a l g o r i t h m , a r t i f i c i a lf i s hs c h o o la l g o r i f l m l , c o m o m e rs a t i s f a c t i o n , o p e nv e h i c l e 勋u 吨p r o b l e m , t u n ed e p e n d e n tv e h i c l er o u t i n gp r o b l e m , t h e3 一p a r t yl o g i s t i c s ， c o m b i n a t i o no p t i m i z a t i o n v 浙扛工业大学博士学位论文 文中常用符号 车辆路径问题的决策变量 盯拥挤厦因子 一 f i t n e s s适应度函数 车辆的载重 一 惯性权重 客户的需求 q ，包加速度常数 j 客户闽的运行成本 玎满意度阀值 到达客户f 的时间是 m 纯) 等待时间 ”i l 寺付啊l 哪 客户f 到- ，的运行时间 岛辑)客户的满意度 车辆七中的客户集合 最在客户处的服务时间 最? 、化。 a p p 表示权重因子衣不仪里因丁 目标函数 染色体 广义费用 基因跏节约费用 种群规模 ( 幻粒子群的信息熵 问题规模 跏粒子f 的位置比f 卯秘丁l 州性互阢 无穷大的整数 交叉概率 v n 车辆总数 变异概率d 总的行驶距离 迭代次数 w t 总的等待时间 算法复杂度 v = “，v 2 ，)粒子的速度 人工鱼的视野 z = ( 毛，而，) 人工鱼或粒子的状 人工鱼的步长 态 0 到l 间的随机教 讪 以 4 勺 。 吩 墨 血z尸工， 见 自： 删 脚 删 浙江工业大学 学位论文原创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进行研究工 作所取得的研究成果。除文中已经加以标注引用的内容外，本论文不包含其他个 人或集体已经发表或撰写过的研究成果，也不含为获得浙江工业大学或其它教育 机构的学位证书而使用过的材料。对本文的研究作出重要贡献的个人和集体，均 已在文中以明确方式标明。本人承担本声明的法律责任 作者签名：灵域 日期佗捧1 月2 日 学位论文版权使用授权 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保 留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。 本人授权浙江工业大学可以将本学位论文的全部或部分内容编入有关数据库进行 检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文 本学位论文属于 1 、保密口，在年解密后适用本授权书 2 、不保密囹 ( 请在以上相应方框内打“4 ”) 作者签名：昊划i 日期舢川年1 月1 ，日 浙江工业大学博士学位论文 1 1 论文的研究背景及意义 第一章绪论 随着世界经济的快速发展和现代科学技术的进步，物流产业作为国民经济中 一个重要的服务行业，正在全球范围迅速发展，并逐渐成为国民经济发展的动脉 和基础产业，其发展程度已成为衡量一个国家现代化程度和综合国力的重要标志 之一。物流产业被誉为经济发展的“加速器”、产业结构演变的“润滑剂”和现代 企业的。第三利润源”。根据我国加入w t o 的承诺，物流业和服务业是晟早开放 的行业之一。目前我国的物流业尚处于起步阶段，与发达国家存在很大差距，最 突出的问题是物流成本较高。2 0 0 5 年中国物流总费用高达3 3 8 6 0 亿元，占g d p 的1 8 6 ，而美国等发达国家物流成本约占g d p 的1 0 左右，中等发达国家( 如韩 国) 的比重在1 5 左右。这表明中国物流业的整体水平严重落后。过高的物流成本， 制约了国民经济的发展，削弱了企业的市场竞争能力。对于我国，降低l 的物流 成本，相当于增加2 0 0 0 多亿的经济效益。因此通过提高物流管理水平和效率，降 低物流成本，可以为企业及社会带来可观的经济效益，改善国民经济运行效率， 提高国际竞争力。因此，国家和各地政府纷纷制定了各种有利于物流发展的政策 和计划。在国家的“十一五”规划中将“大力发展现代物流业”作为今后重点发 展的领域，明确提出“十一五”结束即2 0 1 0 年，全社会物流成本将比2 0 0 4 年下 降2 3 个百分点。 运输配送成本占物流成本的6 0 左右，是影响物流总成本的重要因素，美国 的运输成本仅占到其g d p 的不到6 ，日本也仅为6 5 。而我国运输成本占到g d p 的1 1 。根据中国仓储协会对1 4 6 个企业的调查显示，用于运输的费用占整个物 流费用的比例分别为：生产企业原料物流中占5 8 ，生产企业成品物流中占7 3 ， 商业物流占5 2 。可见该问题对现代物流业发展的重要性以及解决好该问题所 产生的巨大经济利益 作为物流配送优化系统中的关键一环，车辆路径问题( 又称车辆调度问 第一章绪论 题, v e h c l er o u t i n gp r o b l e 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 ) ) 的研究受到 人们广泛关注。该问题由d a n t z i g 和r a m s e t 于1 9 5 9 年首先提出的，经过近五十年 的研究，已成为运筹学与组合优化领域的前沿和研究热点课题。现实生产和生活 中，邮政投递问题、飞机、铁路车辆、水运船舶及公共汽车的调度问题、电力调 度问题等都可以抽象为车辆路径问题。随着电子商务和物流配送的发展，v r p 在 各种连锁店、大型商场、快递等领域有广泛的应用前景。因此对车辆路径问题的 深入研究，有较高的科学意义和工程应用价值。 1 2 车辆路径问题的定义及组成要素 1 2 1 车辆路径问题的定义 车辆路径问题( v e h i c l er o u t i n gp r o b l e m ) 又称车辆调度问题，通常可以描述 为：对一系列装货点和( 或) 卸货点，组织适当的行车线路使车辆有序地通过它们， 在满足一定的约柬条件( 如货物需求量、发送量、交发货时间、车辆容量等限制) 下，达到一定的目标( 如路程最短、费用最少、时间最少、使用车辆数最少等) 。一 般认为不涉及时问的是路径问题，涉及时间的是调度问题。车辆路径问题的示意 图如下图1 1 所示。 2 图1 1 车辆路径问题的示意图 浙江工业大学博士学位论文 1 2 2 车辆路径问题的组成要素分析 根据上面的定义，本小节对车辆路径问题涉及到的各因素进行分析，这些因 素是车辆路径问题分类的依据，如下表1 1 所示。目前已知的研究模型，是对这些 因素一种或几种的组合，而忽略其他因素建立的。随着社会的发展，v r p 也在不 断的发展变化，一些新要素可能会出现并对研究起着至关重要的作用，如仓储配 送一体化优化的库存路径问题( i n v e n t o r yr o u t i n gp r o b l e m ) 等。 表1 1 车辆路径问题构成要素 组成要素属性 仓库单一仓储多仓储 客户 有时间窗，无时间窗，送货收货单计划期，周期计划，确定性需求不确 定性需求静态励态需求，客户间有需求约束，客户间的优先顺序等 车辆的载重，容积，多车型，单一车型，每型车辆数目的限制，有，无行驶 里程( 或时间) 的限制等 道路两无向网络隋向网络，静态网络黝态弼络环确定两络，行驶费用等 客户只能由一辆车服务，客户可由多辆车服务车辆需返回仓库，车辆不返 运输安捧的要求 回仓库，车辆返回同一仓库库辆可返回不同的仓库( 对于多仓情况) 等 最小化总运输成本( 包括车辆数和行驶里程) ，最小化客户等待时间，最 优化目标 大化客户满意度等 1 3 车辆路径问题的研究现状 车辆路径问题的研究经过近5 0 的发展，衍生出众多模型，求解算法更是层出 不穷早在1 9 8 3 年，b o d i n 等在长达1 4 0 多页的v r p 研究综述文章中，列举了6 9 9 篇相关的参考文献。在1 9 9 5 年出版的运筹学与管理科学手册中，第八卷就是 专门讨论车辆路径问题的2 0 0 2 年，p a o l ot o t h 和d a n i e l ev i g o l u 在其出版的著作 中，对v r p 的最新研究进展和发展趋势进行了全面的分析。车辆路径问题近5 0 年的发展趋势如下图1 - 2 所示。该问题的模型随着相关科学的发展，从最初的静态 的v r p ，v r p t w ，v r p p d 等模型，到随机，模糊车辆路径问题，到近1 0 多年由 于计算机通信技术的发展，而产生的动态车辆路径问题，求解方法也同样经历了 精确求解，启发式求解，到现在的智能优化算法限于篇幅和作者的知识水平， 不能对所有的模型和算法一一列举，本文对一些研究比较多的模型和算法进行分 第一章绪论 类说明 图1 2 车辆路径问题发展趋势 1 3 1 车辆路径问题的模型综述 口问题涉及的因素众多，产生很多的模型。根据研究的重点不同，这些模 型存在不同的分类方式。在本节中，根据已有的资料，将研究比较多的模型提取 出来，然后再加入不同的约束，此种分类方法比已有分类更直观。如下图l - 3 所示， 内层圈内显示的是车辆路径问题的一些基本模型，外层圈上表示车辆路径闯题的 一些衍生模型。首先介绍最基本的几种模型。 1 3 1 i 基本模型 1 有能力约束的车辆路径问题( c n 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 ， c 、，i 心) 有能力约束的车辆路径问题，简称车辆路径问恿此模型是车辆路径问题的 基本模型。该模型约束少，一般仅对车辆的载重和行驶的时间( 或距离) 有约束 此模型研究的时间最长。取得的成果最多，大量的精确算法，启发式算法用于求 解此问题，其他模型的各种求解算法也大多衍生于此 4 浙江工业大学博士学位论文 圈1 - 3 车辆路径甸嚣的分类 2 有时同窗约束的车辆路径问题( v e h i c l el h n 恤gp r o b l e mw i t ht i m e w i n d o w s , v r p t w ) 此模型是在有能力约束模型的基础上加入了时间窗约束，时间窗的加入使此 模型贴近实际情况，且求解难度增加很多，此模型是目前研究最多的模型，大量 的智能优化算法都是针对此模型提出的。每个客户有最早的服务时间和最迟的服 务时间作为约束条件。时间窗又分为两类：软时间窗( 即不满足时问窗约束时， 给予惩罚) ，硬时间窗( 不满足时同窗约束，即为不可行解) 。 3 带取送货的车辆路径问题( v e h i c l er o u t i n gp r o b l e mw i t hp i c k - u pa n d d e l i v e r y , v r p p d ) 这类问题分几种情况，一种是客户不仅需要货物，还要返回货物。为了简化 问题，一般认为返回的货物不在客户间交换。而都运回仓库。这种情况在有回收 物流的企业中经常出现，如啤酒、纯净水企业，需要送货，同时回收空瓶种 是需要将货物从取货点客户取走，送到相应的卸货点客户，在这种情况下，客户 间的顺序有前驱后继关系，同时相应的客户要配对，即在同一辆车上面。实际中 的残障人士的接送( h a n d , c a p p e dp c 侣衄t r a n s p o r t a t i o np r o b l e m ) ，邮包快递的收 送都属于此类问题f l - 3 1 第一章绪论 4 周期性的车辆路径问题( p e r o d i cv e h i c l er o u t i n gp r o b l e m , p v r p ) 周期性车辆路径阿题是对v r p 的扩展，v e p 研究的是对车辆的日安捧，而 p v r p 是对车辆的一个周期内多日的安捧。在一个周期内，每个客户在满足需求的 前提下，最少被服务一次，也可以是多次此类问题多出现在食品、能源等行业 中，在牛奶收购，成品油配送等方面在国外有成功的应用实侈| i 嘲。 5 分散配送车辆路径问题( s p u td e l i v e r yv e h i c l er o u t i n gp r o b l e m ，s d v r p ) 分散配送与一般车辆路径问题的不同在于允许一个客户被两辆或者多辆车配 送，该问题是d r o r 和t r u d e a u 在1 9 8 9 年提出的，该问题的求解算法多用启发式算 法【7 一。 6 带回程载货的车辆路径问题( v e h i c l er o u t i n gp r o b l e mw i t h b a e k h a u l , v r p b ) 在此模型中，客户的需求分为两类，一种是需要配送货物，一类是收取货物， 在配送的过程中，需要首先服务配送货物的客户，然后再取货。在进行规划时， 充分考虑车辆容积的限制。此模型是带取送货的车辆路径问题( t 肿) 的一种 特例 1 3 1 2 衍生模型 在上面介绍的基本模型的基础上，针对实际企业中不同的情况，考虑不同的约 束条件，形成了众多的车辆路径问题的衍生模型。每个模型涉及众多因素，如何 将其归类，则视此模型中考虑的主要约束条件。本文就目前研究的较多的一些模 型进行简单介绍 1 多仓库车辆路径f 习m ( m u | t i p l ed e p o t v e h i c l er o u t i n gp r o b l e m ，m - v r p ) 多仓库车辆路径问题在大型生产，流通企业中普遍存在，多个仓库分布在不 同的区域，其求解比单仓的车辆路径问题要更复杂，通常假设从某个仓库出发的 车辆仍需返回此仓库，在求解时，大多算法都是按照某种规则，将客户分配给某 个仓库，然后按照单一仓库车辆路径问题进行求解。目前的求解方法中，改进的 单仓启发式算法比较多 9 - 】 6 浙江工业大学博士学位论文 2 多车型车辆路径问题( h e t e r o g e n e o u sf l e e tv e h i c l er o u t i n gp r o b l e m , h 嘲 一般的车辆路径问题在研究时，通常假设所用车辆为同一类型，而实际生活 中，车辆可有多种类型。对这种情况，g o l d e n 于1 9 8 4 1 刁年提出多车型车辆路径 问题的研究。模型中每种车型的数量限定或者不限定，每种车型的费用不一，优 化的目标是使运输的总成本最小、车辆最少等。目前求解算法主要是动态规划， 列生成等启发式算法和禁忌搜索，遗传算法，蚁群算法等智能优化方法0 3 1 4 3 随机车辆路径问题( s t o c h a s t i cv e h i c l er o u t i n gp r o b l e m , s v r p ) 随机车辆路径问题的研究起于8 0 年代初，目前主要研究的是随机客户、随 机需求、随机路行时间这三方面的内容。对于随机客户问题，在消防、公安、医 疗等公共事业部门和维修、邮递、运输等服务行业经常会出现这种情况。随机需 求量( 冲s d ) 的车辆路径问题，虽然知道确切的客户，却无法知道客户的准确 需求量。这类问题在国外冬季取暖的燃油配送等方面经常出现。随机顾客和需求 的车辆路径f 可m ( v p - , p s c d ) 将v r p s d 和v p p s c 结合在一起。v r p s c d 是一个非 常困难的问题。甚至计算目标函数的值也是相当困难的目前，随机旅行时间的 车辆路径问题( v r p s t ) 研究的不是很多，而随机网络的最短路径问题研究的比较 多，将其已有的成果引入v r p s t ，将是今后研究的方向【1 5 嘲 4 模糊车辆路径问题( f u z zv e h i c l er o u t i n gp r o b l e m , f w z p ) 在实际的车辆调度中，某些待服务客户的需求信息没有或无法给出准确的描 述，这样就需要将模糊概念引入模型和算法来解决这类问题关于车辆路径问题中 模糊信息的处理，如需求模糊、距离时间模糊，这方面的研究还不够深入【挣她1 9 6 1 ， 有许多待研究的问题。另一种形式是将模糊概念引入时间窗，通常客户需要服