（计算机应用技术专业论文）物流配送中车辆调度问题的研究.pdf

中文摘要 物流配送车辆调度问题是指：在给定运输任务的条件下，如何派车、组织循环 运输，使空驶里程最少，运输成本最低。目前我国大多数的物流企业运输资源分配 不均、配送路线安排不合理、运力资源浪费严重，而缺乏完善的物流配送车辆调度 优化方案是造成此现象的重要因素之一。因此对物流配送车辆调度问题的研究具有 重要的现实意义。 目前对单车场、封闭式物流配送车辆调度问题研究较多，而对多车场开放式物 流配送车辆调度问题研究较少，但是多车场开放式物流配送车辆调度问题有很强的 应用背景。本文针对此问题，建立了一种灵活的多目标组合优化模型，设计了适合 多车场开放式车辆路径问题的通用染色体编码方案，并对遗传算法中的交叉变异操 作做了详细说明。此模型可以方便的增减优化目标值，并通过测试用例验证了本文 设计的优化模型和遗传算法在解决多车场多目标开放式物流配送车辆调度问题中的 可行性。 自动化立体仓库出库端车辆调度策略的设计是物流配送车辆调度中的一个关键 问题，好的调度策略可以大大缩短出库端的配货时间。为此本文引入动态优先级理 论，并利用该理论对大型a s r s 出库口车辆调度问题进行了深入研究与分析，提出 了基于动态优先级的a s r s 出库端车辆调度策略，并开发了相应的a s r s 出库口发 货资源监控系统，即a s r s 出库口车辆调度系统，优化了a s r s 出库端车辆调度策 略，大大提高了物流配送当中的配货效率。 本文建立的多目标组合优化模型以及设计的遗传算法求解方案，可以有效的缩 减物流配送中的送货时间；设计的a s r s 出库端车辆调度优化策略及开发的a s r s 出库端车辆调度系统，可以有效缩减车辆在出库端的配货时间。本文对以上两种物 流配送中的车辆调度问题进行研究，大大提高了物流配送效率、减少了物流配送成 本。 关键词：物流配送；车辆调度；多目标组合优化；遗传算法 a b s t r a c t l o g i s t i c sv e h i c l es c h e d u l i n gp r o b l e mm e a n s ：u n d e rt h ec o n d i t i o n so fa g i v e nt r a n s p o r t ，h o ws e l e c tv e h i c l e s ，h o wo r g a n i z ec y c l et r a n s p o r t ，t om a k e t h el e a s tm i l e a g ea n dt h el o w e s tc o s to f t r a n s p o r t a tp r e s e n t ，t h em a jo r i t yo f l o g i s t i c se n t e r p r i s e si no u rc o u n t r ya r ei nt h ec i r c u m s t a n c e st h a tt h e d i s t r i b u t i o no ft r a n s p o r tr e s o u r c e si su n e v e n ，t h ea r r a n g e m e n tf o rd i s t r i b u t i o n r o u t ei su n r e a s o n a b l e ，a n dt h ew a s t eo fc a p a c i t yr e s o u r c e si ss e r i o u s t h el a c k o ft h eo p t i m i z a t i o nv e h i c l es c h e d u l i n gp r o g r a m si so n eo ft h ei m p o r t a n t f a c t o r sc a u s i n gt h i ss i t u a t i o n t h e r e f o r e ，t h er e s e a r c ho nl o g i s t i c sv e h i c l e s c h e d u l i n gp r o b l e mh a si m p o r t a n tp r a c t i c a ls i g n i f i c a n c e a tp r e s e n t ，m o r er e s e a r c hh a sb e e nd o n eo nt h e c l o s e d o n e - d e p o t s c h e d u l i n gp r o b l e m ，b u tl e s s r e s e a r c ho no p e n e dm u l t i d e p o t s c h e d u l i n g p r o b l e m ，a n do p e n e dm u l t i d e p o ts c h e d u l i n gp r o b l e m h a sa s t r o n g a p p l i c a t i o nb a c k g r o u n d af l e x i b l em u l t i - o b j e c t i v eo p t i m i z a t i o nm o d e lf o r o p e n e dm u l t i - d e p o tv e h i c l es c h e d u l i n gp r o b l e mi se s t a b l i s h e di nt h i sp a p e r t h ec o m m o nc h r o m o s o m ee n c o d i n gs c h e m ef o r o p e n e dm u l t i d e p o t s c h e d u l i n gp r o b l e mi sd e s i g n e d ，a n dt h ed e s c r i p t i o nf o rc r o s sa n dm u t a t i o n o p e r a t i o ni si nd e t a i l t h em o d e lc a nc o n v e n i e n t l yi n c r e a s eo rd e c r e a s et h e n u m b e ro fo p t i m i z a t i o no b j e c t i v e t h eg i v e nt e s tc a s ev e r i f i e dt h ef e a s i b i l i t y o ft h eo p t i m i z a t i o nm o d e la n dg e n e t i ca l g o r i t h mu s e di nt h em u l t i d e p o ta n d m u l t i o b j e c t i v eo p e n e dv e h i c l es c h e d u l i n gp r o b l e m i nl o g i s t i c sd i s t r i b u t i o n t h ed e s i g no ft h ev e h i c l e s c h e d u l i n gs t r a t e g yi nt h ee x p o r to fa s r si sa k e yi s s u eo fv e h i c l e s c h e d u l i n gi nl o g i s t i c sd i s t r i b u t i o n g o o ds c h e d u l i n g s t r a t e g yc a ns i g n i f i c a n t l yr e d u c et h et i m eo fl o a d i n gi nt h ee x p o r to fa s r s s od y n a m i cp r i o r i t yt h e o r yi si n t r o d u c e d ，a n dm a d ea ni n d e p t hr e s e a r c ha n d a n a l y s i sf o rt h ev e h i c l e s c h e d u l i n gs t r a t e g yo ft h ee x p o r to f a s r su s i n gt h i s t h e o r y t h ev e h i c l e - s c h e d u l i n gs t r a t e g yo ft h ee x p o r to f a s r sb a s e do nt h e d y n a m i cp r i o r i t yi sp r e s e n t e d ，t h er e s o u r c e sm o n i t o r i n gs y s t e mo f t h ee x p o r t o fa s r s - t h ev e h i c l es c h e d u l i n gs y s t e mo ft h ee x p o r to f a s r si sd e s i g n e d ， t h ev e h i c l es c h e d u l i n gs t r a t e g yo f a s r si so p t i m i z e da n dt h ee f f i c i e n c yo f i l l l o a m n gi nt h ee x p o r to f a s r si se f f e c t i v e l yi m p r o v e d t h em u l t i o b je c t i v ec o m b i n a t o r i a lo p t i m i z a t i o nm o d e l s a n dt h eg e n e t i c a l g o r i t h md e s i g np r o g r a m sm a d e i nt h i sp a p e rc a ne f f e c t i v e l yr e d u c et h e d e l i v e r yt i m eo fl o g i s t i c s t h eo p t i m i z e dv e h i c l es c h e d u l i n gs t r a t e g ya n d t h e v e h i c l es c h e d u l i n gs y s t e mo ft h ee x p o r to f a s r sc a ne f f e c t i v e l yr e d u c et h e t i m eo f l o a d i n gi nt h ee x p o r to f a s r s i nt h i sp a p e r , t h e s e t w ok i n d so 士 v e h i c l es c h e d u l i n gp r o b l e mo fl o g i s t i c sd i s t r i b u t i o na r er e s e a r c h e d ，t h e y c a n g r e a t l vi m p r o v et h ee f f i c i e n c yo f t h et i m eo fl o a d i n ga n dd i s t r i b u t i o ni n l o g i s t i c sa n dr e d u c el o g i s t i c sc o s t s k e yw o r d s ：l o g i s t i c sd i s t r i b u t i o n ；v e h i c l e s c h e d u l i n g ；m u l t i 。o b j e c t i v e c o m b i n a t o r i a lo p t i m i z a t i o n ；g e n e t i ca l g o r i t h m l v 声明尸州 本人郑重声明：所呈交的学位论文，是本人在指导教师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本论文 不包含其他个人或集体已经发表或撰写过的科研成果。对本文的研究 做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明的 法律责任由本人承担。 作者签名： 日期：竺l 竺：兰 关于学位论文使用权的说明 本人完全了解太原科技大学有关保管、使用学位论文的规定，其 中包括：学校有权保管、并向有关部门送交学位论文的原件、复印 件与电子版；学校可以采用影印、缩印或其它复制手段复制并保存 学位论文；学校可允许学位论文被查阅或借阅；学校可以学术交 流为目的，复制赠送和交换学位论文；学校可以公布学位论文的全 部或部分内容( 保密学位论文在解密后遵守此规定) 。 作者签名： 导师签名： 扫 毋。隹袭 砍氰阎 日期：竺宰：皇。2 1 日期： 童：堇：垒里 第一章绪论 第一章绪论 1 1 课题背景 物流( l o g i s t i c s ) ：指在合适时间，将合适的物品以适当的数量准确地送到顾客手 中，它是供应链中最重要的组成部分【l 】1 2 。一般意义上是指在生产和生活中所涉及的 各种物质实体由供给方向需求方的物理性转移过程。这一概念将物流定义在有用的 物、供方、需方等几个基本因素之上。也就是说，我们通常所指的物流是指人们在 生产和生活中发生的有意义的物流行为。整个物流过程是一个物理过程，只改变时 间和空间的状态，不改变其使用价值。其中，时间状态的改变称之为仓储、流通加 工等活动，空间状态的改变称之为运输、搬倒等活动。 物流配送是物流系统中的一个重要环节，它是指按客户的订货要求，在物流中 心进行分货、配货工作，并将配好的货物及时送交收货人的物流活动。配送成本直 接关系到物流企业和部门的效益，目前我国的大多数的物流企业运输资源分配不均、 配送路线安排不合理、运力资源浪费严重，根据中国仓储协会对1 4 6 个企业的调查显 示，用于运输的费用占整个物流费用的比例分别为：在生产企业原料物流中占5 8 ， 在生产企业成品物流中占7 3 ，在商业物流中占5 2 t 引。所以物流配送车辆调度方案 的合理优化，对于整个物流运输速度、成本、效益的影响至关重要。 运输是指“物”的长距离的移动，任何跨越空间的物质实体的流动，都可称为 运输。运输是物流的中心环节之一，被称为国民经济的动脉和现代产业的支柱，从 社会经济的角度讲，运输功能的发挥，缩小了物质交流的空间，扩大了社会经济活 动的范围并实现在此范围内价值的平均化、合理化。在社会经济的发展中，运输的 重要性己经被人们所确认，成为国民经济的命脉。 从物流系统的观点来看，运输作业的关键因素包括运输成本和运输速度两个方 面。运输成本：是指为两个地理位置的运输所支付的款项，以及管理和维持转移中 存货的有关费用，应采用能把系统总成本降低到最低限度的运输方式。运输速度： 是指为完成特定的运输作业所需花费的时间。运输速度和成本的关系，主要表现在 以下两个方面：首先，运输商提供的服务越快速，实际需要收取的费用也就越高。 其次，运输服务越快，转移中的存货就越少，可利用的运输间隔时间越短。因此在 选择最合理的运输方式时，至关重要的问题就是如何平衡其服务的速度和成本。运 输的主要目的就是要以最低的时间、财务和环境资源成本，将产品从原产地转移到 规定地点。同时，产品转移所采用的方式必须能满足顾客有关交付履行和装运信息 物流配送中车辆调度问题的研究 的可得性等方面的要求。所以在物流系统中，必须精确地维持运输成本和服务质量 之间的平衡。低成本运输和高质量服务是令人满意的。 物流配送车辆调度就是研究怎样合理运输的问题，所谓合理运输就是在实现物 资产品实体从物流中心至消费地转移的过程中，充分有效地运用各种运输工具的运 输能力，以最少的人、财、物消耗，及时、迅速、按质、按量和安全的完成运输任 务。其标志是：运输距离最短、运输环节最少、运输时间最短和运输费用最省。据 统计运输费约占整个物流费用的4 0 ，占销售收入的2 8 8 。物流配送车辆调度问题 就是指在给定运输任务的条件下，如何派车、组织循环运输，使空驶里程最少，运 输成本最低。车辆调度是物流管理最重要的部分，正确合理的调度可以有效减少车 辆的空驶率，实现合理路径运输，从而有效减少运输成本，节约运输时间，提高经 济效益。 1 2 课题研究的意义 物流产业的发展，将从整体上改变经济运行的方式，提高经济运行效率，对增 强国际竞争力将起到巨大的推动作用。我国国民经济的发展呼唤物流的进一步发 展，对物流的发展要求如下： ( 1 ) 降低流通成本在g d p 中的比重：在我国目前工业企业生产中，直接劳动成 本占总成本的比重不到1 0 ，而物流费用占商品总成本的比重，从账面反映约为 4 0 ，全社会物流费用支出约占g d p 的2 0 ，而其他发达国家一般在1 0 左右。 这反映了我国物流系统落后，流通成本太高，反映了我国国民经济运行质量不高。 通过发展现代物流业来促进物流合理化，降低流通成本在g d p 中的比重，无疑将 成为我国新的经济增长点。“十五”期间，如果我国物流费用降低到占g d p 的1 5 ， 每年将为社会直接节约2 4 0 0 亿元的物流成本。 ( 2 ) 减少企业流动资金占用：我国工业企业和流通企业由于物流基础设施、技 术和管理的落后，原材料、半成品、成品积压严重，大量流动资金被占用，周转速 度很慢，物流成本过高。据统计，1 9 9 2 年，国有独资、控股工业企业流动资金占用 1 万多亿元，周转速度为1 6 2 次年；1 9 9 9 年，国有独资、控股工业企业流动资金 达3 1 0 0 0 亿元，周转速度仅1 2 次每年，与发达国家相比非常落后。如果工业企业 把物流职能分离出来交给第三方物流企业，通过其先进、科学的专业化服务，就可 以减少流动资金占用，提高核心竞争能力，实现从粗放式经营向集约式经营转变。 ( 3 ) 电子商务的发展需要物流做基础：电子商务是流通领域的一场革命，它把 2 第一章绪论 商品买卖虚拟成一个大的市场，使客户在任何地点、任何时间都可以购买商品。但 是，电子商务需要将网上订的货物及时送到可能在任何地方的客户手里，这就给物 流系统带来很大的挑战。实际上，物流已经成为电子商务发展的瓶颈，需要建立具 有响应性、灵活性和可视化的现代物流系统，需要第三方物流企业的服务。世界5 0 0 强中相当多的企业都是通过第三方物流来解决它的供应链与销售问题的，很多跨国 公司在欧洲、亚洲、美洲等地分别有不同的第三方物流企业为他服务。 ( 4 ) 现代物流产业的发展，将减少由于低水平、条块分割的物流方式造成的巨 大物耗：在传统的物流框架下，一件商品从生产出来到最终的消费环节，至少要被 搬倒、装运十几次。实行社会化的多式联运、一单到底，物流过程中的物耗至少可 以减少几倍。我国汽车空驶率达3 7 左右，意味着全国每年有1 5 0 多万辆载重汽车 无活可干，这种潜在浪费至少也在数千亿元。按现代物流要求，合理的流程设计可 使空驶率降低到5 以下。 在现代物流集约化、一体化的发展中，配送是直接与消费者相连的重要环节， 其核心部分为配送车辆的集约、货物配装及送货过程，而配送车辆优化调度是物流 系统优化、物流科学化的关键一环，是货物从配送中心送达收货人的过程。配送首 要解决的是车辆的调度问题，几十年来这一直是一个研究的热点，在满足和完成各 任务的前提下，正确合理的安排行车路线、提高配送车辆的利用率就可以有效的节 省时间从而减少运输成本【4 】。另外对出库口车辆调度问题的研究，将有效减少货物 装配的时间。所以本文对物流配送车辆调度的研究具有重要意义。 1 3 国内外研究现状 车辆调度问题最早是由d a n t z i g 和r 锄s e i r t 在上个世纪5 0 年代末期提出【5 】【1 】【2 1 ，该 问题一般称之为v e h i c l er o u t i n gp r o b l e m ( v r p ) 或者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 ) ， 现在我们将车辆调度问题一律简称为v r p 。v r p 提出后就很快引起运筹学、应用数 学、组合数学、图论与网络分析、物流科学、计算机应用等学科专家与运输计划制 定者和管理者的极大重视，成为运筹学与组合优化领域的前沿与研究热点问题。各 学科的专家对该问题进行了大量的理论研究及实验分析，取得了很大进展。 国外对物流配送车辆优化调度问题作了大量而深入的研究，例如早在1 9 6 2 年， b a l i n s k i 等人首先提出v r p 的集分割，直接考虑可行解集合，在此基础上进行优化， 建立了最简单的v i 冲模型；1 9 6 4 年，c l a r k e 和w r i g h t 提出了一种启发式节约法来建立 车队配送路线；1 9 6 8 年，r a o 等人在v r p 集分割的基础上引入了列生成方法进行求 物流配送中车辆调度问题的研究 解，这种算法本质上是最短路径算法，同时结合了分枝定界算法；1 9 7 1 年，e i l o n 等 人提出将动态规划法用于固定车辆数的v r p ，通过递归方法求解；1 9 8 1 年，针对带 能力约束、时间窗以及无停留时间的v r p ，f i s h e r 提出了三下标车辆流方程；t h a n g i a h 于1 9 9 1 和j o e 于1 9 9 3 分别用遗传算法求解v r p ，但是都存在“早熟收敛”的问题；2 0 0 1 年，t a n ，l e e ，d u 结合遗传算法、t a b u 树搜索算法的优点，形成知识库，用人工智 能的方法来求解；2 0 0 2 年，t a r a n r i l i s ，k i r a n o n d i s 使用空间决策支持系统来解决车辆路 径问题。 在国内，有关车辆调度问题的研究是在2 0 世纪9 0 年代以后才逐渐兴起的，比国外 相对落后。国内研究对象主要是旅行商问题( t r a v e l i n gs a l e s m a np r o b l e m ，简称t s p ) 、 中国邮递员问题( c h i n e s ep o s t m a np r o b l e m ，简称c p p ) 、有向中国邮递员问题( d i r e c t e d c h i n e s ep o s t m a np r o b l e m ，简称d c p p ) 等，系统性研究还很少见到。西南交通大学的 李军教授和郭耀煌教授对车辆优化调度的基础理论及各类问题进行了系统的研究； 李大为【6 】等以t s p 的最近距离启发式为基础，通过设置评价函数来处理时间窗约束， 求解了简单的v r p 。另外在利用现代优化算法( 如：遗传算法、神经网络方法、模拟退 火等) 对简单t s p 的求解取得了一定成果。蔡延光【7 j 等应用模拟退火法针对满载问题进 行了求解。总体来说，目前我国对车辆调度问题的理论研究仍相对薄弱，需要进一 步研究。 1 4 本文内容的安排 本课题的研究以内蒙古蒙牛乳业股份( 集团) 有限公司的物流配送业务为背景，主 要研究两方面内容：首先，对多车场多目标开放式物流配送车辆调度问题做了研究， 以此可以优化对客户的派车问题及最佳车辆路径的选择问题。其次，对a s 瓜s 出库端 车辆调度策略做了研究，以本文建立的策略对出库口的车辆分配车位，可以减少车 辆的配货时间。本文的研究将在最大程度上减少蒙牛集团的运输成本，给蒙牛集团 带来可观的经济效益。本文研究的具体内容如下： 第一章绪论：介绍了本文研究的背景以及研究的目的与意义，并对国内外对车 辆调度问题的研究现状作了简单介绍。 第二章车辆调度问题概述：首先对物流配送车辆调度问题进行了描述，其次介 绍了车辆调度问题的构成要素和车辆调度问题的分类，最后列举了车辆调度的相关 求解算法。 第三章遗传算法概述：首先对g a 的背景作了简单的介绍，接着对g a 算法的基 4 第一章绪论 本概念、工作流程和算法的组成做了详细描述。 第四章用遗传算法解决多车场多目标开放式车辆调度问题：首先介绍了两种求 解多车场车辆调度的方法，然后对多车场多目标开放式车辆调度问题的研究背景进 行了描述，在此基础上确定了多车场多目标开放式车辆调度问题的数学模型，并详 细描述了用遗传算法对多车场多目标开放式车辆调度问题的求解过程，最后用实例 证明了用遗传算法求解此问题的可行性。 第五章对a s r s 出库端车辆调度策略做了研究，提出了基于动态优先级的a s r s 出库端车辆调度策略，并开发了相应的a s r s 出库端发货资源监控系统，即a s 瓜s 出 库口车辆调度系统，以此策略对出库口的车辆分配车位，可以减少车辆的配货时间。 第六章总结与展望：归纳与总结了本文的创新之处，并提出进一步研究车辆调 度问题的方向。 5 第二章车辆调度问题概述 第二章车辆调度问题概述 2 1 车辆调度问题的描述 “配送 一词是日本引进美国物流学时，对英文单词d e l i v e r y 一词的意译，我国 转学于日本，也直接用了“配送”这个词。配送是物流系统中由运输派生出的功能， 是短距离的运输。具有：配送距离较短，位于物流系统的最末端，处于支线运输、 二次运输和末端运输的位置。在配送中，也包含着其他的物流功能，是多种功能 的组合。配送是物流系统的缩影，也可以说是一个小范围的物流系统。从物流来 讲，配送几乎包括了所有物流的要素，车辆调度就是其中一个最重要且有意义的要 素，所以本文研究的是物流配送车辆调度问题。 物流配送车辆调度优化问题最早是d e n t z i n g 和r a m s e r 在1 9 5 9 年第一次提出的。 从此，车辆调度优化问题很快引起运筹学、应用数学、组合数学、图论与网络分析、 物流科学、计算机应用等学科的专家与运输计划制定者的极大重视，同时也逐渐成 为运筹学与组合优化领域的热点研究问题。由于它应用的广泛性和经济上的重大价 值，一直受到国内外学者的广泛关注。国外将物流配送车辆优化调度问题归结为或 称之为v e h i 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 问题：v e h i c l es c h e d u l i n gp r o b l e m 。 物流配送车辆调度问题的一般性定义是：物流配送车辆调度问题是把一系列的 装货点和( 或) 卸货点，有机的组织起来，形成一系列行车线路，使待调度车辆能 够高效、节能且有序地通过这些点。当然，这种组织方式是应该在满足一定的约束 条件( 例如：用户对货物的需求量、一次性发货量、应交发货时间、单个车场的车 辆容量限制、路程约束、时间限制等) ，最终达到缩短里程、减少开支费用、缩短 运输时间、使用车辆数尽量少等优化目标1 2 j 。 物流配送车辆调度问题一般研究的是在配送中心及用户位置均己知、资源及运 输能力充分、各用户需求量己知的前提下，如何合理、高效、低成本的解决分配与 运送的问题，也就是说如何将货物从配送中心按照一定的要求发送到若干个用户点。 配送方案应该包括两个相关的环节：有哪些用户要被分配到一条回路上，即有哪 些用户的货物应该安排在同一辆车上；每条配送路线上用户的连接顺序。物流配 送车辆调度的最优解实际上是一个效率最高的运输方案，它应明确的规定应派出的 车辆型号、车辆数以及每辆车的具体行车路线。实施这一配送方案，即可以满足用 户的需求，又可以使总的运输行程最短。 7 物流配送中车辆调度问题的研究 2 2 车辆调度问题的构成要素 物流配送车辆调度问题主要包括货物、车辆、配送中心、客户、运输网络、约 束条件、和目标函数等要素。 ( 1 ) 货物 货物是我国交通运输领域中的一个特有专用概念，交通运输领域将其经营的对 象分为两大类：一类是人，一类是物。“物”这一类的运输目标统称为货物。我们 这里所说的货物是指物流配送的对象，每批货物都包括品名、包装、重量、体积、 要求送到( 或取走) 的时间和地点，能否分批配送等属性。 ( 2 ) 车辆 车辆是“车”与车的单位“辆的总称。所谓车，是指陆地上用轮子转动的交通 工具；所谓辆，来源于古代对车的计量方法。本文所说的车辆是指运载货物的工具， 车辆的主要属性包括：类型、工作时间、配送前的停放位置、载重量以及配送任务 完成后的停放位置等。 ( 3 ) 配送中心 配送中心是指接受供应者所提供的多品种、小批量的货物，通过存储、保管、分 拣、配货以及流通加工、信息处理等作业后，将按需要者订货要求配齐的货物送交 顾客的组织机构和物流设施。本文所说的配送中心是指从事配送业务的物流场所或 组织，如可以进行货物集中、分拣、配货、送货等的仓库、车站、港口等固定场所。 在物流配送系统中，配送中心可以只有一个，也可以同时具有多个。 配送中心专业性强，和客户有固定的配送关系，一般实行计划配送，需配送的商 品有一定的库存量，一般情况很少超越自己的经营范围。配送中心的设施及工艺流 程是根据配送需要专门设计的，所以配送能力很强，配送距离较远，配送的品种较 多，配送数量比较大。使用配送中心配送覆盖面宽，规模大，因此，必须有一套配 套的大规模实施配送的设施。本文的研究背景就是基于配送中心的物流配送中车辆 调度问题的研究。 ( 4 ) 客户 客户指的是物流配送的服务对象，可以是各种零售店，也可以是分仓库，还可以 是别的仓库的外调。也就是说客户是有配送任务的对象的统称。客户的属性包括需 求数量、需求时间、需求次数及目前需求的满足动态等。 ( 5 ) 运输网络 第二章车辆调度问题概述 本文的运输网络采用了离散数学中对网的介绍，配送中心、客户、停车场等构成 网络的顶点、它们之间的交互运输构成了无向边，具体的运输任务被称为由有向弧 组成的运输的网络。边、弧的属性包括方向、权值和交通流量限制等。 在运输网络中，边或弧具有一定的权值，该值可以表示为距离、时间或费用。边 或弧的权值变化具有以下几种情况：固定不变，不随着时间和车辆的不同而变化； 随时间段或者车辆不同而变化；既随着时间的不同而变化，又随着车辆的不同而变 化。 对运输网络中的定点、边或弧的交通流量要求分为以下几种情况：无流量限制； 边、弧限制，即每条边、弧上同时行驶的车辆数有限；顶点限制，即每个顶点上同 时装、卸货的车辆数有限；边、弧、顶点都有限制。 ( 6 ) 约束条件 物流配送车辆调度问题应满足以下约束条件：能够满足所有客户对货物品种、规 格、数量的要求：能够在客户要求或者承受的时间内将货物送到；运输车辆每天的 运行时间、运行历程都要有一定的限制，不能超过预定的时间或者里程；在物流配 送过程中实际装载的货物不能超过车辆的最大载重要求，也就是不能超载；当然， 客户的需求也必须在物流中心现有的运力范围内，也就是目前有这个能力去完成待 完成的任务。 ( 7 ) 目标函数 目标函数是指所关心的目标( 某一变量) 与相关的因素( 某些变量) 的函数关系。简 单的说，就是你求解后所得出的那个函数。在求解前函数是未知的，按照你的思路 将已知条件利用起来，去求解未知量的函数关系式，即为目标函数。本课题研究的 物流配送车辆调度问题，可以只选用一个目标，也可以同时选用多个目标。使用概 率比较多的目标函数主要有： 配送的距离最短，也就是在配送过程中车辆所走的路程最短。在实际的物流 配送中，配送里程直接关系到配送车辆的耗油量、磨损程度以及司机疲劳程度等因 素。因此，在众多的目标函数中选择配送里程最短的目标，在某种程度上可以直接 减少运输成本。 配送车辆的载重量与公里数最少，这种方式的目标是将配送距离与车辆的载 重量进行了有机结合，综合来考虑载重量与配送距离之间的关系，以达到最优化的 配置，是比较常用的目标之一。 综合费用最低，完成最多的任务，花最少的成本，这是物流配送中的一个根 9 物流配送中车辆调度问题的研究 本原则。降低各项开支的综合费用是实现物流配送业务中取得良好经济效益的根本 要求。在物流配送中，与配送相关的费用包括：车辆维护费用、车辆耗油费用、车 队管理费用、装卸工所需费用、各部门人员工资费用等。 准时完成任务，无论是分仓库还是分销点，各种用户都对需求的交货时间有 着严格的要求。配送任务完成的准时性，很大程度上决定了配送公司在客户心中的 地位，决定了公司的信誉度。各种成本虽然是必须考虑的因素，也是最实际的因素， 但是为提高配送服务质量，按时完成用户的需求，有时需要将准时性最高作为配送 路线的目标。 使用的车辆数最少，该目标考虑的是使用尽量少的车辆去完成指定的配送任 务。前面的目标叙述了各项指标的要求，但是如果车辆跑的距离最短、也是按时到 达的，但是使用的车辆都没有满载，这无疑也是对资源的一种浪费，也不能是整体 配送效益达到最优，所以必须要求车辆的满载率最高，以充分利用车辆的装载能力。 劳动消耗最低，充分考虑人的因素。也就是使用最少的司机数，这当然和前 面使用最少的车辆数是一致的，只有车辆少了，司机才会少，只有车辆都装满了， 才会使用最少的车辆。只有选择的距离最短了，司机才能工作最短的时间，这些都 是重要的目标值。 2 3 车辆调度问题的分类 车辆调度问题( v i s u a l s c h e d u l ep r o b l e m ，v s p ) 被提出后，国内外各学科的学者从 不同角度对它进行了各种研究，并各自按不同的标准对其进行了分类8 11 9 1 。综合起 来可分为以下几种： ( 1 ) 按车场数目分：有单车场车辆调度问题和多车场车辆调度问题。单车场问题 指配送系统中仅有一个配送中心，多车场车辆调度问题指配送系统中存在多个配送 中心。 ( 2 ) 按配送任务特征分：分为纯送货问题、纯取货问题以及取送混合问题。其中 纯送货问题指仅仅考虑从物流中心向客户送货，而不考虑从用户向配送中心送货； 纯取货问题指单纯考虑把各客户供应的货物取到配送中心不考虑配送中心给客户供 货问题；取送混合问题是上面两者的有机组合，既要考虑将客户需求的货物从物流 中心送到各个客户，同时还考虑将客户提供的货物从客户取到物流中心。 ( 3 ) 按车辆载货状况分：分为满载问题、非满载问题以及满载和非满载混合问题。 满载问题指的是货运量不小于车辆容量，完成一项任务需要不少于一辆车：非满载 1 0 第二章车辆调度问题概述 问题指的是货运量小于车辆容量，多项货物合用一辆车，在实际的车辆配送过程中 经常会出现这种处于非满载的状态；满载和非满载混合问题是上述两者的有机组合， 既存在一部分客户需求和供应的货物数量大于或等于车辆的载重量，同时又存在另 一部分客户需求量或供应的货物数量小于车辆的载重量，上述情况就造成一部分配 送车辆满载运行，而另一部分运行在非满载的状态。 ( 4 ) 按客户对货物处理时间的要求分：分为无时间约束问题和有时间约束问题 p o 。其中无时间约束问题指的是客户对货物的取走和送到的时间没有严格的要求； 有时间约束问题指的是客户要求将其需求的货物在一定的时间范围内送到，并且将 供应的货物在一定的时间范围内取走。有时间约束问题又分为硬时间窗问题和软时 间窗问题，硬时间窗问题指的是对任务的完成有硬性的时间限制，或者说时间要求。 软时间窗问题指的是有一定的时间约束，但是相对比较宽松，尽量在用户规定的时 间范围内将货物送到或者取走，但是如果超越了规定的时间限制可能要有一定的处 罚机制。 ( 5 ) 按车辆类型分：分为单车型问题和多车型问题。单车型问题指所有配送车辆 类型和容量相同，这种情况方便统一管理和装卸。多车型问题指在执行任务过程中 的配送车辆类型和容量不完全相同，这种情况处理起来比较复杂。 ( 6 ) 按车辆对车场所属关系分：分为开放式车辆调度问题和封闭式车辆调度问 题。开放式车辆调度问题指的是车辆完成配送任务后可以不返回其原来发出车场； 封闭式车辆调度问题指的是车辆完成配送任务后必须返回其原来发出车场。本课题 是针对开放式车辆调度问题进行的研究。 ( 7 ) 按优化目标数分：分为单目标问题和多目标问题。单目标问题指的是仅考虑 一个配送目标；而多目标问题指的是同时考虑多个配送目标。 2 4 车辆调度的相关求解算法 用于解决物流配送车辆调度问题的算法分为：精确算法和启发式算法两大类， 精确算法一般用于解决小规模的v r p 问题，车辆调度问题应用最为广泛的算法是启 发式算法，启发式算法并不追求问题的最优解，而是强调问题解的满意性。所以， 启发式算法对于大规模的车辆调度问题能在较短的时间内获得较满意的次优解，并 且这些算法的通用性也很强。常见的启发式算法有如下几种【1 1 】： ( 1 ) c ws a v i n g s 算法 c ws a v i n g s 算法采用了几何中三角形的边定理，即三角形的两边之和大于第三 物流配送中车辆调度问题的研究 边。当路径中有这样的两个边时用第三边来代替，以达到节约配送距离的目的。我 们可以设节点珥口节戊之间的节约量为s i j ，这两点和节点0 2 _ 间的距离为d o i 和d o j ， 贝l j s i j = d o i + d o j d i j ( i j ，i , j = l ，2 ，1 1 ，) ，算法首先求出所有s i j ，并按非增顺序排列。 然后从最大的s i j 开始，确定是否存在两条路径，其中一条从弧( 0 j ) 开始，而另一条以 ( i ，o ) 结束。如果存在，则去掉弧( o j ) 、( i ，o ) ，引入弧( j ，i ) 合并这两条路径。重复上述 过程直到没有路径可以合并。 ( 2 ) s w e e p 算法 s w e e p 算法是一种“先分组后路线”的算法。所谓的分组就是：首先计算出要访 问的顾客的位置的极坐标，并把这些极坐标按角度大小排序，然后在未分配到任何 路径中的顾客中从角度最小的顾客开始，依次将顾客归并到相应的路径中，直到车 辆的能力约束满足为止，再重新选择新的车辆，重复上述过程，直到所有的顾客都 分配完毕。最后利用t s p 的优化算法对各子路经进行优化。 ( 3 ) c l u s t e ra n dr o u t e 算法 一般有两种方法：先聚类后排序方法( c f r s ) 和先排序后聚类方法( r f c s ) 。c f r s 最早由g g i l l e t t 等提出，它是先用启发式方法将节点分成若干路径，然后对路径中的 点进行排序。r f c se h b e s l e y 提出，它先对所有节点进行t s p 排序，然后将大的路径 分成若干个小路径。 ( 4 ) 遗传算法g a 遗传算法使用群体搜索技术，借用适者生存规律进行局部搜索改进，它通过对 当前群体施加选择、交叉、变异等一系列遗传操作，从而产生出新一代的群体，每 一次进化则对应解的一次迭代，并逐步使群体进化到包含或接近最优解的状体。当 迭代次数达到最大次数限制或群体中的个体无显著差异时，迭代终止。j l a w r e n c e 最 先将g a 应用于求解车辆调度问题。 ( 5 ) 禁忌搜索算法t s t s 的思想由g l o v e r 最早提出，它通过对避开一些局部最优解，达到接纳一部分 较差解，从而跳出局部搜索的目的。t s 是对局部邻域搜索的一种扩展，是一种全局 逐步寻优算法，是对人类思维过程的一种模拟【1 2 】【1 3 】。禁忌搜索算法通过利用一个禁 忌表记录已经到达过的局部最优点，并在后面的搜索中，根据某种限制循环的规则 和禁忌表中记录的信息在当前搜索邻域中取一个合适的解。 ( 6 ) 模拟退火算法s a t l 4 1 其思想最早有m e t r o p o l i s1 9 5 3 年提出，o s m a n 于1 9 9 3 年用之解决v i 冲。模拟退火 1 2 第二章车辆调度问题概述 算法用固体退火模拟组合优化问题，将内能模拟为目标函数值，温度演化成控制参 数。由初始解和控制参数初值开始，对当前解重复“产生新解_ 计算目标函数差_ 接受或舍弃”的迭代，并逐步衰减控制参数值，算法终止时的当前解即为所得近似 最优解。 ( 7 ) 蚁群优化算法a c o 蚁群算法模拟了蚁群搜索食物的行为。蚂蚁在寻找食物时，会在它所经过的路 径排放一种外激素( p h e r o m o n e ，在算法中称为信息素) 作为标记，排放的量则根据路 径长度和食物的等级决定。这些外激素可以指导蚂蚁的运动方向，并使蚁群朝着外 激素强度高的方向移动。在用蚁群算法解决车辆调度问题时，可根据优化的目标函 数个数，构造多组相互协作的人工蚁群，使各组分别优化其中的一个目标函数，并 以共用解的方式建立协作关系。 在以上求解v r p 的算法中，有的算法利用全局信息进行整体搜索适合构解，如 g a 等；还有的利用局部信息，适合改进解，如s a 、t s 等。每种方法都各有所长与 不足，一般来说，根据具体的求解问题，采用两种或两种以上的混合方法，能够得 到更好的解。 2 5 ，j 、结 本章从车辆调度基本理论的角度，首先介绍了车辆调度涉及到的基本概念，包 括了问题的描述和构成要素。其次对车辆调度问题的分类进行的描述，列举了一些 相关解决车辆调度问题的算法。 1 3 第三章遗传算法概述 第三章遗传算法概述 3 1 背景介绍 遗传算法( g e n e t i c al g o r i t h m ga ) 是由美 m i c h i g a n 大学j h o l l a n d 教授和他的学 生发展建立的一类借鉴生物界的进化规律一适者生存、优胜劣汰遗传机制演化而来 的概率搜索算法【1 5 】。g a 算法是近几年发展起来的一种崭新的全局优化算法，遗传算 法作为一种非数值并行算法，其思想起源于生物遗传学适者生存的自然规律，通过