物流配送车辆毕业论文

《物流配送车辆毕业论文》由会员分享，可在线阅读，更多相关《物流配送车辆毕业论文（52页珍藏版）》请在装配图网上搜索。

1、洛阳理工学院毕业设计（论文）物流配送车辆路径优化方法研究摘 要 目前，国际物流业正朝着高度专业化和社会化的方向发展。近年来，虽然我国物流业取得了很大的发展，但与国外发达国家相比，仍有较大的差距。在物流各环节中，物流配送对物流企业增加利润起着关键作用，车辆路径问题(VRP)作为解决物流配送问题技术的一部分，得到越来越多研究学者和物流企业的重视。 VRP是一个典型的NP-hard问题，即使在客户规模比较小的情况下，求解也比较困难。因此，研究求解各种条件下 VRP的有效算法显得尤为重要。从目前的研究状况来看，虽然对VRP的研究得到了重视，但是仍没有对实际VRP而临的各种情况进行深入的探讨，而且成果比

2、较分散，无论是研究的深度和广度，都不能满足当今物流业迅速发展的需要。针对上述问题，本文在车辆调度问题现有的理论成果基础上，运用智能方法对各种静态非满载车辆调度问题作了比较系统的研究。首先通过相关文献的总结提炼，较为全面地总结了国内外车辆调度问题的研究现状和研究过程中所存在的不足。然后运用遗传算法对单车场容量约束情况下的车辆调度问题进行优化，并且针对具体情况下不同智能算法的特点进行改进，寻求优化车辆调度问题性能最好的智能算法。最后应用健壮性最好的智能方法对各种静态情况下的车辆调度问题进行研究，这些情况主要包括:单车场VRP，多车场VRP，集送一体化VRP，开放式VRP等。本文对各种静态情况下的车

3、辆调度问题都进行了试验并且给出了代表性的算例，通过与同类文献的比较，显示了本文所提出的智能方法对优化车辆调度问题的有效性和可行性。关键字: 物流配送 车辆调度 遗传算法 数学模型 分支切割算法 Study on Logistics Distribution Vehicle Routing ProblemABSTRACT In recent years, Chinas logistics industry has achieved great development, but as compared with foreign developed countries, there are stil

4、l large gaps. In all the links of logistics, logistics distribution plays a key role in increasing profits of logistics enterprises. As part of solutions to the technical problem of logistics distribution,vehicle routing problem(VRP) is getting more and more attention in academics and enterprises.VR

5、P is a typical NP-hard problem. Even in the relatively small size of the customers, getting the solution also is difficult. Therefore, studying under all conditions for the effective VRP algorithm appears to be particularly important. Judging from the current situation of the study, although the stu

6、dy on VRP has got much attention, but still not on the actual situation facing the VRP-depth study. The VRP research results are rather scattered, the depth and breadth of which are unable to meet todays rapid development of the logistics industry.To realize the problem, in this paper, the deploymen

7、t of various static VRP with non-full load is studied systematically based on current theoretical methods. In order to find the best suitable algorithm, a summary of concerning references is liven and the current insufficiencies of domestic and foreign researches of VRP are reviewed. Then this paper

8、 uses improved genetic algorithm At last, an intelligent method is liven to study on various static VRP. These conditions include single-depot VRP with load and time windows limits, single-depot VRP; multi-depots VRP multi-depots VRP with multi-type vehicle limits, multi-depots open VRP, etc.In this

9、 paper, many representational examples are liven .Compared with the results attained by some other references, the experiments indicate the validity and feasibility of the intelligent method to the VRP.KEY WORDS: Logistics of distribution; Vehicle Scheduling; Genetic algorithm;Mathematic Model; Bran

10、ch cutting algorithm目录前言1第1章 21.1 21.1.1 21.1.2 21.1.3 2第2章 42.1 42.1.1 42.1.2 42.2 52.2.1 5第3章 63.1 63.1.1 63.1.2 63.2 6第4章 74.1 74.1.1 74.1.2 74.2 7第5章 85.1 85.1.1 85.1.2 85.2 85.2.1 85.2.2 8结论9谢 辞10参考文献11附录13外文资料翻译148前言随着社会主义市场经济的不断发展，作为“第三利润源泉”的物流对经济活动的影响日益明显，引起了人们越来越多的重视，成为当前“最重要的竞争领域”。配送是现代物流的

11、一个重要环节，随着物流的全球化、信息化及一体化,配送在整个物流系统中的作用变得越来越重要。配送是连接生产与消费之间的一种中介服务。它是指按客户(包括零售商店、用户等)的订货要求(包括货物种类、数量和时间等方面的要求)，在物流中心(包括配送中心、仓库、车站、港口等)进行分货、配货工作，并将配好的货物及时送交收货人的物流活动。配送不是单纯的运输或送货，而是运输与其他活动（集货，分货，配货）的组合，是“配”与“送”的有机结合。因此对于配送问题的研究可分为对 “配”和“送”两方面的研究。“配”主要为配送中心选址问题，“送”包括旅行商问题(TSP)、车辆路线优化问题(VRP)。由于选址的外部因素（经济，

12、基础设施，环境等）及内部因素（企业战略，劳动力成本和素质等）的影响，单纯考虑距离问题的选址是不合理的，因此在本文中不对“配”进行研究，主要对“送”进行研究。配送路线的优化，是配送优化中的一个关键环节。在配送过程中，配送线路合理与否对配送速度、成本、效益影响很大。设计合理、高效的配送路线方案，不仅可以减少配送时间，降低作业成本，提高企业的效益，而且可以更好地为客户服务，提高客户的满意度，维护企业良好的形象。配送线路优化是指对一系列的发货点和收货点，组织适当的行车路线使车辆有序的通过它们，在满足一定的约束条件下（货物需求量与发送量，车辆容量限制，行驶里程限制），力争实现一定的目标（行驶里程最短，使

13、用车辆尽可能少）。但配送作业情况复杂多变，不仅存在配送点多、货物种类多、道路网复杂、路况多变等情况，而且运输服务地区内需求网点分布也不均匀，使得线路优化问题是一个无确定解多项式难题，需要遗传算法算法去求得近似最优解。本文将以当前的配送线路的优化问题作为研究对象，对各客户需求量及运距进行分析计算，建立VRP数学模型，运用分支切割算法和以及改进的遗传算法法对建立的模型进行求解，对物流配送路线进行优化。最后对两种种方法求得的结果进行比较分析，从而提出较合理的配送方案，以期减少配送里程，降低物流运输成本，提高物流运作效率，客户服务质量和整体竞争力。第1章 绪论1.1 研究背景及意义1.1.1 研究背景

14、自从18世纪工业革命在西方发初以来，人类便以为自己寻到了自我发展的终极密码，随着滚滚的车轮与隆隆的机器轰鸣，一番无边无际、无限无量的乐观发展前景被反复展示。但这种乐观最终被现实击碎，“无限发展观”一步步沦陷。在西方发达国家的经济发展过程中，最初企业是把降低材料的成本当作是扩大利润的一个最重要的来源，所以这时候把降低材料费用作为第一利润源泉。当材料成本降低到一定幅度以后，可能的空间就不大了，这时候发现通过降低人工成本可以获取更多的利润，于是实现了工厂作业的自动化，所以把这种途径称为第二利润源泉。同样，随着市场竞争日益激烈，企业人工费用的降低也是有一定限度的，达到一定限度的时候，企业的发展受到很大

15、的限制。后来人们发现如果能有效地降低在成本中占据相当高比例的物流费用，就等于提高了利润，这时候人们开始把物流称为第三利润源泉。尽管物流活动自古有之，但直到1915年，“物流”这一名词才第一次出现在阿齐.肖的市场流通中的若千问题一书中，经过数十年的理论研究和实际运作，人们越来越认识到物流的重要性。虽然人们对物流的认识有了长足的进步，但是这个领域未知的东西还很多，理论和实践皆不成熟。著名的管理学权威PE德鲁克曾经讲过，“流通是经济领域里的黑暗大陆”。日本早稻田大学西泽修教授在研究物流成本时发现，现行的财务会计制度和会计核算方法都不可能掌握物流费用的实际情况，因而人们对物流费用的了解是一片空白，甚至

16、有很大的虚假性，他把这种情况比作“物流冰山”。冰山的特点，是最大部分沉在水而之下，而露出水而的仅是冰山的一角。物流就是一座冰山，其中沉在水而以下的是我们看不到的黑色领域，而我们看到的不过是物流的一部分。事实证明，物流领域的方方而而对我们而言还是不清楚的，在黑大陆中和冰山的水下部分正是物流尚待开发的领域，也正是物流的潜力所在。随着信息技术的发展尤其是因特网的出现和普及，使电子商务得到了迅速的发展，商务活动所必需的信息流、资金流都可以在网上瞬间实现，这是电子商务成为可能条件之一，大大缩短了商品交易活动的时间和空间，这使传统的商务模式受到极大的挑战。另一方而，人们发现，有形商品最终的交易却无法在网上

17、直接实现，“物流”成了电子商务发展中绕不过去的关键环节，及时履行订单是决定电子商务公司成功的非常重要的因素，而履行订单关键的环节是配送，其系统优化主要是配送车辆优化调度。因此，对配送车辆进行优化调度，可以提高物流经济效益、实现物流科学化，其中车辆路径问题(Vehicle Routing Problems，简称VRP)具有很大的代表性。1.1.2研究意义一、我国发展现代物流的意义1.现代物流产业的发展，是降低企业成本，促进我国经济发展的需要 1）现代物流产业的发展，可以大大降低高昂的物流费用有资料显示，目前我国工业企业生产中，直接劳动成本占总成本的比重不到10%，物流费用占商品总成本的比重高达4

18、0%。全社会物流费用占GDP的比重约为20%，而美国不足10%。如果我国能达到同一水平，按照2006年的GDP水平，全社会可节约2万亿元的物流成本，或者说可以多产生近2万亿元的利润。2)现代物流产业的发展，能极大的减少库存占压资金由于物流速度缓慢，加之企业业务流程以传统模式为主，目前全国长年积累的库存商品高达4万亿元左右。落后的物流和巨大的库存占压资金，使我国众多企业资本周转极其缓慢。目前，我国国有独立核算工业企业流动资本年平均周转速度为1.2次，国有商业流动资本年平均周转2.3次，而现代物流体系发达的日本企业流动资金年平均周转15至18次，沃尔玛、麦德龙、家乐福等跨国连锁流通企业资金的年周转

19、速度则高达20至30次。现代物流产业的发展，将减少低水平、条块分割的物流方式造成的巨大物耗我国传统物流采取的是“大而全”、“小而全”的经营方式，各种物流方式互不关联，物流过程中的物耗惊人。据估算，全国一年蔬菜损失价值达1354亿元，粮食损失价值35.7亿元，钢材锈蚀损失价值1000亿元。在传统的物流模式下，一件商品从生产环节到最终的消费环节，至少要搬运十几次，如果实行社会化的多式联运、一单到底，物流过程中的物耗可以大大减少。2. 现代物流产业的发展，是经济全球化的需要经济全球化的加强是当前世界经济的一个重要特征，其含义是指商品、资本、技术、劳动力等资源配置己超出一个国家的范围，是在地区甚至在全

20、球范围内实现最优配置的过程，其实质是一场以发达国家为主导，跨国公司为推动力，通过交叉投资、兼并收购为主要方式进行的世界范围内产业结构的调整。它的产生意味着“无国界经济”及“地球村”等现象的显现，表明世界经济中各国经济开放度不断提高及相互依存关系的加深。经济全球化的加强迫使国内外工商企业为参与市场竞争，越来越注重集中精力发展主业，培育在技术、管理、采购、营销等上的核心竞争力，一般把非核心的如在运输、仓储、配送等物流业务作为整体供应链的一部分外包给专业的物流公司，这是现代物流产生的重要动因。而目前我国第三方物流市场的特征之一是“两头在外”(物流的需求方和供应商多为跨国公司)，现代物流服务作为传统货

21、运服务的替代品，前者同后者的区别主要表现在其功能的集成和基于合同为基础的客户合作伙伴关系，由此导致现代物流服务的发展潜力巨大。二、物流配送的意义配送本质上是运输，因此创造空间效用自然是它的主要功能。但配送又不同于运输，它是运输在功能上的延伸。物流配送的发展对物流的重要意义可归纳为以下几个方面：1.能促进物流设施和装备的技术进步现代大载重量的运输工具，固然可以提高效率，降低运输成本，但是只适用于干线运输。支线运输一般是小批量，使用载重量大的运输工具则是一种浪费。支线小批量运输频次高、服务性强，要求比干线运输具有更高的灵活性和适应性，而配送通过其他的物流环节的配合，可实现定制化服务，能满足这种要求

22、。发展物流配送有利于促进物流设施和装备的技术进步，具体表现在三个方而:一是促进信息处理技术的进步。随着配送业务的开展，处理的信息量将越来越多，原始手工的信息处理速度慢且容易出错，己经适应不了配送工作的要求，必然大量应用电子计算机这一现代化的信息处理技术;第二是促进物流处理技术的进步，从而提高物流速度，缩短物流时间，降低物流成本，减少物流损耗，提高物流服务质量。配送业务的发展，必然伴随着自动化立体仓库、自动化分拣装置、无人搬运车、托盘化、集装箱化等现代物流技术的应用;第三是推动物流规划技术的开发与应用。配送业务的开展，配送货主越来越多，随之而来的就是产生一个配送路线的合理选择、配送中心选址、配送

23、车辆的配置和配送效益的技术经济核算等问题，对于这些问题的研究解决，能促进我国物流技术的发展，并使之达到一个新阶段。2.能消除交叉运输在没有配送中心的情况下，由生产企业直接运送货物到用户，即使采取直接配送方式，交叉运输也是普遍存在的。由于交叉运输的存在，使输送路线长，规模效益差，运输成本高。如果在生产企业与客户之间设置配送中心，采取配送方式，则可消除交叉运输。因为设置配送中心以后，将原来直接由各生产企业送至各客户的零散货物通过配送中心进行整合再实施配送，缓解了交叉输送，使输送距离缩短，成本降低。用大型卡车成批量的送到消费者的配送中心，再用小型车从配送中心运给用户的方法，可以从总体上节省费用。集中

24、配送有利于集中库存，维持合理的库存水平，消除了分散库存造成的各种浪费;同时还能减少不必要的中转环节，缩短物流周转时间，减少物品的损耗，对提高物流综合经济效益有利。3.能改变仓储职能配送通过集中库存，在同样的需求满足水平上，可使系统总库存水平降低，既降低了存储成本，也节约了运力和其它物流费用。尤其是采用准时制配送方式后，生产可以根据配送中心准时送货而无须保持自己的库存，或者只需保持少量的保险库存，这就可以实现生产企业的“零库存”或低库存，减少资金占用，改善企业的财务状况。开展配送业务后，现代仓储的作用己由储存、保管物品的使用价值向着集散、分送货物，加速物品流通速度的方向发展。仓储业将从储存、保管

25、的静态储存转向以保管储存、流通加工、分类、拣选、物品输送等联为一体的动态储存。建立配送中心后，仓储业的经营活动将由原来的储备型转为流通型，不仅要保证物品的使用价值完好无损，而且要做到货源充足，品种齐全，供应及时，送货上门，其经营方式将从等客上门向主动了解用户的需求状况，以满足用户的各种要求的方向转变。4.提高保证供应速度、方便用户采用配送方式，配送中心比任何单独供货企业有更强的物流能力，可使用户减少缺货风险。由于配送可提供全方位的物流服务，采用配送方式后，用户只需向配送供应商进行一次委托，就可以得到全过程、多功能的物流服务，从而简化了委托手续和工作量，节省了开支。 三、VRP的研究意义 VRP

26、问题作为解决物流配送核心技术的一部分，越来越得到研究学者和物流企业的重视。VRP问题主要解决的问题为:如何有效地使用载运工具来运送各站点间的旅客和货物，要求确定哪些旅客和货物该由何车辆、按何顺序、在何时运送，才能在满足诸如车辆装载能力和运送时间等限制条件下，使总费用为最小。V RP的研究意义主要表现在以下几个方面。1.能提高物流经济效益针对具体的V RP问题，通过对实际情况分析，可以将VRP相关的前提条件和各项成本进行量化，明确VRP的目标和约束，对资源进行优化整合与配置，通过优化配送路径、开展“计划配送”、“共同配送”等形式，消除迂回运输、重复运输、交叉运输、空载运输等不合理现象，减少物流配

27、送成本，提高企业的物流经济效益。据统计fll，我国的汽车空驶率高达37%，如按照现代物流要求合理设计流程，可使空驶率降低到5%能极大减少运载成本。2.能提高物流管理的科学化水平VRP不仅能解决车辆调度的优化问题，同时也是提高物流管理水平的一种手段。一方而，通过对具体VRP问题进行分析，能够得出在现有条件下极大的减小物流成本、提高服务水平的物流配送方案。例如确定配送车辆对客户的服务时间窗范围、优先顺序和服务水平等。同时，对于一些突发事件，能够采取有效的候选方案，减小不确定事件对企业和客户的影响;另一方而，由VRP优化方案实施后反馈的数据，也能对企业员工的工作效率和工作质量进行监督与控制，提高企业

28、管理水平。例如，能够根据预先制定的优化方案与客户反馈的信息与进行对比，对员工的表现进行评价，制定相应的激励机制，提高物流管理的科学化水平。3.能够促进VRP相关领域的发展虽然VRP最初是以物流配送为背景提出来的，但其应用范围早己超出了物流配送领域。在国外，VRP己经广泛的运用于生产、生活的各个方而，如报纸投递及线路的优化、牛奶配送及送达线路的优化、电话预定货物的车辆载货和线路的设计、垃圾车的线路优化及垃圾站选址的优化、连锁商店的送货及线路优化等。随着VRP研究的加深和应用的扩展，该问题的应用不仅仅局限在物流配送领域，还被拓展到仓库货位、拣货优化、电路设计、电网布局等领域。1.2 VRP相关理论

29、研究综述物流配送车辆优化调度问题最早是由Dantzig和Ramser于1959年首次提出，他们描述了一个将汽油送往各加油站的实际问题，并提出了相应的数学规划模型及其求解算法Ell. Bodin, Golden等人在他们的综述文章中对一般的车辆优化调度问题做了详尽的论述。随着研究的深入发展，如何使研究的理论模型更贴近现实中的运输调度问题开始成为研究焦点。Laporte和Nobert等人(1985年)主要研究了带容量和距离限制的车辆优化调度问题，Solomon和Desrosiers等人(1987年)考虑将时M约束加入到一般的车辆优化调度问题中，最早对带时间约束的车辆优化调度问题进行了研究。 90年

30、代以后车辆优化调度问题引起了运筹学、应用数学、组合数学、图论与网络分析、物流科学、计算机应用等学科的专家与运输计划制定者和管理者的极大重视，成为运筹学与组合优化领域的前沿与研究热点问题。随着现代物流的不断发展，多车场车辆优化调度问题、随机车辆优化调度问题、装卸混合车辆优化调度问题等更加复杂的路径问题被不断的提出和研究。目前国内外用于解决该问题的现代数学方法主要分为以下几类:精确优化方法、启发式方法、模拟方法、交互式优化方法。以往广泛采用的是第一种方法，另外三种方法则代表了较近的研究思想。尤其是启发式方法，作为一种逐次逼近的算法，虽然不一定得到最优解，但可以高效地得到具有较高精度的解，而且也易于

31、考虑各种各样的实际问题，因此，现己成为解决物流配送问题的重要方法。随着人工智能技术的引入和不断发展，模拟退火算法和遗传算法等新的方法以及人工神经网络和专家系统等新技术，为解决大规模、多目标车辆优化调度问题提供了新的辅助手段。目前，算法研究集中在对启发式规则和搜索方法的改进，以便提高搜索速度和质量。主要有混合遗传算法、部分自适应遗传算法先聚类分析再优化的两阶段法、蚁群算法、免疫算法、粒子随着高性能计算机的迅速发展，国外应用计算机及现代数学方法调度车辆以优化运输管理效果的研究工作正在较大范围内展开，在车辆调度的形式、构造、分析以及求解方法的实现上都有了许多突破。并且某些常用且比较成熟的算法已被人们

32、运用于实际配送调度系统，如美国IBM以最短路算法和启发式算法为核心算法的VSPX系统，日本以节约法为主要算法的VSS系统，美国美孚利用扫描法调度车辆的HPCAD系统等。 另外，与先进技术的结合也是物流配送车辆优化调度问题的一个突破。例如在国外一些国家将地理信息系统、全球定位系统、智能交通系统等技术应用于物流配送车辆优化调度问题中，更加有助于直观的、实时的反映配送状况，使得该系统更加智能化。群算法等算法在车辆路径优化问题中的应用。 洛阳理工学院毕业设计论文第2章 车辆路径问题及其求解算法基本理论2.1 车辆路径问题及组成要素VRP问题可描述为:给定一系列的客户点和车场，车辆从车场出发，在满足一定

33、的约束条件下，有序的通过这些客户点完成配送任务，最后返回指定位置，使总费用最小。VRP问题涉及的要素很多，本节从VRP的目标和约束两个方而分别阐述。2.1.1 目标VRP问题的目标主要有以下几种：1) 最小化总运输成本，运输成本包括车辆折旧费用、油费，司机工资等；2) 最小化配送车辆总配送里程，即所有配送车辆的总配送距离最小化；3) 最小化配送车辆数，即对于同一配送任务，需要的配送车辆数最小化；4)最大化客户服务水平，将对客户的服务水平进行量化，最大化服务水平；5)其它目标，如最小化配送车辆空载里程，最小化违约时间等。2.1.2 约束 VRP问题的约束主要有以下几种: 1)车辆能力约束。配送车

34、辆都有容量大小，达到容量上限后必须要返回指定位置，这种约束称为车辆能力约束。 2)配送里程约束。即配送车辆的最大配送距离约束，达到这个最大距离需要返回指定位置。 3)任务时间窗约束。设完成任务1需要的时间(装货或卸货)表示为Ti，又设任务i的开始时间需要在一定的时间范围ETi，LTi内，其中ETi为任务i的允许最早开始时间，LTi为任务i的允许最迟开始时间。如果车辆到达i的时间早于ETi车辆需在i处等待。如果车辆到达i的时间晚于LTi，任务i要延迟进行。时间窗约束可分为软时间窗约束和硬时间窗约束两种。 4)车辆发车时间约束。在一个车场中，当接到一项运输任务，并不一定当时就有足够的车辆派出执行任

35、务。例如可能有的车辆还在执行上一项任务，还需一段时间才能回到车场;有的车辆还在维修过程中，还需一段时间才能修复；司机也并不是全都能在一个时间上班发车。在这种情况下，就要考虑发车时间的影响，即车辆发车时间约束。5)配送顺序约束。有的配送任务需要考虑配送顺序，必须先到特定的客户完成配送任务，才能完成后续的配送任务，这种约束在集送一体化VRP中出现较多。6)车辆总数约束。车场的车辆不是无限供应的，有一定的数量限制。7)车型约束。物流配送公司大都有一种以上的货运车辆，由于不同的货物有不同的比重和外形特征，可能有不同的包装方法，运输车辆的载重量和车箱尺寸各异，以及道路条件的限制等等，使得多车型运输组织比

36、单车型复杂得多。当有多种车型可用时，对同一项运输业务来说，使用不同车型的车时、可载量常不一样，所需的空车数也不相同。8)发车、回车车场约束。配送任务或者配送车辆限定了发车或回车车场的约束。9)集送类型约束。分为单送货、单集货和集送一体化三种。配送任务只有送货或只有集货的称为单送货或单集货VRP，一般把这两种作为一种类型处理。如果配送任务不仅需要送货，也需要集货，则称为集送一体化VRP。10)客户货物类型约束。即单个客户配送量的大小、类型约束。2.2 车辆路径问题分类VRP问题的分类法很多，为方便对该问题进行系统研究，本文VRP问题进行如下分类: 1.按VRP前提条件和约束确定性来分，可分为静态

37、VRP和动态VRP。静态VRP的前提条件和约束都是确定的，即在进行优化调度之前所有情况己经确定并且不会改变。动态VRP,即前提条件和约束随时间的改变而发生变化的情况。 2.按VRP涉及车场的数量来分，VRP可分为单车场或多车场两种类型。单车场VRP表示配送车辆发车或回车只有一个车场;多车场VRP的配送车辆则有多个车场可供选择。如下图2-1，2-2所示。图 2-1 单车场VRP问题图 2-2 多车场VRP问题3.按车辆完成配送任务后是否回到原发车车场分，VRP可分为封闭式VRP,开放式VRP和半开放式VRP。封闭式VRP表示配送车辆的发车车场和回车车场一致;开放式VRP的配送车辆不一定回到原发车

38、车场，回车车场可以是指定的多个车场之一，也可以以完成最后一个配送任务为配送结束标志，不用回到车场;半封闭式V RP发车车场与回车车场不同，但回车车场固定。封闭式VRP见图2-1, 2-2。开放式V RP，半开放式VRP如下图2-3, 2-4所示。图 2-3 开放式VRP图2-4半开放式VRP按VRP集送类型分，VRP可分为单送货/单集货VRP和集送一体化VRP。单送货/单集货VRP中配送车辆只送货或只集货;集送一体化VRP则既送货又集货。图2-1, 2-2, 2-3, 2-4都是单送货/单集货VRP,集送一体化VRP如下图2-5所示。图2-5集送一体化VRP5.按客户货物大小来分，分为满载VR

39、P和非满载VRP。满载VRP指配送任务中有客户的配送任务大于车辆的容量上限。非满载VRP指配送任务中客户的货物量均小于车辆能力约束。6.按VRP约束类型来分，可分为能力约束VRP，时间窗约束VRP，里程约束VRP等多种类型。这些VRP类型都是根据其约束条件的特点来进行划分的。上述划分只是针对VRP的某种特性进行的划分，实际上VRP的类型是上述划分的各种组合。本文VRP的研究是按静态/动态一单车场/多车场一封闭式/开方式一其它各种约束的层次进行分类的，以后的各章节中，将会对以上分类的多种组合进行研究。2.3 物流配送车辆路径问题复杂度分析2.3.1 计算的复杂度一算法的复杂性与有效性优化组合问题

40、算法的有效性可以用执行该算法的各种计算资源来度量，其中最重要的、最典型的两个资源是所需的运行时间和存储空间，不过人们一般把最快的算法与最有效的算法等同起来，因为运算时间常常是决定某一特定算法在实际中的实用性和有效性的主要因素。为了更具一般性，人们常常把问题规模n的函数来表示计算的复杂性，比如旅行商问题的城市数、背包问题的物品数。不同的算法具有不同的时间复杂性，那么什么样的算法是好的、可以接受的呢?人们通常认为，仅当算法的时间复杂性函数是关于n的多项式函数时，才认为这个算法是有效的，实用的。二以算法复杂性为基础的算法分类以算法复杂性为基础，可以把算法分为两类:一类是多项式算法，即存在某个以n为变

41、量的多项式P（n），使其时间复杂度函数为O（P（n）的算法;另一类是指数时间算法，n是作为指数出现在时间复杂度里而的。例如搜索2分法的时间复杂性是O(log n)，它是多项式算法，用动态规划方法解TSP问题，它的时间复杂性为O(n22n),它是指数时间算法。三P问题、NP问题、NP完全问题、NP难题1.P问题。如果一个问题有求解它的多项式算法，这个问题称为P问题；2. NP问题。若存在一个多项式函数g(x)和一个验证算法H，对一类判定问题A的任何一个“是”的判定实例I都存在一个字符串S是I的“是”回答，满足其输入长度d(s)不超过g(d(I)，其中d(I为I的输入长度，且验证算法验证s为I的“

42、是”回答的计算时间不超过g(d(I)，则称判定问题A为多项式非确定性问题，简称NP问题。3.判定问题P到Q的归约:是指存在一个转换函数F，它可以把问题P的输入x转换为问题Q的输入F(x)，使得问题P对于输入x得到正确结果当且仅当问题Q对于输入F(x)得到正确结果。多项式归约是用来建立两个为题P和Q之间的复杂程度的比较关系，实际上就是通过转换函数F(x)把求解问题P转化为对问题Q的求解。4. NP-C问题。也称NP完全问题，如果判定问题AE NP且NP中任何一个问题可多项式归约为问题A，则A为NP-C问题；5. NP-hard问题。也称NP难题，NP中任何一个问题可多项式归约为问题A，但不确定是

43、否ANP，称问题A为NP-hard。NP-C能多项式归约为NP-hard，反推不成立。P问题、NP问题、NP完全问题、NP难题的关系如下图2-6所示。图2-6 PNP时，P，NP，NP-C，NP-hard的关系2.3.2车辆路径问题的复杂度VRP被提出来后，对其求解算法的研究一直是研究的重点和难点。在对其求解算法进行研究的同时，不少学者也对它的计算复杂性进行了研究，为确定求解算法的研究方向奠定了基础。Lenstra证明了容量约束VRP是NP-hard问题;Hassin, Shlomi Rubinstein证明了kVRP问题在k等于3或4时，kVRP问题能找到多项式时间算法，但是当k大于4时，只

44、存在求解该问题的指数时间算法。AkioImai, ETSuko Nishimura等证明了多车型VRP属于NP-hardo Solomon指出带时间窗的V RP比一般的VRP更复杂。Hideki Hashimoto, Toshihide Ibaraki等证明了软时间窗VRP属于NP-hard。Savelsbergh提出不仅带时间窗的VRP本身是NP-hard问题，而且当车队大小(可用车辆数)固定时，甚至要得到一个问题的可行解都是一个NP一难问题。Lenstra和Rinnooy Kan在对VRP的计算复杂性进行综述和分析的基础上，证明了几乎所有类型的VRP均为NP-hard问题。 24物流配送车

45、辆路径问题算法基本理论 求解车辆路径问题的算法包括精确算法和近似算法两大类。本节主要介绍精确算法中分支切割法和近似算法中的遗传算法。 2.4.1分支切割算法基本理论分支切割法是在割平面法基础上发展起来的。1958年R. E. Gormory首先提出的，故又称为Gomory割平面法。割平面法对整数规划的发展非常重要，它是解整数规划的第一种方法，而且可以证明通过有限迭代便收敛到最优解。构造割平面的不同，相应的切割算法也不同。割平面算法的基本思路是:在松弛问题中逐次增加一个新约束(即割平而)，它能割去原松弛问题可行域中一块不含整数解的区域，逐次切割下去，直到最终所得松弛可行域的一个最优极点为整数解为

46、止。分支定界(branch and bound算法是一种在问题的解空间树上搜索问题的解的方法，该算法的基本思想是:首先确定目标值的上下界，边搜索边减掉搜索树的某些支，提高搜索效率。分支定界算法采用广度优先或最小耗费优先的方法搜索解空间树，并且在分支定界算法中，每一个活结点只有一次机会成为扩展结点。利用分支定界算法对问题的解空间树进行搜索，它的搜索策略是: 1.产生当前扩展结点的所有孩子结点; 2.在产生的孩子结点中，抛弃那些不可能产生可行解(或最优解)的结点； 3.将其余的孩子结点加入活结点表; 4.从活结点表中选择下一个活结点作为新的扩展结点。如此循环，直到找到问题的可行解(最优解)或活结点

47、表为空。从活结点表中选择下一个活结点作为新的扩展结点，根据选择方式的不同，分支定界算法通常可以分为两种形式。1. FIFO (First In First Out)分支定界算法:按照先进先出原则选择下一个活结点作为扩展结点，即从活结点表中取出结点的顺序与加入结点的顺序相同。2.最小耗费或最大收益分支定界算法:在这种情况下，每个结点都有一个耗费或收益。如果要查找一个具有最小耗费的解，那么要选择的下一个扩展结点就是活结点表中具有最小耗费的活结点;如果要查找一个具有最大收益的解，那么要选择的下一个扩展结点就是活结点表中具有最大收益的活结点。在用割平而法或分支定界法解整数规划时，常会遇到收敛很慢的情形

48、，因此，在使用时，往往割平而法和分支定界法配合使用，称为分支切割算法。2.4.2遗传算法基本理论遗传算法(genetic algorithms，简称GA)是J. Holland于1975年受生物进化论的启发而提出的。GA是基于适者生存的一种高度并行、随机和自适应的优化算法，它将问题的求解表示成“染色体”的适者生存过程，通过“染色体”群的一代代不断进化，包括复制、交叉和变异等操作，最终收敛到“最适应环境”的个体，从而求的问题的最优解或满意解。GA时一种通用的优化算法，其编码技术和遗传操作比较简单，优化不受限制性条件的约束，而其两个显著的特点则是隐含并行性和全局解空间搜索。目前，随着计算机技术的发

49、展，GA愈来愈受到人们的重视，并在机器学习、模式识别、图像处理、神经网络、优化控制、组合优化、遗传学等领域得到了成功的应用。一、遗传算法的基本流程遗传算法是一类随机优化算法，但它不是简单的随机比较搜索，而是通过对染色体的评价和对染色体基因的作用，有效的利用己有的信息来指导搜索最有希望改善优化质量的状态。标准遗传算法的主要步骤可描述如下。1.随机产生一组初始个体构成初始群体，并评价每一个体的适应度(fitness value)。2.判断算法收敛准则是否满足。若满足则输出搜索结果，否则执行以下步骤。3.根据适应度大小以一定的方式执行复制操作。4.按交叉概率Pc执行交叉操作。5.按变异概率Pm执行变

50、异操作。6.返回步骤2。上述算法中，适应度值是对染色体进行评价的一种指针，是GA进行优化所用的主要信息，它与个体的目标值存在一种对应关系;复制操作通常采用比例复制，即复制概率正比于个体的适应值;交叉操作通过交换两父代个体的部分信息构成后代个体，使得后代继承父代的有效模式，从而有助于增加种群的多样性，避免早熟收敛。遗传算法利用生物进化和遗传的思想实现优化过程，区别于传统优化算法，它具有以下的特点: 1.GA对问题参数编码成“染色体”后进行进化操作，而不是针对参数本身，这使得GA不受函数约束条件的限制，如连续性、可导性。 2.GA的搜索过程是从问题解的一个集合开始的，而不是从单个个体开始的，具有隐

51、含并行搜索特性，从而大大减少了陷入局部最优解的可能。 3.GA使用的遗传操作均是随机操作，同时GA根据个体的适应度信息进行搜索，无需其它信息，如导数信息等。 4.GA具有全局搜索能力，最善于搜索复杂问题和非线性问题。遗传算法的优越性主要表现在: 1.算法进行全空间并行搜索，并将搜索重点集中于性能高的部分，从而能够提高效率且不易陷入局部极小。 2.算法具有固有的并行性，通过对种群的遗传处理可处理大量的模式，并且容易并行实现。 二、遗传算法的关键参数与操作设计 通常，遗传算法的设计是按以下步骤进行的: 1.确定问题的编码方案。 2.确定适应度函数。 3.遗传操作数的设计。 4.算法参数的选择，主要

52、包括种群数目、交叉与变异概率、进化代数等等。 5.确定算法的终止条件。 下面对关键参数与操作的设计做简单的介绍。 1.编码 将问题的解用一种码来表示，从而将问题的状态空间与GA的码空间相对应，这很大程度上依赖于问题的性质，并将影响遗传操作的设计。由于GA的优化过程不是直接作用在问题参数的本身，而是在一定编码机制对应的码空间上进行的，因此编码的选择是影响算法性能与效率的重要因素。函数优化中，不同的码长和码制，对问题求解的精度与效率有很大的影响。二进制编码将问题的解用一个二进制串来表示，十进制编码将问题的借用一个十进制串来表示，显然，码长将影响算法的精度，而且算法将付出较大的存储量。实数编码将问题

53、的解用一个实数来表示，解决了编码对算法精度和存储量的影响，也便利于优化中引入问题的相关信息，它在高维复杂优化问题中得到广泛的应用。组合优化中，由于问题本身的性质，编码要根据实际情况编制。2.适应度函数 适应度函数用于对个体进行评价，也是优化过程发展的依据。在简单问题的优化时，通常可以直接利用目标函数变换成适应度函数，而在复杂问题优化时，往往需要构造合适的评价函数，使其适应GA进行优化。3.算法参数 种群数目是影响算法优化性能和效率的因素之一。通常，种群太小则不能提供足够的采样点，以致算法的优化性能较差，甚至的不到问题的可行解;种群太大时尽管可增加优化信息以阻卜早熟收敛的发生，但是无疑会增加计算

54、量，从而使收敛时间太长。交叉概率用于控制交叉操作的频率。概率太大，种群中串的更新很快，进而会使高适应度的个体会被很快破坏;概率太小，交叉操作很少进行，使搜索停滞不前。变异概率是加大种群多样性的重要因素。概率太大会使GA称为随机搜索，概率太小则不会产生新个体。确定最优参数是一个极其复杂的优化问题，要从理论上严格解决这个问题是十分困难的，因此很多场合都是根据具体实验情况调整的。4.算法的终止条件GA的收敛理论说明了GA以概率1收敛的极限性质，因此我们要追求的提高算法的收敛速度，这与算法操作设计和参数选取有关。然而。实际应用中不允许让它无停止的发展下去的，而且通常问题的最优解也未必知道，因此需要有一

55、定的条件来终止算法的进程。最常用的终止条件就是事先给定一个最大进化步数，或者是判断最佳优化值是否连续若干步没有明显变化等。 GA是一个复杂的非线性智能计算模型，纯粹用数学方法来预测其运算结果很难，而且这方而的工作还远远不够。目前，为了兼顾优化质量与效率，实际应用GA时许多环节还只是凭经验来解决，这方而还有待更深入的研究与发展。2. 5本章小结 本章首先从目标和约束两个方而对VRP的组成要素进行分析，然后根据不同的分类方法对VRP问题进行了分类，最后分析了VRP的复杂度和求解VRP的常用算法理论进行了简单介绍。本章是后而各章节的总括，是全文的理论基础。第3章 物流配送静态车辆路径问题的精确算法研

56、究 本章将应用分支切割算法对静态车辆路径问题的最基本的类型一一能力约束车辆调度问题(Capacitated VRP，简称CVRP)进行研究。3. 1问题的描述和数学模型3.1.1问题的描述CVRP可描述为:考虑货物需求量、发送量和车辆容量三种约束的条件下运输车辆的路径优化问题。它可以描述为:物流配送渠道由1个车场、n个送货点(城市)组成，送货的车辆从车场出发，到各送货点送货，每个送货点的需求货物重量为gr，每个客户只能被服务一次，每辆车限定容量为qA屯，每辆车达到各送货点把货物卸载完之后返回车场。费用函数为总路程数，目标为使总路程数最小。 3. 1 .2数学模型设G=(V，A)为一个完备图，其

57、中V=0，1，n，为图中顶点的集合，车场由0表示，客户由1，2n表示；每个客户的配送量为；Vc = V/0表示客户集合。集合SVc ，；(S)表示G中有且仅有一个端点在S中的弧的集合；E(S)表示G中两个端点都在S中的弧的集合；l(S)表示S中客户最少需要的配送车辆数；Xij表示配送车辆在两个客户点i， j间的运行次数；Cij表示配送车辆在两个客户点i， j间的配送费用；K 表示总共配送车辆数。则CVRP的整数规划模型可表示如下： (3-1)s.t x (i)=2 (i=1,.,n) (3-2)x( (S) 2l(S) (SV，S2) (3-3)x (0)=2K (3-4)xi,j 0,1 (

58、1ijn) (3-5)x0,i 0,1,2 (i=1,.,n) (3-6)模型中公式（3-2）为度约束等式，用来约束每个客户恰好被服务一次；不等式（3-3）为连接不等式。对车辆的能力进行了约束，同时也保证了路径是相连的;等式(3-4）为车辆约束不等式。对总共的配送车辆数进行了限制，保证所用的车辆恰好等于K。(3-5)，(3-6)为整数约束，当iVc，jVc时，xi，j只能为0或1，意义为要么配送车辆在两客户i，j之间的路径旅行一次，要么不旅行。当i=0, jVc时，xi，j除了可以取0，1外，还能取2，其意义为路径中仅包含一个客户和车场。由于上述数学模型不好直接用线形规划进行求解，去除连接不等

59、式和整数约束不等式之后，得到CVRP的线形松弛模型，如下所示： （3-7）s.t x (i)=2 (i=1,.,n) (3-8)x (0)=2K (3-9)xi,j 1 (1ijn) (3-10)xi,j 1 (1ijn) (3-11)x0,i 2 (i=1,.,n) (3-12)x0,i 0 (i=1,.,n) (3-13)3. 2单车场能力约束车辆路径问题的分支切割法设计3. 2. 1切割面的产生由公式(3-7)至(3-13)可知，初始线形松弛模型只包含度约束不等式、车辆约束不等式和变量上下界约束，变量的可行域与原CVRP模型相比大大增加，因此需要构造切割而，割去非整数点，而使原问题的全部

60、可行解仍然保留在松驰问题剩下的可行域中。本章用到的切割而产生不等式有以下几种。一、梳子不等式令H,W1,Wk V，如果满足以下约束，则称节点集合H,W1,Wk为图G=(V,A)中的一个梳子。， i=1,.,k (3-14) ， i=1,.,k (3-15) ， i=1,.,k (3-16)， ij （3-17）K 3 k为奇数 （3-18）集合H称为梳子柄，集合城称为梳子齿，如下图3-1所示。梳子不等式公式见公式(3-19)。 （3-19） HW1 W2W3 图 3-1 VRP梳子二、连接不等式公式(3-3)对车辆能力约束进行了限制，同时也保证了路径是相连的。由于集合S是Vc的任意一个子集，因此其组合达到个。由于数 能把所有约束都加入松弛模型进行运算，因此本章采用以下几种启发式算法替代连接不等式。1 搜索1如果R S，令，执行如下搜索步骤：step1：令R=；step2：如果 |R| =|S|2，结束；step3：令；令；step4：如果Z ( R)Z(R)，结束；step5：如果 Z( R)0，加入约束：，结束；step6：如果 0 Z (R)Z(R)，令R = R；转 step2。2 搜索2由相关文献证明公式(3-3)与下式(3-20)，(3-21)等价。 (3-20)