基于CW算法的海王星辰连锁药店市内配送优化物流管理专业

1、题题 目目基于 CW 算法的海王星辰连锁药店市内配送优化社会化分工日益精细化，使得供应与生产、生产与消费在时间和空间上出现了矛盾，促使物流在社会生产和生活中扮演着越来越重要的作用，物流的运营水平关系着一个国家经济发展的水平，各国政府都正大力发展本国物流。配送是物流运作中的一个重要环节，车辆路径问题是物流运输系统的核心组件，研究车辆路径问题有助于企业降低物流成本、提高运作效率、提高客户满意度。车辆路径问题将运筹学理论与管理实践紧密地结合在一起，是近半个世纪以来运筹学领域最成功的研究之一。 本文主要结合海王星辰在宁波市内的配送路径优化实例，简单介绍了城市物流的一些基本特征及发展的意义、国内外对车辆

2、路径的研究现状、车辆路径优化问题，因本文采取节约算法作为路径优化的工具，故并着重介绍了节约算法的概念及其算法过程，最后详细的介绍了海王星辰路径优化的方案过程及其得出的结果。关键字：物流；车辆路径问题；配送路径优化；节约算法Abstractwith more and more refined distribution of social labor, the supply、the production and the consumption hardly work well in time and space any longer, which resulted in an increasing

3、ly important role of the production and the logistics in the social life. The countrys economic development is mainly contributed by logistics operators, so governments are making great efforts to develop logistics. Distribution is an important part of logistics, Vehicle routing problem is the main

4、problem in the field of logistics transportation system, research on vehicle routing problems will help enterprises to reduce logistical cost, improve operation efficiency, and enhance customer satisfaction comprehensively. Since vehicle routing problems tightly connect theory of Operation Research

5、with practice of management, which was named as one of the most successful areas in Operation Research in the past half century. This paper mainly with the Nepstar distribution path optimization instance in Ningbo City, brief introduction to some basic features and significance of the development of

6、 urban logistics, the research status of the vehicle path in china and abroad, vehicle routing problem. For this article to take to save algorithm as a tool in path optimization, so it focuses on the concept of saving algorithm described in detail, and last detailed the Nepstar path optimization sol

7、ution process and the results.Key words: logistics；Vehicle routing problem；distribution route optimization；saving algorithm目录1 选题背景和研究意义.12 城市物流特征及发展城市物流意义.22.1 城市物流配送.22.2 城市物流的特征.22.3 城市配送的现状.32.4 发展城市物流的意义.43 车辆路径优化问题.63.1 车辆路径优化的定义.63.2 国内外车辆路径问题研究动态.73.2.1 国外车辆路径问题研究现状.73.2.2 国内车辆路径问题研究现状.83.3

8、车辆路径问题的分类.93.4 车辆路径问题算法分类.123.4.1 精确算法.123.4.2 启发式算法.123.4.3 智能算法.134 节约算法的理论基础及算法设计.164.1 CW 节约算法提出.164.2 CW 节约算法原理及特点.164.2.1 CW 节约算法的基本原理.164.2.2 CW 节约算法对车辆进行优化调度的步骤.174.2.3 CW 节约算法的特点.174.3 节约算法设计.174.3.1 模型的数学描述.174.3.2 数学模型的建立.185 案例分析.195.1 案例背景.195.2 案例数据分析.205.2.1 供应门店选择及分布 .205.2.2 供应门店需求量

9、.225.2.3 配送车辆选择.245.2.4 配送距离的确定 .245.2.5 算法程序设计.255.3 结果分析与算法改进 .275.3.1 结果分析及得出的改进方案.275.3.2 改进方案的设计.285.4 改进算法得出的运行结果与分析 .295.4.1 运行结果.295.4.2 结果分析与确定.315.5 案例分析总结 .32致谢.34参考文献.35附录.36附录 1 配送距离和时间原始数据.36附录 2 配送路径距离表.45附录 3 节约里程表.46附录 4 初始算法程序代码.47附录 5 方案一算法主要程序代码.55附录 6 方案二算法主要程序代码.6111 选题背景和研究意义当

10、今，世界经济发展日益趋于全球化，市场竞争也异常激烈，在此背景下产生了一个新兴行业物流业。物流是社会经济和商品流通发展到一定阶段的必然产物，为了满足社会生产和消费需求，对运输、仓储、装卸搬运、包装、流通加工、配送、信息处理等物流环节进行现代化管理、控制及信息化作业的经济活动。随着世界贸易的高速发展和信息网络技术的日益完善，全球经济一体化步伐的加快，特别是我国加入 WTO 以后，物流业作为国民经济中一个新兴的产业，将会成为我国 21 世纪经济发展的重要产业和新的经济增长点。作为“第三利润源泉”的物流对经济活动的影响日益明显，越来越得到了人们的重视，成为当前“最重要的竞争领域” ，未来市场竞争，物流

11、将起着举足轻重的作用，而配送是物流中一个重要的直接与消费者相连的环节， 物流术语中对配送的定义为：物品从供应地向接收地的实体流动过程，根据实际需要，将运输、储存、装卸搬运、流通加工、配送、信息处理等基本功能，实施有机结合。配送的核心部分是配送车辆的集货、货物分拣及送货过程，而车辆配送路径的合理优化，对于整个物流运输速度、成本、效益影响至关重要。但是目前，由于我国的物流产业起步晚，尚存在着许多问题。如何改变这种局面，使物流行业健康稳步发展，是国民生产力发展急需解决的难题，当前主要可从提高物流配送服务质量入手。在现代物流系统中，配送是一个重要环节，而在配送业务中，能否将货物及时送交收货人手中是物流

12、系统优化的关键，配送的质量好坏决定服务水平的高低，同时影响到客户对整个物流服务的满意程度。然而物流车辆在配送过程中，会涉及到车辆路径优化的问题。因此结合实际的配送情况，规划好物流配送的行进路线，有利于节省配送费用和提高配送服务质量。同时，优化后的物流配送路径，有利于缓解交通压力。由此说明，物流车辆路径优化问题在交通和物流规划中具有举足轻重的地位。选取恰当的车辆路径，可以加快物流系统对客户需求的响应速度，提高服务质量，增强客户对物流环节的满意度，降低服务商的运作成本。另外，由于在车辆配送过程中，有个别客户对物流配送时间提出高要求，为了提高服务质量和满意度，所以必须对于配送时间要求严格掌控。总的来

13、说，本文是为了提高物流配送系统的服务质量和节省配送费用，对物流车辆配送路径的优化进行的研究。为了更加形象的分析问题，本文将选取宁波市区海王星辰药店的药品配送为例，对中小型城市内的车辆路径优化进行研究。22 城市物流特征及发展城市物流意义2.1 城市物流配送 所谓物流配送就是按照用户的货物( 商品) 订货要求和物流配送计划，在物流配送节点( 仓库、商店、货运站、物流配送中心等) 进行存储、分拣、加工和配货等作业后，将配好的货物送交收货人的过程。而城市物流配送是指在城市范围内进行的物流配送业务活。 所谓城市物流是指为城市服务的物流，它服务与城市经济发展的需要，指物品在城市内部的实体流动，城市与外部

14、区域的货物集散以及城市废弃物清理的过程，并存在不同的模式、体系和存在形态，和其他形式的物流有一定的区别。城市物流配送系统的服务对象可归类为：政府、工业、商业、农业、大众客户。即电子商务中所描述的B to G，B to B，B to C。城市物流配送已随客户需求变化从“少品种、大批量、少批次、长周期”向“多品种、小批量、多批次、短周期”转变。由于城市范围一般处于汽车运输的经济里程。因而这种物流配送往往采用汽车实现。城市物流是城市经济发展的产物，同时，城市物流又服务于城市经济发展的需要，并且是城市经济的一个有机组成部分。不论城市地域范围大小，物流活动都具有共同的属性。城市物流所包含的范畴可以有两种

15、理解：一种理解是城市物流仅仅是城市内部范畴的物流，而城市的输入物流及城市的输出物流是发生在若干城市之间的物流，已经属于区域物流的范畴，这是对城市物流侠义的理解；另一种理解是包括城市内部的物流以及以城市为主体的城市外部物流，例如，城市的输入物流及城市的输出物流，这是对城市物流广义的理解。2.2 城市物流的特征 城市物流师连接企业物流和区域物流之间的纽带，即服务与城市经济发展的需要，也服务于区域经济发展的需要。城市聚集了大量的人口、政府机构、工商企业、商品、文化教育机构，分布着大量的航空、铁路、公路等交通运输网络和枢纽站点，在政治、经济、文化生活中起着重要的作用，具有较强的吸引力、辐射力和综合服务

16、能力，对周边地区经济发展能起到渗透、带动作用。城市经济和区域经济的形成是城市物流产生的条件，城市商品和服务市场的繁荣为城市物流的发展奠定了坚实的基础。城市物流的发展又为城市的发展起到有力的支撑作用，因此城市物流与城市经济涉及的范围是一致的，从这个意义上说城市物流可以理解为是以城市为依托的区域物流，因此，有关区域物流的理论与政策、区域物流的规划原则与方法、区域物流发展对策等等也适用于城市物流。城市物流的主要特点有：（1） 与以承载大宗货物为主的区域物流相比，城市物流的密度大、承载的货物种类繁3多，且这种情况与城市的规模成正比，因此城市物流的管理难度也更大。但是从另一方面来讲，城市物流的主要特点是

17、城市主体的一元化，所有的城市都具有统一的政府组织，城市行政组织可以统筹和管理物流，因此，城市物流又具有非常强的可控性。（2） 与以长途运输为主的区域物流相比，城市物流采用的大多是以公路为主的短途运输方式。受城市范围的制约，城市物流的短程性非常突出，再大的城市，城市的最大直径无非在百公里以内，城市中心物流密度再大的部位，也要远远低于这个数字。由于城市消费需求的多样化，城市分布的商业网点大多靠近消费者居住地，因此在货物到达城市后就需要以各种小型车辆分装运送，运送的载体几乎都是以公路为主。同时以多批次、少批量、多用户物流为主要的物流形式，更强调物流服务，而很难有效的降低物流成本。（3） 除了以上两点

18、特点之外，城市物流还具有精益化的运作模式。城市是一个国家经济水平最高的地区，有进行精益化运作的需求和条件。更重要的是，城市交通条件的制约和生态的脆弱性，不允许进行粗放的物流活动。因此，低噪音、低排放、小吨位、封闭型的物流车辆是城市物流的主要工具，执行的是准时、准确的物流方式。这种精益的运作，是城市物流的重要特点。2.3 城市配送的现状 随着经济的发展，物流业在我国城市有了一定的基础。但是，城市物流在发展过程中，也暴露出了许多问题。（1） 涉及面广，协调管理难城市物流配送管理涉及到城市交通警察局、运管局（处）、城管、规划等部门以及众多的工商企业，涉及面广，协调管理难度较大。各个主体根据部门相关职

19、责，从城市物流配送不同的角度，对城市物流配送进行管理。在一个完整的城市物流配送活动中，往往受到不同部门的监督与管理，过多部门的涉入，造成了职能的交叉，管理内容繁杂，交叉管理多。（2） 基础设施落后，机械化和信息化的配送设备更少我国大部分城市货运基础设施多年来投入严重不足，极少具有上规模的货运站场和仓储设施，且仍然大量使用手工整理、手工票据、人工装卸作业，信息系统比较落后，不能及时跟踪货物和获得配送信息。而国外的现代物流企业早已普遍应用电子数据交换、电子自动订货、配送需求计划、货物跟踪查询服务等业务。我国城市物流企业构建的信息系统，对数据的采集、统计、分析、预计能力还很不够，没有一套基于全程供应

20、链管理的信息系统，与实物流、资金流的同步谢姐能力差，很难形成客户“门到门”的物流管理。随着新的城市规划的实施和城市经济的增长，这些物流基础设施和信息化必须跟上经济发展脚步，否则城市物流将成为城市经济发展的瓶颈问题。4（3） 经营模式小，难以形成规模化的城市物流由于城市内众多的企业都自办物流，经营规模小，市场份额少，服务功能少，竞争力、融资能力弱，货物不稳定且结构单一、缺乏网络或网络分散、经营秩序不规范，难以形成规模经营，缺乏网络化运作，导致信息沟通不通畅。由此造成了城市物流资源严重浪费、企业物流成本难以降低、物流服务难以提高问题。所以如何将城市内企业物流进行整合，或者发展第三方物流企业，实现共

21、同配送，使城市物流更专业化、信息化、功能化，政府应该予以重视。（4） 缺少城市物流配送通道，设置不合理调查发现，城市物流配送中有很多道路通行限制现行，在重要物流节点和大学的商业聚集区，配送拥堵现行突出，配送运输通道不通畅。同时，城市对于货车的行驶的时间及车型限制，对于降低配送成本和及时完成配送产生了一定的影响。而且，在很多地方没有根据土地利用情况来设置不同的配送通道区域，只是简单地按照城市中心区与非中心区的划分来标定路段，限制车辆通行。（5） 供应链管理提高了企业对城市物流配送的重视程度供应链管理的实施，使企业更注重交付效率与效果。虽然大量干线运输与配载效率再提升的空间很小，但最为最后一公里的

22、配送由于直接面对客户，直接影响到产品服务与配送时间效率，也就直接关系到企业的市场发展和企业效益。所以，企业对城市物流配送的城市成都需要得到很大的提高。2.4 发展城市物流的意义随着城市经济发展的加快，城市物流的作用越来越大，建立一个高效率的城市物流体系就显得越来越有必要，城市物流对整个城市的发展促进作用非常明显，主要体现在：（1）促进优化区域产业结构。通常来说，城市是商品集散和加工的中心，并且物流设施和基础建设相对比较齐全，消费比较集中且需求量大，交通与信息发达，城市水平己成为物流业发展的一个重要条件。而物流产业发展带来的商流、资金流、信息流、技术流的集聚，以及交通运输业、商贸业、金融业、信息

23、业和旅游等多种产业的发展，又有助于城市产业结构的合理化。此外，由于物流是对分散的货物流动进行集中处理，必然要求利用现代化的物流设施、先进的信息网络进行协调和管理，真正的现代物流属于技术密集型和高附加值的高科技产业，具有资产结构高度化、技术结构高度化、劳动力高度化等特征。从这个角度来说，建立城市物流体系，发展城市物流，将有利于城市产业结构向高度化方向发展。（2）推动区域经济的快速增长。加强城市物流基础设施的建设，提高物流技术水平，加快物流速度，无疑对区域经济的发展具有极为重要的意义。现代物流的实质是一种供应链管理，中心城市发展现代物流，很大程度上是一个组织和理顺供应链关系的问题。只有建立高效运作

24、的物流系统，理顺各种供应链关系，才能解决好5城市积聚的货物快捷地发运到周边地区乃至更远的地方，使中心城市对周边地区的辐射功能和在经济上的龙头带动作用才能真正得以发挥。最近十几年，上海、深圳、厦门、宁波等城市在发展物流的过程中通过对基础设施的投资，对当地的经济拉动非常的明显。上海市的物流业以每年213的速度增长，为传统制造业、信息产业和全融业的快速增长奠定了坚实的基础，为上海经济的发展做出了巨大的贡献。（3）增强城市的综合竞争力。如提升城市功能，改善城市国民经济运行效率，提高全社会经济效益，扩大吸引外资，增加就业机会，改善城市投资环境。（4）促进城市的现代化。现在很多城市人流、物流混杂，交通、仓

25、储、流通加工等都集中在城区，城市污染严重。发展现代物流，改造城市的物流系统可以降低物耗和节约能源。有效控制车辆污染，合理使用土地，及时处理废弃物，美化城市环境。国外在城市建设中，都把物流系统重新规划、重新改造。例如日本就把城区里的流通加工、仓库等等重新设计、规划，放到郊区交通发达的地方，建立物流中心。所以，建立合理的城市物流系统是城市现代化的需要。63 车辆路径优化问题3.1 车辆路径优化的定义 车辆路径问题最早由学者Dantzig和Ramser于1959年提出，一般可定义为：对于一系列装货点和（或）卸货点，组织合适的行车线路，使载货车辆有序地通过它们，在满足一定的约束条件（如货物需求量、发送

26、量、交发货时间、车辆容量限制、行驶里程限制、时间限制等）下，达到一定的目标（如路程最短，费用最少，时间尽量少，使用车辆数量尽量少等）。车辆路径问题的示意图如图3.1所示：图3.1 车辆路径问题示意图车辆路径优化问题实际上就是从中心仓库出发，对一系列特定位置和需求量的客户点，选择最优的行驶路线同时调用一定数量的车辆，使车辆有序的访问各客户点的过程。车辆必须在满足特定的约束条件(如客户需求量，车辆载重量等)下，使得货物尽快到达客户点并且运输总费用最低。从图论的角度来说，车辆路径问题可以描述为一个无向图，其中,GV A，V代表顶点的集合， ，代表连接多个顶01,.,NVv vv( ,)|,ijijE

27、v vv vV ijE顾客配送服务中心7点之间线段的集合，通常称为边的集合。顶点表示配送中心的位置，其他顶点则表0v示有待服务的顾客的集合。通常在上定义一个非负的距离矩阵或成本矩阵，E ijDd此处代表从顶点 到顶点的距离或者成本等。ijdij 与旅行商问题（TSP）对比可以看出，车辆路径问题（VRP）就是TSP问题中，给每个客户添加了固定的需求量，同时每一辆车增加了一些约束量，包括时间限制，车辆的容量限制等。图3.2所示是上图中给每个客户添加固定需求和一些约束条件后的VRP问题的解：图3.2 拥有三条路线的一般的VRP的一个可行解3.2 国内外车辆路径问题研究动态3.2.1 国外车辆路径问题

28、研究现状由于车辆路径问题将运筹学理论和企业物流活动紧密联系在一起，自提出后便引起运筹学、图论与网络分析、应用数学、物流科学、计算机应用等学科的专家和管理者的重视，成为运筹学和组合优化领域的前沿和热点问题。国外对物流配送车辆路径问题作了大量而深入的研究，例如早在 1983 年 Bodin、Golden 等人在他们的综述文章中就列举了 700 余篇文献。1962 年，Balinski 和 Quandt 最早使用了集分割法，在对可行解集合直接考虑的基顾客配送服务中心11（28）10（16）9（21）8（6）7（25）6（27）5（7）4（19）3（29）2（17）1（13）8础上进行优化，并提出了最

29、简单的 VRP 模型。1964 年，Clarke 和 Wright 提出一种较有效的启发式算法Clarke-Wright 节约算法。Paessens 等人通过使用适当的数据结构，降低了它的复杂度，ClarkeWright 法随后成为许多专家和学者研究 VRPTW 的基础。随后，Rao 等人引入了列生成方法对 VRP 进行求解。在该方法中，原问题被转化为简化问题，考虑的范围是所有可能的可行解的子集，在此基础上复杂求解，从而寻找最短路径。随着 20 世纪 70-80 年代数学规划和网络分析的发展，人民提出了精确的数学方法解决 VRP 问题，主要有：分枝定界法、割平面法、网络流算法、动态规划法等。如

30、Lee 等为 VRP 建立了一个确定的动态规划模型并设计了一个基于最短路径搜索算法的精确算法。Azi 等通过首先产生所有非支配可行解，然后对路径进行选择排序的方法，建立了一个基于带限制最短路径算法的求解方法。到了 90 年代，人工智能分发展促进了对 VRP 算法的研究，人们采用了模拟退火算法、遗传算法、例子群算法、禁忌搜索算法、蚁群优化算法和人工神经网络算法等智能优化算法。1994 年 Garcia 等首先将禁忌算法应用于 VRPTW 问题。用禁忌搜索算法求解 VRP 问题，虽然能保证对不同的有效搜索途径的探索，但由于涉及复杂的邻域转换和求解策略，因而在实际中不容易实现；Osman 于 199

31、3 年对 VRP 问题的模拟退火算法进行了研究，提出模拟退火方法适合于解决路线分组问题；神经网络模型由McCulloch 和 Pitts 于 1943 年提出，模型主要是利用神经网络中神经元的协同并行计算能力来构造的优化算法；遗传算法是 70 年代由美国 J.Hollan 教授和他的学生建立发展起来的，其基本思想是模拟生物进化中“适者生存”的规律；蚁群算法是 Dorigo 提出的一种基于群体仿生的智能优化算法；微粒群算法算法是由 Kennedy 和 Eberhart 于1995 年提出的一种基于群智能方法的演化计算技术等。3.2.2 国内车辆路径问题研究现状国内对 VRP 问题的研究起步比较晚

32、，大约于 20 世纪 80 年代开始。经过 20 多年的研究，取得了一些成果，但与国外相比，目前仍处于起步状态。在解决具体问题方面：郭耀煌、李军是国内第一批研究 VRP 的学者，他们用传统启发式算法解决了一些相对简单的 VRP 问题，如送货点比较少得容量约束、时间窗约束 VRP；李大卫等以 TSP 的最近距离启发式为基础，通过设置评价函数来处理时间约束，求解了简单的 VRP；张涛等人则是通过遗传算法来保证搜索的全局性，用 3-OPT算法来加强局部搜索能力，得到针对 VRP 的混合算法；蔡延光用遗传算法、模拟退火算法等研究重载 VRP 问题，取得了一些成绩。在理论综述方面：汪寿阳、林岩等对选址路

33、径问题的研究进行了分析；祝崇隽较全面的回顾了 VRP 领域的最新进展；黄虹，张正雄等对车辆路径问题进行研究现状的分析和展望；陈文兰，戴树贵等对车辆路径安排问题算法做了研究综述；谢秉磊、郭9耀煌等对动态 VRP 的最新发展作了评述等。尽管国内学者在 VRP 的研究方面已经有了一定的成果，但是总的说来还是处在起步阶段，由于该问题涉及许多要素，而且为了满足实践的需要，还将融合其它新的要素，仍有很多新的问题值得进一步研究。主要表现在如下几个方面：（1） 研究的问题大多是确定型问题，很少见到研究不确定条件下，特别是实时调度情况下 VRP 的文献。实际中引起不确定性的因素很多且交叉影响，而目前的研究却主要

34、集中在由单一不确定性因素（尤其是需求的不确定性）引起的 VRP，未综合考虑车辆、客户、路况等各种不确定性，同时对不确定性的研究也只限于单一的随机或模糊形式的不确定性，没有考虑更复杂的粗糙情形或者双重不确定性等形式，与广泛的实际应用尚有距离。（2） 在车辆调度的中，应根据使用者的实际制定相关的目标，有些目标甚至相互冲突（比如客户满意度的提高和运作成本的降低就可能是一对矛盾） ，因此在决策中需要更多地考虑多目标的情况，但 VRP 的以往研究主要集中于单一目标问题，对多目标问题的研究尚显不足。（3） 研究问题的手段比较单一。目前国内主要用智能算法对 VRP 进行研究，在可参考的文献中，还没有见到用精

35、确算法做算例的研究成果。（4） 需要建立统一的算法评估体系，主要包括求解VRP算法的复杂性分析和收敛性分析（定界分析） ，通过算法的复杂性分析，可以为评定算法寻优效率提供依据，为设计更快的算法提供理论依据；收敛性分析为评定算法搜索能力提供衡量标准，可以知道该算法可得到的最好和最差解的范围，为使用者选择满足所求问题的搜索精度要求的算法提供依据。而目前只能对VRP的各种算法性能进行经验评价，而且各算法选用的测试数据不全相同，很难客观地评定算法的优劣，因此有必要建立统一的算法评估考核指标体系。3.3 车辆路径问题的分类根据以上国内外研究动态的研究得出车辆路径问题涉及到的各因素是车辆路径问题分类的依据

36、。Bodin(1983)等人将影响车辆路径问题的主要因素整理如表3.1所示。表 3.1 影响调度和路径的主要因素序号因素可能的选择1可行车队的大小一辆；多辆2可行车队的种类单一的（仅有一种车型） ；异质的（多种车型） ；特殊的3车辆的出发点单一场站（单一物流中心）：多场站4需求的类型确定性需求；随机性需求；允许满足部分需求105需求的位置在顾客点上；在路线上；混合型6网络形态间接；直接；混合；欧几里得几何7车辆容量限制全部一样；不一样；没有容量限制8最大行车时间各绕路皆相同；不同绕路不同时间；没有时间限制9作业只有拣货；只有送货；有拣货和送货；粉刺运送10成本变动成本（或绕路成本） ；固定成本

37、（或车辆成本） ；一般成本（没有服务时的成本）11目标最小绕路成本；最小固定成本与变动成本；最小车辆使用数目；最大服务或便利效用函数；最大服务或便利效用函数；最大顾客优先权效用函数目前已知的研究模型是对这些因素中的一种或几种的组合同时忽略其他因素建立的。车辆路径问题的主要模型如下： （1）按起讫点划分为：一是起讫点不同的单一车辆路径问题；二是多个起讫点的车辆路径问题；三是起讫点相同的车辆路径问题。（2）按照有无车辆容量限制分为：有能力约束的车辆路径问题(CapacitatedVehicle Routing Problem，CVRP)和没有能力约束的车辆路径问题。CVRP是指任意车辆路径的总重量

38、不能超过该车辆的重量或体积的能力负荷。（3）有时间窗约束和无时间窗约束的车辆路径的问题。包括硬时间窗(Hard Time windows)和软时间窗(Soft Time windows)约束。引出带时间窗(包括硬时间窗和软时间窗)的车辆路径问题(Vehicle RoutingProblem withTime windows，VRPTW)。如果到达任务点的时间是事先规定的，则称该问题是带时间窗要求的车辆优化调度问题；若到达和离开时间没有规定，则称该问题就是一个直接的线路安排问题。带时间窗的VRP又可分为硬时间窗VRP和软时间窗VRP。硬时间窗VRP 指每项任务必须在要求的时间内完成，软时间窗VR

39、P指如果某项任务不能在要求的时间范围内完成，则给予一定的惩罚。（4）满载和非满载的车辆路径问题。当每个客户需求量小于车辆容量时，用一辆车执行一项任务就存在不满载运行情况，调度时可安排一辆车执行多项任务，即在一辆车上装载不同货主的货物，这类问题称为非满载VRP。当然， 这类问题有一个前提条件，即不同货主的货物允许混装。当每个客户需求量大于车辆容量时，用一辆车执行一项任务就不能满足客户的需求，此时需要一辆以上的车对其进行送货，车辆能够满载，该问题称为满载VRP。（5）单车场和多车场的车辆路径问题(Singleand Multi-Depot Vehicle Routing Problem)。单车场车

40、辆路径问题是指所有的车辆均从一个配送中心发出，完成各自的任务后11都返回该配送中心。多车场车辆路径问题是指，存在着多个配送中心，车辆可以从任何一个配送中心派出，完成任务后，车辆也可以返回其中的任何一个配送中心，随着供应链的集成一体化，多车场的车辆路径问题将越来越多、越来越重要。对于这类问题可以通过一定的方法将其转化为单车场的车辆路径问题。（6）按车辆类型数量分为：单车型问题(所有配送车辆的载重量相同)和多车型问题(配送车辆的载重量不完全相同) (Mixed/Heterogeneous Fleet Vehicle Routing Problem。MFVRP/ HFVRP)。（7）按车辆对车场的所

41、属关系分为：开路车辆路径问题(Open Vehicle RoutingProblem) （即车辆完成配送任务后可以不返回其发出车场) 和封闭车辆路径问题(即车辆完成配送任务后必须返回其发出车场)。（8）按配送任务特征分：纯送货问题、纯取货问题、取送混合问题(Vehicle Routing Problem with Pick-up andDelivery，VRPPD)。纯送货问题仅考虑从物流中心向客户送货，也称为纯卸问题；纯取货问题仅考虑把各客户供应的货物取到物流中心，也称为纯装问题；VRPPD既考虑将客户需求的货物从配送中心送到各个客户，同时考虑将客户供应的货物从客户取到物流中心，也称为装卸混

42、合问题或集货和送货一体化问题。（9）确定型需求车辆路径问题、模糊需求车辆路径问题(Fuzz Vehicle Routing Problem，FVRP)、随机需求车辆路径问题(VehicleRouting Problem withStochastic Demand ，VRPSD) 。随机需求车辆路径问题目前主要研究的是随机客户、随机需求、随机时间这三方面的内容。随机客户问题在物流领域经常会出现。随机需求车辆路径问题(VRPSD)，虽然知道确切的客户，却无法知道客户的准确需求量。模糊需求车辆路径问题FVRP：在实际的车辆调度中，某些待服务客户的需求信息没有或无法给出准确的描述，所以就需要将模糊概念

43、引入模型和算法来解决这类问题；另一种形式是将模糊概念引入时间窗，通常客户需要服务的时间虽然有一个范围，但是一个模糊量。车辆在客户要求的范围内到达都是可行的，但到达的时间不同，客户的满意度可能不同，这类问题同时是多目标优化的问题。(10) 周期性的车辆路径问题(Periodic VehicleRouting Problem，PVRP )。周期性车辆路径问题是对VRP的扩展，VRP研究的是对车辆的日安排，而PVRP是对车辆的一个周期内多日的安排。在一个周期内，每个客户在满足需求的前提下，最少被服务一次，也可以是多次。（11）非对称网络车辆路径问题(Asymmetric Network Vehicl

44、e Routing Problem，AVRP)。非对称网络车辆路径问题在现实生活中比较常见，如单行道或禁止左转等交通标识的存在，使得从甲地到乙地，和从乙地到甲地的距离(或时间)并不相同。由于非对称网络的这个特性，使得许多在VRP中成功应用的算法不能直接用于非对称网络的求解，目前的许多求解算法都是基于非对称TSP问题的算法而来的。12（12）按目标多少分为：单目标车辆路径问题和多目标车辆路径问题。单目标车辆路径问题仅考虑一个配送目标；多目标车辆路径问题同时考虑多个配送目标，比如说同时考虑里程最短、费用最少、时间最短等。3.4 车辆路径问题算法分类由于VRP对节约物流成本、提高物流系统效率有重要的

45、意义，该问题的求解算法一直是物流和算法研究领域的一个热点问题。早期的研究者主要构造精确算法求解VRP。一般来说，精确算法对于客户数小于50的VRP具有较高的性能，但是，对于更大规模的VRP，精确算法的处理时间通常就难以接受了。对于更大规模的VRP，研究者主要通过构造启发式算法来求解。3.4.1 精确算法 精确算法是求出最优解的算法，主要有分枝定界法、割平面法、动态规划法、网络流算法等。（1）枝定界法。分枝定界法求解VRP问题的基本思想是，以相应的不含整数约束的VRP问题的最优解为出发点，若此解是整数解，那么这个解就是原VRP问题的最优解，否则非整数解的相邻整数作附加条件，形成2个分枝，即2个子

46、问题，进行求解。若对上面2个子问题求出最优解是整数解，则停止该子问题的分枝，否则继续分枝求解。这种方法只能适用于求解小型VRP问题。（2）割平面法。割平面法求解VRP问题的基本思想是，在求解相应的不含整数约束的VRP问题上，增加线性约束条件(几何术语称为割平面)，以将可行域切割掉一部分，使其切割掉的部分只包含非整数解，没有切割掉任何整数可行解，直到切割后得到的可行域有一个整数坐标的极点恰好是最优解为止。由于割平面法求解时间过长，故不适用于大规模问题。（3） 动态规划法。动态规划法求解VRP问题的基本思路是，将VRP问题视为一个n阶段的决策问题，进而将其转化为依次求解n个具有递推关系的单阶段的决

47、策问题，从而简化计算过程。用这种方法可求得VRP的最优解，但仅适用于较小规模的寻优问题。（4）网络流算法。网络流算法求解VRP问题的基本思想是，首先构建VRP问题的网络模型，找到网络中需调量最大的弧，然后通过调节弧流量或弧两端节点上的位势，来减少弧上的需调量，直至所有弧的需调量都等于零。由于网络模型的顶点数目和边的数目会显著影响网络流算法时间效率，所以这种算法只适用于小规模的VRP问题。由于精确算法在求解时引入了严格的数学方法(手段)，精确算法的计算量一般会随着问题规模的增大呈指数增长，从而使该类算法只能有效求解小规模的VRP问题，如在客户数量较少、运输网络较简单时，才能求得物流配送车辆调度问

48、题的精确最优解，在实际中其应用范围很有限。133.4.2 启发式算法 启发式算法在求解VRP问题时通常是从初始解出发，以邻域搜索的方式实现解的改进，并在较短的时间内获得一个可以接受的解。它包括:（1）节约算法。该算法的基本思路是，按节约值从大到小构造路径，在车辆容量限制下，依序将对应的两客户点排入路径中，直至所有客户都被排入路径为止。这种算法具有运算速度快的优点，特别是在小规模的配送优化中，节约算法的优化精度与最优解很接近，并且能够很快给出结果。但在客户规模增加后，容易出现不理想的优化结果。（2）最邻近法。算法从配送中心开始，搜索距离配送中心最近的、未访问的节点作为第一个节点并设为已访问，然后

49、以该点为中心搜索与之相邻的、未访问的节点，如果加上该点不会超出容量限制，则将该点加入到线路中并设为已访问，否则结束该条线路。重复上述步骤，寻找距离配送中心最近的未访问的节点作为新线路的第一个节点，生成新的线路，直到将所有的节点都访问过。最邻近法算法简单，可以在较短时间内求得初始解。但易早熟收敛，容易陷入局部最优。（3）最近插入法。最近插入法的算法流程与最邻近法基本相似。这种算法的关键是依序选择最合适的未分配的节点在路线中进行最佳位置的插入，以构建配送路线，直至不存在可行插入节点时新增一条初始路线。用最近插入法求得的解比最邻近法求得的解更优，但在计算过程中，也耗费了更多的计算量。（4）扫描法。它

50、假设车辆的路线位于一个几何平面上，平面上所有的点都以极座标来表示，配送中心为原点。先选定一尚未使用的车辆，在不违反车辆容量限制的前提下，从角度最小且尚未指派的节点开始，依顺时针或逆时针的方向扫描。当车辆容量超过时，结束该条线路。重复上述步骤，生成新的线路，直到将所有的节点都被排入。最后再用求解旅行商问题(TSP)的算法对每一条路线分别进行优化。用扫描法求解VRP问题，能在较短的时间内求得可行的满意解，但不一定能导出最优解。3.4.3 智能算法20世纪90年代以来，由于人工智能方法在解决组合优化问题中的强大功能，不少学者开始将人工智能引入车辆路线问题的求解中，并构造了大量的基于人工智能的启发式算

51、法(智能化启发式算法)。智能化启发式算法包括:（1）禁忌搜索算法。它是一种全局逐步寻优算法，引入了一个禁忌表，记录下已经搜索过的局部最优点，在下一次搜索中利用禁忌表中的信息不再或者有选择地搜索这些点，以此来跳出局部最优点，从而实现全局优化。用禁忌搜索算法求解VRP问题，虽然能保证对不同的有效搜索途径的探索，但由于涉及复杂的邻域转换和求解策略，因而在实际中不容易实现。（2）模拟退火法。模拟退火法是是一种基于热力学原理的随机搜索算法。用模拟退火14法求解VRP问题时，把物理退火中原子获得能量相当于分配最优节点，将原子振动模拟为线路寻优空间的随机搜索。搜索过程由执行分配的成对交换完成，搜索初始解为配

52、送总成本。对现有分配情况用任意成对交换产生新的分配，从而对配送路线不断进行改进，直至找到最优路线。模拟退火算法适合大规模的需求固定或者随机需求的VRP问题。从理论上讲，用这种方法求解VRP问题，可以求得全局最优解，但在实际应用中，由于受计算时间的限制，往往只能给出一个近似的最优解。为了使模拟退火算法求出的近似解更准确，一般重复执行模拟退火法多次，从中选取最好的解作为最终的近似最优解。（3）神经网络算法。神经网络模型主要是利用神经网络中神经元的协同并行计算能力来构造的优化算法。它将实际问题的优化解与神经网络的稳定状态相对应，把实际问题的优化过程映射为神经网络系统的演化过程。袁健和倪勤在2000年

53、曾用神经网络算法求解了随机需求情形的VRP问题。神经网络算法求解VRP问题可能会导致网络最终收敛于局部极小解，甚至可能收敛到问题的不可行解。此外，网络最优的最终结果很大程度依赖于网络的参数，即参数鲁棒性较差。（4）遗传算法。遗传算法是进行局部搜索改进的一类算法。遗传算法求解VRP问题时，主要利用生物进化世代性与最优路线搜索迭代性间的共性，在全局范围内搜索配送路线的最优解。如遇同一级配送节点分支的相同耗费情况，则均予以考虑，分别参与下一步骤迭代，并由后续步骤逐渐淘汰，最终确定最优配送路线；如遇同一级配送节点分支的不同耗费情况，则适者幸存0，由耗费少的配送分支获得继续迭代的权利，但并不能确定其最优

54、资格，必须参与后续淘汰步骤，直至迭代结束，得到最优配送路线。遗传算法具有良好的鲁棒性、灵活性、通用性，特别适合于大规模VRP 问题的求解。但由于算法本身还存在的一些缺陷，如易出现早熟收敛，局部搜索能力差，因此，不能保证最大概率收敛到全局最优解。（5）蚁群算法。蚁群算法基本原理是模拟蚁群搜索食物的行为: 蚂蚁群找到食物时，它们总能找到一条从食物到巢穴之间的最优路径。这是因为蚂蚁在寻找路径时，会在路径上释放出一种特殊的信息素。当它们碰到一个还没有走过的路口时，就随机地挑选一条路径前行，并释放出与路径长度有关的信息素。路径越长，释放的激素浓度越低。当后来的蚂蚁再次碰到这个路口的时候，选择激素浓度较高

55、路径概率就会相对较大。这样就形成了一个正反馈，最优路径上的激素浓度越来越大，而其他的路径上激素浓度却会随着时间的流逝而消减，最终整个蚁群会找出最优路径。该算法在求解VRP问题方面有良好效果，但存在如计算时间较长、容易陷入局部最优等问题。（6）微粒群算法。PSO算法是通过模拟鸟群的捕食行为来达到优化问题的求解。首先在解空间内随机初始化鸟群，鸟群中的每一只鸟称为粒子0，这些粒子0在解空间内以某种规律移动，经过若干次迭代后找到最优解。在每一次迭代中，粒子通过15跟踪2个/极值0来更新自己。第一个是粒子本身的最优解(Pbest0)；另一个极值是整个微粒群目前找到的最优解(Obest0)。找到这2个极值

56、后，每个粒子根据自己的飞行速度，决定自身的走向及飞行距离。用PSO算法求解VRP问题具有收敛速度快、依赖的经验参数少、简便易行等特点。但与其他进化类优化算法一样，存在易于陷入局部最优的缺陷。从上述分析可知，求解VRP问题的方法有很多，但各种方法在一定时期、一定情况下都有各自的优点，都具有解决某一类问题的优越性。164 节约算法的理论基础及算法设计由于本文主要研究的是基于节约算法的路径优化问题，所以本章详细介绍下节约算法。4.1 CW节约算法提出CW节约算法是一类最为经典的构造型启发式算法之一，1964年，Clark和Wright最早提出该算法，并被简称为CW节约算法。该算法的思想是：根据顾客点

57、之间的最短距离、最小成本或运输路程所用最小时间（即最大节约量）为原则，将路线外的客户点依次插入到线路中，直到所有的点都被安排进路线为止。4.2 CW节约算法原理及特点4.2.1 CW节约算法的基本原理假如由一家配送中心()向两个用户，送货，配送中心到两客户的最短距0P1P2P离分别是和，和间的最短距离为，的货物需求量分别是和01C02C1P2P12C1P2PaQ，且(+)小于运输装载量，如图 1 所示，如果配送中心分别送货，那么需要bQaQbQQ两个车次，总路程为: 10102=2SCC如果改用一辆车对两客户进行巡回送货，则只需一个车次，行走的总路程为: 2010212SCCC有三角形的性质我

58、们知道:120102CCC所以第二次配送方案明显优于第一种，且行走总路程节约:010212SCCC1P2P01C02C0P0P1P2P01C02C+图 4.1 节约里程法的基本原理17如果配送中心的供货范围内还存在着 3 ，4 ，5 ，n 个用户，在运载车辆载重和体积都允许的情况下，可将它们按着节约路程的大小依次联入巡回路线，直至满载为止，余下的用户同样方法确定巡回路线，另外派车。4.2.2 CW 节约算法对车辆进行优化调度的步骤基于节约里程法的基本思路，在配送网络中寻找这样的三角形的回路：尽可能装载多的货物，且节约尽可能多的行驶里程。具体的步骤如下：（1） 形成初始解。初始解满足顾客的需求，

59、而且所有的约束条件，如车辆载重量的限制、车辆总数的限制等也能得到满足。基本的初始解为直送式配送， 即不考虑线路合并的一对一的配送模式，配送中心对每个客户的送货点均指派一辆车或多辆车完成配送。（2） 进行节约度的计算。即计算出左图中的，即两个客户之间010212SCCC的历程节约度为这两个客户节点分别到配送中心的里程之和减去客户节点之间的距离。（3） 对节约度从大到小进行降序排列。（4） 进行回路的合并。从节约度排序表找出产生该节约度的两个客户节点 、，并ij判断连接 、的回路是否存在合并的可能性。如果一个回路以（，）开始，ijpj一个回路以( ， )结束，则该回路可以合并，并进行下面的合并操作

60、：删除ip两个回路中的部分路径（，）和（ ，），然后引入新的连接( ，)，pjipij得到新的回路（， ，）。pijp4.2.3 CW 节约算法的特点CW 节约算法是一种启发式算法，属于构造式启发式算法，与智能启发式算法有区别，它属于逐次逼近法的一种，该算法在求小规模运输配送路线，优化车辆调度问题方面有自身的优势，该算法具有技术步骤简单，易懂，计算速度快，并且易于考虑各种实际问题的优点。4.3 节约算法设计4.3.1 模型的数学描述由于海王星辰的药品配送属于药品零售的范畴，其突发性状况比较小，对于时间的要求也比较小，所以配送过程只要避开城市的早晚高峰即可。本文为保证药品能够及时满足各门店每日销