（机械电子工程专业论文）基于蚁群算法的多配送中心车辆调度问题的研究.pdf

基于蚁群算法的多配送中心车辆调度问题的研究 摘要 物流配送是现代化物流系统的一个重要环节，它是指按用户的订货要求， 在配送中心进行分货、配货，并将配好的货物及时送交收货人。在配送业务中， 存在许多优化决策问题，其中配送车辆调度问题对配送企业加快配送速度、提 高服务质量、降低配送成本及增加经济效益影响较大。根据配送中心数目的多 少，物流配送车辆调度问题有单配送中心车辆调度问题和多配送中心车辆调度 问题之分。在城市物流体系中，往往存在多个配送中心。因此，对多配送中心 车辆调度问题的研究具有重要的现实意义。 同时物流配送车辆调度问题作为一个n p ( n o n d e t e r m i n i s t i cp o l y n o m i a l 多 项式复杂程度的非确定性问题) 难题，随着客户数量的增加，可选的配送路径 方案数量将以指数速度急剧增长。因此，用启发式算法求解该问题就成为人们 研究的一个重要方向。本文将在建立多配送中心车辆调度问题数学模型的基础 上，研究采用蚁群算法对其求解。 本文围绕多配送中心车辆调度问题开展研究，主要做了以下工作： ( 1 ) 本文分析了分解法求解多配送中心车辆调度问题的数学模型，并在 此基础上结合整体法思路给出了整体法求解多配送中心车辆调问题的数学模 型。 ( 2 ) 本文采用蚁群算法来解决车辆的路径选择问题，同时结合分解法和 整体法给出了蚁群算法解决多配送中心车辆调度问题的算法模型和实现过程。 ( 3 ) 对蚁群算法的各个参数的特性进行了分析，并在m m a s 蚁群算法 ( m a x - m i n a n ts y s t e m ) 的基础上对蚁群算法进行了一定的改进。 ( 4 ) 对本文给出的算法模型进行了试验计算，并分析了分解法和整体法 各自的特点。 关键词：物流配送，车辆调度，蚁群算法，多配送中心，时间窗 t h er e s e a r c ho fm u l t i d e p o t s1 i j e h i c l es c h e d u l i n gp r o b l e m b a s e d0 1 3a n tc o l o n ya l g o r i t h m a b s t r a c t d is t r i b u t i o 1isa ni m p o r t a n te l e m e n ti nm o d e r n1 0 9 i s t i c ss y s t e r a i tif i c l u d e sp i c k ir i gu pg o o d sf r o md i s t r i b u t i o r lc e n t e ra n dd e l i v e r i n g g o o d s t ot h ec u s t o m e f so nt i m e a m o n gd is t r i b u t i o nb u s i n e s st h e r ea r e m a n yo p t i m i z i n gs t r a t e g i e s t h ev e h i c l es c h e d u l ir i gp r o b l e mh a sg r e a t e f f e c to ni m p r o v ir i gd i s t r i b u t i o ns p e e d ，q u a li t yo fs e r v i c ea n de c o n o m y b e n e f i t a c c o r d in gt ot h en u m b e r o fd i s t r i b u t i o nc e n t e r ，t h ev e h i c l e s c h e d u l i n gp r o b l ( 3 mc a r lb ed i v i d e di n t os i n g l e - d e p o tv e h i c l es c h e d u l i n g p r o b l e ma n dm u l t i d e p o t sv e h i c les c h e d u l i n gp r o b l e m t h em o d e r nc i t y l o g is t i c ss y s t e mu s u a l l yh a sm o r et h a no n ed e p o t s ot h i sp a p e rh a sb o t h t h e o r e t i c a la n dp r a c t i c a lv a l u e a san p h a r dp r o b l e m t h ed is t r i b u t i o nr o u t i n gp l a r t so fm u l t i d e p o t s v e h i c l es c h e d u l i n gp r o b l e mw i l lir l c r e l ；t s ee x p o n e n t i a l l ya l o n gw i t ht h e a d d in go fc u s t o m e f s s oi tb e c o m e sa ni m p o r t a n ts t u d y i n gt r e n dt os o l v e t h ev e h ic l es c h e d u li n gp r o b l e mw i t hh e u r is t i ca l g o r i t h m o nt h eb a s i s o fb u i1 d i n gt h em o d e lo fi i i u l t i d e p o t sv e h i c l es c h e d u l i n gp r o b l e m t h i s p a p e rs t u d i e st os o l v et h ep r o b l e mw i t ha n tc o l o n ya l g o r i t h m f o c u s i n go i lr a u l t i d e l ) o t sv e h i c l es c h e d u l i n gi ) r o b l e v a t m s9 a p e r m a i n l yir l c l u d e st h er l e x tc o i l t e n t s ： ( 1 ) t h isp a p e ra n a l y s e st h em o d e lo fm u l t i d e p o t sv e h i c l es c h e d u l i n g p r o b l e ms 0 1v in gw i t hs e p a r a t i o i lm e t h o d b a s e do nt h isa n a l y s isa n d c o m b ir l e sw i t ht h e o r yo fh 0 1 i s t i cm e t h o d ，t h i sp a p e ri f i t r o d u c e st h em o d e l o fi l l u l t i d e p o t sv e h i c l es c h e d u l i n gp r o b l e ms o l v i n gw i t ht h eh o l i s t i c m e t h o d ： ( 2 ) t h isp a p e ra d o p t sa n tc o l o n ya l g o r i t h mt os o l v et h er o u t i n g1 r o b l e m a tt h es a m et i m ec o m b i f t o sw i t ht h es e p a r a t i o i lm e t h o da n dh o l i s t i cm e t h o d t h isp a p e rir l t r o d u c e st h em o d e lo fm u l t i d e p o t sv e h i c l es c h e d u l i n g p r o b l e ms 0 1v i n gw it ht h ea n tc o l o i l ya l g o r i t h m ( 3 ) a 1 s ot h i sp a p e ra n a ly s e st h ep a r a m e t e r so ft h ea n tc o l o n ya l g o r i t h m a n di m p l o v e st h et h ea n tc 0 1 0 i l va 】g o t i t h mb a s e do nm a x m i l 3a n ts y s t e m ( 4 ) d or e s e a r c ho nt h em o d e l si n t r o d u c e db yt h i sp a p e r ，a n da n a l y s e s t h es p e c i a l t yo fs e p a r a t io i lm e t h o da n dh 0 1 is t icm e t h o d k e y w o r d s ：d is t r i b u t i 0 1 3 ，v e h ic 1es c h e d u l i n g ，a n tc o l o n ya l g o r i t h m m u l t i d e p o t s t i m ew i n d o w s 实例4 1 的已知条 分解法实验数据 整体法实验数据表 实例5 1 的已知条 分解法实验结果 整体法实验结果 表清单 件表3 6 3 7 3 7 件表4 9 4 9 4 9 1 2 4 4 表袁 q u 1 4 5 表表 2 3 5 5 表表 独创性声明 本人声明所里交的学位论文是本人在导师指导下进行的研究工作及取得的研究成 果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得 金匿王些盍堂 或其他教育机构的学位 或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示谢意。 学位论文作者签名：舞这王 签字日期：z 秭年争月刁日 学位论文版权使用授权书 本学位论文作者完全了解金魍王些太堂有关保留、使用学位论文的规定，有 权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借 阅。本人授权金壁王些太堂可以将学位论文的全部或部分内容编入有关数据库进 行检索可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：备岔叁 导师签名： 玄芬叠 ， 签字日期：z 嘭年争月刁日签字日期：沙彩年尹月矽日 学位论文作者毕业后去向： 工作单f = ；7 ： 通讯地址： 电话 邮编 致谢 本论文是在导师张建军副教授悉心教诲和无微不至的关怀下完成的。从论 文的选题、论文的架构及写作等方面，无不凝聚着张老师的心血。三年来。张 老师无论是在学习上还是在生活上都给了我极大的关心和帮助，使我得以顺利 完成硕士研究生阶段的学习。在我所取得每一点的成绩中都倾注了张老师的大 量心血。张老师的渊博知识、严谨的治学态度、敏锐的学术思想、以及积极进 取的科研精神是我终生学习的楷模。在此谨向张老师致以衷心的感谢和崇高的 敬意! 衷一b 的感谢在三年来一直关心我和培养我的分布式控制实验室的张利老 师，三年来张利老师无论在生活上或在学习上都给了我很大的支持和鼓励，是 她对我们实验室弟子母亲般的关心和爱护，让我在实验室三年学习过程中感到 了家的温暖。感谢韩江洪研究员对我的指导和帮助，他严谨的治学态度和工作 作风始终是我学习的楷模。 感谢我的师兄王跃飞老师、毕翔老师、王世福等在项目研发中的无私帮助。 感谢我的好朋友周晓峰、赵春亮、郭松青、陆荣峰、刘波、张天华、周明发等 在生活和学习上对我的关心和帮助，以及我的师弟师妹们，在项目开发中对我 的支持。特别感谢张群、谢成童、应建平同学在项目开发、论文写作过程当中 给予我的帮助。 同时，我要感谢我的父母、哥哥和其他关心我的家人，没有他们的支持和 鼓励，也就没有我今天所取得的成绩。 最后，我还要衷心的感谢合肥工业大学传授我知识的老师们，分布式控制 实验室和机械与汽车学院的领导和老师，以及其他帮助和支持过我的朋友们! 作者：辛达 2 0 0 6 年4 月 1 1 研究背景和意义 第一章绪论 随着社会经济的不断发展，企业间在降低生产成本、改善产品品质和扩大 销售方面的竞争越来越激烈。入们认识到，一个企业能否成功再也不局限于单 个孤立的企业了。现代企业的竞争主要是在企业与其合作伙伴所组成的供应链 和其它供应链之间的竞争。从而使串连整个供应链的物流对经济活动的影响日 益明显。当前，现代物流已被公认为是企业在降低物质消耗、提高劳动生产率 以外创造利润的第三个重要源泉，也是企业降低生产经营成本，提高产品市场 竞争力的重要途径【1 1 。在经济发达国家和一些经济水平较高的发展中国家，现 代物流水平已成为影响企业竞争力的关键因素。 据统计2 0 0 3 年和2 0 0 4 年我国企业的物流成本大约是销售收入的3 1 左 右，而国际上发达国家是在6 1 1 之间。这就意味着通过降低物流成本来提 高企业利润将会有很大的空间。据测算，2 0 0 3 年我国全社会物流总成本占g d p 的比重是2 1 4 。我国现在每年的国内生产总值大概是1 0 万多亿元，只要能 够降低1 的物流成本，就可以减少1 0 0 0 亿元的成本支出。因此，优化物流企 业车辆调度管理，可以提高运力的利用效率，降低企业的物流成本，增强我国 物流企业的竞争能力1 2 】。 同时电子商务的兴起和蓬勃发展，猛烈地冲击着世界各国企业传统的经营 理念、市场营销、管理模式和业务流程，给社会商务活动方式、人们的消费方 式、企业的生产方式和传统行业带来了一场革命。 联合国贸易和发展会议( u n c t a d ) 在日内瓦发表了题为 2 0 0 4 年电子商务 及其发展状况的报告，对全球电子商务、互联网以及信息通信技术的发展进 行了全面分析。报告表明截至2 0 0 3 年底，全球网民人数已超过6 7 6 亿，约占 世界总人口的1 1 8 。其中，发展中国家的网民人数己占全球网民总数的3 6 。 从2 0 0 0 年到2 0 0 3 年，发展中国家的网民人数猛增了近5 0 。从2 0 0 3 年6 月 到2 0 0 4 年6 月，全球网站数猛增2 6 ，总数超过5 1 6 0 万个。从2 0 0 3 年4 月 到2 0 0 4 年4 月，全球使用s s l 协议以保障交易安全的网站数量猛增5 6 7 ， 达到3 0 万个。电子商务的蓬勃发展给全球带来巨大的财富，但是物流配送技 术却跟不上电子商务的这种迅猛发展势头。例如在城市中，物流配送己成为网 上购物发展的一个瓶颈。可以说物流在电子商务中具有不可代替的作用 4 1 。 物流配送是物流中一个重要趵直接与消费者相连的环节，是电子商务活动 不可缺少的内容。配送是在集货、配货基础上，按货物种类、品种搭配、数量、 时间等要求所进行的运送，是“配”和“送”的有机结合。物流配送过程主要 包括：从生产工厂进货并集结的集货作业；根据各个用户的不同需求，在配送中 心将所需要的货物挑选出来的配货作业；考虑配送货物的质量和体积，充分利 用车辆的载重和容积的车载货物的配装及配送路线的确定。 由于配送是对顾客服务的重要一环，因此配送的地位十分突出，如何实现 快速而准确的配送是企业在经营方面必须解决的重要课题。目前我国的物流配 送基本上还停留在“只送不配”的水平上，造成物流配送效率低下，车辆空驶 严重，物流配送成本很高，服务质量却很低。鉴于此，研究运用科学方法合理 组织物流配送，以提高企业的服务质量、减少库存、降低经营成本、增加经济 效益是十分必要的。 在影响物流配送系统的几个关键因素中，配送车辆的调度问题涉及面较 广，需要考虑的因素较多，对配送企业提高服务质量、降低物流成本、增加经 济效益的影响也较大，因此本文将着重研究物流配送车辆调度问题。 国外将物流配送车辆调度问题归结为v r p ( v e h i c l er o u t i n gp r o b l e m ，即车 辆路径问题) 、v s p ( v e h i c l es c h e d u l i n gp r o b l e m ，即车辆调度问题) 和 m t s p ( m u l t i p l e t r a v e l i n gs a l e s m a n p r o b l e m ，即多路旅行商问题) 。该问题子1 9 5 9 年由d a n t z i g 和r a m s e r 提出后1 3 ，很快便引起运筹学、应用数学、组合数学、 图论与网络分析、物流科学、计算机应用等学科的专家以及运输计划制定者的 极大重视，并一直是运筹学与组合优化领域的前沿与热点问题。在现实生产和 生活中，邮政投递问题、飞机、铁路车辆、水运船舶及公共汽车的调度问题、 电力调度问题、管道铺设问题、计算机网络拓扑设计问题等都可以抽象为物流 配送车辆调度问题。本文所研究的物流配送车辆调度问题的求解方法对解决上 述问题也是有效的。 1 2 车辆调度问题概述 1 2 1 车辆调度问题的描述 配送车辆调度问题可以描述为：在一个存在供求关系的系统中，有若干台 车辆、若干个配送中心和客户，要求合理安排车辆的行车路线和出行时间，从 而在给定的约束条件下，把客户需求的货物从配送中心送到客户，并使目标函 数取得优化。 配送车辆调度问题可归结为如下的一般网络模型：设g = ( v e ，a ) 是一个 连通的混合网络，v 是顶点集( 表示配送中心、客户、停车场等) ，e a 分别为 无向的边集和有向的弧集，e 中的边和a 中的弧均被赋权( 可以表示配送的距 离、时间或费用) ，v ，e ，a 分别为v ，e ，a 的子集，求满足约束条件( 包括客户 的货物需求数量约束、需求时间约束、配送车辆一次配送的最大行驶距离约束、 车辆的最大载重量约束等) ，并包含v ，e t ，a 的一些巡回路线，使目标函数取得 优化，目标函数可以取配送总里程最短、配送车辆总吨位公里数最少、配送总费 用最低、配送总时间最少、使用的配送车辆数最少、配送车辆的满载率最高等 1 4 1 1 5 。 1 2 2 车辆调度问题的构成要素 配送车辆调度问题主要包括货物、车辆、物流中心、客户、运输网络、约 束条件、和目标函数等要素胴。 ( 1 ) 货物 货物是配送的对象，可将每个客户需求( 或供应) 的货物看成一批货物，每 批货物都包括品名、包装、重量、体积、要求送到( 或取走) 的时间和地点，能 否分批配送等属性。 ( 2 ) 车辆 车辆是货物的运载工具，其主要属性包括：车辆的类型、载重量、车辆的工 作时间、配送前的停放位置及完成任务后的停放位置等。 ( 3 ) 物流中心 也称为物流基地、物流据点，是指可以进行集货、分拣、配货、配装、送 货作业的配送中心、仓库、车站、港口等。在配送系统中，物流中心的数量可 以只有一个，也可以有一个以上。 ( 4 ) 客户 包括分仓库、零售商店等，客户的属性包括需求( 或供应) 货物的数量、需 求( 或供应) 货物的时间、需求( 或供应) 货物的次数及需求( 或供应) 货物的满足程 度等。 ( 5 ) 运输网络 运输网络是由顶点( 指物流中心、客户、停车场) 、无向边、有向弧组成的， 边、弧的属性包括方向、权值和交通流量限制等。 运输网络中边或弧的权值可以表示为距离、时间或费用。边或弧的权值变 化分为以下几种情况：固定，即不随着时间和车辆的不同而变化：随时间段不 同而变化；随车辆的不同而变化：既随着时间的不同而变化，又随着车辆的不 同而变化。 对运输网络中的定点、边或弧的交通流量要求分为以下几种情况：无流量 限制：边、弧限制，即每条边、弧上同时行驶的车辆数有限：顶点限制，即每 个顶点上同时装、卸货的车辆数有限；边、弧、顶点都有限制。 ( 6 ) 约束条件 配送车辆调度问题应满足的约束条件主要包括：满足所有客户对货物品 种、规格、数批的要求；满足客户对货物发到时间范围的要求；在允许的时间 进行配送( 如有时规定白天不能通行货车等) ；车辆在配送过程中的实际载货量 不得超过车辆的最大允许装载量：在物流中心现有的运力范围内等。 ( 7 ) 目标函数 对配送车辆调度问题，可以只选用一个目标，也可以选用多个目标。经常 选用的目标函数主要有： 配送里程最短，考虑到配送里程与配送车辆的耗油量，磨损程度以及司机 疲劳程度等直接相关，因此采用配送里程最短的目标在某种程度上可以直接衡 量运输成本。 配送车辆的吨位公里数最少，该目标将配送距离与车辆的载重量结合起 来考虑，是比较常用的目标之一。 综合费用最低，降低综合费用是实现配送业务的经济效益的基本要求。 在配送中，与取送货有关的费用包括；车辆维护和行驶费用、车队管理费用、 货物装卸费用、有关人员工资费用等。 准时性最高，由于客户对交货时间有较严格的要求，为提高配送服务质 量，有时需要将准时性最高作为配送路线的目标。运力利用最合理。该目标要求 使用的较少的车辆完成配送任务，并使车辆的满载率最高，以充分利用车辆的 装载能力。 劳动消耗最低，即以司机人数最少、司机工作时间最短等为目标。 1 2 3 车辆调度问题的分类 配送车辆调度问题可按照其构成要素划分不同的种类。 l 、按物流中心的数目分：有单物流中心问题( 配送系统中仅有一个物流中 心) 和多物流中心问题( 配送系统中存在多个物流中心) 。 2 、按车辆载货状况分：有满载问题( 由于客户需求和供应的货物数量大于 或等于车辆的载重量，所以完成一项配送任务需要一辆及其以上的配送车辆、 配送车辆需要满载运行) 、非满载问题( 山于客户需求或供应的货物数量小于车 辆载重量。多项配送任务可以共用一辆配送车辆，车辆在配送过程中经常处于 不满载状态) 、以及满载和非满载混合问题( 由于一部分客户需求和供应的货物 数量大于或等于车辆的载重最，而另一部分客户需求或供应的货物数量小于车 辆的载重量，造成一些配送车辆需要满载运行，而另一些车辆则经常处于不满 载状态1 。 3 、按配送任务特征分：有纯送货问题( 仅仅考虑从物流中心向客户送货， 也称为纯卸问题) 、或纯取货问题( 仅考虑把各客户供应的货物取到配送中心， 也称为纯装问题) 、及取送混合问题( 即考虑将客户需求的货物从物流中心送到 各个客户，同时考虑将客户供应的货物从客户取到物流中心，也称为装卸混合 问题或者集、送货一体化问题) 。 4 、按客户对货物取( 送) 时间的要求分；有无时间约束问题( 客户对货物的 取走和送到的时间无具体要求) 和有时间约束问题( 客户要求将需求的货物在规 定的时间窗内送到，将供应的货物在规定的时间窗内取走，也称为有时间窗的 问题) 。有时间约束问题又分为硬时间窗问题( 客户要求货物必须在规定的时间 窗内送到或取走，不能提前或拖后) 和软时间窗问题( 尽量在规定的时间窗内送 到或取走客户的货物，但可以提前或拖后，发生提前或拖后的情况时。要对配 4 送企业实施一定的惩罚) 。 5 、按车辆类型分：有单车型问题( 所有配送车辆的载重量相同) 和多车型问 题( 配送车辆的载重量不完全相同) 。 6 、按车辆对车场所属关系分：有车辆开放问题( 即车辆完成配送任务后可 以不返回其发出车场) 和车辆封闭问题( 车辆完成配送任务后必须返回其发出车 场) 7 、按优化目标数分：有单目标问题( 仅考虑一个配送目标) 和多目标问题( 同 时考虑多个配送目标) p j 。 1 3 车辆调度问题的研究现状 国外将物流配送车辆调度问题归结为v r p ( v e h i c l e r o u t i n gp r o b l e m ，即车 辆路径问题) 、v s p ( v e h i c l es c h e d u l i n gp r o b l e m ，即车辆调度问题) 和 m t s p ( m u l t i p l et r a v e l i n gs a l e s m a np r o b l e m ，即多路旅行商问题) 。该问题被提 出后，不少专家学者对其计算复杂性进行了研究，这是确定其求解算法研究方 向的基础。l e n s t r a 和r i n n o o y k a n 在1 9 8 1 年文献中t 6 1 ，对v s p 的计算复杂性 进行了综述和分析；d a n t z i g 和f u i k e r s o n ( 1 9 5 4 ) 证明了有确定开始时间的物流 配送车辆调度问题的复杂性为o ( n 3 】：k a r p ( 1 9 7 2 ) 证明了旅行商问题( t s p ) 和有 向旅行商问题( d i r e c t e dt r a v e l i n gs a l e s m a np r o b l e m ，简称d t s p ) 为n p 难题， p a p a d i m i t r i o u ( 19 7 6 ) 证明了多重旅行商问题( m u l t i p l et r a v e l i n gs a l e s m a n p r o b l e m ，简称m t s p ) 为n p 难题【7 】；s a v e l s b e r g ht s l ( 1 9 8 5 ) 和s o l o m o n l 9 1 ( 1 9 8 61 提出有时限的物流配送车辆调度问题比一般的物流配送车辆调度问题更复杂； s a v e l s b e r g h ( 1 9 8 5 ) 提出有时限的物流配送车辆调度问题不仅问题本身是n p 难 题，甚至在车队大小固定时，找一个可行解也是n p 难题：l e n s t r a 和r i n n o o p y k a n 还证明了几乎所有类型的物流配送车辆调度问题均为n p 难题等。 求解物流配送车辆调度问题的方法很多，究其实质，可以分为精确算法和 启发式算法两大类。精确算法是指可求出其最优解的算法，主要有：分枝定界法、 割平面法、网络流算法、动态规划法等。由于精确算法的计算量一般随问题规 模的增大呈指数增长，在实际中其应用范围很有限，多用于规模较小的问题【1 0 l 。 为此。专家们把精力主要用在构造高质量的启发式算法上】【2 针。 启发式算法( h e u r i s t i c s ) 是指一种基于直观或经验构造的算法，目标是在可 接受的花费( 计算时间、占用空间等) 下得出待解决问题的满意解，而不一定是 最优解。启发式方法中最具代表性的就是由c l a r c k 和w r i g h t t 2j 1 提出的节约法 ( s a v i n gm e t h o d ) ；典型启发式算法中还包括由l i n 和k e r n i g h a n t 2 2 】提出的，并 由c h r i s t o f i d e s 【2 川等人所推广的分支交换探索法：1 9 7 4 年g i l e t 和m i l l e r 2 q 提 出的扫描法( s w e e pm e t h o d ) ；g l o v e r 在1 9 8 6 年提出了禁忌搜索算法这一概念 “，进而形成一套完整算法；7 0 年代美国j h o l l a n d 教授和他的学生建立发展 起来了遗传算法 26 】；m e t r o p o l i s 在1 9 5 3 年提出了模拟退火算法【2 7 1 ；意大利学 者m d o r i g o 等人首先提出了蚁群系统，并用于求解t s p 问题【2 8 l ； 根据配送系统中配送中心数目的多少，配送车辆调度问题有单配送中心问题和多 配送中心问题之分。在现实物流体系中，常常出现多个配送中心的情况。因此，对多 配送中心车辆调度问题的研究具有重要的现实意义。国内现有对配送车辆调度问题的 研究主要集中在单配送中心问题上，对多配送中心车辆调度问题的研究相对较少。国 外g u y d e s a u l i n i e r s 、t a i h i s w u 、b u r a k k a z a z 、r o b e r t t s u m i c h r a s t 、s s a l h i 、n r a c h u t h a n 、s t e f a ni m i c h 、m i c h a e lw a s n e r 等专家对多配送中心车辆调度问题进行了研 究f 2 9 1 【3 6 1 ，并取得了一些很有价值的研究成果。其中。g u yd e s a u l r t i e r s 等研究了有时 问窗的多配送中心车辆调度问题：t a i - h s iw u 等人将多配送中心车辆调度问题分解成 两个子问题；多配送中心的选址问题和一般的单配送中心车辆调度问题；s t e f a ni m i c h 研究了多车型取送混合的多配送中心车辆调度问题。 1 4 本文的主要内容 蚁群算法是一种仿生的随机搜索寻优方法，是生物界的群体启发式行为， 现已陆续应用到组合优化、人工智能、通讯等多个领域。蚁群算法的正反馈性 和协同性使其可用于分布式系统，隐含的并行性更使之具有极强的发展潜力。 本文研究了采用蚁群算法来解决多配送中心车辆调度问题，并对有时限和无时 限两种情况分别进行了分析。 第一章介绍了论文的研究背景和意义，并对车辆调度问题进行描述。 第二章详细介绍了蚁群算法。论述了蚁群算法的原理、数学模型、特点和 算法步骤；对算法的优缺点进行了分析，最后介绍了算法的研究进展。 第三章主要对多配送中心车辆调度问题进行了描述。分析了解决多配送中 心车辆调度问题的两种主要方法：分解法一将多配送中心车辆调度问题转化为 多个单配送中心车辆调度问题，然后进行优化组合；整体法一将多配送中心车 辆调度问题本身看作一个复杂的组合优化问题进行研究。并分别给出了分解法 和整体法求解多配送中心车辆调度问题的数学模型。 第四章主要研究了分别在整体法和分解法的基础上采用蚁群算法来求解 无时限多配送中心车辆调度问题。给出了蚁群算法结合整体法及蚁群算法结合 分解法求解问题的模型、算法描述和实现过程。最后对上述两种方法进行了试 验计算，并对两种方法的试验结果进行比较和分析。 第五章主要描述了分别在整体法和分解法的基础上采用蚁群算法来求解 有时限多配送中心车辆调度问题。并对两种方法的试验结果进行比较和分析。 第六章为本文总结与工作展望。 6 第二章蚁群算法的概述 2 1 蚁群算法背景介绍 蚂蚁是一类群居昆虫，虽然单个蚂蚁的行为极其简单，但由这样单个简单 的个体所组成的蚁群群体却表现出极其复杂的行为，能够完成复杂的任务。蚁 群还能够适应环境的变化，当在蚁群运动路线上突然出现障碍物时，蚁群能够 很快的找到最优路径。人们经过大量的研究发现，蚁群之所以能够表现出复杂 有序的行为，个体之间的信息交流与相互协作起着重要的作用。蚂蚁个体之间 是通过一种称之为外激素( p h e r o m o n e ) 的物质进行信息传递。蚂蚁在运动过 程中，能够在它所经过的路径上留下该物质。同时蚂蚁在运动过程中能够感知 这种物质的存在及其强度，并且以此物质指导自己的运动方向。蚂蚁倾向于朝 着该物质强度高的方向移动。因此，由大量蚂蚁组成的蚁群的集体行为便表现 出一种信息正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的 概率就越大。蚂蚁个体之间就是通过这种信息的交流达到搜索食物的耳的。 由于受到自然界真实蚁群集体行为的启发，由意大利学者m d o r i g o 等人 首先提出了一种基于种群的模拟优化算法一一蚁群算法。蚁群算法有较强的鲁 棒性、分布式计算、易于与其它方法结合等优点。所以该算法在求解旅行商问 题( t r a v e l i n gs a l e s m a n p r o b l e m ，t s p ) 问题、指配问题( a s s i g n m e n tp r o b l e m ) 、 j o b s h o p 调度等问题，取得了一系列较好的实验结果2 8 f 3 7 】【3 叭。 2 2 基本蚁群算法 2 2 1 蚁群算法的基本思路 为了解决某个含有n 个节点的完全图g 中的某个“最优路径”问题，首先 在连接各路径的节点上摆上总数固定的蚂蚁，而这些蚂蚁向下一路径转移的规 律是基于以下两个参数： 每条道路都有p h e r o m o n e 这一参数，记录了蚁群系统对于过去对该路 径留下的“信息素浓度”，也就是对过去时刻该路径可靠性的评判。 每条道路都有v i s i b i l i t y 参数，记录了该路径本身的“能见度”，也就是 对于如果选择该路径，将来可能的最优度的评判。 根据上述的两个参数，产生一项新的参数，也就是每只蚂蚁向下一个节点 运动的概率p 。两个参数中的p h e r o m o n e 被两个自然现象所制约，首先就是“蒸 发”现象，就像在自然界一样，整个系统每条道路上的信息素都会随着时间的 流逝而减弱：还存在另一现象，即每次搜索的结果中被选中的路径上的“信息 素”会根据某种规律被增强。而v i s i b i l i t y 则相对固定，一般和道路的长度成反 比。这样蚁群中每个独立的智能体( a g e n t ) 依次地寻找下一条可行的路径，并且 更新p h e r o m o n e ，直到找到所需要的一条完整的路径，或者完成某项指标，如找 7 到食物，如此找到路径就算一个可行解h 9 1 。 整个蚁群根据上述规律不断的运动，对各条道路上的“信息素浓度”随时 作出“正反馈”，而这些“信息素”也指导蚁群不断优化通向食物的道路。 2 2 。2 基本蚁群算法模型 由于蚁群搜索食物的过程与著名的旅行商问题( t s p ) 之间十分的相似。 现以n 个城市的t s p 问题( 0 , 1 ，h 一1 表示城市序号) 来说明蚁群算法模型。 设m 是蚁群中蚂蚁的数量，d 。( i j = 1 , 2 ，n ) 表示城市i 和城市j 之间的距 离，6 ，( f ) 表示t 时刻位于城市i 的蚂蚁的个数，m = b i ( f ) 。瓦g ) 表示t 时 刻在i j 连线上残留的信息量。在初始时刻，各条路上的信息量相等，并设 丁p ( o ) = c ( c 为常数) 。7 7 。表示由城市i 转移到城市j 的启发信息，该启发 信息是由要解决的问题给出的，在1 8 9 问题中一般取刁，= 。蚂蚁k ( k = 1 , 2 ，m ) 在运动过程中，根据各条路径上的信息量决定转移方向，p ：( t ) 表 示在t 时刻蚂蚁k 由位置i 转移到位置j 的概率，由下面公式确定： f 毒缫躲踟俐。 ，( f ) = ：i 鄹7 5 4 。咿8 4 ( z ) 【o 枷# m 妇g 其中，a l l o w e d k = 0 ，1 ，n 1 一t a u k 表示蚂蚁k 下一步允许选择的城市。人 工蚁群系统具有记忆功能，用t a u k ( k = 1 , 2 ，m ) 用以记录蚂蚁k 当前所走 过的城市，集合t a u k 随着进化过程动态的调整。 蚂蚁留下的信息素会随着时间而挥发，所以每一只蚂蚁完成对所有n 个城 市的访问后( 即一个循环结束后) ，必须对残留信息进行更新。根据下厩来更 新信息量： f f ( 1 + 行) 2p f f 0 ) + f 口 p ( o ，1 ) ( 2 2 ) 丁。= f ： ( 2 3 ) 其中p 表示信息索的残留系数，t 表示第k 只蚂蚁在本次循环中留在路径i j 上的信息量，a _ 。表示本次循环中路径i j 上的增量。 m d o r i g o 曾给出3 种不同的模型，分别称之为a n tc y c l es y s t e m 、a n tq u a n t i t y s y s t e m 、a n td e n s i t ys y s t e m ，它们的差别在于表达式r ：。 在a n tc y c l es y s t e m 模型中： a 彳： 丢，若第娘蚂蚁在本次循环中经过日 ( 2 - 4 ) 【0 ，否则 其中q 是常数，l k 表示第k 只蚂蚁在本次循环中所走路径的长度： 在a n td e n s i t ys y s t e m 和a n tq u a n t i t ys y s t e m ，f ：分别为： 吲：坛，第帜蚂蚁在本次循环中经瑚 陋5 ) 1 0，否则 f ：；= ? 嚣蚂蚁在本次循种经过i j ( 2 - 6 ) 乃2 1 0 ，否则 它们的区别在于：后两种模型中，利用的是局部信息，而前者利用的是整 体信息，在求解t s p 问题时，性能较好。因而通常采用它作为基本模型。 2 2 3 基本蚁群算法参数说明 对蚁群算法性能有影响的参数主要有：信息素残留系数p 、信息启发式因 子a 、期望值启发式因子1 3 和总信息量q 等。 ( 1 ) 信息素残留系数p 的大小直接影响着蚁群算法的全局搜索能力和收敛 速度。p 取得过小，将影响算法的全局搜索能力，容易陷入局部最小值；p 取 得过大，将影响算法的收敛速度。对于a n tc y c l es y s t e m 模型p 一般取0 5 比较 合适【5 8 】【5 9 】。 ( 2 ) 信息启发式因子a 的大小反映了蚁群在路径选择中随机性因素的强 弱，a 的取值越大，则蚂蚁选择以前走过的路径的可能性越大，搜索的随机性 减弱，容易陷入局部最优解。a 的取值越小，虽然可以提高随机搜索能力，但 是算法的收敛速度会受到影响。 ( 3 ) 期望值启发式因子e 的大小反映了蚁群在路径选择中确定性因素的强 弱，其值越大，蚂蚁在选择局部最短路径的可能性越大，虽然收敛速度加大， 但是同样容易陷入局部最优解而停滞。 ( 4 ) 总信息量q 为蚂蚁循环一周时释放在所经过的路径上的信息素总量。 总信息量q 越大，则在蚂蚁已经走过的路径上信息索的累积加快，可以加强蚁 群搜索时的正反馈性能，有助于算法的快速收敛，缺点是容易陷入局部最优解 而停滞但信息总量q 对算法的性能影响有赖于上述三个参数的配置。 2 3 蚊群算法的优缺点及研究进展 2 3 1 蚁群算法的优点 1 、蚁群算法是一种自组织的算法。在系统论中，自组织和它组织是组织 的两个基本分类，其区别在于组织力或者组织指令是来自于系统的内部还是来 自于系统的外部，来自于系统内部的是自组织，来自于系统外部的是他组织， 如果系统在获得空间的、时间的或者功能结构的过程中，没有外界的特定干预， 我们便说系统是自组织的。在抽象意义上讲，自组织就是在没有外界作用下使 得系统墒增加的过程( 即是系统从无序到有序的变化过程) 。蚁群算法充分体现 了这个过程。以蚂蚁群体优化为例子说明，当算法开始的初期单个的人工蚂蚁 无序的寻找解，算法经过一段时间的演化，人工蚂蚁间通过信息激素的作用， 自发的越来越趋向于寻找到接近最优解的一些解，这就是一个无序到有序的过 程。 2 、蚁群算法本质上是一种并行的算法。每只蚂蚁搜索的过程相对独立， 仅通过信息激素进行通信。所以蚁群算法可以看作是一个分布式的多a g e n t 系 统，它在问题空间的多点同时开始进行独立的解搜索，不仅增加了算法的可靠 性，也使得算法具有较强的全局搜索能力。 3 、蚁群算法是一种正反馈的算法。从真实蚂蚁的觅食过程中我们不难看 出，蚂蚁能够最终找到最短路径，直接依赖于最短路径上信息激素的堆积，而 信息激素的堆积却是一个正反馈的过程。对蚁群算法来说，初始时刻在环境中 存在完全相同的信息激素，给予系统一个微小扰动，使得各个边上的轨迹浓度 不相同，蚂蚁构造的解就存在了优劣，算法采用的反馈方式是在较优的解经过 的路径留下更多的信息激素，而更多的信息激素又吸引了更多的蚂蚁，这个正 反馈的过程使得初始的不同得到不断的扩大，同时又引导整个系统向最优解的 方向进化。因此，正反馈是蚂蚁算法的重要特征，它使得算法演化过程得以进 行。 4 、蚁群算法具有较强的鲁棒性。相对于其它算法，蚁群算法对初始路线 要求不高，即蚁群算法的求解结果不依赖于初始路线的选择，而且在搜索过程 中不需要进行人工的调整。其次，蚁群算法的参数数目少，设置简单，易于蚁 群算法应用到其它组合优化问题的求解。 5 、易于与其它方法结合。蚁群算法很容易与其它启发式算法相结合，以 改善算法的性能【4 0 【4 1 】【42 1 。 2 3 2 蚁群算法的缺陷 1 算法需要较长的的搜索时间。蚁群中各个体的运动是随机的，虽然通过 信息激素交换能够向着最优路径进化，但是当群体规模较大时，很难在较短的 时间内从大量杂乱无章的路径中找出一条较好的路径。这是因为在进化的初 期，各个路径上的信息激素差别不大，通过信息正反馈，使得较好路径上的信 息激素逐渐增大，经过较长一段时间，才能使得较好路径上的信息激素明显高 于其它路径，随着这一过程的进行，差别越来越明显，从而最终收敛，这一过 程一般需要较长的时间。 2 蚁群算法易于出现早熟停滞现象。在蚁群算法中，蚁群的转移是由各条 路径上留下的信息激素浓度和城市间距离来引导的，蚁群运动的路径总是趋向 于信息激素最强的路径。但是由于各路径上的初始信息激素相同，蚁群创建第 一条路径的引导信息主要是城市间的距离信息，这样蚁群在所经过的路径上留 下的信息激素就不一定能反映出最优路径的方向，不能保证蚁群创建的第一条 路径能引导蚁群走向全局最优路径。随着算法的重复执行，信息激素都积累在 这条局部最优的路径上，使该条路径上的信息激素浓度远远大于其它路径上的