摘要
物流配送中的车辆调度问题是一个应用性很强的问题，随着现代商业的发展，企业的配送任务越来越复杂，多车场车辆路径问题（Multiple-Depot Vehicle Routing Problem，MDVRP）逐渐成为车辆调度新的重要研究方向。所谓多车场配送，是指为了服务更广阔的地理范围内的顾客配送车辆可以从多个车场出发去完成运输任务，达到提高车辆利用率、减少总的运输距离、节约运输成本的目的。
本文从三方面做了一些探索性工作：多车场的单向车辆调度问题、二级库存系统中转载运输的车辆调度和循环物流的车辆调度。首先，绪论概述了论文的研究背景和动机、研究目的和意义、国内外发展动态和水平等；然后，对物流配送及多车场车辆调度的进行简介，主要介绍物流配送的一些新趋势，及在这些新趋势下MDVRP研究的分类，并对其常见的算法进行了概述；再次，本文重点对多车场单向配送的车辆调度进行研究，主要包括数学模型的建立、对常见的几种启发式算法进行介绍并进行了改进，并通过实例证明改进的算法能够起到较好的效果；接着，本文还研究了多车场双向配送的车辆调度，先分析了物流配送中的双向调度问题及其分类，然后选择了二级库存系统转载的车辆调度和循环物流的车辆调度进行具体的研究，建立了数学模型，并提出解决此问题的一种启发式算法，根据该算法进行了实验验算及分析。
关键字：物流配送车辆调度多车场问题启发式算法
Abstract
With the development of modern business, the trend of corporation become big and global and the acquirement of scale logistics, which impel the necessity of building more than one distribution centers. So Multiple-Depot Vehicle Routing Problem(MDVRP)，will become a new important branch of vehicle routing problem. But, up till now many study about VRP are emphasized on single depot，just a little are about multi-depot VRP. Multi-depot VRP means there are more than one depot from which vehicles can go out to distribution.
This paper try to do some research from three aspects: Heuristic algorithm of one-way MDVRP, MDVRP of the transshipment in Two-Echelon System and in the Cycling Logistics system. There are five part consist of the paper. The first part tell some ground and the motility of the research, as well as the literature review. Then part two introduces the new trend of distribution and basic concept about MDVRP. And the third part study the mathematic formulation and Heuristic algorithm of the pickup or delivery of MDVRP, a example prove the Heuristic algorithm is well. And then part four expands the way to the problem of both pickup and delivery MDVRP, which include the Two-Echelon System and Cycling Logistics system. And the mathematic formulation and the Heuristic algorithm have also been given.
Key words: logistics distribution,    vehicle routing problem
Multiple-depot problem,    heuristic algorithm
独创性声明
本人声明：所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除文中已经标明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。
学位论文作者签名：
日期：年月日
学位论文版权使用授权书
本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。
保密□，在年解密后适用本授权书。
本论文属于
不保密□。
(请在以上方框内打 “ √ ” )
学位论文作者签名: 指导教师签名:
日期:  年月日日期:  年月日
1  绪论
1.1 研究背景
在现代物流配送活动中，配送的主体活动是分拣配货及末端或支线运输，其中以送货为目的的末端或支线运输是实现配送的主要手段。在配送活动中配送线路是否合理对配送速度、成本、效益影响很大。对配送线路进行优化决策，可以使物流决策部门或物流规划人员充分利用企业物流资源，发挥物流配送系统潜力，提高物流经济效益，实现物流科学化。
从世界连锁业发展的实践来看，一个便利连锁公司在拥有20个店、总面积达到4000平方米时就要考虑建
配送中心；一个超市连锁公司，在拥有10个店、总面积达到5万平方米时就有建立配送中心的必要；大型超市如配送距离超过300公里，也必须考虑配送中心的布局。所以当便利连锁公司或大型超市连锁公司发展到一定的规模后，就需要建立多个配送中心（如图1－1），如果物流服务区域较大却只拥有一个配送中心，这样就难以保证配送的及时性，导致整个服务水平降低。并且，从配送成本上考虑，在规模大的区域内单一配送中心的成本也较高。为了适应这种状况，多数物流公司在同一个较大的区域内一般设立多个配送中心。比如沃尔玛1990年在全球有14个配送中心，发展到2001年增加到70个配送中心。
图1－1 多配送中心配送图
总配送中用户 总站与分站的货物交
车辆配送路分配送中
在现代物流发展过程中，共同配送是物流配送技术创新的重要成果，成为连锁企业实行同一采购配送的重要方式。集送一体化作为共同配送的重要方法之一，将地区小批货物的集货、送货或相向的运输加以整顿，使之综合进行混装运输。这样使得原来的集货或送货单向运输变为双向混载式配送，从一定程度上扩大服务对象，提高车辆实载率，降低空驶率，进而有效降低交通量[1]。物流论文
因此，综上所述要想解决物流配送中这些新情况的车辆调度问题，就应该在基本车辆调度问题的基础上，考虑多车场、混合业务的情况，对多车场车辆调度及业务复杂的集送一体化进行研究。如图1－2所示。
图1－2物流配送车辆调度的新问题
1.2 研究目的
配送中运输费用约占50%以上，因此合理规划运输线路和配送车辆计划对降低配送成本，提高配送效益具有极其重要作用。由于配送情况每天都是在变化的，如：多配送中心趋势、业务复杂化（集送一体化）等，如何根据具体的配送情况合理的确定配送线路和配送车辆计划是个重要课题。
本文针对多车场车辆调度、二级库存系统中转载运输车辆调度和循环物流的车辆调度进行探讨。在理论上通过对数学模型及启发式算法的研究，更加完善车辆调度理论问题；在实践中能够为共同配送或战略
联盟等背景下形成的多配送中心的车辆调度应用，降低物流配送的运营成本，提高服务水平。
多车场车辆路径问题（Multiple-Depot Vehicle Routing Problem，MDVRP）作为