（应用数学专业论文）带有转运中心的车辆组合运输问题研究.pdf

1 北京化工大学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究工作所取得的成果。除文中已经注明引用的内容外，本 论文不含任何其他个人或集体己经发表或撰写过的作品成果。对本文 的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 作者签名：蛊塑 蹴 关于论文使用授权的说明 学位论文作者完全了解北京化工大学有关保留和使用学位论文 的规定，即：研究生在校攻读学位期间论文工作的知识产权单位属北 京化工大学。学校有权保留并向国家有关部门或机构送交论文的复印 件和磁盘，允许学位论文被查阅和借阅；学校可以公布学位论文的全 部或部分内容，可以允许采用影印、缩印或其它复制手段保存、汇编 学位论文。 保密论文注释：本学位论文属于保密范围，在上年解密后适用 本授权书。非保密论文注释：本学位论文不属于保密范围，适用本授 权书。 作者签名：童塑嘶型：! ：三! 导师签名：翌蒸墅堕日期：竺丑：兰里 学位论文数据集 中图分类号 0 2 2 4 学科分类号 0 7 0 1 论文编号 密级非保密 学位授予单位代码 1 0 0 1 0 学位授予单位名称北京化工大学 作者姓名 肖辉君 学号2 0 0 3 0 0 0 5 8 4 获学位专业名称 应用数学获学位专业代码 0 7 0 1 0 4 课题来源 自选课题研究方向最优化理论与方法 论文题目 带有转运中心的车辆组合运输问题研究 关键词 转运中心，车辆运输问题，动态规划算法，混合算法 论文答辩日期 2 0 0 7 - 5 - 3 0论文类型 l 应用研究 学位论文评阅及答辩委员会情况 姓名职称工作单位学科专长 指导教师杨丰梅教授 北京化工大学最优化理论 评阅入l杨国孝教授 北京理工大学应用数学 评阅人2赵宝元副教授北京化工大学应用数学 评阅人3杨永愉教授 北京化工大学应用数学 评阅人4 评阅人5 撇员糊杨国孝教授北京理工大学 应用数学 答辩委员1 赵宝元副教授北京化工大学 应用数学 答辩委员2 杨永愉教授北京化工大学应用数学 答辩委员3 答辩委员4 答辩委员5 注：一论文类型：1 基础研究2 应用研究3 开发研究4 其它 二中图分类号在中国图书资料分类法查询 三学科分类号在中华人民共和国国家标准( c b t1 3 7 4 5 - 9 ) 镁学科分类与代码中 查询 四论文编号由单位代码和年份及学号的后四位组成 3 一 摘要 带有转运中心的车辆组合运输问题研究 摘要 本文主要对带有转运中心的各类车辆组合运输问题进行了研究。 首先，介绍了物流系统中车辆运输配送优化问题的发展、分类和研究 对象，概述了各种基本算法。其次，深入研究了带有转运中心的几类 物流系统的数学模型、算法优化和算例比较。最后，对未来的研究方 向进行了展望。 本文的主要创新点在于： ( 1 ) 针对带有转运中心的几类车辆组合运输问题建立了具有实 际意义、又便于操作的混合整数线性规划模型，其中包括多期单产品、 单期多产品和多期多产品的物流系统。模型的特色在于模型中的目标 函数加入了路径选择的控制变量，从而降低了问题的复杂性。同时， 又是从单一问题到系列问题的研究，体现了研究思路的连贯性和研究 方法的应用延续性。 ( 2 ) 通过应用动态规划算法、分支定界法以及两阶段法设计了 该物流系统的混合算法。算例实验表明，算法的可操作性和运行效果 以及解的满意性都得到了很大提高。 关键词：转运中心；车辆运输问题；动态规划算法；混合算法 北京化工大学硕士学位论文 一_ 一 一一 t h er e s e a r c ho fv e h i c l er o u t i n g p r o b l e m s w i t ht r a n s s h i p m e n tp o i n t s a b s t r a c t i nt h ed i s s e r t a t i o n ，t h ev e h i c l er o u t i n gp r o b l e m s ( v r p ) w i t h t r a n s s h i p m e n tp o i n t sa r em a i n l ys t u d i e d f i r s t l y , t h ed e v e l o p m e n t ，t h e c l a s s i f i c a t i o n sa n dt h es t u d i e do b j e c to ft h ev e h i c l er o u t i n g p r o b l e m sa r e i n t r o d u c e d t h e n ，v a r i o u sb a s i ca l g o r i t h m sa r eg i v e ni nd e t a i l s e c o n d l y ， m a t h e m a t i c a lm o d e l s ，o p t i m i z e da l g o r i t h m sa n dn u m e r i c a le x a m p l e so f s e v e r a lv e h i c l er o u t i n gp r o b l e m sw i t ht r a n s s h i p m e n tp o i n t sa r es t u d i e d f i n a l l y , t h ed i r e c t i o no ff u t u r er e s e a r c hi ss u g g e s t e d o u rm a i nn o v e lw o r ki sl i k ef o l l o w s ： ( 1 ) f i r s to fa l l ，b a s e do nt h es e v e r a lv e h i c l er o u t i n gp r o b l e m sw i t h t r a n s s h i p m e n tp o i n t s ，m a t h e m a t i c a lm o d e l sw h i c hh a v ep r a c t i c a l m e a n i n g sa n dc o n v e n i e n tt oo p e r a t ea r eb u i l ti n c l u d i n go fs i n g l ep r o d u c t o nm u l t i 。p e r i o d sp r o b l e m ，m u l t i 。p r o d u c t so ns i n g l ep e r i o dp r o b l e ma n d m u l t i - p r o d u c t so nm u l t i - p e r i o d sp r o b l e m t h ef e a t u r eo ft h em o d e l si s a d dt h ec o n t r o lv a r i a b l e sw h i c hi sc h o o s et h ep a t hi nt ot h eo b j e c t i v e f u n c t i o n s a n di tm a d et h ep r o b l e ms i m p l e r m e a n w h i l e ，i ti sa l s ot h e r e s e a r c hf r o ms i n g l ep r o b l e mt oas e r i e so fp r o b l e m s t h a te m b o d i e dt h e 上 tr k 摘要 i d e ao fac o h e r e n tr e s e a r c ha n dt h ec o n t i n u o u sa p p l i c a t i o no ft h em e t h o d s ( 2 ) t h e nt h en e wi m p r o v e da l g o r i t h mi sg i v e ni nd e t a i l t h a ti s d y n a 面cp r o g r a m m i n ga l g o r i t h ma n dh y b r i da l g o r i t h mw h i c h i sm a d eu p b yt w o p h a s em e t h o da n d t h eb r a n c h 。a n d - b o u n d a l g o r i t h m a n d a p r a c t i c a l n u m e r i c a l e x a m p l e i su s e dt o c o m p a r et h e r e s u l t s t h e e x p e r i m e n t a le x a m p l e ss h o wt h a tt h ei m p r o v e da l g o r i t h mc a l lb ee a s y o p e r a t e d t h er e s u l t sa n dt h es a t i s f a c t i o n o ft h es o l u t i o n sh a v eb e e n k e y w o r d s ：t r a n s s h i p m e n tp o i n t s ，t h ev e h i c l er o u t i n g p r o b l e m s f v r d ，d y n a m i cp r o g r a m m i n ga l g o r i t h m ，h y b r i d a l g o r i t h m i i i 一 北京化工大学硕士学位论文 目录 第一章绪论1 1 1 物流系统概述l 1 1 1 物流系统发展现状及需求前景l 1 1 2 物流系统分类及其他问题3 1 2 物流配送系统概述_ 4 1 2 1 物流配送基本概念4 1 2 2 物流配送主要研究对象5 1 3 本文的主要内容和结构6 第二章车辆调度问题的算法8 2 1 计算复杂性8 2 2 旅行商方法8 2 3 动态规划法9 2 4 节约法9 2 5 扫描法1 0 2 6 分区配送算法1 1 2 7 方案评价法1 3 2 8 现代优化计算方法1 3 第三章多期单产品车辆组合运输问题1 5 3 1 问题描述1 5 3 2 原始模型1 5 3 3 改进解法1 6 3 3 1 模型改进1 6 3 3 2 算法优化1 7 3 4 数值实验1 9 3 5 结论2 1 i v 目录 第四章单期多产品车辆组合运输问题2 2 4 1 问题提出2 2 4 2 模型建立2 2 4 3 算法概述2 3 4 3 1 策略描述2 4 4 3 2 算法描述2 4 4 4 数值实验2 4 4 5 结论”一“”? ”“”- ”2 6 第五章多期多产品问题2 7 5 1 基本问题2 7 5 2 建立模型2 7 5 3 算法描述“2 9 5 3 1 动态规划算法2 9 5 3 2 算法概述3 0 5 3 3 算法流程图3 l 5 4 数值实验3 l 5 5 结论”一”3 3 第六章总结与展望3 4 6 1 总结”一“一”3 4 6 2 未来研究的展望3 4 参考文献3 6 附 录3 9 一 致谢”。”。一”。4 8 研究成果及发表的学术论文4 9 v 符号说明 符号说明 自备车集合 雇佣车种类集合 考虑期间集合 自各车可能路径集合 自备车i 的最大容量限制 j 种雇佣车辆的最大容量限制 从1 3 点运往n 3 点的车辆的最大容量限制 该种车辆的运行费用 自备车i 从路径r 运行的费用 j 种车辆的一次雇佣费用 单件产品每天的库存费用 第p 天的总需求量 沿路径r 运行一次的时间 自备车辆每天的最长运行时间限制 期间数 v i ， ， p r 耽 哆嘞 岛 岛 9白易0 w r 第一章绪论 1 1 物流系统概述 第一章绪论 物流科学登上历史舞台只不过数十年时间，由于它对社会经济和企业经营具 有强大的影响力，引起了经济界和企业界的高度重视，而被称为“未开发的黑大 陆 、“第三利润源泉气。企业脚下的金矿一【1 1 1 1 1 物流系统发展现状及需求前景 物流产业被认为是国民经济发展的动脉和基础产业，其发展程度成为衡量一 国现代化程度和综合国力的重要标志之一，被喻为促进经济增长的。加速器 。 近年来，伴随着经济全球化进程的加快，现代信息网络技术的日益完善，我国物 流发展日益呈现上升的态势。2 0 0 5 年l 至9 月，全国社会物流总值为3 5 6 万亿 元，同比增长2 5 1 ，明显高于同期g d p 的增长速度。物流规模迅速扩大，表明 经济增长对物流需求越来越大，经济发展对物流的依赖程度也越来越高【2 1 改革开放以来，经过建国五十多年特别是改革开放后二十多年的建设，中国 物流业也同国民经济其他部门一样有了较大发展，基本建成了由铁路、公路、水 运、民航和管道运输组成的物流运输基础设施体系。 其发展现状如下： 1 交通、通信等物流基础设施的能力大为提高，市场物流网络逐步扩大，以 铁路、公路、海运、航空、管道运输五种方式组成的综合运输体系基本形成，交 通运输对于国民经济发展的瓶颈制约得到缓解。公用通讯网的通信能力和技术水 平明显提高，网络规模居世界第二。以现代信息技术为基础的专用物流信息网开 始在一些部门和地区建立。过去从事物资流通的企业已经脱离了计划体制的束 缚，初步形成一支社会化、专业化的产业队伍，并建立了以中心城市为依托的城 乡一体的流通网络。 2 物流规模可以从量的角度反映物流业的发展水平，主要包括物流活动中的 运输、储存、包装、装卸搬运和流通加工的作业量。由于运输是实现产品位移的 中心环节，我们可以用运输量和输送能力来近似衡量社会物流规模。统计资料知， 1 9 9 5 年我国共完成货物运输量1 2 3 7 亿吨，2 0 0 1 年达到1 5 8 6 亿吨。由此可见， 我国物流规模在不断扩大。 3 随着对外贸易的迅猛发展，国际物流量快速增长。近几年，代表我国国际 北京化工大学硕士学位论文 物流发展规模的海上国际集装箱运输量，平均以两位数的速度快速增长。以沿海 主要港口为中心的国际集装箱多式联运网络也己初步形成。 4 物流质量有所提高，但还有待改善。物流质量主要由物流时间、物流费用、 物流效率来衡量。中国物流业由于受多方面因素的影响，物流质量总体水平比较 低。 ( 1 ) 有关资料显示，我国工业生产中物流所占用的时间几乎为整个生产过程 的9 0 。 ( 2 ) 物流费用在生产费用中所占的比例，因各种产品对物流的依赖程度不同 而不同。据有关资料介绍，若从物流业总体费用考虑，物流费用占商品总成本的 比重已经超过了4 0 。 ( 3 ) 一般情况，我们用物流相关行业的成本费用总和与国民生产总值的比率 来评价物流总体效率。目前，发达国家的这个比值为9 5 - 1 0 ，而我国却高达 2 0 左右企业流动资金年周转速度不到2 次，批发、零售业周转速度不到3 次， 大大低予发达国家的周转速度。因缺乏合理的物流组织，公路货运空驶率高达 4 7 嘣3 1 。 5 造成上述问题的原因有： ( 1 ) 体制障碍。多年来计划经济体制下形成的行业垄断、部门分割、地区封 锁的状况，还没有完全根除。充分竞争的物流市场还没有完全形成，物流资源得 不到有效整合。 ( 2 ) 政策障碍。税收、工商注册、土地、收费等一些政策还不适应现代物流 业发展的需要。 ( 3 ) 技术标准障碍。物流的不同环节、不同运输方式之间的技术、信息标准 不统一，货物多次装卸、多次拆箱装箱等现象相当普遍。 而在原来的计划经济体制下，我国经济活动中的生产和流通被当作两个彼此 隔绝的要素。随着社会主义市场经济的逐步建立，这种模式已经发生了变化，两 者之间的界限逐渐被打破。生产、流通与消费等经济活动的各个方面被“物流一 综合在一起，形成以市场为导向，以客户满足为宗旨，以获取系统总效益最优化 为目标的新兴行业。但是，由于我国物流业的发展起步较晚，又受到种种条件的 制约，因此还存在着不少问题，迫切需要我们加以重视和研究，清除一切阻碍物 流健康发展的不利因素，以充分发挥物流业的优势。 从总体来看，我国物流产业的规模目前还比较小，发展水平也比较低。这种 情况一方面是由我国经济发展的水平和阶段决定的，另一个更重要的问题是还存 在着许多影响和制约物流业健康发展的因素所以。物流业的需求主要围绕以下 几个方面 第一章绪论 1 由于思想观念仍没有脱离旧体制，对搞好物流业的重要性认识不足，所以 迫切需要物流管理观念的更新。 2 物流基础设施和装备条件制约着物流效率的提高。由于过去长期受“重生 产，轻流通 思想影响，我国物流基础设施总体规模仍然偏小：运输网络密度分 别为1 3 4 4 4 8 公里万平方公里和1 0 4 3 公里万人，分别只相当于美国的1 9 6 和 1 5 8 ；德国的9 和1 5 8 ：印度的2 4 9 和4 8 3 ；巴西的7 1 3 和8 8 ，不 仅落后于发达国家，而且与印度、巴西等发展中国家相比也存在较大差距。另外， 还存在以下问题：仓储设施落后，大量的仓库是五、六十年代的老旧建筑；现代 化的集装箱、散装运输发展不快；高效专用运输车少：汽车以中型为主，能耗大， 效率低；装卸搬运的机械化水平低 3 物流产业管理模式不合理。目前，中国物流业仍是分散的管理方式，涉及 众多的专业和综合部门，造成了物流行业管理中存在条块分割、部门分割的现象， 缺乏统一规划，重复建设严重。加上市场发育滞后，全国物流企业处于小、多、 散、弱的状况，难以形成有效的社会服务网络。此外，已经形成的社会物流系统 与企业物流由于管理目的、手段不同，两者不能有效地结合与协调发展，也对物 流合理化产生不利影响。 4 物流企业的经营管理和服务水平比较低。目前，我国物流企业的规模、实 力都比较小，只能简单地提供运输和仓储服务，而在流通加工、物流信息服务、 库存管理、物流成本控制等物流增值服务方面，尤其在物流方案设计以及全程物 流服务等方面还没有全面展开。多数从事物流服务的企业，缺乏必要的服务规范 与内部管理规程，经营管理粗放，很难提供规范化的物流服务，服务质量比较差。 5 物流基础理论研究落后，物流专业人才缺乏。我国从事物流理论研究的科 研机构很少，物流教育也处于落后水平。在全国上千所高等院校中，设置物流专 业的只有1 0 所左右。而且，物流企业自身也忽视对人才的引进，据有关资料统 计，在我国物流产业中，具有中专以上文化水平的职工仅占总体职工人数的7 5 ， 这一水平大大低于其他产业。从而可以看出，优化物流系统刻不容缓【们】。 在这种形势下，研究如何通过实施科学的物流管理，以提高物流效率、降低 物流成本、提高服务质量是十分必要的。 1 1 2 物流系统分类及其他问题 分类： 按照不同的标准，物流可作不同的分类，通常，物流可以按以下几种方式 1 按物流的范畴分为社会物流和企业物流 北京化工大学硕士学位论文 社会物流属于宏观范畴，包括设备制造、运输、仓储、装饰包装、配送、信 息服务等，公共物流和第三方物流贯穿其中；企业物流属于微观物流的范畴，包 括生产物流、供应物流、销售物流、回收物流和废弃物流等。 2 根据作用领域的不同，物流分为生产领域的物流和流通领域的物流 生产领域的物流贯穿生产的整个过程。生产的全过程从原材料的采购开始， 便要求有相应的供应物流活动，即采购生产所需的材料；在生产的各工艺流程之 间，需要原材料、半成品的物流过程，即所谓的生产物流；部分余料、可重复利 用的物资的回收，就是所谓的回收物流；废弃物的处理则需要废弃物物流。 流通领域的物流主要是指销售物流。在当今买方市场条件下，销售物流活动 带有极强的服务性，以满足买方的需求，最终实现销售。在这种市场前提下，销 售往往以送达用户并经过售后服务才算终止，因此企业销售物流的特点便是通过 包装、送货、配送等一系列物流实现销售 3 根据提供服务的主体不同，将物流分为第三方物流和企业内部物流 第三方物流( t h i r dp a r t yl o g i s t i c s ，3 p l ) 。是指由物流劳务的供方、需 方之外的第三方去完成物流服务的运作模式。第三方就是提供物流交易双方的部 分或全部物流功能的外部服务提供者。 企业内部物流是指一个生产企业从原材料进厂后，经过多道工序加工成零 件，然后零件组装成部件，最后组装成成品出厂，这种企业内部物资的流动称为 企业内部物流。 4 按物流的流向不同，还可以分为内向物流和外向物流 内向物流是企业从生产资料供应商进货所引发的产品流动，即企业从市场采 购的过程；外向型物流是从企业到消费者之间的产品流动，即企业将产品送达市 场并完成与消费者交换的过程。 在物流系统中，最大的成本投资就是配送中心的建设；而且配送中心居于重 要的枢纽地位，起着承上启下的作用。因此物流配送中心的合理选址就显得十分 重要好的配送中心，应该能够将各种因素对未来物流配送造成的影响作好综合 的考虑和权衡睁脚因此，物流配送中心的选址和建设问题是一个需要综合考虑 的难题。 物流配送所面对的实际情况是复杂的，货物的流动方向也很可能是随机的， 或者逆向的，如何处理这方面的关系也是物流将面对的一个实际问题。 1 2 物流配送系统概述 1 2 1 物流配送基本概念 第一章绪论 物流配送是物流系统中的一个重要环节，它是指按客户( 包括零售商店、用 户等) 的订货要求( 包括在货物种类、数量和时间等方面的要求) ，在物流中心( 也 称物流基地、物流据点，包括配送中心、仓库、车站、港口等) 进行分货、配货 工作，并将配好的货物及时送交收货人的物流活动。物流配送过程主要包括以下 作业环节：从生产工厂进货或运达并集结的集货作业；根据各个客户的不同需求， 在物流中心将所需要的货物挑选出来的分货和配货作业：考虑配送货物的重量和 体积，充分利用车辆的载重和容积的货物配装作业；合理确定车辆配送路线并及 时送货的作业。可见，物流配送是一种集集货、存储、配货、配装、送货等多种 功能为一体的物资流通方式。如下图l l ： 图1 - 1 物流配送结构图 目前我国的物流配送基本上还停留在“只送不配 的水平上，造成物流配送 效率低下，车辆空驶严重，物流配送成本很高，服务质量却很低。鉴于此，本文 将着重研究物流配送车辆调度问题中的带有转运中心的车辆组合运输问题。该问 题包括集货线路优化、货物配装及送货线路优化等，是物流配送系统的关键问题 之一。 1 2 2 物流配送主要研究对象 国外将物流配送车辆调度问题归结为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 et r a v e l i n gs a l e s m a np 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 5 1 。 北京化工大学硕士学位论文 国外对物流配送车辆调度问题作了大量而深入的研究。早在1 9 8 3 年 b o d i n g o l d e n 等人在他们的综述文章中就列举了7 0 0 余篇有关文献。在 c h r i s t o f i d e s ( 1 9 8 5 ) ，g o l d e n 和a s s a d ( 1 9 8 8 ) 编辑的论文集中，以及a l t i n k e m o 和 g a r i s h ( 1 9 9 1 ) ，l a p o r t e ( 1 9 9 2 ) ，s a l h i ( 1 9 9 3 ) 等的综述文章中都对该领域的研究成 果进行了详尽的阐述。该研究领域的代表人物主要有b o d i n , c h r i s t o f i d c s ，g o l d e n , a s s a d ，b a l l ，l a p o r t e ，r i n n o o yk a n , l e n s t r a , d e s r o s i e r s 和d c s r o c h c r s 等t 川。 国内也有一些对物流配送车辆调度问题的研究。李大卫等以t s p 的最近距 离启发式算法为基础，通过设置评价函数来处理时间窗约束，求解了简单的v s p 。 张震针对单车场满载问题，提出了考虑运输行程约束的优化方法蔡延光等应用并 行禁忌搜索算法和模拟退火算法对满载问题进行了求解。刘浩等用模拟退火算法 求解了两车型随机需求的v r p 。张涛等用禁忌搜索算法和遗传算法的混合策略 求解了v r p 。王莉用启发式算法求解了有时限的v r p 。袁健等用神经网络法求 解了v r p 。姜大立、李大卫分别用遗传算法求解了无时限椭时限的物流配送 车辆调度问题。近年来，郭耀煌、李军、谢秉磊等对物流配送车辆调度问题进行 了较为深入的研究，提出了多种求解算法。周双贵对物流配送车辆调度问题的模 型和求解方法也进行了较为深入的研究【1 4 1 。 而本文所主要研究的带有转运中心的车辆组合运输问题的求解方法对解决 上述问题也是有效的。尤其是转运中心的提出，实现了很多问题，如制造业的货 物运输、邮政投递、产品分销等系统的费用时间的优化。可见，本文将带有转运 中心的物流配送车辆组合运输问题作为研究对象，具有一定的理论和现实意义。 1 3 本文的主要内容和结构 本文主要研究了三类物流配送中带有转运中心的车辆组合运输问题。第二章 主要探讨物流系统中的车辆调度问题的各种基本算法，为后面的扩展奠定基础。 第三章提出了多期单产品带有转运中心的车辆组合运输问题的改进模型，该模型 即有原始模型的车辆安排功能，又通过控制变量，增加了路径选择功能；同时， 给出了一种新的混合算法l 一一在动态规划算法基础上进行分支定界和两阶段算 法的混合，并用实际算例进行了算法比较第四章在上一章的基础上。对单期单 产品带有转运中心的车辆组合运输问题进行了研究，就模型、算法、算例给出了 详细的解，仍然以更满意解为目标。第五章更进一步，研究了多期多产品带有转 运中心的车辆组合运输问题，对它的模型、算法、算例进行了初步的研究。最后， 就物流配送中的其他问题进行了探讨，并且给出了总结和展望 本文的基本结构如图1 2 ： 第一章绪论 图l - 2 文章结构图 北京化工大学硕士学位论文 2 1 计算复杂性 第二章车辆调度问题的算法 v r p 提出后，不少专家学者对其计算复杂性进行了研究，这是确定其求解 算法研究方向的基础。在l e n s t r a 和r i n n o o y k a r l 的文献中，对v s p 的计算复杂 性进行了综述和分析；d a n t z i g 和f u i k e r s o n ( 1 9 5 4 ) i 正明了有确定开始时间的v r p 的复杂性为o ( n - ) ；s a v e l s b e r g h ( 1 9 8 5 ) 和s o l o m o n ( 1 9 8 6 ) 提出有时限的心比一 般的v r p 更复杂；s a v e l s b e r g h ( 1 9 8 5 ) 提出有时限的v r p 不仅问题本身是n p 难 题，甚至在车队大小固定时，找一个可行解也是n p 难题；l e n s t r a 和r i n n o o p yk a r l 还证明了几乎所有类型的v r p 均为n p 难题。 v r p 作为一个n p 难题，随着客户数量的增加，可选的配送路径方案数量将 以指数速度急剧增长，。即出现组合爆炸现象。据计算，对于一个有2 0 个顶点的 t s p ( t r a v e l i n gs a l e s m a np r o b l e m ，即旅行商问题) ，其可能的路径总数为2 0 1 ( 2 2 0 ) 6 0 8 1 0 6 ，即使用每秒一亿次的计算机按穷举搜索法求解，也需要计算3 5 0 年。 v r p 作为一个约束性多路旅行商问题，与t s p 相比，不仅约束条件更为复杂， 而且存在多条配送路径，因此，其计算量会比t s p 大得多。一般地，只有在客 户数量较少、运输网络较简单时，才能求得物流配送车辆调度问题的精确最优解。 求v r p 的方法很多，究其实质，可以分为精确算法和启发式算法两大类。 精确算法是指可求出其最优解的算法，主要有：分枝定界法、割平面法、网络流 算法、动态规划法等。由于精确算法的计算量一般随问题规模的增大呈指数增长， 在实际中其应用范围很有限。为此，专家们把精力主要用在构造高质量的启发式 算法上。下面对v r p 的一些常用求解方法进行简单论述【1 7 - 2 3 】。 2 2 旅行商方法 d a n t z i g 和r a m s e r 提出v r p 后，将该问题作为旅行商问题的推广问题进行 求解。旅行商问题，也称为货郎担问题、巡回销售员问题该问题是一个典型的 组合优化问题，可以简单地描述为：设有n 个城市并已知各城市间的旅行费用， 找一条走遍所有城市且费用最低的旅行路线。物流配送车辆调度问题可以说是对 旅行商问题加以一定的限制而形成的，这些限制包括：客户有一定的货物需求( 或 供应) 数量且要求货物在一定的时间范围内送到( 或取走) ，配送车辆的装载量限制 及一次配送的最大行驶距离限制等，即物流配送车辆调度问题是一个多约束的旅 第二章车辆调度问题的算法 行商问题。同时，物流配送车辆调度问题还可以归结为在每一个配送路线中的旅 行商问题。如果把从一个物流中心用一台配送车辆向l 个客户送货的物流配送车 辆调度问题考虑为l + 1 个点的旅行商问题，则它的解是：从物流中心出发，对 所有的客户巡回一次，再回到物流中心的距离为最短的路线。在物流配送车辆调 度问题中，可以把全部配送路线划分为几条大的配送路径，每台配送车辆只沿一 条配送路径送货，即只访问物流中心一次。因此，除了实际的物流中心外，还可 以再虚设几个物流中心，这样，物流配送车辆调度问题就可以转化为有几个封闭 循环线路的旅行商问题，即多路旅行商问题。可见，物流配送车辆调度问题是一 个约束性的多路旅行商问题。将物流配送车辆调度问题转化为旅行商问题后，就 可以利用求解旅行商问题的方法加以求解。目前求解旅行商问题的算法主要有： 近邻法、贪婪法、分枝定界法、最近插入法、最远插入法、双极小生成树法、剥 脱法、空间填空曲线法、k a r p 法、l i t k e 法、c h r i s t o f i d e $ 法、2 - 交叉法、k - 交叉 法、l i n - k e m i g h a n 法、神经网络法、禁忌搜索法、模拟退火法、遗传算法等。 2 3 动态规划法 动态规划是一种常用的运筹学方法，它适于解决这样的问题：某个大问题可 以划分为几个阶段，每个阶段形成一个子问题，各个阶段是相互联系的，每个阶 段都要做出决策，并且某个阶段的决策，常影响下一阶段的决策，从而影响整体 决策。在动态规划求解过程中，作为整个过程的最优策略具有这样的性质：无论 过去的状态和决策如何，对其决策所形成的状态而言，余下的诸决策必须构成最 优策略，这是动态规划的最优化原理。利用这个原理可以把多阶段决策的求解过 程看成是一个连续的递推过程，由后向前逐步推算。在求解时，各状态前面的状 态和决策，对其后面的子问题而言，只不过相当于其初始条件而己，并不影响后 面过程的最优策略。动态规划求解问题的一个突出弱点是：当问题中的变量个数 太多时，将会由于计算机存储器容量和计算速度的限制而无法求解。 从理论上讲，利用动态规划法可以求得物流配送车辆调度问题的精确最优 解。该方法的缺点是：由于动态规划方法本质上是一种枚举法，当物流配送车 辆调度问题较复杂时，状态转移公式将变得十分复杂，求解也会十分复杂，甚至 会因为计算机存储量的限制和计算速度的限制而根本无法求解；使用动态规划 法求解物流配送车辆调度问题时，很难考虑到实际配送过程中的一些具体要求 ( 如按客户指定的时间窗送货或取货等) 。 2 4 节约法 北京化工大学硕士学位论文 节约法【1 4 1 是由c l a r k e 和w r i g h t 于1 9 6 4 年提出的。该方法提出了从多条可供 选择的配送路径中，选出最佳配送路径的方法。 1 用节约法求解物流配送车辆调度问题的步骤 第一步：做出最短距离矩阵。即根据配送网络图中物流中心与客户之间以及 客户相互之间的距离，计算出物流中心与各客户之间以及各客户相互之间的最短 距离矩阵。求配送网络顶点间的最短距离时可采用求最短路的算法，如d i j k s t r a 算法等。 第二步：编制节约里程表。即根据物流中心与客户间及各客户相互间的最短 距离矩阵，利用节约量计算公式计算出客户相互间的节约里程。节约里程的计算 结果有正有负，当节约里程的计算结果为负数时，无实际意义，取其节约量为0 ， 将节约里程填入节约里程表。 第三步。编制节约里程顺序表。即将节约里程表中的节约里程按由大到小的 顺序排列，然后填入节约里程顺序表。 第四步：制定配送路线。即根据节约里程顺序表中节约里程的大小顺序和物 流配送车辆调度问题的约束条件，逐渐组成配送路径图。 2 节约法的特点 节约法是一种启发式方法，它属于逐次逼近法的一种，用该方法不一定能求 得物流配送车辆调度问题的精确最优解，但可以高效地得到问题的近似最优解。 该方法具有计算步骤简单，计算速度快，且易于考虑各种实际问题的优点。该方 法的缺点是未组合点零乱、边缘点难于组合以及有时解的质量不高等。 2 5 扫描法 用扫描法【1 4 1 求解v r p 的步骤扫描法是由g i l l e t 和m i l l e r 于1 9 7 4 年提出的， 该方法的基本思路是采用逐次逼近的方法求解v r p 。利用扫描法求解v r p 时， 物流中心及客户的位置都用极坐标表示，其中物流中心位于坐标原点。 1 用扫描法求解v r p 的步骤如下： 第一步。对客户进行编号。将所有客户按极坐标角度由小到大的顺序编上序 号，若两客户的极坐标角度相同，则将距离物流中心较近的客户给予较小的序号。 设客户的序号分别为l 、2 、l ； 第二步：作初始配送路线按客户序号由小到大的顺序，依次将客户l 、2 、 j i ，纳入初始配送路线l ，其中，j l 为在满足物流配送车辆调度问题的约束条件 ( 主要为车辆装载能力约束和车辆一次配送最大行驶距离约束) 的前提下，第一 第二章车辆调度问题的算法 辆车所能到达的最后客户，换句话说，若将客户j l + l 也纳入路线l ，就会违反 v l 姆的约束条件。按同样的方法依次将客户j l + l 、j l + 2 、j 2 纳入初始配送路 线2 ；最后将客户j k 1 + l 、j k a + 2 、l 纳入初始配送路线k 。上述k 条初始配 送路线即构成初始配送路径方案，该配送路径方案的总配送距离为各配送路线的 距离之和。 第三步：配送路线的调整。试着将路线k ( 贿，2 , k - 1 ) 上的一个客户与路 线k + l 上的一个或多个客户进行交换，如果交换后能够使总配送距离减少，则实 施这种交换，否则放弃交换。选择交换客户时一般遵循以下原则：从路线k 上 去掉的客户应当是在路线k 上所有客户中距坐标原点( 即物流中心) 距离最近的 客户。被考虑用来加在路线k 上的客户应当是：在路线k + l 上的所有客户中离 最后加到路线k 上的客户最近的客户p ；被考虑加在路线k 上的下一个客户是在 路线k + l 上距离客户p 最近的客户。按照此方法对各条配送路线上的客户逐步替 换，以使总配送距离逐步减小。最终将得到该客户编号方案下优化的物流配送路 径方案。 第四步：通过改变客户编号，寻求其它优化的配送路径方案。改变客户编号 的方法主要有以下两种：旋转坐标轴，以改变第一个客户。例如，可通过旋转 坐标轴使原来的第二个客户位于x 轴上，这样一来，原来的第二个客户就变成第 一个客户，相应地，原来的第三个客户变成第二个客户，原来的第l 个客户变 成第l 1 个客户，原来的第1 个客户变成第l 个客户，按照这种编号方法，通过 步骤二和三，可求得另外一种优化的配送路径方案。再旋转坐标轴，还可得到更 多优化的配送路径方案。将客户按极坐标角度从大到小的顺序依次进行编号， 采用这种客户编号方法，也可得到另外的配送路径优化方案。 第五步：求得v r p 的满意解。从上述多个优化的配送路径方案中，选取总 配送距离最小的方案作为v r p 的满意解。 2 扫描法的特征 扫描法是一种逐次逼近法，用该方法不一定能求得v r p 的最优解，但是能 够有效地求得问题的满意解。对于某个具体的v r p ，由于存在多种客户编号方 法，当仅选择一种客户编号方案用扫描法求解时，其计算量相对较小，但相应地 解的质量可能不会很高；当选用多种客户编号方案用扫描法求解时，一般能得到 质量很高的满意解，但相应地，计算量会成倍增加。研究表明，对于v r p ，当 每条路线上的客户数目大体相同且配送路线不太多时，用扫描法求解是非常有效 的。 2 6 分区配送算法 北京化工大学硕士学位论文 1 分区配送算法因】的思考方法 两阶段法是求解物流配送车辆调度问题的一种常用的启发式算法。两阶段法 主要有以下两类：一类是先求配送路线，后分段，即先对客户利用旅行商方法求 出其最优巡回配送路线( 阶段1 ) ，然后根据问题的各种约束条件( 如车辆装载限 制、车辆一次配送的最大行驶距离限制等) 对其路线进行分段( 阶段2 ) ，在每一 小段内，车辆按用旅行商方法确定的配送路线行驶；二是先划分区域，再求行车 路线，即先根据各种约束条件进行配送区域划分( 阶段1 ) ，然后在各小区域内利 用旅行商方法设计最优配送路线( 阶段2 ) 。虽然从表面上看，两类算法仅求解次 序不同，但实际上两类算法的计算结果往往大不相同。研究表明，第一类算法不 能做到渐进最优。因此，除少数早期启发式算法采用第一类算法外绝大多数启 发式算法均采用第二类算法。由于在第二类算法中。划分配送区域的问题十分关 键，因此，也称该类算法为分区配送算法。对于配送区域划分问题，有关学者提 出了许多具有实用价值的算法，如s a n i l y 和a f e d e r g r u v a 提出的极端分区算法 和改进圆形分区算法，j u l i e nb r a r n d 和d a v i ds i m c h i l e v i 提出的基于基地启发式 分区( l e 娜) 算法，s v i s w a n t h a n 和k a m l e s h tm a t h u r 提出