（运筹学与控制论专业论文）具有时间窗的集送货vrp问题的并行算法研究.pdf

南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名：群钓 i 一，矿年r 月二矿e t 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名：学位论文作者签名： 解密时间：年 月 日 各密级的最长保密年限及书写格式规定如下： 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 学位论文作者签名：鲜序j 之矿年厂月1 ，日 分类号： udc ： 理学硕士学位论文 学校代码：! q q 5 堇 学号：2 1 2 0 0 5 0 2 0 4 具有时间窗的集送货v r p 问题 的并行算法研究 姓名： 堡鏖宝 年级：二雯雯五级 专 业：运签堂皇控剑论 研究方向： 运签堂皇塑岱筐堡 导师： 陵丞巫熬拯 南开大学信息技术科学学院 二零零八年五月 摘要 摘要 在经济全球化和信息化的推动下，现代物流已从为社会提供传统运输服务， 扩展到以现代科技为支柱的综合物流系统。为了降低物流运输企业的成本，提 高运作效率，全面提高客户满意度，车辆调度与路径优化问题越来越受到人们 的关注。 本文首先回顾了国内外有关车辆路径问题( 冲) 的研究成果，对v r p s d p 和v r p t w 的基本概念、主要分类、研究的发展和现状进行了系统、详细的介 绍，并指出了目前研究中存在的问题。针对这些问题，本文做了以下几方面的 工作： 设计了带有时间窗约束的v r p s d p ( v i 冲t w s d p ) 的并行分枝定价算法。 根据所使用并行开发工具的特点，在搜索树构造的层次上以主从式策略实现了 分枝定价算法的并行化。利用双向动态规划算法求解作为定价子问题的带有时 间和容量两类资源约束的最短路径问题。根据v r p t w s d p 的特点，开发了按时 间资源进行分枝的方法，并在实验中与完全按弧分枝的方法在计算效果上进行 了对比。在并行分枝定价算法求解v r p t w s d p 实例的有效性实验中，详细分析 了算法并行化对生成的节点数、加速比和相对加速比的影响。以a h g a 和 c g p g a 为基础，设计了v r p t w s d p 的串、并行遗传算法。 设计了求解v r p s d p 的粗粒度并行遗传算法( c g p g a ) 。并行算法以单向 环作为连接拓扑，各子群体独立进行遗传操作，迁移算子用于群体间的信息交 流，采用多样性替换的方法进行个体替换。本文给出了c g p g a 算法在集群系统 上的重复非阻塞m p i 实现。对典型v r p s d p 实例进行测试的结果表明，该遗 传算法能较快地获得小规模问题的最优解，并能有效地求解大规模的问题。 关键词：车辆路径问题并行优化算法遗传算法分枝定价 a b s t r a c t a b s t r a c t w i t ht h e p r o m o t i o no fe c o n o m i cg l o b a l i z a t i o na n di n f o r m a t i o nt e c h n o l o g y , m o d e r nl o g i s t i c sh a sd e v e l o p e df r o mp r o v i d i n gt r a d i t i o n a lt r a n s p o r t a t i o ns e r v i c et o t h ei n t e g r a t e dl o g i s t i c ss y s t e ms u p p o r t e db ym o d e mt e c h n o l o g y i no r d e rt or e d u c e l o g i 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 f i c i e n c ya n de n h a n c ec u s t o m e rs a t i s f a c t i o n , v e h i c l es c h e d u l i n ga n dr o u t i n gp r o b l e mh a sa t t r a c t e dm o r ea n dm o r ea t t e n t i o n f i r s t l y , i nt h i sd i s s e r t a t i o nt h ed o m e s t i ca n df o r e i g nr e s e a r c ho nv e h i c l er o u t i n g p r o b l e m ( v r p ) i sr e v i e w e d ，t h eb a s i cc o n c e p t , m a i nc a t e g o r i e sa n ds t a t e - o f - a r tf o r v r p s d p v r p t wa r ei n t r o d u c e ds y s t e m i c a l l ya n di nd e t a i l s o m es h o r t c o m i n g so f t h ee x i s t i n gw o r ka r ea n a l y z e d t ot h e s ep r o b l e m s ，t h ef o l l o w i n gr e s e a r c hw o f k sh a v e b e e nc o n d u c t e d a p a r a l l e lb r a n c h - a n d - p r i c ea l g o r i t h m ( p a r a l l e lb & p ) i sd e v e l o p e dt os o l v e v r p t w s d ea c c o r d i n gt ot h ef e a t u r e so fp a r a l l e lt o o l ，t h ea l g o r i t h mi sp a r a l l e l i z e d b ym a s t e r - s l a v ea p p r o a c ho nt h es e a r c ht r e el e v e l a ne l e m e n t a r ys h o r t e s tp a t h p r o b l e mw i t hc a p a c i t ya n dt i m e w i n d o wr e s o u r c ec o n s t r a i n si ss o l v e db yab o u n d e d b i d i r e c t i o n a l d y n a m i cp r o g r a m m i n gp r o c e d u r e ，w h i c ha r i s e s 嬲ap r i c i n g s u b - p r o b l e m ab r a n c h i n gs t r a t e g yb a s e do nt i m ei sp r e s e n t e db yt h en a t u r eo f v r p t w s d p , w h i c hi sc o m p a r e dw i t hb r a n c h i n go na r c $ i ne x p e r i m e n t i nf u r t h e r e x p e r i m e n t , t h ea l g o r i t h m se f f e c to nt h en u m b e ro fn o d e s ，s p e e d u pr a t i oa n dr e l a t i v e s p e e d u pr a t i oi sa n a l y z e di nd e t a i l b a s e d0 1 1t h ea h g aa n dc g p g a ，b o t hs e r i a lg a a n d p a r a l l e lg a a r ed e v e l o p e dt os o l v ev r p t w s d e a c o a r s e g r a i n e dp a r a l l e lg e n e t i ca l g o r i t h m ( c g p g a ) i sd e v e l o p e dt os o l v e v r p s d et h ep a r a l l e la l g o r i t h mu s e s1d r i n g 鹊t h et o p o l o g y , w i t ha s e r i a lg a ( s g a ) r u n n i n go ne a c hp r o c e s s o r t h em i g r a t i o no p e r a t o ri su s e dt oc o m m u n i c a t eb e t w e e n s u b p o p u l a t i o n s ，a n dd i v e r s i t yr e p l a c e m e n tt or e p l a c ei n d i v i d u a l s t h ea l g o r i t h mw i t h t h e r e p e a t e d l yn o n b l o c k i n g m p io nc l u s t e r s y s t e m i s i m p l e m e n t e d t h e c o m p u t a t i o n a lr e s u l t sc a r r i e do u to nv r p s d pb e n c h m a r ki n s t a n c e si n d i c a t et h a tt h e g a sa r ec a p a b l eo fo b t a i n i n go p t i m a ls o l u t i o n sv e r yf a s tf o rs m a l l - s i z e dp r o b l e m s ， a n de f f e c t i v ef o rs o l v i n gl a r g e - s i z e dp r o b l e m s i i a b s t r a c 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 a l l e lo p t i m i z a t i o na l g o r i t h m ；g e n e t i c a l g o r i t h m ；b r a n c h - a n d - p r i c e 目录 目录 摘要i a b s t r a c t i i 目录i v 第一章绪论1 第一节研究背景与意义l 1 1 1 研究背景l i i 2 研究意义。：3 第二节v r p 问题的研究综述3 1 2 1v r p 问题的描述与分类4 1 2 2v r p 问题的主要求解算法。5 第三节冲s d p r p l w 问题的研究综述7 1 3 1v r p s d p 问题的研究综述。7 1 3 2v r p t w 问题的研究综述9 第四节研究中存在的问题以及本文的研究内容1 0 第二章并行算法简介1 3 第一节并行算法的目标、分类和设计过程1 3 2 1 1 并行算法的目标和分类1 3 2 1 2 并行算法的一般设计过程1 4 第二节并行算法的设计环境及性能评价准则17 2 2 1 并行算法的设计环境1 7 2 2 2 并行算法的性能评价准则1 8 第三节并行算法在车辆路径问题中的应用2 0 第三章v r p t w s d p 的并行精确算法研究2 2 第一节v r p t w s d p 的模型及分枝定价算法介绍2 2 3 1 1 v r p t w s d p 的数学模型一2 2 3 1 2 分枝定价算法2 6 i v 目录 第二节并行分枝定价算法2 8 3 2 1 r c e s p p 的双向动态规划2 8 3 2 2 定价算法3 4 3 2 3 分枝方法3 5 3 2 4 分枝定价算法的并行化实现3 6 第三节计算实例及结果分析3 9 3 3 1 不同分枝方法对串行算法的影响3 9 3 3 2 并行分枝定价算法的有效性分析4 l 第四章v l 冲t w s d p 的并行遗传算法研究4 5 第一节v r p t w s d p 的自适应混合遗传算法4 5 4 1 1 染色体结构和解码方法4 5 4 1 2 遗传算子设计4 7 4 1 3 算法步骤4 9 4 1 4 计算实例及结果分析5 0 第二节v r p t w s d p 的粗粒度并行遗传算法5 3 4 2 1 遗传算子5 4 4 2 2 个体迁移策略5 4 4 2 3 算法的重复非阻塞m p i 实现及算法流程5 5 4 2 4 计算实例及结果分析5 7 第五章总结与展望6 0 第一节本文的主要研究成果6 0 第二节进一步的研究方向6 0 参考文献一6 2 致谢6 7 个人简历6 8 v 第一章绪论 第一章绪论 随着社会、经济和技术的飞速发展，全球经济一体化趋势和市场竞争程度 的日益加强，企业已经发现依靠降低商品的成本来提高经济效益的空间已经越 来越小，便纷纷将目标转向控制物流的成本。因此，物流在企业间竞争以获得 更多的资源和发展空间方面，就日益凸显出其重要的战略意义。进入2 l 世纪的 中国，必将加快现代物流的发展，以此增强企业的核心竞争力，优化资源配置， 提高经济运行质量，实现中国经济体制与经济增长方式的两个根本性转变，从 而推动中国经济的持续健康发展【i 】。 车辆路径问题一直是物流配送活动中最基本的问题之一，研究车辆路径问 题的实用、有效的优化方法，对于促进物流配送、智能交通、运输调度等领域 的发展具有重要的理论和实际意义，对提高企业的社会和经济效益无疑具有重 要的作用。 本章首先介绍研究的背景与意义，进而对国内外有关车辆路径问题尤其是 带时间窗和集送货需求的车辆路径问题的研究现状进行了回顾，最后概括了全 文的研究思路和内容。 第一节研究背景与意义 1 1 1 研究背景 从传统物流( p h y s i c a ld i s t r i b u t i o n ) 的出现到今天日益发展完善的现代物流 ( l o g i s t i c s ) ，物流概念经历了一个内涵不断丰富，外延日益扩大，适用范围日趋 宽广的历史演变过程【2 】。目前，现代物流已经被公认为企业在降低物质消耗、提 高劳动生产率之外的“第三利润源泉 。高效的现代物流能够为国民经济的持续 高速发展提供不可或缺的基础动力。以美国为例，作为物流概念的发源地，美 国目前已经形成了比较成熟的物流管理体制。根据美国供应链管理协会提供的 美国国家物流数据，目前，美国物流总费用已经突破l 万亿美元。物流总费用 上升的主要原因是运输费用的上升，公路货车运输费用一直占美国物流总费用 的5 0 左右。 与发达国家相比，中国的物流业存在高速发展与效率偏低共存的现象。2 0 0 7 第一章绪论 年中国社会物流总额突破7 5 万亿元，同比增长2 6 2 ；国内物流业增加值达1 6 9 万亿元，同比增长1 8 8 。统计数据显示，物流总额与国内生产总值相比的物流 需求系数由2 0 0 6 年的2 8 提高到2 0 0 7 年的3 2 ，表明中国社会经济的发展对现 代物流业需求持续增大的趋势。然而从另一个方面，根据全国第三产业普查资 料，我国交通运输、仓储、代理和批发等行业的成本费用之和占国民生产总值 的比重为1 5 左右，而美国的全社会物流费用支出仅仅占其国民生产总值的1 0 左右。这充分表明中国的物流业还具有非常广阔的发展空间。 车辆路径问题( v e h i c l er o u t i n gp r o b l e m ，v r p ) 自1 9 5 9 年由d a n t z i g l 3 首次提 出以来，一直是物流配送活动中最基本的问题之一。c a n e n 和s c o t t 将v r p 称为 “最近十年来运筹学领域最成功的研究之一【4 】。同时具有集送货需求的车辆路 径问题w r pw i t hs i m u l t a n e o u sd e l i v e r i e sa n dp i c k u p s ，v r p s d p ) 是对传统v r p 的扩展和变形，即每个客户同时具有配送和收集两类需求。而带有时间窗约束 的同时具有集送货需求的车辆路径问题( v r p s d pw i t l lt i m ew i n d o w s ， v r p t w s d p ) , 贝i j 是对v r p s d p 问题的进一步扩展，不仅考虑每个客户同时具有配 送和收集需求，还考虑客户对服务时间具有一定的要求，从而更贴近物流业的 实际情况。 v r p s d p 和v r p t w s d p 在物流业具有非常普遍的应用，主要包括以下三个 方面： ( 1 )配送中心配送问题 零售业的发展使得供应商直接面对客户的营销方式越来越困难，越来越多 的供应商开始采用物流中心对客户进行配送的作业方式。物流中心发出的车辆 不仅对各个客户进行货物配送，同时还根据需要进行产品回收。 ( 2 )快件与货运公司 如美国联合包裹运送服务公司( u p s ) 、联邦快运( f e d e x ) 等国际速递业公司通 常采用门对门的服务方式，即对服务客户进行上门集货和送货的服务。 ( 3 )逆向物流 全新的资源环境观和经济观的演变，带来了企业对逆向物流的关注。逆向 物流是指企业对客户手中的产品进行有偿或无偿回收的过程。逆向物流在给企 业带来直接经济效益的同时，还能给企业带来成本下降、客户满意度提高、环 2 第一章绪论 保等多方面的间接效益。将逆向物流与正向物流结合，就转变为本文研究的 t w s d p 问题。 1 1 2 研究意义 正是由于现代物流业对整个国家经济具有十分重大的意义，而目前中国物 流管理仍然比较落后；改变当前中国物流行业普遍专业化程度低、高耗低效等 问题，接受新的物流管理思想、改进管理方法、采用现代物流新技术，已经成 为中国物流企业的当务之急。对于中国物流企业来说，对v r p t w s d p 的研究作 为发展敏捷配送的一个重要组成部分，是实现物流现代化的基础和重要保证， 其研究成果不仅可以帮助企业提高服务水平，为客户提供快捷、准时、安全、 舒适的服务，解决发展电子商务中速递这一“瓶颈约束，而且有助于企业节 约运输成本，改善车辆利用效率，缩短生产周期，加速资金周转，实现资源的 合理配置，汲取“第三利润源泉”的财富；还可以有效缓解城市交通拥挤、能 源短缺、大气污染等问题，保证交通资源合理配置与利用，实现效率、资源、 环境和价值观念各方面的内在统一，促进物流业的进步和社会经济的可持续发 展。 综上所述，v r p 问题作为典型的组合优化问题，是运筹学领域研究的热点， 其各类问题模型在现实中有着广泛的应用。研究v p , p 和v r p t w s d p 高效率的 算法对于促进物流配送、智能交通、运输调度等领域的发展具有重要的实际意 义，可以获得巨大的社会和经济效益。 第二节v r p 问题的研究综述 早在1 9 8 3 年b o d i n 等【5 】在他们长达1 4 0 页的对v r p 研究进展的综述文章中， 就列举了6 9 9 篇相关的参考文献。在1 9 9 5 年出版的( ( h a n d b o o l 【si no p e r a t i o n s r e s e a r c ha n dm a n a g e m e n ts c i e n c e ) ) 6 1 书中，第八卷专门讨论了车辆路径问题。 2 0 0 2 年，t o m 和v i g o r 在 t h ev e h i c l er o u t i n gp r o b l e m s o c i e t yf o ri n d u s t r i a la n d a p p l i e dm a t h e m a t i c s ) ) t t l q 】，对v i 冲的最新研究进展和发展趋势作了全面的分析。 国内对v r p 研究的专著有李军和郭耀煌编写的物流配送车辆优化调度理论与 方法【8 】一书，对这方面的研究情况也做了系统介绍。通过世界各国广大研究人 员的共同努力，现已提出许多用于求解不同类型v r p 问题最优解或近似解的模 型及其精确或启发式算法，以及相应的软件包。 3 第一章绪论 本节主要对v r p 的研究现状进行综述，而在下一节中介绍同时具有集送货 需求车辆路径问题和带时间窗车辆路径问题的研究现状。 1 2 1v r p 问题的描述与分类 v r p 的一般定义为“对一系列装货点和( 或) 卸货点，组织适当的行车线 路，使车辆有序地通过它们，在满足一定的约束条件( 如货物需求量、发送量、 交发货时间、车辆容量限制、行驶里程限制、时间限制) 下，达到一定目标( 如 里程最短、费用最少、时间尽量少、使用车辆尽量少等) 。”【8 l 自从v r p 问题被提出后，许多学者从不同角度按不同标准进行了多种分类： ( 1 )按任务特征分类 可分为纯配送问题和纯收集问题( 车辆在所有客户点只装货或卸货，即集 货或送货问题) 及集送货一体化问题( 每个客户有不同的配送和收集需求，即 装卸货混合问题) 。 ( 2 )按任务性质分类 可分为对弧服务问题( 如邮递员问题) 和对点服务问题( 如旅行商问题) 以及混和服务问题( 如交通车辆路线安排问题) 。 ( 3 )按车辆载货状况分类 可分为满载问题( 货运量不小于车辆容量，完成一项任务需要不只一辆车) 和非满载问题( 货运量小于车辆容量，多项任务合用一辆车) 。 ( 4 )按车场数目分类 可分为单车场问题和多车场问题。 ( 5 )按车辆类型分类 可分为单车辆类型问题( 所有车辆类型相同容量相同) 和多车辆类型问题 ( 执行任务车辆的类型和容量不完全相同) 。 ( 6 )按车辆对车场的所属关系分为类 可分为车辆开放问题( 车辆可以不返回其出发车场) 和车辆封闭问题( 车 辆必须返回其出发车场) 。 4 第一章绪论 1 2 2v r p 问题的主要求解算法 求解v r p 问题的算法一般分为三类：精确算法、启发式算法和智能优化算 法。 ( 1 )精确算法 精确算法一般可分为：分枝定界算法、直接树搜索算法、动态规划算法以 及基于整数线形规划的算法等。 ( a ) 分枝定界算法 l a p o r t e 等人利用该方法对车辆调度路径进行了求解唧。这种方法主要利用 v r p 和其松弛形式的多旅行商问题之间的关系，将v r p 问题变形为多旅行商后， 再利用分枝定界算法得到问题的最优解。 ( b ) k 度中心树相关算法 该方法由c h r i s t o f i d e s 等人【1 0 】提出，对固定车辆数m 的多旅行商问题进行k 度中心树松弛，所以该方法需要知道所需车辆数的下界。该模型从边的角度建 立，出发点用k 条边来表示，其它点用两条边表示，通过拉格朗日松弛法，将 其中一个约束条件消去，并进一步将原来的最小化问题转换成3 个易于求解的 子最小化问题，然后进行求解。 ( c ) 动态规划算法 e i l o n 等人采用动态规划算法对v r p 问题进行了求解【】，它针对的也是固定 车辆数的v r p 。为了减少问题的计算规模，引入了可行性规则或松弛过程以减 少状态的数量。该方法要求转换函数易于求解，映射出来的范围小，可求得很 好的下界。 ( d ) 整数线形规划算法 整数线性规划算法以车辆流模型、货物流模型和集合划分模型为基础，根 据模型的特殊构型，应用一定的技术划分成易于求解的子问题，再利用分枝割 平面算法、分枝定价算法( b r a n c ha n dp r i c e ，b & p ) 【1 2 】或分枝定价割平面算法 ( b r a n c ha n dc u ta n dp r i c e ) 1 3 1 等方法求解。分枝割平面法根据v 1 冲问题的特殊 性，构造一些有效的不等式( 如“梳子”不等式等) 使搜索空间进一步缩小， 加快算法的求解速度【1 4 】。 精确算法基于严格的数学手段，在问题规模比较小时，能够求得最优解， 但是当问题规模扩大时，求解时间呈指数级增长。目前使用精确算法很难求解 5 第一章绪论 客户数量超过1 0 0 的问题。因此为了能够在合理的计算时间内求得问题的近似 最优解或满意解，下面介绍的启发式算法就成为研究的一个重要方向。 ( 2 )启发式算法 ( a ) 节约一插入算法 该类算法由c l a r k e 和w r i g h t 提出，是最早被提出用来求解车辆数不固定 v r p 问题的启发式算法【1 5 1 。该算法首先生成客户数量的路径，通过计算合并任 意两条路径后可节约的行驶费用，并按照节约的行驶费用进行排序，根据排序 的结果以及可行性条件对路径进行合并，直到无法找到更好的解。另外， s o l o n l o n 【1 6 1 提出的插入算法，g d r e 跚【1 刀提出的g e n i 插入算法等也都属于节约 一插入算法的范畴。 ( b ) 先分组后安排路径 该类算法先将客户分组，然后对每组客户设计行车路线，如g i l l c t t 掣1 8 】提 出的s w e e p 算法以及r e n a u d 等【1 9 】提出的p e t a l 算法等。 ( c ) 先安排路径后分组 这类算法先构造包含所有客户的长路径，然后按照某种规则将长路径分成 可行的路径；如空间填充曲线算法【2 0 】、回路算法【2 1 1 等。 ( d ) 改进交换算法 该类算法在始终保持解的可行条件下，通过反复迭代，用每次产生的解替 代原来的解，力图向最优目标靠近，直到无法进一步改进目标函数为止；如l i n t 2 2 】 提出的2 o p t 和3 - o p t 交换算法以及b r c e d a m 2 3 1 提出的串重置串交换算法等。 ( 3 )智能优化算法 进入2 0 世纪9 0 年代，智能优化算法成为v r p 研究中新的趋势。模拟退火 算法( s i m u l a t e da n n e a l i n g ) 、禁忌搜索算法( t a b us e a r c h ) 、遗传算法( g e n e t i c a l g o r i t h m ) 和蚂蚁算法( a n ta l g o r i t h m ) 等智能优化算法已经成功地求解了许 多v r p 问题。 ( a ) 模拟退火算法 模拟退火算法由某一较高初温开始，利用具有概率突跳特性的m e t r o p o l i s 抽样策略在解空间中进行随机搜索，伴随温度的不断下降重复抽样过程，最终 得n i 口- j 题的全局最优解。模拟退火算法已被应用于求解v r p 问题，如o s m a n 2 4 1 6 第一章绪论 和b r e e d a m 2 5 】等。 ( b ) 禁忌搜索算法 g e n d r e a u 等最先将该算法应用于v r p 问题，他们先构造一系列的初始解， 然后利用禁忌搜索算法对所得到的初始解不断进行改进【2 6 1 。其后t a i l l a r d 通过按 角度对原问题的空间进行分割，再用禁忌搜索结合模拟退火对子问题求解【2 7 】。 禁忌搜索是求解v r p 问题比较好的启发式算法，已成功地应用于许多经典的 v r p 问题。 ( c ) 遗传算法 l a w r e n c e 最先将遗传算法用于v r p 问题的研列2 引。张涛通过遗传算法来保 证搜索的全局性，用3 - o p t 算法加强局部搜索能力，得到针对v r p 问题的混合 算法，该算法可以求解1 9 9 个客户的大规模问题【捌。 ( d ) 蚂蚁算法 b u l l n h e i m e r 第一次将蚂蚁算法应用于v r p 问题当中，建立了蚂蚁算法应用4 于v r p 问题的基本框架0 0 1 。刘志硕等提出了一种求解v r p 的自适应蚁群算法， 具有很强发现较好解的能力，计算效率也较高【3 l 】。 第三节v r p s d p n r p 刑问题的研究综述 同时具有集送货需求的车辆路径问题( 冲s d p ) 是对经典v r p 问题的一 种扩展，它既可以送货给客户，又可以从客户处集货，具有更加普遍的应用价 值。例如在逆向物流中，通常需要统一考虑从车场运出的商品和需要运回车场 的商品。由相同的车辆同时满足客户这两方面的需求有利于充分协调正向和逆 向物流的关系，发挥整体作用。 带时间窗的车辆路径问题( v r p t w ) 贝j 是对经典v r p 问题的另外一种扩展， 它不仅考虑客户对集送货的需求，同时考虑客户对服务时间的要求。例如邮政 投递系统需要将信件或包裹在指定的时间之前送达目的地；而港口的集送货则 要求运输公司必须在船到港之前将出口的货物送达港口，并且只有在船到港之 后才可能取走进口的货物。另外，仓库的开放时间、道路网络的通行时间等等 也都会形成v r p t w 问题。 1 3 1v r p s d p 问题的研究综述 在物流中心的实际运作中，客户既需要得到从车场运出的货物，同时还需 7 第一章绪论 要将客户一定数量的货物运回车场，他们通常不希望送货服务和集货服务这两 项活动分开来处理。如果车辆停留一次可以完成所有的送货和集货任务，就能 够减少大量的劳动耗费。同时具有集送货需求的车辆路径问题( v i 冲s d p ) 则针 对这种情况，一般以总车辆行驶路程最短，并要求每个客户被且仅被服务一次。 v r p s d p 问题由m i n 在上个世纪八十年代末首先提出，用来求解公共图书 馆的一个实际运送问题【3 2 】。在巴西，需要使用直升飞机实现在陆地和位于里约 热内卢洲盆地上的石油勘探地区之间运输人员，这也是一类v r p s d p 问题， g f l v 提出了一种有效的启发式算法求解这一运输问趔 】。此后超过十年的时 间里没有任何关于这类问题的成果刊出。 近几年来，该问题又重新引起了学者们的广泛兴趣。作为v r p 问题的扩展， v r p s d p 也是一个典型的n h l a r d 问题，因此现有的研究主要以设计该问题的 近似算法为主。s a l h i 和n g a y 提出的群组插入算法不仅能求解集货和送货需求混 排的车辆路径问题( v r p m d p ) p 4 】，也可适用于v r p s d p 的求解。最近，s f l m 和n a g y 在定义v r p s d p 的强可行和弱可行状态的基础上，提出了基于邻域搜索 的启发式方法，其总体效果要优于文献【3 4 】中提出的插入式算、法【巧】。d e t h l o f f 从 逆向物流的角度研究了v r p s d p ，建立了相应的数学模型，并给出了基于剩余 装载能力的插入算法，分别用四种不同的方式计算插入费用，并通过实验数据 对这些方式的求解效果进行了比较p 6 j 。 c f i s p i m 和b 眦d 将禁忌搜索和可变邻域搜索( v a r i a b l en d g h b o u r h o o d s e a r c h ) 算法相结合，提出了解决这一问题的混合算、法【了丌。由于他们在构造初始 解的过程中，求解了一个装箱问题，因此他们的算法能很好地降低车辆使用数 目，但总路程却大幅度增加。c h 和w u 利用插入式规则产生初始解后，以 r e c o r d t o r c c o r dt r a v e l 方法为框架，结合邻域搜索和禁忌表提出了解决该问题 的启发式算法，实验表明对于小规模实例该算法能得到最优解【3 引。m o n t a n e 和 g a l v 设计了求解v r p s d p 的禁忌搜索算法，使用了4 种不同的邻域结构，并 根据禁忌频率增加了集中搜索和分散搜索机制【3 9 1 。 g a n e s h 和n a r 吼d m 提出了一个先对客户点进行聚类，然后进行分类以形成 一条路径，并将其分配给相应的车辆，最后利用g a 进一步改善求解效果的4 阶段启发式算法c l o v e s ( c l 鹏t e rn o d e s ，o r i e n t sn o d 鹤a l o n gar o u t e ，船s i g n v e l l i c l e st 0t h er o u t e s 。r u i n gg at 0i m p r o v et l l es e a r c h ) ，用以求解包括v r p s d p 在内的有各类客户需求的v r p 问题m j 。b i 觚c h e s s i 和黜g h i n i 利用构造法、邻域 8 第一章绪论 搜索法和禁忌搜索法分别求解具有混合或者同时集送货需求的v r p ，实验结果 表明使用复杂和可变邻域结构的搜索算法效果较好【4 。v u r a l 在他的硕士论文中 将求解机器调度问题的遗传算法经过改进后，用于求解v r p s d p 4 2 1 。 在精确算法方面，d e l l a m i c o 等开发了求解v r p s d p 的分枝定价算法，提 出了不同的分枝策略，并分别利用精确动态规划法和状态松弛的动态规划法求 解定价子问题，比较了两者之间的求解效果，该算法最大可求解客户点规模为 4 0 的问题【4 引。 国内近年来也出现了相关的研究，郎茂祥提出了用模拟退火算法求解 v r p s d p 问题，建立了一种直观的数学模型，设计了客户直接排列的解的表示 方法，并通过实验与单向配送策略进行了比较洲。 1 3 2v r p t w 问题的研究综述 相比经典v r p 问题，v r p t w 更贴近企业的实际情况，因此企业中的这种 需求使得众多研究者开始逐渐关注对带时间窗的车辆路径问题的研究。 s o l o m o n 和d e s r o s i e r s 等人于1 9 8 7 年首先考虑将时间约束加入到经典的车 辆路径问题中，最早对带时间约束的车辆路径问题进行了研究【4 5 1 。d e s r o c h e r s 进一步对用于求解带时间窗的车辆路径问题的各种优化方法进行了总结【删。 带时间窗的车辆路径问题的求解方法也可以区分为精确算法启发式算法和 智能优化算法三大类。在精确算法方面，k o l e n 、d e s r o c h e r s 、f i s h e r 、k o h l 等人 将应用于经典v r p 问题的各种精确算法如分枝定界算法等应用于v r p t w 的求 解，成功地解决了一些规模较小的v r p b 妒4 5 钓】。 s o l o m o n 最早将求解经典v r p 的路径构造算法扩展应用于v r p t w 的求解 中，并通过实验证明了启发式算法在求解v r p t w 中的可行性和有效性，为其 后研究启发式算法在带时间窗的车辆路径问题中的应用奠定了理论基础【4 5 1 。此 外，p o t v i n 4 7 】的并行插入算法、k o s k o s i d i s 4 8 1 的一般分配算法以及k o n t o r a v i d s 4 9 j 的贪心随机自适应搜索算法等都是应用于求解v r p t w 的比较成功的启发式算 法。在上述的启发式算法的基础上，许多研究者提出了各种通过对初始解中边 的交换或节点的交换来改进初始解性能的方法，例如文献 3 9 】。c u r r i e 和s a l h i 则引进多货物品种和多车型约束，建立o 1 规划模型，并给出一个基于贪婪算法 和后悔成本的混合算法来求解带时间窗约束的车辆路径问题【删。 近年来，t h a n g i a n 、o s m a n 等人则将禁忌搜索算法、模拟退火以及遗传算法 9 第一章绪论 等智能优化算法引入到v r p t w 的求解中，取得了显著优于一般启发式算法的 结果【5 1 1 。c u r r i e 和s a l h i 设计了一个禁忌搜索算法求解v r p t w ，研究结果证明 了其算法的有效性l 驯。 国内对v r p t w 的研究起步较晚，目前主要集中在以智能优化算法求解 v r p t w ，例如求宾松、符卓等通过引入一种新的编码方法、交叉和变异概率的 自适应机制，构造一个改进的遗传算法来求解带软时间窗的车辆路径问题垆引。 霍佳震、张磊等通过对模型的分解和过滤，结合实际情况，以修正的c l a r k e - w r i g h t 节约启发式算法为基础进行插入式排序，求解带有时间窗的集货和送货一体化 车辆路径问题【5 3 1 。张炯、郎茂祥等则对带时间窗的配送车辆调度问题建立直观 描述的数学模型，通过一种新的解的表示方法构造了求解该问题的禁忌搜索算 法，并以2 1 个节点的运输网络为例进行了实验计掣州。 第四节研究中存在的问题以及本文的研究内容 综上所述，国内外的学者在v r p 、v r p s d p 和v r p t w 的数学模型和求解 算法等方面开展了众多前沿性的研究，取得了较大的进展。但是随着社会经济 的发展，许多实际问题，例如燃油补充问题、食品和饮料配送问题、工业垃圾 收集问题和集装箱货物运输问题等等，都要求在经典v r p 的研究中不断考虑新 的因素，以满足人们日益多样化的需求。而新因素的加入也必然需要人们不断 开发出符合其特性的有效算法。并行计算技术、现代通信技术等高新科技的飞 速发展，也要求在v r p 的研究中能充分利用其他领域的研究成果，以最大限度 地提高客户的满意度、降低运输成本，实现企业利润的最大化。 目前的研究中主要存在下列问题： ( 1 ) 对于v r p 的扩展问题的研究中，研究最多的就是v r p s d p 和v r p t w ， 它们各自涉及了客户多种需求的一个方面。例如在对v r p s d p 的研究中，强调 了客户同时具有配送和收集需求的特点，但通常忽视了客户对服务时间的要求； 而在对v r p t w 的研究中，则强调客户对服务时间的要求，而通常仅仅考虑配 送或者仅仅考虑收集需求。显然，将两方面结合起来考虑能够更加贴近企业的 实际情况，更加有助于实际问题的解决。因此需要综合对v r p s d p 和v r p t w 的研究，开发出针对v r p t w s d p 的求解算法。 ( 2 ) 求解v r p 的智能优化算法在解的质量方面优于经典的启发式算法，而 1 0 第一章绪论 且许多专家也认为经典的启发式算法几乎已经没有进行重大改进的余地，因此 智能优化算法现今已