帝峰模具公司物流配送路径优化研究毕业论文.docx

帝峰模具公司物流配送路径优化研究毕业论文目 录 TOC o 1-3 h z u摘 要 abstract 第1章 绪 论 11.1 研究背景 11.2国内外研究现状 21.2.1 国外研究现状 21.2.2 国内研究现状 41.3研究目的、意义和方法 61.3.1 研究目的 61.3.2 研究意义 61.3.3 研究方法 71.4 本文研究内容 7第2章 相关理论概述 92.1 物流配送 92.1.1 物流配送的概念 92.1.2 物流配送的功能 92.1.3 物流配送的要素 102.2 配送路径优化问题 112.2.1 配送路径优化的目标 112.2.2 配送路径优化问题的分类 122.2.3 配送路径优化问题的解法分类 132.3 本文配送路径优化方法 152.3.1建立VRP模型 152.3.2最近插入法 152.3.3 扫描法 162.3.4节约算法 17第3章 帝峰模具公司物流配送路径现状分析 193.1 公司简介 193.2 公司物流配送路径现状 193.3 公司物流配送路径存在的问题分析 223.3.1 回路总数过多 223.3.2对流运输 233.3.3经验化操作 23第4章 帝峰模具公司物流配送路径优化策略 254.1 建立VRP模型优化配送路径 254.2 公司物流配送路径的优化 254.3.1运用最近插入法优化 254.3.2 运用扫描法法优化 284.2.3运用节约算法优化 324.4 三种优化方案比较分析 37结 论 40致 谢 41参考文献 42 第1章 绪 论1.1 研究背景物流是为了满足消费者需要而进行的从供应地到接收地的原材料、中间产品、最终产品及相关信息的有效流动和储存计划、实施和控制的管理过程,其功能是通过运输、仓储、装卸搬运、包装、流通加工、配送、信息处理等活动过程有机结合起来实现的1。其中配送对于物流的运行和发展有着深刻的社会根源和历史背景。在市场经济体系中，物流配送犹如人体的血管，把国民经济各个部分紧密地联系在一起。物流配送是物流的基本功能，作为直接面向最终客户提供的物流服务，在满足现代化的物流需求方面发挥着极其重要的作用。如果没有配送就会影响物流的经济效益和社会效益，可以说物流成果主要是通过配送来实现的。物流配送一般处于物流末，是直接面向用户提供服务的环节，它具有提高物流经济效益，优化、完善物流系统，改善物流服务，降低物流成本等功能，在物流系统中占有重要的地位。随着市场经济的繁荣，企业业务规模日益扩大，物流配送作为现在现代企业一个重要环节，其效率高低直接影响企业的服务质量、配送成本，而配送路径优是物流配送的核心问题，因此物流配送路径优化问题是成为当前物流研究中的一个重要课题,所以它是一项特殊的、综合性的物流运动，其主要包括集货作业、配货作业、车载货物的配装、配送线路的确定。配送实际上是一个局部物流，是大物流在小范围内的运作，配送是物流系统的终端。是否具备及时的配送时间影响服务水平的高低，这需要对车辆配送路径的合理优化和配送时间的掌控2。现代物流己成为世界经济发展的研究重点，我国政府也对物流产业的发展和监管非常重视。但是目前，由于我国的物流产业起步晚，尚存在着许多问题。如何改变这种局面，使物流行业健康稳步发展，是国民生产力发展急需解决的难题，当前主要可从提高物流配送服务质量入手。在现代物流系统中，配送是一个重要环节，而在配送业务中，能否将货物及时送交收货人手中是物流系统优化的关，配送的质量好坏决定服务水平的高低，同时影响到客户对整个物流服务的满意程度。然而物流车辆在配送过程中，会涉及到车辆路径优化问题。由此说明，物流车辆路径优化问题是物流运作管理面临的重点问题，在交通和物流规划中具有举足轻重的地位。武汉帝峰模具是一家集设计、生产、销售、配送于一体的经营五金模具和塑胶模具的有限责任公司。作为一家以生产为主的企业，其在配送运输方面存在一定的不足之处，配送工作效率较低，配送成本较高。从车辆路径优化方面考虑配送优化，对运输路线进行合理规划，寻找一条符合实际情况的优化路径，这样才能从实际上节省配送费用，缓解交通的压力，使配送工作顺利进行，从而节省配送过程中运输费用耗费，而且使配送服务水平提高，并提高用户的满意度，以致提高工作效率，减少运营成本。1.2国内外研究现状1.2.1 国外研究现状Clarke 和 Wright（1964） 对 Dantzig 和 Ramser 提出 VRP问题模型的求解算法进行了改进，提出了更为有效的启发式算法Clarke-Wright节约法，后来该算法成功的用于求解车辆路径优化问题2；Miller&Gillet(1974)提出扫描法(SweepMethod),目的在于求解车辆调度问题,并针对当时几个求解相似问题的算法进行比较,证明该算法所求得的解较优于其它的方法3；Dorigo，Maniezzo和Colorni（1991）等意大利人将蚁群算法用于求解旅行商问题，并取得了很好的效果，后来，Dorigo 在基本蚁群系统的模型的基础上又提出蚂蚁群系统(Ant Colony System，ACS)模型，该模型改进了蚂蚁系统模型的信息素更新方法和路径选择方式；Gendreau,HertZandL即orte(1994)使用插入法求解旅行商问题,再用贪婪法(GreedyMethod)进行路线切割,从而产生初始解；Kennedy和Eberhart（1995）等美国博士，提出了粒子群算法，Eberhart博士等人对基本粒子群算法进行了改进，该算法被成功的用于求解物流路径规划问题；Renaud（1995）等意大利博洛尼亚大学的博士对多配送中心的车辆路径规划问题(Multiple Depot Vehicle Routing Problem，MDVRP)进行了研究，MDVRP 比一般的 VRP问题模型更为复杂，配送车辆的参考点有多个配送中心，每个配送中心都有车辆参与网点的配送任务，这样路径规划问题非常复杂，但多配送中心的车辆路径规划问题是目前物流业迅速发展的一种趋势。美国的 G.B.Dantzig在1947年提出线性规划、美国的B.Jackowski等人1985年提出隐式枚举算法、以及美国的J.Culberson在1992年提出了迭代的贪心算法后来都成功的被用来求解小规模数据网点的物流路径规划问题，这是一类精确式算法，在求解小规模网点的物流路径规划问题具有计算速度快、求解精确的特点4；Babraroosglu&Ogzur(1999)利用禁忌搜寻法为土耳其某物流公司构建一套决定货车配送点顺序的方法DETABA,以二种乱数选取节点的方法产生初始解,找到其中最佳的解作为初始解,再以插入法(InsertinoProcdeuer)作为搜寻邻近解的移步方法,最后以2一opt改善方法找到最优解的值；su&chen(1999)成功地将自组织影射网络应用在车辆配送区域及路线规划问题的求解上,其算法的主要概念是利用类神经网络快速运算、自我组织与平行处理的特性,配合M个一维环状网络拓扑来表现车辆路线配送问题；T. Ralphs（2003）等美国利哈伊大学的研究者对CVRP问题模型进行了研究，CVRP是相对VRP问题提出的，表示参与配送任务的每一辆车都有自身的约束条件，如载重量、最大行驶里程等等，在满足这些约束条件的前提下，完成所有网点订单任务的配送，目标是总成本最少的路径规划问题，后来有很多研究者在CVRP问题模型的基础上提出了带有时间窗约束的CVRP 问题模型，本文的研究的物流路径规划问题带有多个时间窗约束5。1.2.2 国内研究现状通过查阅相关文献资料了解到目前国内学者在企业的物流路径优化问题的研究起步较晚，有些学者在研究这方面课题时也提出过一些有建设性的思路6：杨宝石（2013）把城市快递配送路径问题看作是简单的旅行商问题（Travel Salesman Problem，TSP），针对该问题模型除了考虑了一般性的约束之外，仅仅只额外考虑了容量约束。当问题规模不大时，可以得到全局最优解；何俊生（2013）针对同城快递配送路径问题，提出了两个模型，一个不考虑时间窗约束仅考虑容量约束，另一个同时考虑，采用 Dijkstra 遗传优化算法求解并进行了比较对比分析。姜艳和关雪（2008）提出了一个线性混合整数规划模型，该模型主要考虑时间窗约束和单车快件数目上限约束；杨从平（2014）针对快递物流配送车辆路径问题，考虑了容量约束和单车最大行程距离约束，采用蚁群算法对桂林市某快递网络的配送路径进行了优化。李炳会（2008）则用超时惩罚对时间约束进行了替代，即快递超过预定时间需要赔偿以进行惩罚；陈敏（2009）研究了如何快速响应动态信息的车辆调度问题，并将其描述成是一个实时带时间窗车辆路径问题（Real-time Vehicle Routing Problem with Time Windows，RT-VRPTW）。针对实际调度问题的规模、复杂度和特性，将动态问题转化成静态问题，提出了一种混合禁忌搜索算法；胡明伟和唐浩（2010）则研究了快递服务相关的动态车辆路径问题，并将其描述成带时间窗的动态旅行修理员问题（Dynamic Traveling Repairman Problem with Time Windows，DTRPTW），建立了包括服务客户数量最大、客户等待时间最小以及总运行时间最短三重优化目标模型；吴海东（2011）针对城市快递服务问题，重点研究了服务质量相似性和快递车辆交接行为这两大新的快递服务趋势，同时建立两阶段模型，在满足随机客户需求的条件下，还能够保证快递配送的路径得到最优。目前国内对 VRP 问题的研究很多都停留在理论研究阶段，实验成果并没用广泛的进行实际应用，而且研究的问题模型都有一定的条件约束和局限性。1.3研究目的、意义和方法1.3.1 研究目的为了提高物流配送系统的服务质量和节省配送费用,对物流车辆配送路径的优化和行程时间的预测所进行的研究，本文通过制定较为合理化、人性化的物流车辆配送路径,满足实际的物流配送要求,从而能将货物迅速、安全地送到客户手中,达到提高服务水平的要求；与此同时，加快物流系统对客户需求的物流配送路径优化和行程时间预测响应速度,提高服务质量,增强客户对物流环节的满意度,降低服务商的运作成本使整体的服务水平提高7。1.3.2 研究意义第一，本文结合实际的配送情况，对配送车辆路径优化理论与方法进行系统研究是物流集约化发展、建立现代调度指挥系统、发展智能交通运输系统和开展电子商务的基础，同时,优化后的物流配送路径,有利于缓解交通压力8；第二，规划好物流配送的行进路线,有利于节省配送费用,而对行程时问精确的预测反过来有利于指导物流规划的行进路线,引导车辆沿途配送物资9；第三，物流配送路径优化,是物流配送优化中关键的一环。对货运车辆进行路径优化,可以提高物流经济效益、社会效益、实现物流科学化10；第四，优化配送路径问题对提高物流企业配送效率，降低物流配送成本，促进经济的快速发展都具有重要的作用，从而对物流配送路径规划的研究具有非常高的应用价值11。1.3.3 研究方法1、文献参考：本文主要是通过对互联网上的相关文献、资料以及图书进行详细的阅读和思考，并参考其中相关有用的文字以及解决问题的思路及方法。2、实地考察：在武汉帝峰模具有限公司实习期间，将搜集的资料进行大致的提炼，对于物流配送路径的各项考虑因素进行主次分类，并带着这些疑问在公司实习之余对配送路径方案进行大致的理解与总结。3、定量分析法：依据近三个月物流单据结合运筹学相关知识，运用节约算法、扫描法和改进的最近插入法进行必要的分析与运算，并比较三种方法的结果以得到较优路径的设计方案。1.4 本文研究内容本文以武汉帝峰模具有限公司为例，在对物流配送业务进行研究的基础上,针对物流配送中对成本影响较大的车辆路径问题(VRP)进行集中研究, 在车辆载重限制、时间限制、客户需求量限制和指定地点的条件下建立了VRP数学模型,并利用启发式算法中的三种方法优化配送路径，并选出较优方案12。本文的研究内容如下:第一章阐述本文的研究背景，国内外研究现状，研究意义、目的和方法；第二章对物流配送和配送路径优化问题进行了相关理论的概述，并介绍了节约算法、扫描法和最近插入法的原理及步骤13；第三章主要介绍了本人实习所在公司，描述了其在物流配送路径方面的现状以及存在的问题；第四章是本文的重点部分,首先介绍了关于改进公司配送路径的基本思路，其次运用节约算法、扫描法以及改进的最近插入法优化配送路径，然后比较三者得出的结论并选出较优方案。 第2章 相关理论概述2.1 物流配送2.1.1 物流配送的概念物流的含义是：依照客户的订单要求，在物流中心组织分货、配货，然后把分配完毕的物品以合适的数量在规定的时间内，以现代化的运送形式，运送到客户手中，以实现资源的优化配置。其中，按照国家质量技术监督局发布的中华人民共和国国家标准“物流术语”（GB/T 183542001），配送是指在经济合理区域范围内根据用户要求，对物品进行拣选、加工、包装、分割、组配等作业，并按时送达指定地点的物流活动14。物流配送可以被抽象的理解为一种共同化的服务模式，可涵盖以下几个方面：各类资源共同使用；设施共同采用；管理过程的共同进行15。具体来说，物流配送是物流活动的一种独特的业务形态，其独特之处在于它不是单独存在的，而是与资金流、物流、信息流进行了有机结合，这些资源的流动均存在于物流配送的整个过程中，可以毫不夸张的说，物流配送可以包含物流活动的必要因素。从表面上看，配送是从运输衍生而来的功能，实际上，物流配送基本能够涵盖物流的所有职能，是一个完整的过程。2.1.2 物流配送的功能1、配送完善和优化了物流系统。第二次世界大战后，高水平的干线运输呼唤支线运输和小搬运配套，但支线运输和小搬运在适应性、灵活性、服务性上的欠缺，致使运力不合理、运输成本过高，配送的出现使干线运输、支线运输及小搬运统一，输送过程得以优化和完善16。2、配送提高了末端物流的效益。配送通过大批量进货，集中发货，以及将多个小批量集中一起大批量发货，都能有效的节省运力，实现经济运输，降低成本，使末端的物流经济效益得到提高17。3、配送通过集中库存使企业实现低库存或零库存。采取准时制配送方式之后，生产企业可以依靠配送中心的准时配送而不需保持自己的库存或保持少量安全库存而不必留有经常库存18。4、配送简化事物，方便客服。采用配送的方式，客户只需向一处订购，或一个进货单位联系就可以订购到以往需要去许多地方才能顶到的货物，因此大大的减轻了客户的负担，并节省开支19。5、配送可以降低整个社会物资的库存水平。发展配送，实行集中库存，整个社会物资的库存总量必然低于各企业分散的库存总量，并有利于灵活高度，有利于发挥物资的作用20。2.1.3 物流配送的要素1、备货。该环节是配送工作的最基础环节，主要包括以下几项任务：寻货源；购货物；货物统计汇总；日常质量检验；会计核算；日常交接工作等。物流企业应该定期对客户需求进行预测，并进行定量的货物储备，以备不时之需。备货环节是配送的起始环节，在一定程度上影响了整个配送的成败，因此，在这个环节，应该努力降低成本，提高配送效益。2、存储。可以分为储备与暂存这两种主要形态。储备的含义是根据某一时期制定的配送经营目标及要求，建立起的资源保障以保障配送目标得以实现, 暂存的含义是在配送当天，依照分拣配货的具体要求，在理货场所进行的少量应急准备12。但一般情况下，该种情况下的储备数量很大，并且结构也相对较为完善，根据货源多少及到货量，有计划的制定储备方案。3、分拣与配货。这一点是物流配送区别于其他物流形式的功能要素，它也是一项特别重要的支持性工作，在一定程度上决定了物流配送的成败13。它是提升送货质量和档次的必然要求，也是企业提高自身服务水平的重要方式。4、配装。在电子商务环境下，客户订单一般较小，也较为频繁，这样就存在货物的装配问题，如何能够集合不同类型的货物，最大程度的提高货车运力，是需要考虑的重要问题。5、运输。电子商务环境下的终端运输一般属于短途、较小规模的运输，相比于干线运输，物流配送的运输面临着路径选择的问题。在顾客分布分散、数量较多的情况下，如何能够将装配和线路进行有效的搭配，是一个难度很大的工作。6、送达服务。在货物送到顾客面前以后，应该做好交接工作，完成相关手续的办理及业务结算，并且按照顾客的要求进行卸货。7、配送加工。配送加工能够提升顾客的满意度，与普通流通加工有所不同，配送加工主要是为了满足客户的基本需求。2.2 配送路径优化问题物流路径优化问题通常可以这样描述：由多辆车将货物从一个或多个配送中心送到多个地理位置上分散的客户，在满足一定的约束条件（货物的需求量、发送量、交货时间、车辆负载量限制、行驶路程限制、时间限制等）下，如何安排车辆及其行驶路线使得总的配送费用最小21。这是物流配送的一个核心问题。2.2.1 配送路径优化的目标确定配送路线可以采取各种数学方法和在数学方法基础上发展和演变出来的经验方法。无论采取何种优化方法,我们首先都要明确物流配送路径的优化目标,才能有效地针对目标进行优化。目标的选择根据配送的具体要求、配送中心的水平、实力及客观条件而定,可以有以下多种选择：1、效益最高：在选择以效益为目标时,通常以企业当前的效益为主要考虑因素,同时兼顾长远的效益，效益是企业整体经营活动的综合体现,可以用利润来表示,故在计算时是以利润数值最大化为目标值，但由于效益是综合的反映,在拟定数学模型时,很难与配送路线之间建立函数关系,所以一般很少采用这一目标22。2、成本最低：计算成本比较困难,但和以效益为目标相比有所简化,在成本和配送路线之间有密切关系、且成本对最终效益起决定作用的情况下,采用以成本最低为目标实际上等于选择了以效益为目标,比较实用可行23。3、 路程最短：如果成本和路程相关性较强,而和其他因素是微相关时,则可以选择路程最短为目标,这样可以避免许多不易计算的影响因素,大大简化算，但需要注意的是,有时候路程最短并不意味着成本最低,如果道路条件、道路收费影响了成本,单以最短路程为最优解则不合适了。4、吨公里最小：是长途运输中常作为选择目标,在多个发货站、多个收费站、整车发到的情况下,选择吨公里最低为目标可以取得满意结果，在配送路线选择中,以吨公里最小为目标在一般情况下并不适用,但在采取共同配送方式时,也可以作为目标24。5、准时性最高：准时性是配送中重要的服务指标,以准时性为目标确定配送路线就是要将各客户的时间要求和到达各客户点的先后顺序进行协调安排,这样有时难以顾及成本问题,甚至需要牺牲成本来满足准时性要求。但对准时性的要求必须建立在控制成本的基础上。6、运力利用最合理：在运力非常紧张、运力与成本或效益有一定相关的情况下,为了节约运力、充分运用现有运力,而不需外租或新购车辆,也可以运力安排为目标,确定配送路线。针对不同的物流配送问题,要根据具体情况选择优化目标。本文研究的物流配送问题根据帝峰模具公司物流系统的特点,将优化目标设定为路程短、准时性高、运力利用合理。2.2.2 配送路径优化问题的分类物流路径优化问题按照各种因素的不同形成了不同的种类，如表2-125。表2-1 不同分类依据下的路径优化问题类型分类依据_x0007_类型_x0007_问题描述_x0007_x0007_任务特征_x0007_单向物流_x0007_车辆仅取货或送货问题_x0007_x0007_x0007_双向物流_x0007_带同时取货送货的问题_x0007_x0007_配送中心数目_x0007_单配送中心_x0007_仅一个配送中心服务客户_x0007_x0007_x0007_多配送中心_x0007_有多个配送中心服务客户_x0007_x0007_车辆载货状况_x0007_满载问题_x0007_货物量不小于车容量_x0007_x0007_x0007_非满载问题_x0007_货物小于车容量_x0007_x0007_车辆类型_x0007_单车型_x0007_所有车辆类型和最大载货量相同_x0007_x0007_x0007_多车型_x0007_车辆的类型和最大载货量不同_x0007_x0007_车辆行程约束_x0007_有行程约束_x0007_所有车辆不能超过最大行程_x0007_x0007_x0007_无行程约束_x0007_所有车辆没有最大行程限制_x0007_x0007_按时间分_x0007_带时间窗约束_x0007_在规定时间段内送达_x0007_x0007_x0007_无时间窗约束_x0007_无时间限制_x0007_x0007_优化目标分类_x0007_单优化目标_x0007_按单一目标进行最优化_x0007_x0007_x0007_多优化目标_x0007_按多目标进行最优化_x0007_x0007_2.2.3 配送路径优化问题的解法分类针对早期与现今的车辆路径问题模型，已有相当多的文献提出求解方法，可分为以下五大类26：1、系统仿真法(Simulation )此方法主要应用于行车线路与物流配送中心区位的选择。优点在于可直接观察系统安排的效率与效果，但由于问题的实际情况多变且具有不确定性，很难将要实现的配送情形系统逻辑化为仿真程序；2、人机互动法人机互动法是一种结合使用者的直觉、经验、以及专业能力，纳入求解过程的一种方法，这种方法可以让决策者在电脑上产生途径的中间阶段。此方法结合人类决策与计算机计算能力，在求解的过程中，通过高度的人机交互模式，结合专家的决策信息计算出结果。该方法的优点是寻优的过程中，决策者可以很清楚地看到各约束条件之间的替代关系以及参数变化可能导致的成本变化；3、精确解法(Exact Procedures )精确解法一般应用于线性规划和非线性规划等数学规划技术，以便求得问题的最优解。在 VRP 问题研究的早期，主要是单源点(One-Point)(即配送中心、车场等)派车，研究如何用最短路线(或最短时间内)对一定数量的需求点(即用户)进行车辆调度，因此主要运用精确算法求出问题的最优解。精确式算法一般有以下几种方法：分枝定界法(Branch and Bound Approach )、割平面法(Cutting Planes Approach )、网络流算法(Network Flow Approach)和动态规划方法(DynamicProgramming Approach)等；4、启发式算法(Heuristics )由于上述三种方法的求解效率较差，所以大部分的学者都致力于启发式解法的发展。该方法在解题时可减少搜寻的次数，所以是一种容易且快速求解困难问题的算法。车辆路径问题的启发式解法，包括节约法(Saving method)、最邻近法(Nearest neighbor )、插入法(Insertion )及扫描法(Sweeping )等；5、智能算法（现代启发式算法）进入20世纪80年代，一些新颖的优化算法，如人工神经网络算法、遗传算法、模拟退火算法、禁忌算法、混沌等，通过模拟或揭示自然现象或过程得到发展，其思想涉及数学、物理、生物进化、人工智能等各方面，为解决复杂问题提供了新的思路和手段。在优化领域，由于这些算法构造的直观性与自然机理，因而被称为智能优化算法(intelligentoptimization algorithms)或现代启发式算法（meta-heuristic algorithms)15就目前的情况来看，智能算法应用于VRP的研究还不深入，一般都只考虑比较简单的约束(容量约束、时间窗约束)，与实际应用还有相当大的距离。但是，用智能优化算法解决VRP问题已经得到了人们的重视，相当多的学者致力于这方面的研究，发展势头很强劲，是进行VRP研究的一个热点方向。相对于传统启发式算法, 现代启发式算法不要求在每次迭代中均沿目标值下降方向, 而允许在算法中适当接受目标值有所上升甚至不可行的解, 其目的是能够跳出局部搜索邻域。2.3 本文配送路径优化方法在配送路径优化问题的诸多解法当中，本文选择启发式算法当中的三种最常被运用到的方法进行方案的优化。2.3.1建立VRP模型多回路运输问题（ VRP）是现实中十分普遍的一种调配问题，其问题是如何对车辆进行调度。因此，VRP（Vehicle Routing Problem）模型应运而生，并成为解决多回路问题的一个相当成功的模型。该问题研究目标是：对一系列顾客需求点设计适当的路线，使车辆有序地通过他们，在满足一定的约束条件下（如货物需求量、发送量、车辆容量限制，行驶里程限制等），达到一定的优化目标（如里程最短，费用最小，时间尽量少等）。一个典型的VRP模型可以如下表述：（1）基本条件：现有m辆相同的车辆停在一个共同的源点v0，它需给n个客户提供货物，顾客为v1、v2，vn ，两点之间路线为cij27。（2）模型目标：确定所需的车辆数N，并指派这些车辆到一个回路中，同时包括回路内的路径安排和调度，使总费用最小。（3）限制条件：N不大于m；每一个订单都要完成；每辆车完成任务后都要回到源点v0；车辆的容量不能超过一定限制值；配送路线上所有配送点的配送需求量总和不能大于配送车辆的最大载重量；从配送中心出发到配送结束并返回配送中心的路程不能大于配送车辆的最大行驶距离；每条配送路线必须由一辆配送车辆配送，且要满足路线上所有需求点的要求，特殊问题还需考虑时窗限制、运输规章限制28。2.3.2最近插入法最近插入法是一种解决旅行商问题的启发式算法,其结合最邻近法与节省法的观念，依序将顾客点插入路径中以构建配送路线,该方法首先以起点最近的 HYPERLINK /wiki/%E9%9C%80%E6%B1%82 o 需求 需求点作为路线的种子点，再根据最邻近点插入法的概念，以插入值最小者作为下一个插入点，最后再用一般化节省值公式，以其中节省值最大者决定插入的位置，重复进行选取与插入的步骤，为了使物流配送的时间最少、距离最短、费用最低，并使合并后的总运输距离节约的里程最大，直到达到一辆车的装载限制时，再进行下一条路线的优化29。最近插入法由四步完成30：1、找到c0i最小的节点vi，形成一个子回路，T=v0，vk，v0；2、在剩下的节点中，寻找一个离子回路中某一节点最近的节点vk，若此时回路的总货运量未超过车的载重限制，则继续步骤（3），否则，转（1）寻找新的一条回路；3、路径优化过程对每条路径进行局部搜索，调整路径内或路径间节点访问顺序，改善路径的质量，在子回路中找到一条弧（i，j）,使得cik+ckj-cij最小，然后将节点vi插入到节点vi，vj之间，用两条新的弧(i，k)，（k，j）代替原来的弧（i，j），并将节点vk加入到子回路中。若此时该回路的总路程为未超过车辆的行程限制，则继续步骤（4），否则转步骤（1），寻找新的一条回路；4、重复步骤（2）和（3），直到每一个节点都被归入某一个子回路中。2.3.3 扫描法扫描法是用于求解车辆数目不限制的VRP问题的算法，它采用“先分组后路线”的过程，所谓分组就是派给每辆车一组客户点。一种简单的分组方法是将以配送中心为原点的坐标平面划分为多个扇形区域，并初步将每个扇形区域的点分派给一辆车，然后扩充路线，如果在进行了一次“分组-路线”的路线构造后，还存在未分配点，则再进行“分组-路线”程序，如此反复，直到所有的点均已分配为止19。扫描算法的主要步骤：1、以起点0点作为极坐标系的原点，并一连通图中的任意一顾客点和原点的连线定义为角度零，建立极坐标系；然后对所有的顾客所在的位置，进行极坐标变换；2、从最小角度的顾客开始建立一个组，按逆时针方向，将顾客逐个加入到组中，直到顾客的需求总量超出了负载的限制。然后继续建立一个新的组，继续按逆时针方向，将客户加入组中20；3、重复2中的过程，直到所有客户都被分类为止；4、对各个组内的单回路进行路径优化。2.3.4节约算法节约算法是目前用来解决运输车辆数目不确定的VRP模型的最有名的启发式算法，其思想在于按节约值(较短路径与原路径之差)由大至小排序，在车辆容量限制下，依序将对应的两客户点排入路径中，直至所有客户都被排入路径为止。关键在于当节约值较大的两顾客点被排入路径时，除需考虑车辆容量限制方面采用“量力而为”的策略外，更需要考虑到时间的限制，此方法的优点是提高车辆的利用率20。节约算法的核心思想是将运输问题中存在的两个回路（0， ，i，0）和（0，j， ，0）合并成一个回路（0， ，i，j，0），在上面的合并操作中，整个运输问题的总运输距离会发生变化，如果变化后总运输距离下降，则称节约了运输距离21。其中cio代表从顾客 i 至起点的距离，coj代表从起点至顾客j的距离，cji则代表从顾客 j 至顾客 i 的距离，相应的变化值叫做节约距离Cij 。计算两结点 i 与 j 间的节约值 QUOTE * MERGEFORMAT Cij 时，应先计算原路径中各往返路径的总和，再与较短路的总路径和相比较。两结点间的节约值的计算公式与意义如式（1）所示。 （1）两结点的原路径与较短路的调整过程如图2-1所示。 调整前 调整后图2-1 节约算法的图像描述节约里程算法主要步骤：1、设需求点集NR=1,2, n,各点需求量Ri,各点间最短距离cij；2、确定各车辆配送点集I1，I2，,Im令Ij=j, j=1,2,n (先采取单点配送)；3、计算所有点对的节约度Cij ，然后对计算结果进行升序排列。4、从升序排列的节约度序列中的最上面的值开始，直到节约里程Cij的队列空为止,重复下列步骤:按照节约里程Cij队列从大到小的顺序,分析客户i和j之间合并的可能性(是否满足装载限制条件、不在同一路径内以及合并次数不超过2),将i, j连接起来,即可令Ii=IiIj;Ij=，如果不是这样,则从节约里程队列中去除当前的节约里程，分析下一个客户对22。 第3章 帝峰模具公司物流配送路径现状分析 3.1 公司简介武汉帝峰模具有限公司成立于2012年，位于武汉市江夏开发区大桥新区107国道旁。它是以五金模具与塑胶模具的研发与制造、提供销售配送服务为一体的实体企业。公司拥有专业技术人才二十余名和各种机械加工设备，下设设计部门，生产部门，营销部门，物流部门等职能部门，各部门通力协作，为社会奉献优质高效的各类模具，为客户提供专业专心的技术支持和服务，武汉帝峰模具有限公司自成立以来，坚持“以诚为本，以信为根”，“用科技创造绿色生活”的经营理念，立志成为模具新技术的领航者的企业愿景，扎实走科技与生产相结合的产业化道路，专业生产各种模具产品。目前公司产品涵盖湖北省各市县并以优厚的实力、合理的价格、优良的服务与多家企业建立了合作关系。3.2 公司物流配送路径现状公司的客户主要位于其所在地的周边县市，共有9个县市，如孝感市、天门市、荆州市等，编号如表3-1，地区分布如图3-1所示,但需求较小，公司为推广产品，采用每月专车送货上门服务。公司现拥有4辆40吨的货车，若车辆使用欠缺时，可租赁车辆。表3-1 客户所在城市编号客户编号_x0007_1_x0007_2_x0007_3_x0007_4_x0007_5_x0007_6_x0007_7_x0007_8_x0007_9_x0007_x0007_所在城市_x0007_孝感市_x0007_天门市_x0007_荆州市_x0007_石首市_x0007_仙桃市_x0007_咸宁市_x0007_黄石市_x0007_黄冈市_x0007_麻城市_x0007_x0007_已知武汉帝峰模具有限公司位置为0点，分别向周围编号为1、2、3、4、5、6、7、8、9共9个小客户点配送本期新型五金模具，其拥有2辆40吨的车40吨卡车最大载量为12套模具。各点需求量为Ri，每辆车的行驶里程为Li，Li700公里，客户点1，2，9。各县市每月需求模具的基本数据如图3-2所示。图3-1 帝峰模具公司配送地区基础图图3-2 各客户点的需求量图3-3 各客户点的配送距离目前，对小客户公司采用的配送线路如图3-2所示。图3-2 公司现有配送路线各配送线路的里程，所需司机数量的基本情况如表3-2所示。表3-2 配送信息表路线_x0007_运距_x0007_运货量_x0007_车型_x0007_司机_x0007_工资_x0007_x0007_0-1-2-0_x0007_293.9km_x0007_9套_x0007_40吨货车_x0007_1_x0007_500_x0007_x0007_0-3-4-0_x0007_574km_x0007_8套_x0007_40吨货车_x0007_2_x0007_1000_x0007_x0007_0-5-6-0_x0007_337.6km_x0007_6套_x0007_40吨货车_x0007_1_x0007_500_x0007_x0007_0-7-8-9-0_x0007_344km_x0007_10套_x0007_40吨货车_x0007_1_x0007_500_x0007_x0007_总计_x0007_1549.5km_x0007_33套_x0007_440吨货车_x0007_5_x0007_2500_x0007_x0007_由上表可知，公司每月需40吨货车4车次配送，司机5人次，所需工资2500元，运输总里程为1549.5千米，消耗柴油697.28升，所需燃油费3625.86元，一共花费6125.86元。3.3 公司物流配送路径存在的问题分析虽然公司对物流部门的大力支持，物流部门快速发展，物流部门的交通设施改善很多，物流配送成本也降低了很多，但相比于同行业其他企业，公司目前配送线路的弊端在于：配送路线的回路过多，存在对流运输的现象，经验化操作过多，优化不彻底，导致总运距过长，消耗作业时间偏多，不能充分利用车辆配载容积，浪费较多人力和物力资源，物流成本的花费还是很高，影响公司盈利22。3.3.1 回路总数过多在公司现有路径的图中，9个客户点设置4条回路，平均每条回路有2.25个客户点；9个客户点总需求量为33套模具，平均每个客户点需求量约3.67套；由于每条回路中有一辆配送车辆，故每辆车平均装载约8.26套模具。而公司的40吨货车可装载12套模具，所以平均每辆车利用率为68.9，计算结果偏低，导致车辆非满载运输，运力利用不充分，造成车辆，人力，资金上的浪费。对于此种情况来说，关键因素在于路径回路总个数，所以最有效的方法是通过减少总会路个数，充分利用车辆配载容积，提高车辆利用率，进而节约车辆与人力上的成本。3.3.2对流运输对流运输亦称相向运输、交错运输，是指同一种货物，或彼此间可以互相代用而又不影响管理、技术及效益的货物，在同一线路上或平行线路上作相对方向的运送，而与对方运程的全部或一部分发生重迭交错的运输称对流运输，已经制定了合理流向图的产品，一般必须按合理流向的方向运输，如果与合理流向图指定的方向相反，也属对流运输11。如图3-5中，从4号地区回到起点的路线与从起点到5号地区的路线（图中用圆圈画出）虽然不是一条回路中的配送路径，但是它在平行线路上作相对方向的运送，属于对流运输的情况，同样情况的还有20与05（图中用斜线画出），20与03（图中用菱形画出）两对路线，这种现象会导致人力、物力等资源的浪费。图3-3 现有路径中的对流运输现象3.3.3经验化操作经调查，由于企业建立时招聘的人员大多具有多年物流经验，不免会根据以往的工作经验进行工作，其设计的运输配送路径经验化操作过多，从而导致企业增加目标地区之后，他们不会积极地重新去计算和安排配送的运输路径，而是凭以往经验操作此过程。如图3-6中，客户点3和客户点4是最近与公司合作的客户，距离公司胶原且两点相离较近，物流部门便仅把两点归于一条回路当中，并没有将九个客户点放在一起重新计算作合理安排。图3-4 经验化操作下的一条回路第4章 帝峰模具公司物流配送路径优化策略4.1 建立VRP模型优化配送路径对帝峰模具有限公司的配送系统建立VRP模型。基本条件：帝峰模具有限公司需给9个客户送货，客户依次为1，2，,9，现有3辆40吨的货车（每百公里油耗45L），司机每天工资500元，柴油每升5.20元。模型目标：确定所需要的车辆的数目N、车辆类型、司机数量以及各车行走的路径，并指派这些车辆到一个回路中，同时包括回路内的路径安排和调度，使得运输总费用最小。限制条件：（1）全程的总时间不超过驾驶员每天最大工作时，以避免疲劳驾驶23，所以基于人性化与安全的考虑，当运输里程超过350公里时，需配备两名司机，为防止突发运输事件，车辆必须当天回到公司，减去由于装卸货等影响因素，各车最大运输距离为650公里。（2）每辆货车走过一个回路之后都要回到起点0处。（3）不能超过车辆的容量限制。40吨的货车最多可装12套模具。4.2 公司物流配送路径的优化4.3.1运用最近插入法优化1、第一条路径：令T=0,N=0，1，2,9，比较表4-1中从0出发的所有路径大小。因为minc0iiN，1i9=c01=61.4km，所以就有顾客点0，1构成一个子回路，T1=0，1，0，此时r1=5,L1=122.8km。然后在剩余客户点（2，3，4，5，6，7，8，9）中寻找到0和1中某一点的最小距离，minc0i，c1iiN，1i9且i1=c08=77km，r8=2，因为r1=r1+r8=712，所以在子回路T1=0，1，0插入点8。由于对称性，无论将8插入到0和1之间往返路径中，结果都是一样的，这样，构成了一个新的子回路T1=0