（管理科学与工程专业论文）物流配送车辆路径选择研究.pdf

r 煳 r e s e a r c ho fv e h i c l e sr o u t i n gp r o b l e mf o rl o g i s t i c sa n d d i s t r i b u t i o n at h e s i ss u b m i t t e dt o d a l i a nm a r i t i m eu n i v e r s i t y i np a r t i a lf u l f i l l m e n to ft h er e q u i r e m e n t sf o rt h e d e g r e eo f m a s t e ro f e n g i n e e r i n g b y n i em i n g y i m a n a g e m e n ts c i e n c ea n de n g i n e e r i n g t h e s i ss u p e r v i s o r a s s o c i a t ep r o f e s s o rx u ed a s h e n m a y 2 0 1 1 y i 丫妒 p j i i i 大连海事大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明 本论文是在导师的指导下 独立进行研究工作所取得的成果 撰写成博 硕士学位论文 堑逾酲鲎至援堕焦垄竖珏究 除论文中已 经注明引用的内容外 对论文的研究做出重要贡献的个人和集体 均已在文中以 明确方式标明 本论文中不包含任何未加明确注明的其他个人或集体已经公开发 表或未公开发表的成果 本声明的法律责任由本人承担 学位论文作者签名 盈垒墨二 学位论文版权使用授权书 本学位论文作者及指导教师完全了解大连海事大学有关保留 使用研究生学 位论文的规定 即 大连海事大学有权保留并向国家有关部门或机构送交学位论 文的复印件和电子版 允许论文被查阅和借阅 本人授权大连海事大学可以将本 学位论文的全部或部分内容编入有关数据库进行检索 也可采用影印 缩印或扫 描等复制手段保存和汇编学位论文 同意将本学位论文收录到 中国优秀博硕士 学位论文全文数据库 中国学术期刊 光盘版 电子杂志社 中国学位论文全 文数据库 中国科学技术信息研究所 等数据库中 并以电子出版物形式出版发 行和提供信息服务 保密的论文在解密后遵守此规定 本学位论文属于 保密口在 年解密后适用本授权书 不保密耐 请在以上方框内打 4 论文作者签名 嚣培名 导师签名 钇叶 日期 矽 年乡月2 多日 叼 一 亡 中文摘要 摘要 近年来我国物流总值在高速增长 经济发展对物流配送的依赖程度也越来越 高 但是我国现代物流配送业的发展还处在起步阶段 与发达国家的技术水平还 存在较大差距 我国的现代物流在功能和发展潜力上的瓶颈在于现代物流系统的 不完善以及物流作业过程的不合理 自然形成的物流系统由于缺乏前瞻性和系统 规划 在物流资源的配置 物流网络的结构等方面 很难保证其可靠性 合理性 协调性和最优化 而物流作业过程 主要是运输过程和仓储过程 仍以经验管理 为主 基本上没有采用优化理论和方法 不合理现象随处可见 难以产生 第三 利润 对车辆路线进行优化不仅可以帮助决策者迅速做出科学正确的决定 提高 配送效率和客户满意度 而且对改善城市交通状况有重要作用 因此 对路线选 择问题的研究具有重要意义 本文首先对物流配送中的v r p 问题进行详细地阐述 包括研究背景 研究目 的和意义 并对现代物流配送 车辆路径选择问题和蚁群算法的国内外研究现状 作总结归纳 在本文的理论基础部分主要介绍了蚁群算法 其次对物流配送路径 选择系统进行总体的分析与设计 并设计了车辆路径选择模型及其求解算法 这 是论文的主要部分 最后实例实现了基于总路程最短的路径选择模型的求解算法 并对主要模块进行设计和实现 本文研究的技术路线是用m a t l a b 2 0 1 0 b 实现蚁群算法对最短路径的计算 用 c 撑语言对模块编程和设计界面 用h t m l 和j a v a s c r i p t 脚本语言加载和操作地图 数据库使用a c c e s s 数据库 关键词 物流配送 车辆路径问题 蚁群算法 建模 哆l p 英文摘要 a b s t r a c t i nr e c e n ty e a r s c h i n a sg d ph a sb e e nr a p i dg r o w t ho fl o g i s t i c sa n de c o n o m i c d e v e l o p m e n ti si n c r e a s i n g l yd e p e n d e n to nl o g i s t i c sa n dd i s t r i b u t i o ni n d u s t r y h o w e v e r m o d e ml o g i s t i c sa n dd i s t r i b u t i o n i n d u s t r yi nc h i n ai s s t i l l i n t h ee a r l y s t a g e so f d e v e l o p m e n t c o m p a r e dt ot h et e c h n i c a ll e v e lo fd e v e l o p e dc o u n t r i e st h e r ei saw i d eg a p t h ed e v e l o p m e n to fc h i n a sm o d e m l o g i s t i c sb o t t l e n e c ki st h ei m p e r f e c t i o n so fm o d e m l o g i s t i c ss y s t e m sa n dl o g i s t i c so p e r a t i o np r o c e s su n r e a s o n a b l e l o g i s t i c so p e r a t i o n s t r a n s p o r t a t i o na n d w a r e h o u s i n gm a n a g e m e n te x p e r i e n c ei n t h e p r o c e s si s s t i l l d o m i n a t e dl a r g e l y b yo p t i m i z a t i o nt h e o r ya n dm e t h o d s a n o m a l yc a l lb es e e n e v e r y w h e r e i ti sd i f f i c u l tt oh a v ea t h i r dp r o f i t o p t i m i z i n gv e h i c l er o u t e sw i l ln o t o n l yh e l pd e c i s i o nm a k e r st om a k es c i e n t i f i c a l l ys o u n dd e c i s i o n sq u i c k l ya n di m p r o v e d i s t r i b u t i o ne f f i c i e n c ya n dc u s t o m e rs a t i s f a c t i o n b u ta l s og o o dt oi m p r o v eu r b a n 蚴c c o n d i t i o n s t h e r e f o r e t h es t u d yo fc h o i c ef o rv e h i c l es c h e d u l i n gi si m p o r t a n t f i r s t t h i st h e s i sd e s c r i b e st h ep r o b l e mo fv r pi nd e t a i l i n c l u d i n gb a c k g r o u n d p u r p o s ea n dm e a n i n g a n ds u m m e du pt h em o d e ml o g i s t i c sa n dd i s t r i b u t i o n v e h i c l e r o u t i n gp r o b l e m sa n da n tc o l o n ya l g o r i t h mr e s e a r c hs t a t u s i nt h et h e o r yp a r t i n t r o d u c e st h ea n tc o l o n ya l g o r i t h m s e c o n d l o g i s t i c sa n dd i s t r i b u t i o ns y s t e mf o r r o u t i n ga n a l y s i sa n dd e s i g n a n dd e s i g no fv e h i c l er o u t i n gm o d e la n di t s s o l u t i o n a l g o r i t h m w h i c hi st h em a i np a r to ft h et h e s i s f i n a l l y a ne x a m p l eu s e dt od e s i g na n d i m p l e m e n td i s t a n c e b a s e ds h o r t e s tp a t hs e l e c t i o nm o d u l e i nt h i st h e s i s a n tc o l o n ya l g o r i t h mi su s e dt oc a l c u l a t et h es h o r t e s tp a t h a n du s e m a n a b2 010 bt oa c h i e v ei t m o d u l ep r o g r a m m i n ga n di n t e r f a c ed e s i g ni st ou s ec 撑 l a n g u a g et oa c h i e v e h t r n la n dj a v a s c r i p ts c r i p t i n gl a n g u a g e sa leu s e dt ol o a da n d m a n i p u l a t em a p s t h i st h e s i su s e st h ea c c e s sd a t a b a s e t h e s ea l et h et e c h n i c a ll i n eo f t h i st h e s i s k e yw o r d s l o g i s t i c sa n dd i s t r i b u t i o mv e h i c l e sr o u t i n gp r o b l e m a n tc o l o n y a l g o r i t h m m o d e l i n g 弓j 彳 i 飞 目录 目录 第1 章绪论 1 1 1 问题的提出 l 1 1 1 研究的背景 1 1 1 2 研究的目的和意义 3 1 2 国内外研究现状综述 4 1 2 1 国内外现代物流配送研究现状 4 1 2 2 国内外车辆路径问题 r p 研究现状 6 1 2 3 国内外蚁群算法研究现状 8 1 3 论文的组织结构 1 0 第2 章理论基础及相关技术 1 2 2 1t s p 问题 1 2 2 1 1t s p 问题的研究背景 1 2 2 1 2t s p 问题描述及其数学模型 13 2 1 3v r p 问题与t s p 问题的关系 1 4 2 2 蚁群算法 j 15 2 2 1 蚁群算法的原理 1 5 2 2 2 蚁群算法的数学模型 17 2 3 开发平台 2 0 2 3 1c 群的数据库访问技术 2 0 2 3 2m a t l a b 与c 拌的接口技术 2 0 2 3 2c 稃访问脚本语言 2 0 第3 章物流配送车辆路径选择系统的分析与设计 2 2 3 1 总体分析 2 2 3 1 1 需求分析 2 2 3 1 2 系统分析 2 2 3 2 总体设计 2 5 3 2 1 系统框架结构 2 5 3 2 2 系统功能设计 2 7 3 2 3 系统操作流程 2 8 3 2 4 系统信息流程 2 8 3 2 5 系统设计核心 2 9 第4 章物流配送车辆路径选择建模 3 1 4 1 问题描述 31 4 2 基于成本的车辆路径选择模型设计 3 2 4 2 1 模型设计 3 2 目录 4 2 2 模型的建立 3 3 4 3 基于路程的车辆路径选择模型设计 3 4 4 3 1 模型设计 3 4 4 3 2 模型的建立 3 5 4 4 算法设计 3 6 4 4 1 算法分析 3 6 4 4 2 算法模型 3 6 4 4 3 求解步骤及流程图 3 8 4 4 4 算法验证 4 0 第5 章路径选择模型的实例实现 4 1 5 1 路径选择模型的算法实现 4 1 5 2 路径选择模型的模块实现 4 3 5 2 1 开发平台 4 3 5 2 2 总体结构 4 3 5 3 客户管理模块 4 5 5 3 1 模块设计 4 5 5 3 2 模块实现 4 7 5 4v r p 主模块 4 9 5 4 1 模块设计 4 9 5 4 2 模块实现 5 0 5 5 运行过程与结果分析 5 5 第6 章总结与展望 5 8 参考文献 6 0 攻读学位期间公开发表的论文 6 4 致谢 6 1 z 物流配送车辆路径选择研究 1 1 问题的提出 第1 章绪论 1 1 1 研究的背景 近几年 随着我国经济的飞速发展 国民生活的水平迅速提高 人们对物资 的需求也越来越多 促进了生产业 制造业和物流业等各行各业的蓬勃发展 传 统的物流企业大多是自己负责仓储 运输及配送 大大增加了企业的经营负担与 成本 因此 专家们提出 物流企业应该向专业化发展 于是 第三方物流 应 运而生了 它是供方与需方之外的第三方物流企业 物流配送企业 它主要负 责仓储 运输与配送 是供应商与客户之间的纽带 是整个物流过程中的重要环 节 今天 随着经济的日益全球化 作为 第三利润源泉 的现代物流业 其发 展正受到政府 企业界和学术界的高度重视 而配送是物流过程中直接与客户相 联系的重要环节 其地位尤为突出 随着企业管理的不断现代化 信息网络架构基础上的电子商务被建立起来 电子商务的理念将人们迅速地引向了瞬间交易 它的应用构造了企业与供应商和 客户间相互连结的网络 电子商务下的物流配送改变了以往物流信息的接收和传 递方式 它按照客户的需求 统一对货物进行信息管理和调度 最后将货物送至 收货人 使配送方式实现了信息化 网络化 自动化 智能化 柔性化等 这种 统一管理调度的配送方式使得整个配送管理流程可视化 它代表了配送发展的主 方向 因而拥有良好的发展前景和现代化趋势 目前总结四点如下 1 集约化 区域化趋势 配送的集约化是由传统的单个企业的独立化配送活 动发展为整个企业甚至整个行业的团体配送活动模式 这样不仅提高了车辆的使 用效率 减少了城市的交通拥堵 更为社会带来了社会效益和经济效益 区域化 是将配送不仅仅局限在某个市内 而是将范围扩大到城市间 省间甚至是国家间 或更大范围的配送 使配送活动向国际化方向发展 2 信息化 自动化和机械化趋势 配送的信息化是利用计算机网络技术构建 一个能够对货物 车辆 人员和客户等基本信息和整个配送流程实行管理和调度 第1 章绪论 的配送系统 例如辅助订货系统 辅助分拣系统 辅助调度系统等 配送的自动 化和机械化是将原有的人工配送作业发展为无人操作的自动化物流设施 例如自 动分拣机 自动搬运系统等 配送的信息化 自动化和机械化为快速 准确 高 效 优质的配送服务提供了技术基础 3 条码化 数字化和组合化趋势 为了配合配送流程自动化 机械化的发展 趋势 条形码技术在这一领域被广泛的应用 将货物贴上条形码 使货物与自动 机械归并为组合化货物单元 条码技术解决了人工数据录入效率低下的问题 大 幅度的提高了分拣和配货的速度 如今此技术也在其它许多行业中被广泛应用 4 配送方式多样化趋势 随着市场需求的不断变化 不但配送的活动和范围 明显扩大 配送的方式也在日趋多样化 在配送作业中 除了传统的配送形式外 还衍生出多种新的配送方式 如产地直送 即时配送 共同配送 托盘配送 定 时定路线配送等 其中 产地直送有效地缩短并优化了配送流程 降低了配送成 本 特别是对需求量大 订购周期稳定的货物 其优势更加明显 多种配送方式 组合应用意在寻求配送效率和配送效益的最优化 虽然物流配送的发展前景良好 但是物流成本在企业运作费用中一直占有很 高的比重 这使得成本竞争成为企业竞争的最有效手段之一 据调查 物流成本 占生产成本的4 0 左右 而运输成本在物流成本中所占的比例是最高的 特别在 我国 物流成本占g d p 比重高达2 0 左右 远远高于发达国家 因此 运输调度 问题是物流配送中的关键问题之一 而运输成本的高低主要取决于运输方式的选 择 车辆的调度和路径的选择等问题 配送路线优化是运输合理化的重要内容 配送路线是否合理对配送速度 成本 效益影响很大 因此 本文将针对其中的 车辆路径问题作较深入地研究 配送活动中涉及了许多需要被管理者优化决策的问题 用计算机对这些问题 提供技术支持 是物流作业中比自动化 信息化更高层次的应用 是物流业的智 能化在电子商务环境下发展的一个新趋势 用计算机对车辆路径选择问题提供决 策支持 不仅可以提高决策的准确度 加快对客户需求的响应速度 更可以提高 服务质量和客户的满意度 降低配送成本 因此 如何让计算机对物流配送中的 车辆路径问题进行分析计算 并输出最佳路线方案 成为众多学者研究的焦点 叫 1 物流配送车辆路径选择研究 车辆路径问题 r o u t i n gv e h i c l ep r o b l e m s v r p 就由此诞生了 车辆路径问题的求解方法分为精确算法和启发式算法 由于很难用精确算法 求解 启发式算法是求解车辆路径问题的主要方法 启发式算法的研究分为三个 阶段 第一阶段为简单的启发式算法 如 运筹学方法 线性规划方法 非线性 规划方法 动态规划方法 组合优化方法 分支定界法 爬山法 贪婪法等 这 些方法虽然取得了不错的效果 但并没有持续多久 就出现了求解时间上的问题 直到1 9 8 5 年车辆路径问题被证明是n p h a r d 问题后 学者们对该问题的研究开始 进入第二阶段 第二阶段为基于一般启发式算法的近似优化算法 如 指派法 集合分割法和它们之间的混合算法等 第三阶段是较新的方法 如 禁忌搜索算 法 模拟退火算法 遗传算法 人工神经网络算法 蚁群算法以及它们之间或它 们和一般启发式算法之间的混合算法等人工智能算法 这些方法研究至今 已取 得了很好的进展 能够在一个可以接受的时间范围内求出问题的近似最优解 1 1 2 研究的目的和意义 中国加入w t o 后 国际上的许多跨国物流企业纷纷进军中国物流市场 加大 了我国物流业的竞争力 客户对物流配送的要求也越来越高了 怎样能够低成本 的将货物快速及时的送到客户手中以提高客户满意度是企业值得思考的重要问 题 然而 我国的物流配送管理还有许多环节不够完善 与国外物流企业的技术 和管理水平相比尚有一定差距 若要跟上现代物流的发展 提升企业的管理和决 策水平显得越来越重要 对车辆路线进行优化不仅可以帮助决策者迅速做出科学 的决定 还可以帮助企业降低成本 提高效率 提升客户满意度 因此 对配送 路径选择问题的研究具有重要意义 我国的现代物流在功能和发展潜力上的瓶颈在于现代物流系统的不完善以及 物流作业过程的不合理 自然形成的物流系统由于缺乏前瞻性和系统规划 在物 流资源的配置 物流网络的结构等方面 很难保证其可靠性 合理性 协调性和 最优化 而物流作业过程 主要是运输过程和仓储过程 仍以经验管理为主 基 本上没有采用优化理论和方法 不合理现象随处可见 难以产生 第三利润 现 代物流系统正朝着自动化 信息化 集成化的方向快速发展 一个好的物流系统 第1 章绪论 的建立与优化已经不可能通过人的经验手段或数学的解析推理来完成 因此计算 机建模以辅助人工决策作为一种先进的解决问题的手段被越来越多地应用到现代 物流系统的分析评价中 本文针对上述情况 研究设计一个应用于物流配送中的车辆路径选择系统 并对车辆路径选择问题进行建模和算法设计 最后实例实现 以验证模型和算法 的有效性 1 2 国内外研究现状综述 1 2 1 国内外现代物流配送研究现状 在美国 物流作业流程的合理化已从二十世纪六十年代开始受到普遍重视 美国企业对物流配送采取了几种措施 主要是将老式仓库改建成配送中心 对装 卸 搬运和仓库通过电脑管理实行标准化操作以及对连锁店组建统一的配送中心 连锁店的配送中心有多种 主要是仓储型 零售型和批发型 在日本 零售业是 首先引入物流系统的行业之一 便利店作为其新的零售形式迅速发展 现已遍及 日本 这种新的零售业需要新的物流技术来管理 以保证供应链的顺畅 因此 日本的物流配送具有分销渠道发达 配送共同化等特点 就配送中心建设方面 日本是第一个提出物流园区这一概念的国家 日本的物流园区主要是由政府推进 建设的 政府不仅为物流园区提供规划策略 出台相关政策 还加大资金投入 加强园区内的基础设施建设 通过这些措施 物流园区不仅成功吸引了大量国内 外的物流企业入驻 加大了企业间的竞争 而且加快了其专业化 信息化 自动 化的发展和物流技术水平的提高 在欧洲 特别是在德国 物流配送是根据客户 订单中的需求 在各个配送点进行捡货 配货 最后将货物送到收货人手中 德 国物流园区的发展也与政府有紧密的关系 德国政府不仅投入基础设施的建设 还将物流园区的规划建设同交通干线和枢纽的规划建设联系起来 物流园区的现 代化发展也受到政府的重视 各种信息化 自动化 电子化的技术和设施以及现 代化管理模式也被推广应用 从德国的零售业发展过程可以看出 德国对物流园 区的规划和建设具有前瞻性 由外国一些工业发达国家的物流配送发展现状可以 看出 政府对物流配送的规划和发展都是十分重视的 2 物流配送车辆路径选择研究 相比之下 我国在二十世纪七十年代之前几乎还没有 物流 一词 但物流 活动的各个环节早已在许多领域中被使用 从九十年代起 物流配送开始受到广 泛的关注和蓬勃的发展 许多城市纷纷建立起配送中心 随着物流业的持续发展 城市配送业也日益受到重视 我国越来越多的城市都开始兴建物流中心 配送中 心 国内专家学者也开始对物流配送的知识和技术进行学习研究 物流基础设施 开始改善 物流技术水平也有了很大的提高 但是 我国的物流业在现阶段的发 展还很不成熟 有许多新兴的中小型物流企业尚处于起步期 管理和技术水平尚 未发展完善 导致我国整体的物流水平参差不齐 由此看出 国内配送业主要存 在以下两个问题 1 配送各环节不够集约化 我国现阶段的配送方式 主要是单个企业的个别化 分散化的配送活动 即 配送作业主要由各专业公司独立运作 缺乏统一性 配送中心也还没有发挥出整 合信息和资源 组织协调 管理调度等重要作用 导致信息冗余 效率低下 流 通费用多 客户响应度低 服务质量较差 不能满足客户的多种服务需求 因此 我国的物流配送应加快集约化步伐 将传统的订货 装卸 存储 分拣 流通加 工 运输 信息管理等分散的 跨企业的活动进行有机整合 用一个系统对整个 配送作业流程统一管理和调度 以节约流通费用 提高经济效益和客户满意度 2 现代化技术水平较低 目前 计算机在我国物流配送领域的应用程度较低 仅局限在对日常事务的 管理 而配送活动中的许多需要决策的重要问题 如配送中心的选址 车辆的调 度 路径的选择 货物的组配及最优库存等方面 还处于人工或半人工状态 能 够辅助决策的物流信息系统的开发相对落后 因此 我国应向物流管理信息化 物流资源社会化 物流体系综合化的方向发展物流配送业 3 综上所述 虽然近年来我国物流总值在高速增长 经济发展对物流配送的依 赖程度也越来越高 但是我国现代物流配送业的发展还处在起步阶段 与发达国 家的技术水平还存在较大差距 需要我们理论联系实际 结合国情 对物流配送 业提高重视和深化制度改革 对物流基础设施加大资金投入 并培养物流配送方 面的专业人才 以促进今后我国物流配送业的技术提升和长期发展 第1 章绪论 1 2 2 国内外车辆路径问题 v r p 研究现状 车辆路径问题的求解方法分为精确算法和启发式算法 精确算法的v r p 求解 方法主要有两种 图模型法和数学模型法 整数规划法 穷举搜索法 e x h a u s t i v e s e a r c hm e t h o d 贪婪算法 g r e e d ym e t h o d 4 1 动态规划法 d y n a m i cp r o g r a m m i n g a l g o r i t h m 线性规划算法 l i n e a rp r o g r a m m i n ga l g o r i t h m 分支界定法 b r a n c h d e l i m i t a t i o na a l g o d t h m 树状寻优法等算法都属于精确算法 这些算法取得了一 些研究成果 例如 m l f i s h e r 提出了解决车辆路径日常问题的k t r e e s 最优解算 法 5 m p a d b e r g 等提出了解决大规模旅行商问题的分枝剪枝算法 6 1 c h r i s t o f i e d s 等提出了用动态规划法扩大空间变量范围来解决v r p 问题 7 1 f u m e r o 等提出了对 拉格朗日松弛问题的改进方法及子梯度算法 引 l o r e n al u i z 等提出了列生成方法 的优化算法 改进了列生成法存在能力受限的p m e d i a n 问题等1 9 j 精确算法虽然提出的较早 且应用也比较广泛 但由于它只局限于逻辑模型 使得其表现太过于抽象 求解结果很难被直观的展现在人们眼前 虽然精确算法 在早期可以在一定的数据范围内求得最优解 但是随着现代物流交易的次数与日 剧增 系统规模的不断扩大 用精确算法进行求解不仅求解过程非常复杂 而且 难以求出最优解 在用数学模型对物流系统进行分析时 需要进行大量的假设或 简化 这使得求出的结果与实际状况难免存在误差 相比之下 启发式算法能很 好的避免以上种种问题 因此 启发式算法成为求解车辆路径问题的主要算法 1 9 5 9 年 d a n t z i g 和r a m s e r 最先提出了车辆路径问题 v r p 1 1 0 l 之后很快引 起了数学 物流 计算机及相关领域的专家学者和管理者的重视 从那时起 v r p 成为了该领域的热点课题并持续至今 几十年间 专家们对该问题进行了大量的 研究实验 在理论和实践上取得了很多成果 1 9 6 4 年 c l a r k e 和w r i g h t 在d a n t z i g 和r a m s e r 的算法基础上做了改进 提出了 c l a r k e w r i g l l t 启发式节约算法 用来辅助对车队配送路线的决策问题1 1 1 模拟退火 算法具有全集搜索功能 并且收敛速度快 在v r p 问题中被研究应用 1 9 9 3 年 o s m a n 研究了模拟退火算法在v r p 路线分组问题中的应用情况1 1 2 2 0 0 1 年 b e n t 等为了降低运输成本 在使用大邻域搜索法降低费用之前 对车辆路线的数量用 模拟退火算法进行最小化并获得了成功 1 3 l 2 0 0 2 年 o m b u k i 提出了一种由遗传算 适 物流配送车辆路径选择研究 法和禁忌搜索算法组成的混合算法 首先用遗传算法对路线分组进行仿真建模 然后用禁忌搜索算法对路线进行优化 1 4 由于遗传算法能够很好的求解组合优化 问题 许多学者都对启发式算法进行优化组合 以便更好的解决v r p 问题 这时 期涌现出许多研究成果 相关的参考文献已有几百篇之多 同年 p a o l ot o t h 等在 其著作中全面分析并总结了车辆路径问题的最新研究成果和未来发展趋势 1 5 1 1 9 9 4 年 m l f i s h e r 对车辆路径问题做了阶段性总结 他把启发式算法的研究分为 三个阶段 1 6 1 第一阶段为2 0 世纪6 0 至7 0 年代 这一阶段的主要方法是简单的启发 式算法 如 运筹学方法 线性规划方法 非线性规划方法 动态规划方法 组 合优化方法 分支定界法 爬山法 贪婪法等 这些方法虽然取得了不错的效果 但并没有持续多久 就出现了求解时间上的问题 直到1 9 8 5 年s a v e l s b e r g h 提出了车 辆路径问题是n p h a r d i h j 题后1 1 7 l 学者们对该问题的研究开始进入第二阶段 第二 阶段为2 0 世纪7 0 至8 0 年代 这一阶段的主要方法是基于一般启发式算法的近似优 化算法 如 指派法 集合分割法和它们之间的混合算法等 第三阶段为2 0 世纪 8 0 年代至今 这一阶段的方法是较新的求解方法 如 禁忌搜索算法 模拟退火 算法 遗传算法 人工神经网络算法 蚁群算法以及它们之间或它们和一般启发 式算法之间的混合算法等人工智能算法 这些方法研究至今 已取得了很好的进 展 能够在一个可以接受的时间范围内求出问题的近似最优解 在有时间窗的车辆路径问题 v r 删的研究方面 1 9 9 4 年 t h a n g i a h 设计了 一种由模拟退火和禁忌问题搜索组成的混合遗传算法来解决带时间窗的v r p 问 题 取得了有效的成果 1 8 l 1 9 9 5 年 t h a n g i a h v 提出了一种以遗传算法为基础 用 入一交换算法对线路组进行优化i 约g i d e o n 系纠1 9 1 9 9 8 年 b e r g e r 提出了一个将 时间窗和遗传算法进行混合的混合遗传算法 2 0 1 1 9 9 9 年 b u l l r t h e i m e r 等提出了将 蚁群算法应用于车辆路径问题中 并设计了一种改进的蚁群算法对其求解 该算 法虽然优化了其搜索速度 但没有优化最优解 2 1 j 同年 g a m b a r d e l l a 等提出一种 多重蚁群算法 该算法在蚁群算法的基础上结合2 o f f 交换法和候选城市的路径选 择策略对v r p 问题进行联合求解 但其最优解仍没有多少改善 2 2 1 2 0 0 4 年 b e l l 等提出了对多重蚁群算法的改进算法 搜索速度有了提高 但是其求解范围只能 限制在一定规模内 2 3 j 同年 r e i m a n n 等提出了一种能求解大规模v r p 问题的基于 第1 章绪论 节约法的蚁群算法 解决了求解范围受限的问题 2 4 l 但是其求解过程过于复杂 不能被广泛应用 与国外相比 国内对车辆路径问题的研究起步较晚 是从2 0 世纪9 0 年代后才 开始的 落后于国外约三十年 研究成果也相对较少 但也取得了一些成果和进 展 1 9 9 8 年 蔡延光等研究了并行表搜索算法 模拟退火算法等算法在多重运输 调度问题上的应用 取得了一些成果 2 5 1 2 6 1 2 0 0 0 年 谢秉磊 李军等研究了遗传 算法在有时间窗的v r p 问题和非满载的v r p i h 题上的应用 2 7 1 2 8 l 2 0 0 1 年 袁庆达 等研究了怎样用禁忌搜索算法对配送路线的初始解进行优化 2 9 1 在对v r p t w i 题 的研究方面 张丽萍等于2 0 0 2 年提出了一种改进遗传算法 该算法成功地克服了 遗传算法的 早熟性收敛 问题 得到了更接近的最优解 3 0 l 2 0 0 4 年 李宁等设 计了应用于有时间窗的v r p 问题的粒子群算法 构建了该问题的粒子表达方法 3 2 0 0 3 至2 0 0 4 年 崔雪丽 马良等尝试用蚂蚁算法求解v r p i j 题 3 2 3 3 l 刘云忠等也 将蚁群算法用于解决v r p 问题 但是此算法存在搜索速度延迟等缺点 不能很好 的应用于车辆路径问题 3 钔 国内在这方面的理论研究已取得了较大的进展 但对实际应用系统的开发研 究才刚刚起步 尽管如此 我国的经济和科技的飞速发展已让世界惊叹 相信在 不久的将来 我国的经济增长和科学发展更会上升到一个新台阶 目前 我国的 商品经济已比较发达 但物流配送能力还有很大欠缺 事实表明 我国的物流配 送业需要更高程度的信息化 自动化和机械化 迫切需要加大物流基础设施的投 入力度和建设能够统一规划调度的物流配送中心 美国 同本 德国等发达国家 的对物流配送的研究起步较早 经验和技术也很成熟 他们的管理经验和自动化 技术水平对我国物流配送业的发展具有很好的借鉴意义 我们应该在学习国外经 验技术的基础上 结合国情 促进我国物流配送业的技术提升和长期发展 1 2 3 国内外蚁群算法研究现状 蚁群算法自被提出以来 已有十余载 其理论和应用研究都取得了非常大的 进展 从只能对一维静态问题的优化发展到可以对多维动态问题的组合优化 从 只能解决离散事件的研究发展到可以解决连续事件 其研究领域也从单一的旅行 多 0 t 4 物流配送车辆路径选择研究 商问题拓展到各个应用领域 不仅在软件方面 蚁群算法在硬件实现上也取得了 一定的进展 另外 在其模型优化改进和与其它仿生算法相结合的研究方向上也 取得了许多成果 从而使这种新一代仿生优化算法展现出广阔的研究空间和发展 前景 3 5 1 3 6 l 1 9 9 2 年 d o r i g om 最早提出了蚁群优化算法一蚁群系统 a n ts y s t e m a s 并将其应用于求解旅行商问题 根据菲尔蒙更新方式的不同 他还给出了三种信 息素更新算法 蚁环算法 a n t c y c l es y s t e m 蚁量算法 a n t q u a n t i t ys y s t e m 和蚁 密算法 a n t d e n s i t ys y s t e m 3 7 1 其中蚁量算法和蚁密算法是对局部信息的更新 而蚁环算法是对整体信息的更新 因此蚁环算法求解v r p 问题的效果最好 他还 分析了蚁群初始分布对解的影响 提出了加强精英蚂蚁影响的精英策略 e l i t i s t s t r a t e g y 所谓精英蚂蚁 就是在众多遍历所有节点的蚂蚁中 走出最优路径的蚂 蚁 研究发现 精英蚂蚁的数量选择要限于一个范围内才能达到最优 若低于该 范围 不利于蚂蚁尽早发现更好的路径 而高于该范围 则精英蚂蚁很可能在搜 索早期陷入局部最优解 导致结果偏差 1 9 9 6 年 为了解决a s 的缺陷 g a m b a r d e l l a 和d o r i g om 又提出了一种改进的蚂 蚁算法一蚁群系统 a n t c o l o n ys y s t e m a c s t 3 羽 该系统是以a n t q 算法f 3 9 j 为基 础的 a c s 的算法思想是 蚂蚁在未遍历所有路径的搜寻过程中采用负反馈机制 即每只蚂蚁从一个节点搜寻到另一个节点时 这条路径上的信息素都按一定规则 被消除一部分 从而对信息素浓度进行局部调整 在所有寻优蚂蚁结束遍历后 会用全局信息对信息素浓度进行调整 并且只对最优路径上的信息素浓度进行加 强 a c s 的好处在于它克服a s 了中容易陷入局部最优解的问题 负反馈机制的消 除规则是 一 1 一p 晚 肚l 其中0 p o 且d f 一 i j e v i 为已知 设稚f l 篓妥歹燮氅婪 2力lo 队肌 边 j 不在最优路径上 卜 7 则t s p 问题的数学模型可以用下面的线性规划方程表示 m i n z 2 d 驴 2 3 善勤乩f y s t 乩缈 寥玎s m i sc v 勤 o 1 f 矿 2 4 其中 蚓表示集合s 中包含于图g 的顶点数 式 2 3 为所求目标函数 所求解 即为遍历所有顶点的总权数最小的h a m i l t o n 回路 式 2 4 的前两个约束保证每个 顶点只有一条边进和一条边出 式 2 4 的第二个约束保证了图s 中不出现子回路 组合优化问题所求得的解往往不唯一 有时可能存在多个解 但所求得的最大或 最小值总是唯一的 2 1 3v r p 问题与t s p 问题的关系 d a n t z i g 和r a m s e r 两位学者提出 v r p 问题可以作为t s pi h l 题的推广问题求 解 v r p 问题可以说是具有一系列的约束条件的t s p 问题 这一系列的约束条件 包括 客户有一定的订货需求和订货数量 要求配送中心将货物在客户规定的时 物流配送车辆路径选择研究 问内送到 配送车的载重量约束 即载重量满足其路线上所有销售点的订货量 配送车每次送货的最大行驶距离限制等 因此 可以说v r p 问题的每个子配送路 线都是一个t s p 问题 v r p 问题是一个有一系列约束条件的多路t s p 问题 也就 是说 对v r p 问题的求解可以转化为对t s p 问题的求解 即可以用求解t s p 问题 的方法来求解v r p 问题 4 9 1 因此本文将参照t s p 问题的数学模型来建立路径选择 的数学模型 2 2 蚁群算法 2 2 1 蚁群算法的原理 1 蚂蚁寻食 蚁群算法是通过模拟自然界蚂蚁的寻径方式而研究出的一种仿生算法 经研 究发现 蚂蚁在寻找食物的过程中 会在经过的路径上留下一种物质 叫信息素 也n t t 多 t 激素 这种信息素能够帮助蚂蚁找到从蚁穴到食物的最短路径 原理是 蚂蚁在觅食时 会随机选择不同的路径前行 当找到食物目标时 从蚁穴通往食 物的路径可能有多个 而最佳路径只是其中的一个 随后的其他蚂蚁通过感知前 面蚂蚁在不同路径上留下的信息素强弱来选择路径前进 同时这些蚂蚁在前行时 也会留下信息素 随着觅食蚂蚁的增多 短距离路径上信息素会越来越强 而长 距离路径上的信息素会逐渐挥发甚至消失 最后从蚁穴到食物之间就会被蚂蚁找 到一条最短路径 蚂蚁就是通过信息素来进行信息交换和彼此协作 以达到高效 运回食物的目的 蚂蚁寻食的过程可以简化用下图表示 第2 章理论基础及相关技术 图2 1 蚂蚁的寻食过程 f i g 2 1t h ep r o c e s so fs e e kf o o d o fa n t s 假设从蚁穴s 到食物e 有两条路线s a e 和s b e 两只速度相同的蚂蚁a 和b 同时从s 点出发 分别随机选择一条路线s a e 或s b e 两只蚂蚁的速度均为每个 时间单位前进一步 左图为前进了5 个时间单位时的情况 走s a e 的蚂蚁找到了 食物 而走s b e 的蚂蚁只走了路程的一半到达b 点 右图为经过1 0 个时间单位 时的情况 走s a e 的蚂蚁找到食物并已返回蚁穴s 而走s b e 的蚂蚁才到达e 点 假设蚂蚁每个时间单位会留下1 个单位的信息素 则经过2 0 个时间单位后 蚂蚁a 沿路线s a e 往返了2 趟 平均每处留下4 个单位的信息素 而蚂蚁b 沿路 线s b e 只往返了一趟 平均每处留下2 个单位的信息素 其比值为2 1 根据两 只蚂蚁在两条路线上留下信息素的比值 蚁群在路线s a e 和s b e 上分别增派的蚂 蚁数为2 和1 再经过2 0 个时间单位后 两条路线上的信息素单位变为1 2 和4 比值为3 1 蚁群再在路线s a e 和s b e 上分别增派的蚂蚁数为3 和1 若按以上 规律继续进行 根据信息素的指导 最终所有的蚂蚁都会选择路线s a e 而放弃路 线s b e 路线s a e 就是蚁群找到的从蚁穴到食物的最佳路径 2 自然蚁群与人工蚁群 基于自然界的蚂蚁寻食过程 可以构造人工蚁群来求解最优路径选择问题 蚂蚁在人工蚁群中被看做具有简单功能的工作单元 两者都是根据信息素的浓度 来选择路径 不同之处是人工蚁群具有一定的记忆力 已访问过的节点不会重复 物流配送车辆路径选择研究 访问 同时 人工蚁群是通过算法有意识地选择路径而不是随机选择 即蚂蚁到 每个节点的距离为已知 人工蚁群算法在蚂蚁的搜寻过程中 通过信息素的概率分布来决定城市的转 移 信息素的更新方式有两种 一种是信息素的挥发 就是蚂蚁在运动过程中留 下的信息素浓度会随时间按一定规律自动减弱 这是为了避免蚁群算法在计算过 程中迅速陷入局部最优解 另一种是信息素的增强 在所有蚂蚁找到的路径中选 择最优路径 对该路径上的弧进行信息素的增强 这种信息素的更新方式是基于 蚁群算法的三个独特机制 选择机制 路径上的信息素残留越多 蚂蚁选择该 路径的概率越大 更新机制 某路径被蚂蚁经过的次数越多 该路径上的信息 素就会越大 同时 所有路径上的信息素也会随时间以一定的速率慢慢挥发 协调机制 蚂蚁就是通过信息素的浓度来彼此沟通协作的 2 2 2 蚁群算法的数学模型 在描述蚁群算法的数学模型之前 先对t s p 问题做简单介绍tt s p 问题即旅 行商问题 是由k m e n g e r 于1 9 3 2 年提出的 它可以描述为 一名推销员要到若 干个城市去推销商品 他从某个城市出发 途径所有的城市仅一次 然后回到出 发点 问如何选择一条路径使总行程最短 t s p 问题属于n p 完全问题 它的特点 是易于描述但求解困难 t s p 问题也属于组合优化问题 而且众多领域的优化问 题都可以通过t s p 问题求解 如交通线路的规划 大型电路的设计 物流配送及 计算机网络路由等 概括来讲 只要是需要遍历所有节点且只一次的求总权数最 小的问题都可以归结为t s p 问题 本文所研究的v r p 问题可以看做一个有多个约 束条件的多路t s p 问题 因此本文可以用求解t s p 问题的算法来求解v r p 问题 为了说明蚁群算法 本文以t s p 问题为例来描述蚁群算法的数学模型和求解步骤 模型中的符号 m 为蚁群中蚂蚁数量 k 1 1 9 m n 为需要遍历的城市数 d o i j 1 2 n 表示城市i 到j 的距离 第2 章理论基础及相关技术 b i t 表示t 时刻位于城市i 的蚂蚁数 则有小t 所o o 表示t 时刻城市i 到j 的路径上留下的信息素痕迹 初始时刻 各条