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

题 目 基于CW算法的海王星辰连锁药店市内配送优化 社会化分工日益精细化，使得供应与生产、生产与消费在时间和空间上出现了矛盾，促使物流在社会生产和生活中扮演着越来越重要的作用，物流的运营水平关系着一个国家经济发展的水平，各国政府都正大力发展本国物流。配送是物流运作中的一个重要环节，车辆路径问题是物流运输系统的核心组件，研究车辆路径问题有助于企业降低物流成本、提高运作效率、提高客户满意度。车辆路径问题将运筹学理论与管理实践紧密地结合在一起，是近半个世纪以来运筹学领域最成功的研究之一。 本文主要结合海王星辰在宁波市内的配送路径优化实例，简单介绍了城市物流的一些基本特征及发展的意义、国内外对车辆路径的研究现状、车辆路径优化问题，因本文采取节约算法作为路径优化的工具，故并着重介绍了节约算法的概念及其算法过程，最后详细的介绍了海王星辰路径优化的方案过程及其得出的结果。 关键字：物流；车辆路径问题；配送路径优化；节约算法 Abstract with 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 increasingly important role of the production and the logistics in the social life. The country's 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 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 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 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 solution process and the results. Key words: logistics；Vehicle routing problem；distribution route optimization；saving algorithm 目录 1 选题背景和研究意义 1 2 城市物流特征及发展城市物流意义 2 2.1 城市物流配送 2 2.2 城市物流的特征 2 2.3 城市配送的现状 3 2.4 发展城市物流的意义 4 3 车辆路径优化问题 6 3.1 车辆路径优化的定义 6 3.2 国内外车辆路径问题研究动态 7 3.2.1 国外车辆路径问题研究现状 7 3.2.2 国内车辆路径问题研究现状 8 3.3 车辆路径问题的分类 9 3.4 车辆路径问题算法分类 12 3.4.1 精确算法 12 3.4.2 启发式算法 12 3.4.3 智能算法 13 4 节约算法的理论基础及算法设计 16 4.1 CW节约算法提出 16 4.2 CW节约算法原理及特点 16 4.2.1 CW节约算法的基本原理 16 4.2.2 CW节约算法对车辆进行优化调度的步骤 17 4.2.3 CW节约算法的特点 17 4.3 节约算法设计 17 4.3.1 模型的数学描述 17 4.3.2 数学模型的建立 18 5 案例分析 19 5.1 案例背景 19 5.2 案例数据分析 20 5.2.1 供应门店选择及分布 20 5.2.2 供应门店需求量 22 5.2.3 配送车辆选择 24 5.2.4 配送距离的确定 24 5.2.5 算法程序设计 25 5.3 结果分析与算法改进 27 5.3.1 结果分析及得出的改进方案 27 5.3.2 改进方案的设计 28 5.4 改进算法得出的运行结果与分析 29 5.4.1 运行结果 29 5.4.2 结果分析与确定 31 5.5 案例分析总结 32 致谢 34 参考文献 35 附录 36 附录1 配送距离和时间原始数据 36 附录2 配送路径距离表 45 附录3 节约里程表 46 附录4 初始算法程序代码 47 附录5 方案一算法主要程序代码 55 附录6 方案二算法主要程序代码 61 1 选题背景和研究意义 当今，世界经济发展日益趋于全球化，市场竞争也异常激烈，在此背景下产生了一个新兴行业——物流业。物流是社会经济和商品流通发展到一定阶段的必然产物，为了满足社会生产和消费需求，对运输、仓储、装卸搬运、包装、流通加工、配送、信息处理等物流环节进行现代化管理、控制及信息化作业的经济活动。随着世界贸易的高速发展和信息网络技术的日益完善，全球经济一体化步伐的加快，特别是我国加入WTO以后，物流业作为国民经济中一个新兴的产业，将会成为我国21世纪经济发展的重要产业和新的经济增长点。 作为“第三利润源泉”的物流对经济活动的影响日益明显，越来越得到了人们的重视，成为当前“最重要的竞争领域”，未来市场竞争，物流将起着举足轻重的作用，而配送是物流中一个重要的直接与消费者相连的环节，《物流术语》中对配送的定义为：物品从供应地向接收地的实体流动过程，根据实际需要，将运输、储存、装卸搬运、流通加工、配送、信息处理等基本功能，实施有机结合。配送的核心部分是配送车辆的集货、货物分拣及送货过程，而车辆配送路径的合理优化，对于整个物流运输速度、成本、效益影响至关重要。 但是目前，由于我国的物流产业起步晚，尚存在着许多问题。如何改变这种局面，使物流行业健康稳步发展，是国民生产力发展急需解决的难题，当前主要可从提高物流配送服务质量入手。在现代物流系统中，配送是一个重要环节，而在配送业务中，能否将货物及时送交收货人手中是物流系统优化的关键，配送的质量好坏决定服务水平的高低，同时影响到客户对整个物流服务的满意程度。然而物流车辆在配送过程中，会涉及到车辆路径优化的问题。因此结合实际的配送情况，规划好物流配送的行进路线，有利于节省配送费用和提高配送服务质量。同时，优化后的物流配送路径，有利于缓解交通压力。由此说明，物流车辆路径优化问题在交通和物流规划中具有举足轻重的地位。 选取恰当的车辆路径，可以加快物流系统对客户需求的响应速度，提高服务质量，增强客户对物流环节的满意度，降低服务商的运作成本。另外，由于在车辆配送过程中，有个别客户对物流配送时间提出高要求，为了提高服务质量和满意度，所以必须对于配送时间要求严格掌控。总的来说，本文是为了提高物流配送系统的服务质量和节省配送费用，对物流车辆配送路径的优化进行的研究。 为了更加形象的分析问题，本文将选取宁波市区海王星辰药店的药品配送为例，对中小型城市内的车辆路径优化进行研究。 2 城市物流特征及发展城市物流意义 2.1 城市物流配送 所谓物流配送就是按照用户的货物( 商品) 订货要求和物流配送计划，在物流配送节点( 仓库、商店、货运站、物流配送中心等) 进行存储、分拣、加工和配货等作业后，将配好的货物送交收货人的过程。而城市物流配送是指在城市范围内进行的物流配送业务活。 所谓城市物流是指为城市服务的物流，它服务与城市经济发展的需要，指物品在城市内部的实体流动，城市与外部区域的货物集散以及城市废弃物清理的过程，并存在不同的模式、体系和存在形态，和其他形式的物流有一定的区别。 城市物流配送系统的服务对象可归类为：政府、工业、商业、农业、大众客户。即电子商务中所描述的B to G，B to B，B to C。城市物流配送已随客户需求变化从“少品种、大批量、少批次、长周期”向“多品种、小批量、多批次、短周期”转变。由于城市范围一般处于汽车运输的经济里程。因而这种物流配送往往采用汽车实现。 城市物流是城市经济发展的产物，同时，城市物流又服务于城市经济发展的需要，并且是城市经济的一个有机组成部分。不论城市地域范围大小，物流活动都具有共同的属性。城市物流所包含的范畴可以有两种理解：一种理解是城市物流仅仅是城市内部范畴的物流，而城市的输入物流及城市的输出物流是发生在若干城市之间的物流，已经属于区域物流的范畴，这是对城市物流侠义的理解；另一种理解是包括城市内部的物流以及以城市为主体的城市外部物流，例如，城市的输入物流及城市的输出物流，这是对城市物流广义的理解。 2.2 城市物流的特征 城市物流师连接企业物流和区域物流之间的纽带，即服务与城市经济发展的需要，也服务于区域经济发展的需要。城市聚集了大量的人口、政府机构、工商企业、商品、文化教育机构，分布着大量的航空、铁路、公路等交通运输网络和枢纽站点，在政治、经济、文化生活中起着重要的作用，具有较强的吸引力、辐射力和综合服务能力，对周边地区经济发展能起到渗透、带动作用。城市经济和区域经济的形成是城市物流产生的条件，城市商品和服务市场的繁荣为城市物流的发展奠定了坚实的基础。城市物流的发展又为城市的发展起到有力的支撑作用，因此城市物流与城市经济涉及的范围是一致的，从这个意义上说城市物流可以理解为是以城市为依托的区域物流，因此，有关区域物流的理论与政策、区域物流的规划原则与方法、区域物流发展对策等等也适用于城市物流。 城市物流的主要特点有： （1） 与以承载大宗货物为主的区域物流相比，城市物流的密度大、承载的货物种类繁多，且这种情况与城