物流配送路径优化策略物流配送路径存在的问题路径分析物流配送路径现状分析配送路径优化问题的分类

1、高效率合理的配送是物流系统顺利运行的保证,配送线路安排的合理与否对配送速度、本钱、效益影响很大.所以正确合理地安排车辆的配送线路,实现合理的线路运输可以使企业到达科学化的物流治理,这也是企业提升自身竞争力的有效途径之一.本文以帝峰模具的配送方案为例,对其配送现状中存在的问题进行分析,并运用节约算法、扫描算法以及改良后的最近插入法对配送线路进行优化,提出物流配送线路优化的方案,并且得到了相对满意的结果.优化后的配送线路有效提升了帝峰模具的作业效率,降低物流本钱,从而提升企业的经济效益,并让公司能够在剧烈的竞争市场立足,同时,也可以给同类企业提供参考.关键词:帝峰模具配送路径优化最近插入法扫描法节

2、约算法AbstractReasonableandefficientdistributionistheinsuranceofasmoothrunninglogisticssystem,distributionlinearrangementisreasonableornothasagreatinfluenceonthespeedofdelivery,costsandbenefits.Therefore,toarrangeareasonableandcorrectdeliverylineforvehicleandachieveareasonabletransportlinecanenableente

3、rprisestoachievescientificlogisticsmanagement,whichisoneoftheeffectivewayforanenterprisetoimproveitscompetitiveness.ThispapertakeDifengMoldCo,Ltd.distributionasanexampletoanalysisoftheproblemsexistinginthestatusofitsdistribution,throughthesavingalgorithm,theimprovedinsertmethodandscanningmethodofthe

4、sethreemethodsareoptimizedfordistributionlines,logisticsdistributionrouteoptimizationschemeisputforward,andarelativelysatisfactoryresultsareobtained.Optimizeddistributionlineseffectivelyimprovethegravelslogisticscompany'sefficiency,reducelogisticscosts,therebyimproveenterpriseeconomicbenefits,an

5、dgravelscaninthefiercemarketcompetition,atthesametime,alsocanprovideareferenceforsimilarenterprises.KeywordsDifengMoldCo,LtdDistributionrouteoptimizationscanningmethodtheimprovedinsertmethodthesavingalgorithm目录TOCo"1-3"hzu第1章绪论1.1 研究背景61.2 国内外研究现状71.2.1 国外研究现状71.2.2 国内研究现状91.3 研究目的、意义和方法11

6、1.3.1 研究目的111.3.2 研究意义111.3.3 研究方法121.4 本文研究内容12第2章相关理论概述2.1 物流配送142.1.1 物流配送的概念142.1.2 物流配送的功能142.1.3 物流配送的要素152.2 配送路径优化问题162.2.1 配送路径优化的目标162.2.2 配送路径优化问题的分类182.2.3 配送路径优化问题的解法分类192.3 本文配送路径优化方法202.3.1 建立VRP模型202.3.2 最近插入法212.3.3 扫描法222.3.4 节约算法23节约里程算法主要步骤：24第3章帝峰模具公司物流配送路径现状分析3.1 公司简介253.2 公司物流

7、配送路径现状253.3 公司物流配送路径存在的问题路径分析283.3.1 路径迂回283.3.2 对流运输293.3.3 经验化操作过多30第4章帝峰模具公司物流配送路径优化策略4.1 建立VRP模型优化配送路径314.2 公司物流配送路径的优化314.3.1运用最近插入法优化314.3.2运用扫描法法优化354.2.3运用节约算法优化394.4三种优化方案比拟分析44结论致谢参考文献第1章绪论1.1 研究背景物流是为了满足消费者需要而进行的从供给地到接收地的原材料、中间产品、最终产品及相关信息的有效流动和储存方案、实施和限制的治理过程.其功能是通过运输、仓储、装卸搬运、包装、流通加工、配送、

8、信息处理等活动过程有机结合起来实现的.其中配送对于物流的运行和开展有着深刻的社会根源和历史背景.在市场经济体系中,物流配送犹如人体的血管,把国民经济各个局部紧密地联系在一起.物流配送是物流的根本功能,作为直接面向最终客户提供的物流效劳,在满足现代化的物流需求方面发挥着极其重要的作用.如果没有配送就会影响物流的经济效益和社会效益,可以说物流成果主要是通过配送来实现的.著名治理大师彼得德鲁克说“美国人花费的每美元中,大概有美分是花在产品制成以后的活动上,即在产品己经完工的以后从经济学角度看,配送是将事物的物质特性转换成经济价值的过程,它为产品带来了客户.由可见配送活动及配送治理的重要性.物流配送一

9、般处于物流末,是直接面向用户提供效劳的环节,它具有提升物流经济效益,优化、完善物流系统,改善物流效劳,降低物流本钱等功能,在物流系统中占有重要的地位.随着市场经济的繁荣,企业业务规模日益扩大,物流配送作为现在现代企业一个重要环节,其效率上下直接影响企业的效劳质量、配送本钱,而配送路径优是物流配送的核心问题,因此物流配送路径优化问题是成为当前物流研究中的一个重要课题,所以它是一项特殊的、综合性的物流运动,其主要包括集货作业、配货作业、车载货物的配装、配送线路确实定1配送实际上是一个局部物流,是大物流在小范围内的运作,配送是物流系统的终端.是否具备及时的配送时间影响效劳水平的上下,这需要对车辆配送

10、路径的合理优化和配送时间的掌控.现代物流己成为世界经济开展的研究重点,我国政府也对物流产业的开展和监管非常重视.但是目前,由于我国的物流产业起步晚,尚存在着许多问题.如何改变这种局面,使物流行业健康稳步开展,是国民生产力开展急需解决的难题,当前主要可从提升物流配送效劳质量入手.在现代物流系统中,配送是一个重要环节,而在配送业务中,能否将货物及时送交收货人手中是物流系统优化的关,配送的质量好坏决定效劳水平的上下,同时影响到客户对整个物流效劳的满意程度.然而物流车辆在配送过程中,会涉及到车辆路径优化问题.由此说明,物流车辆路径优化问题是物流运作治理面临的重点问题,在交通和物流规划中具有举足轻重的地

11、位.武汉帝峰模具是一家集设计、生产、销售、配送于一体的经营五金模具和塑胶模具的有限责任公司.作为一家以生产为主的企业,其在配送运输方面存在一定的缺乏之处,配送工作效率较低,配送本钱较高.从车辆路径优化方面考虑配送优化,对运输路线进行合理规划,寻找一条符合实际情况的优化路径,这样才能从实际上节省配送费用,缓解交通的压力,使配送工作顺利进行,从而节省配送过程中运输费用消耗,而且使配送效劳水平提升,并提升用户的满意度,以致提升工作效率,减少运营本钱.1.2 国内外研究现状1.2.1 国外研究现状很多国外学者对仓储货位优化的问题进行了研究,比方以下几位：Clarke和Wright(1964)对Dant

12、zig和Ramser提出VRP问题模型的求解算法进行了改良,提出了更为有效的启发式算法Clarke-Wright节约法,后来该算法成功的用于求解车辆路径优化问题2；Miller&Gillet(1974)提出扫描法(SweepMethod),目的在于求解车辆调度问题,并针对当时几个求解相似问题的算法进行比拟,证实该算法所求得的解较优于其它的方法3；wialldr(1989)首先将禁忌搜寻法应用于车辆路线问题上,设计重复的虚拟物流中央,将车辆路线问题转换成旅行商问题(TSP),利用2-opt或3-opt方法求解车辆路线；Dorigo,Maniezzo和Colorni(1991)等意大利人将

13、蚁群算法用于求解旅行商问题,并取得了很好的效果,后来,Dorigo在根本蚁群系统的模型的根底上又提出蚂蚁群系统(AntColonySystem,ACS)模型,该模型改良了蚂蚁系统模型的信息素更新方法和路径选择方式,并使用了一种随机选择和最优选择混合的路径选择方式,而信息素更新采用全局更新和局部更新的方式,提升了算法的全局收敛水平,相比于蚂蚁系统模型的性能有较大的提升,收敛速度明显加快.后来很多学者对根本的蚁群算法进行改良,求解不同的问题模型；Gendreau,HertZandL即orte(1994)使用插入法求解旅行商问题,再用贪婪法(GreedyMethod)进行路线切割,从而产生初始解；K

14、ennedy和Eberhart(1995)等美国博士,提出了粒子群算法,Eberhart博士等人对根本粒子群算法进行了改良,该算法被成功的用于求解物流路径规划问题；Renaud(1995)等意大利博洛尼亚大学的博士对多配送中央的车辆路径规划问题(MultipleDepotVehicleRoutingProblem,MDVRP)进行了研究,MDVRP比一般的VRP问题模型更为复杂,配送车辆的参考点有多个配送中央,每个配送中央都有车辆参与网点的配送任务,这样路径规划问题非常复杂,但多配送中央的车辆路径规划问题是目前物流业迅速开展的一种趋势.美国的G.B.Dantzig在1947年提出线性规划、美国

15、的B.Jackowski等人1985年提出隐式枚举算法、以及美国的J.Culberson在1992年提出了迭代的贪心算法后来都成功的被用来求解小规模数据网点的物流路径规划问题,这是一类精确式算法,在求解小规模网点的物流路径规划问题具有计算速度快、求解精确的特点4;Babraroosglu&Ogzur(1999)利用禁忌搜寻法为土耳其某物流公司构建一套决定货车配送点顺序的方法DETABA,以二种乱数选取节点的方法产生初始解,找到其中最正确的解作为初始解,再以插入法(InsertinoProcdeuer)作为搜寻邻近解的移步方法,最后以2一opt改善方法找到最优解的值；su&che

16、n(1999)成功地将自组织影射网络应用在车辆配送区域及路线规划问题的求解上,其算法的主要概念是利用类神经网络快速运算、自我组织与平行处理的特性,配合M个一维环状网络拓扑来表现车辆路线配送问题；T.Ralphs(2003)等美国利哈伊大学的研究者对CVRP问题模型进行了研究,CVRP是相对VRP问题提出的,表示参与配送任务的每一辆车都有自身的约束条件,如载重量、最大行驶里程等等,在满足这些约束条件的前提下,完成所有网点订单任务的配送,目标是总本钱最少的路径规划问题,后来有很多研究者在CVRP问题模型的根底上提出了带有时间窗约束的CVRP问题模型,本文的研究的物流路径规划问题带有多个时间窗约束5

17、.在这些论文相继发表之后由于该问题无论在理论上还是应用上都具有代表性,它是典型的物流配送优化问题,引起更多学者对许多相关学科的研究,导致该问题变成运筹学研究的焦点.1.2.2国内研究现状通过查阅相关文献资料了解到目前国内学者在企业的物流路径优化问题的研究起步较晚,有些学者在研究这方面课题时也提出过一些有建设性的思路6:杨宝石2021把城市快递配送路径问题看作是简单的旅行商问题TravelSalesmanProblem,TSP,针对该问题模型除了考虑了一般性的约束之外,仅仅只额外考虑了容量约束.当问题规模不大时,可以得到全局最优解.丁洁2021那么将城市快递配送路径问题转化为多重旅行商问题Mul

18、tiTravelSalesmanProblem,MTSP,同时考虑到MTSP问题求解难度较大,故先将其转化为TSP问题,接着结合最小生成树的深度优先搜索算法来确定快递员最终的行车路线,以求得到该问题的近似最优解；何俊生2021针对同城快递配送路径问题,提出了两个模型,一个不考虑时间窗约束仅考虑容量约束,另一个同时考虑,采用Dijkstra遗传优化算法求解并进行了比拟比照分析.姜艳和关雪2021提出了一个线性混合整数规划模型,该模型主要考虑时间窗约束和单车快件数目上限约束；杨从平2021针对快递物流配送车辆路径问题,考虑了容量约束和单车最大行程距离约束,采用蚁群算法对桂林市某快递网络的配送路径进

19、行了优化.李炳会2021那么用超时惩罚对时间约束进行了替代,即快递超过预定时间需要赔偿以进行惩罚；张迅和刘海东2021根据快递配送的特点,研究了采用快件递送和揽收同时效劳的配送策略的车辆路径问题.他们假设车辆在配送中央与客户点之间或客户点之间行驶的时间服从正态分布,各客户点均带有有软时间窗约束,以及快件揽收数量服从泊松分布,依此建立一个线性混合整数规划的多目标模型,目标函数包括：行驶路程最短,时间惩罚值最小和快件揽收数量最大.同时他们提出了一种遗传算法：该遗传算法采取种群个体适应度值排序和最正确个体保存的选择策略,以及通过参数限制自适应交叉概率来保证所求结果的优良性,通过设计算例并采用Matl

20、ab软件进行编程运算,实验结果证实了该遗传算法的可行性；陈敏2021研究了如何快速响应动态信息的车辆调度问题,并将其描述成是一个实时带时间窗车辆路径问题Real-timeVehicleRoutingProblemwithTimeWindows,RT-VRPTW.针对实际调度问题的规模、复杂度和特性,将动态问题转化成静态问题,提出了一种混合禁忌搜索算法,该算法分为两个阶段：第一阶段,首先采用插入法生成初始方案；第二阶段,引入改良的禁忌启发式搜索算法对全局进行优化,实验结果说明该算法行之有效；胡明伟和唐浩2021那么研究了快递效劳相关的动态车辆路径问题,并将其描述成带时间窗的动态旅行修理员问题Dy

21、namicTravelingRepairmanProblemwithTimeWindows,DTRPTW),建立多目标优化模型,该模型包括效劳客户数量最大、客户等待时间最小以及总运行时间最短三重优化目标.他们采用基于词典式的排序方法,同时改良了Or-opt局部搜索算法.根据仿真实验结果显示,与单目标模型相比,多目标优化模型能够明显降低被拒绝效劳的客户数量和客户等待时间,同时总运营时间未发生明显增长；吴海东(2021)针对城市快递效劳问题,重点研究了效劳质量相似性和快递车辆交接行为这两大新的快递效劳趋势,同时建立两阶段模型,在满足随机客户需求的条件下,还能够保证快递配送的路径得到最优.目前国内对

22、VRP问题的研究很多都停留在理论研究阶段,实验成果并没用广泛的进行实际应用,而且研究的问题模型都有一定的条件约束,约束条件不同,那么对应的问题模型也不一样,求解的算法也不太一样,这样算法就有一定的局限性.1.3研究目的、意义和方法1.3.1 研究目的为了提升物流配送系统的效劳质量和节省配送费用,对物流车辆配送路径的优化和行程时间的预测所进行的研究,本文通过制定较为合理化、人性化的物流车辆配送路径,满足实际的物流配送要求,从而能将货物迅速、平安地送到客户手中,到达提升效劳水平的要求；与此同时,加快物流系统对客户需求的物流配送路径优化和行程时间预测响应速度,提升效劳质量,增强客户对物流环节的满意度

23、,降低效劳商的运作本钱使整体的效劳水平提升7.1.3.2 研究意义第一,本文结合实际的配送情况,对配送车辆路径优化理论与方法进行系统研究是物流集约化开展、建立现代调度指挥系统、开展智能交通运输系统和开展电子商务的根底.同时,优化后的物流配送路径,有利于缓解交通压力；第二,规划好物流配送的行进路线,有利于节省配送费用,而对行程时问精确的预测反过来有利于指导物流规划的行进路线,引导车辆沿途配送物资；第三,物流配送路径优化,是物流配送优化中关键的一环.对货运车辆进行路径优化,可以提升物流经济效益、社会效益、实现物流科学化8;第四,优化配送路径问题对提升物流企业配送效率,降低物流配送本钱,促进经济的快

24、速开展都具有重要的作用,从而对物流配送路径规划的研究具有非常高的应用价值.1.3.3 研究方法(1)文献参考：本文主要是通过对互联网上的相关文献、资料以及图书进行详细的阅读和思考,并参考其中相关有用的文字以及解决问题的思路及方法.(2)实地考察：在武汉帝峰模具实习期间,将搜集的资料进行大致的提炼,对于物流配送路径的各项考虑因素进行主次分类,并带着这些疑问在公司实习之余对配送路径方案进行大致的理解与总结.(3)定量分析法：依据近三个月物流单据结合运筹学相关知识,运用节约算法、扫描法和改良的最近插入法进行必要的分析与运算,并比拟三种方法的结果以得到较优路径的设计方案.1.4本文研究内容本文以武汉帝

25、峰模具为例,在对物流配送业务进行研究的根底上,针对物流配送中对本钱影响较大的车辆路径问题(VRP)进行集中研究,在车辆载重限制、时间限制、客户需求量限制和指定地点的条件下建立了VRP数学模型,并利用启发式算法中的三种方法优化配送路径,并选出较优方案9.本文的研究内容如下：第一章阐述本文的研究背景,国内外研究现状,研究意义、目的和方法；第二章对物流配送和配送路径优化问题进行了相关理论的概述,并介绍了节约算法、扫描法和最近插入法的原理及步骤；第三章主要介绍了本人实习所在公司,描述了其在物流配送路径方面的现状以及存在的问题；第四章是本文的重点局部,首先介绍了关于改良公司配送路径的根本思路,其次运用节

26、约算法、扫描法以及改良的最近插入法优化配送路径,然后比拟三者得出的结论并选出较优方案.PAGE45第2章相关理论概述2.1 物流配送2.1.1 物流配送的概念物流的含义是：依照客户的订单要求,在物流中央组织分货、配货,然后把分配完毕的物品以适宜的数量在规定的时间内,以现代化的运送形式,运送到客户手中,以实现资源的优化配置.配送(distribution)起源于“送货上门.20世纪60年代初期,生产企业或中转仓库根据客户的需求,将货物准确的运送到客户手中,形成了配送的雏形一一“普通送货.随着客户对产品多样化和差异化的要求,为了满足客户的需求,原始的普通送货开始转向分拣、配货、送货一体化.因此产生

27、了配送.根据国家质量技术监督局发布的中华人民共和国国家标准“物流术语(GB/T18354-2001),配送是指在经济合理区域范围内根据用户要求,对物品进行拣选、加工、包装、分割、组配等作业,并按时送达指定地点的物流活动.我们可以将物流配送抽象的理解为一种共同化的效劳模式,共同化可涵盖以下几个方面：各类资源共同使用；设施共同采用；治理过程的共同进行.具体来说,物流配送是物流活动的一种独特的业务形态,其独特之处在于它不是单独存在的,而是与资金流、物流、信息流进行了有机结合,这些资源的流动均存在于物流配送的整个过程中,可以毫不夸张的说,物流配送可以包含物流活动的必要因素.从外表上看,配送是从运输衍生

28、而来的功能,实际上,物流配送根本能够涵盖物流的所有职能,是一个完整的过程.物流配送在很大程度上容易被外部环境所影响,随机性很强,因此,需要建立起完整的治理与限制,并需要强有力的理论与技术支持.2.1.2 物流配送的功能(1)配送完善和优化了物流系统.第二次世界大战后,高水平的干线运输呼唤支线运输和小搬运配套,但支线运输和小搬运在适应性、灵活性、效劳性上的欠缺,致使运力不合理、运输本钱过高,配送的出现使干线运输、支线运输及小搬运统一,输送过程得以优化和完善.(2)配送提升了末端物流的效益.配送通过大批量进货,集中发货,以及将多个小批量集中一起大批量发货,都能有效的节省运力,实现经济运输,降低本钱

29、,使末端的物流经济效益得到提升.(3)配送通过集中库存使企业实现低库存或零库存.采取准时制配送方式之后,生产企业完全可以依靠配送中央的准时配送而不需保持自己的库存或保持少量平安库存而不必留有经常库存.(4)配送简化事物,方便客服.采用配送的方式,客户只需向一处订购,或一个进货单位联系就可以订购到以往需要去许多地方才能顶到的货物,因此大大的减轻了客户的工作量和负担,也节省了事务的开支.(5)配送可以降低整个社会物资的库存水平.开展配送,实行集中库存,整个社会物资的库存总量必然低于各企业分散的库存总量.同时,配送有利于灵活高度,有利于发挥物资的作用.止匕外,集中库存可以发挥规模经济优势,降低库存本

30、钱10.2.1.3物流配送的要素(1)备货.该环节是配送工作的最根底环节,主要包括以下几项任务：寻货源；购货物；货物统计汇总；日常质量检验；会计核算；日常交接工作等.物流企业应该定期对客户需求进行预测,并进行定量的货物储藏,以备不时之需.备货环节是配送的起始环节,在一定程度上影响了整个配送的成败,因此,在这个环节,应该努力降低本钱,提升配送效益.(2)存储.可以分为储藏与暂存这两种主要形态.储藏的含义是根据某一时期制定的配送经营目标及要求,建立起的资源保证以保证配送目标得以实现.一般情况下,该种情况下的储藏数量很大,并且结构也相对较为完善,根据货源多少及到货量,有方案的制定储藏方案.暂存的含义

31、是在配送当天,依照分拣配货的具体要求,在理货场所进行的少量应急准备.(3)分拣与配货.这一点是物流配送区别于其他物流形式的功能要素,另外它也是一项特别重要的支持性工作,在一定程度上决定了物流配送的成败.它是提升送货质量和档次的必然要求,也是企业提升自身效劳水平的重要方式.(4)配装.在电子商务环境下,客户订单一般较小,也较为频繁,这样就存在货物的装配问题,如何能够集合不同类型的货物,最大程度的提升货车运力,是需要考虑的重要问题.(5)运输.电子商务环境下的终端运输一般属于短途、较小规模的运输,相比于干线运输,物流配送的运输面临着路径选择的问题.在顾客分布分散、数量较多的情况下,如何能够将装配和

32、线路进行有效的搭配,是一个难度很大的工作.(6)送达效劳.在货物送到顾客面前以后,应该做好交接工作,完成相关手续的办理及业务结算,并且根据顾客的要求进行卸货.(7)配送加工.配送加工能够提升顾客的满意度,与普通流通加工有所不同,配送加工主要是为了满足客户的根本需求.2.2 配送路径优化问题物流路径优化问题通常可以这样描述：由多辆车将货物从一个或多个配送中央送到多个地理位置上分散的客户,在满足一定的约束条件(货物的需求量、发送量、交货时间、车辆负载量限制、行驶路程限制、时间限制等)下,如何安排车辆及其行驶路线使得总的配送费用最小.这是物流配送的一个核心问题11.2.2.1 配送路径优化的目标配送

33、路径合理与否对配送速度、本钱、效益影响颇大,因此,采用科学的合理的方法确定配送路线是配送活动中非常重要的一项工作.确定配送路线可以采取各种数学方法和在数学方法根底上开展和演变出来的经验方法.无论采取何种优化方法,我们首先都要明确物流配送路径的优化目标,才能有效地针对目标进行优化.目标的选择根据配送的具体要求、配送中央的水平、实力及客观条件而定,可以有以下多种选择：(1)效益最高：在选择以效益为目标时,通常以企业当前的效益为主要考虑因素,同时兼顾长远的效益.效益是企业整体经营活动的综合表达,可以用利润来表示.因此在计算时是以利润数值最大化为目标值.但由于效益是综合的反映,在拟定数学模型时很难与配

34、送路线之间建立函数关系,所以一般很少采用这一目标.(2)本钱最低：计算本钱比拟困难,但和以效益为目标相比有所简化,在本钱和配送路线之间有密切关系、且本钱对最终效益起决定作用的情况下,采用以本钱最低为目标实际上等于选择了以效益为目标,比拟实用可行.(3)路程最短：如果本钱和路程相关性较强,而和其他因素是微相关时,那么可以选择路程最短为目标,这样可以预防许多不易计算的影响因素,大大简化算.但需要注意的是有时候路程最短并不意味着本钱最低,如果道路条件、道路收费影响了本钱,单以最短路程为最优解那么不适宜了.(4)吨公里最小：是长途运输中常作为选择目标,在多个发货站、多个收费站、整车发到的情况下,选择吨

35、公里最低为目标可以取得满意结果.在配送路线选择中,以吨公里最小为目标在一般情况下并不适用,但在采取共同配送方式时,也可以作为目标(5)准时性最高：准时性是配送中重要的效劳指标,以准时性为目标确定配送路线就是要将各客户的时间要求和到达各客户点的先后顺序进行协调安排,这样有时难以顾及本钱问题,甚至需要牺牲本钱来满足准时性要求.但对准时性的要求必须建立在限制本钱的根底上.(6)运力利用最合理：在运力非常紧张、运力与本钱或效益有一定相关的情况下,为了节约运力、充分运用现有运力,而不需外租或新购车辆,也可以运力安排为目标,确定配送路线.针对不同的物流配送问题,要根据具体情况选择优化目标.本文研究的物流配

36、送问题根据帝峰模具公司物流系统的特点,将优化目标设定为路程短、准时性高、运力利用合理.2.2.2 配送路径优化问题的分类物流路径优化问题根据各种因素的不同形成了不同的种类,如表2-1.表2-1不同分类依据下的路径优化问题类型122.2.3 配送路径优化问题的解法分类针对早期与现今的车辆路径问题模型,已有相当多的文献提出求解方法,可分为以下五大类13:(1)系统仿真法(Simulation)此方法最早由Golden和Skiscim于1986年提出,主要应用于行车线路与物流配送中央区位的选择.优点在于可直接观察系统安排的效率与效果,但由于问题的实际情况多变且具有不确定性,很难将要实现的配送情形系统

37、逻辑化为仿真程序；(2)人机互动法人机互动法是一种结合使用者的直觉、经验、以及专业水平,纳入求解过程的一L.种方法,这种方法可以让决策者在电脑上产生途径的中间阶段.此方法结合人类决策与计算机计算水平,在求解的过程中,通过高度的人机交互模式,结合专家的决策信息计算出结果.该方法的优点是寻优的过程中,决策者可以很清楚地看到各约束条件之间的替代关系以及参数变化可能导致的本钱变化；(3)精确解法(ExactProcedures)精确解法一般应用于线性规划(包括经过了专门处理的分枝定界法、割平面法和标号法)和非线性规划等数学规划技术,以便求得问题的最优解.在VRP问题研究的早期,主要是单源点(One-P

38、oint)(即配送中央、车场等)派车,研究如何用最短路线(或最短时间内)对一定数量的需求点(即用户)进行车辆调度,因此主要运用精确算法求出问题的最优解.精确式算法一般有以下几种方法：分枝定界法(BranchandBoundApproach)、割平面法(CuttingPlanesApproach)、网络流算法(NetworkFlowApproach)和动态规划方法(DynamicProgrammingApproach)等；(4)启发式算法(Heuristics)由于上述三种方法的求解效率较差,所以大局部的学者都致力于启发式解法的开展.该方法在解题时可减少搜寻的次数,所以是一种容易且快速求解困难问

39、题的算法.车辆路径问题的启发式解法,包括节约法(Savingmethod)、最邻近法(Nearestneighbor)、插入法(Insertion)及扫描法(Sweeping)等；(5)智能算法(现代启发式算法)进入20世纪80年代,一些新奇的优化算法,如人工神经网络算法、遗传算法、模拟退火算法、禁忌算法、混沌等,通过模拟或揭示自然现象或过程得到开展,其思想涉及数学、物理、生物进化、人工智能等各方面,为解决复杂问题提供了新的思路和手段.在优化领域,由于这些算法构造的直观性与自然机理,因而被称为智能优化算法(intelligentoptimizationalgorithms)或现代启发式算法(m

40、eta-heuristicalgorithms).就目前的情况来看,智能算法应用于VRP的研究还不深入,一般都只考虑比拟简单的约束(容量约束、时间窗约束),与实际应用还有相当大的距离.但是,用智能优化算法解决VRP问题已经得到了人们的重视,相当多的学者致力于这方面的研究,开展势头很强劲,是进行VRP研究的一个热点方向.相对于传统启发式算法,现代启发式算法不要求在每次迭代中均沿目标值下降方向,而允许在算法中适当接受目标值有所上升甚至不可行的解,其目的是能够跳出局部搜索邻域.2.3 本文配送路径优化方法在配送路径优化问题的诸多解法当中,本文选择启发式算法当中的三种最常被运用到的方法进行方案的优化.

41、2.3.1 建立VRP模型多回路运输问题(VRP)是现实中十分普遍的一种调配问题,此类调配的核心问题是如何对车辆进行调度.因此,VRP(VehicleRoutingProblem)模型应运而生,并成为解决多回路问题的一个相当成功的模型.该问题研究目标是：对一系列顾客需求点设计适当的路线,使车辆有序地通过他们,在满足一定的约束条件下(如货物需求量、发送量、车辆容量限制,行驶里程限制等),到达一定的优化目标(如里程最短,费用最小,时间尽量少等).它涉及了多辆交通工具的效劳对象的选择和路径确定两方面问题.一个典型的VRP模型可以如下表述：(1)根本条件：现有m辆相同的车辆停在一个共同的源点v0,它需

42、给n个客户提供货物,顾客为v1、v2,vn,两点之间路线为cij14.(2)模型目标：确定所需的车辆数N,并指派这些车辆到一个回路中,同时包括回路内的路径安排和调度,使总费用最小.(3)限制条件：N不大于m；每一个订单都要完成；每辆车完成任务后都要回到源点v0;车辆的容量不能超过一定限制值；配送路线上所有配送点的配送需求量总和不能大于配送车辆的最大载重量；从配送中央出发到配送结束并返回配送中央的路程不能大于配送车辆的最大行驶距离；每条配送路线必须由一辆配送车辆配送,且要满足路线上所有需求点的要求,特殊问题还需考虑时窗限制、运输规章限制15.2.3.2 最近插入法最近插入法是一种解决旅行商问题的

43、启发式算法,其结合最邻近法与节省法的观念,依序将顾插入路径中以构建配送路线16.该方法首先以起点最近的点作为路线的种子点,再根据最邻近点插入法的概念,以插入值最小者作为下一个插入点,最后再用一般化节省值公式,以其中节省值最大者决定插入的位置,重复进行选取与插入的步骤,为了使物流配送的时间最少、距离最短、费用最低,并使合并后的总运输距离节约的里程最大,直到到达一辆车的装载限制时,再进行下一条路线的优化17.客点需求最近插入法由四步完成18:1找到c0i最小的节点vi,形成一个子回路,T=v0,vk,v0;2在剩下的节点中,寻找一个离子回路中某一节点最近的节点vk,假设此时回路的总货运量未超过车的

44、载重限制,那么继续步骤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问题的算法,它采用“先分组后路线的过程,所谓分组就是派给每辆车一组客户点.一

45、种简单的分组方法是将以配送中央为原点的坐标平面划分为多个扇形区域,并初步将每个扇形区域的点分派给一辆车,然后扩充路线,如果在进行了一次“分组-路线的路线构造后,还存在未分配点,那么再进行“分组-路线程序.如此反复,直到所有的点均已分配为止19.扫描算法的主要步骤：1以起点0点作为极坐标系的原点,并一连通图中的任意一顾客点和原点的连线定义为角度零,建立极坐标系；然后对所有的顾客所在的位置,进行极坐标变换；2从最小角度的顾客开始建立一个组,按逆时针方向,将顾客逐个参加到组中,直到顾客的需求总量超出了负载的限制.然后继续建立一个新的组,继续按逆时针方向,将客户参加组中；3重复2中的过程,直到所有客户

46、都被分类为止；4对各个组内的单回路进行路径优化.2.3.4 节约算法节约算法是目前用来解决运输车辆数目不确定的VRP模型的最有名的启发式算法,其思想在于按节约值较短路径与原路径之差由大至小排序,在车辆容量限制下,依序将对应的两客户点排入路径中,直至所有客户都被排入路径为止.关键在于当节约值较大的两顾客点被排入路径时,除需考虑车辆容量限制方面采用“量力而为的策略外,更需要考虑到时间的限制,此方法的优点是提升车辆的利用率20.节约算法的核心思想是将运输问题中存在的两个回路0,i,0和0,j,0合并成一个回路0,i,j,0,在上面的合并操作中,整个运输问题的总运输距离会发生变化,如果变化后总运输距离

47、下降,那么称节约了运输距离21.其中cio代表从顾客i至起点的距离,coj代表从起点至顾客j的距离,cji那么代表从顾客j至顾客i的距离,相应的变化值叫做节约距离QUOTE*MERGEFORMAT工ij.计算两结点i与j间的节约值QUOTE*MERGEFORMATzCij时,应先计算原路径中各往返路径的总和,再与较短路的总路径和相比拟.两结点间的节约值的计算公式与意义如式1所示.（1）两结点的原路径与较短路的调整过程如图2-1所示.i00i调整前调整后图2-1节约算法的图像描述节约里程算法主要步骤：1设需求点集NR=1,2,n,各点需求量Ri,各点间最短距离cij;2确定各车辆配送点集I1,I

48、2,1Im令上j,j=1,2,in先采取单点配送;(3)计算所有点对的节约度QUOTE*MERGEFORMATz2Cij,然后对计算结果进行升序排列.(4)从升序排列的节约度序列中的最上面的值开始,直到节约里程Cij的队列空为止,重复以下步骤：根据节约里程Cij队列从大到小的顺序,分析客户i和j之间合并的可能性(是否满足装载限制条件、不在同一路径内以及合并次数不超过2),将i,j连接起来,即可令I"=IiUIj;,如果不是这样,那么从节约里程队列中去除当前的节约里程,分析下一个客户对22.第3章帝峰模具公司物流配送路径现状分析1.1 公司简介武汉帝峰模具成立于2021年,位于武汉市江

49、夏开发区大桥新区107国道旁.它是以五金模具与塑胶模具的研发与制造、提供销售配送效劳为一体的实体企业.公司拥有专业技术人才二十余名和各种机械加工设备,下设设计部门,生产部门,营销部门,物流部门等职能部门,各部门通力协作,为社会奉献优质高效的各类模具,为客户提供专业专心的技术支持和效劳,武汉帝峰模具自成立以来,坚持“以诚为本,以信为根,“用科技创造绿色生活的经营理念,立志成为模具新技术的领航者的企业愿景,扎实走科技与生产相结合的产业化道路,专业生产各种模具产品.目前公司产品涵盖湖北省各市县并以优厚的实力、合理的价格、优良的效劳与多家企业建立了合作关系.1.2 公司物流配送路径现状公司的客户主要位

50、于其所在地的周边县市,共有9个县市,如孝感市、天门市、荆州市等,编号如表3-1,地区分布如图3-1所示,但需求较小,公司为推广产品,采用每月专车送货上门效劳.公司现拥有4辆40吨的货车,假设车辆使用欠缺时,可租赁车辆.表3-1客户所在城市编号图3-1帝峰模具公司配送地区根底图武汉帝峰模具位置为0点,分别向周围编号为1、2、3、4、5、6、7、8、9共9个小客户点配送本期新型五金模具,其拥有2辆40吨的车40吨卡车最大载量为12套模具.各点需求量为Ri,每辆车的行驶里程为Li,Li<700公里,客户点1,2,9.各县市每月需求模具的根本数据如图3-2所示.图3-2各客户点的需求量图3-3各

51、客户点的配送距离资料来源：帝峰模具公司信息系统|目前,对小客户公司采用的配送线路如图3-2所示.图3-2公司现有配送路线各配送线路的里程,所需司机数量的根本情况如表3-2所示.表3-2配送信息表资料来源：帝峰模具公司信息系统由上表可知,公司每月需40吨货车4车次配送,司机5人次,所需工资2500元,运输总里程为1549.5千米,消耗柴油697.28升,所需燃油费3625.86元,一共花费6125.86元.1.3 公司物流配送路径存在的问题分析在物流车辆配送中,公司其往往需向几个不同顾客的运送货物,每个用户又会对货物有不同的需求,这将造成配送复杂性.虽然公司对物流部门的大力支持,物流部门快速开展

52、,物流部门的交通设施改善很多,物流配送本钱也降低了很多,但相比于同行业其他企业,公司目前配送线路的弊端在于：配送路线的回路过多,存在对流运输的现象,经验化操作过多,优化不彻底,导致总运距过长,消耗作业时间偏多,不能充分利用车辆配载容积,浪费较多人力和物力资源,物流本钱的花费还是很高,影响公司盈利22.1.3.1 回路总数过多在公司现有路径的图中,9个客户点设置4条回路,平均每条回路有2.25个客户3.67套；由于每条点；9个客户点总需求量为33套模具,平均每个客户点需求量约回路中有一辆配送车辆,故每辆车平均装载约8.26套模具.而公司的40吨货车可装载12套模具,所以平均每辆车利用率为68.9

53、%,计算结果偏低,导致车辆非满载运输,运力利用不充分,造成车辆,人力,资金上的浪费.对于此种情况来说,关键因素在于路径回路总个数,所以最有效的方法是通过减少总会路个数,充分利用车辆配载容积,提升车辆利用率,进而节约车辆与人力上的本钱.1.3.2 对流运输对流运输亦称相向运输、交错运输,是指同一种货物,或彼此间可以互相代用而又不影响治理、技术及效益的货物,在同一线路上或平行线路上作相对方向的运送,而与对方运程的全部或一局部发生重迭交错的运输称对流运输.已经制定了合理流向图的产品,一般必须按合理流向的方向运输,如果与合理流向图指定的方向相反,也属对流运输.如图3-5中,从4号地区回到起点的路线与从

54、起点到5号地区的路线图中用圆圈画出虽然不是一条回路中的配送路径,但是它在平行线路上作相对方向的运送,属于对流运输的情况,同样情况的还有2-0与0-5图中用斜线画出,2一0与0一3图中用菱形画出两对路线,这种现象会导致人力、物力等资源的浪费.4图3-3现有路径中的对流运输现象1.3.3 经验化操作经调查,由于企业建立时招聘的人员大多具有多年物流经验,不免会根据以往的工作经验进行工作,其设计的运输配送路径经验化操作过多,从而导致企业增加目标地区之后,他们不会积极地重新去计算和安排配送的运输路径,而是凭以往经验操作此过程.如图3-6中,客户点3和客户点4是最近与公司合作的客户,距离公司胶原且两点相离

55、较近,物流部门便仅把两点归于一条回路当中,并没有将九个客户点放在一起重新计算作合理安排.图3-4经验化操作下的一条回路第4章帝峰模具公司物流配送路径优化策略4.1 建立VRP模型优化配送路径对帝峰模具的配送系统建立VRP模型.根本条件：帝峰模具需给9个客户送货,客户依次为1,2,日,现有3辆40吨的货车(每百公里油耗45L),司机每天工资500元,柴油每升5.20元.模型目标：确定所需要的车辆的数目N、车辆类型、司机数量以及各车行走的路径,并指派这些车辆到一个回路中,同时包括回路内的路径安排和调度,使得运输总费用最小.限制条件：(1)全程的总时间不超过驾驶员每天最大工作时,以预防疲劳驾驶23,

56、所以基于人性化与平安的考虑,当运输里程超过350公里时,需配备两名司机,为预防突发运输事件,车辆必须当天回到公司,减去由于装卸货等影响因素,各车最大运输距离为650公里.(2)每辆车完成任务之后都要回到源点0处.(3)不能超过车辆的容量限制.40吨的货车最多可装12套模具.4.2 公司物流配送路径的优化4.2.1 运用最近插入法优化第一条路径：令丁=0川=0,1,2,9,比拟表4-1中从0出发的所有路径大小.由于minc0i|iCN,1<i<9=c01=61.4km,所以就有顾客点0,1构成一个子回路,T1=0,1,0,此时M=5,L1=122.8km.然后在剩余客户点(2,3,4

57、,5,6,7,8,9)中寻找到0和1中某一点的最小距离,minc0i,c1iiCN,14i?9且iW1=c08=77km,r8=2,由于r1=r1+r8=7v12,所以在子回路T1=0,1,0插入点8.由于对称性,无论将8插入到0和1之间往返路径中,结果都是一样的,这样,构成了一个新的子回路T1=0,1,8,0,r1=7,L1=275.1km.再次寻找剩余客户点到0,1,8中某一点的最小距离：可知最小距离为c78=41.4km.此时,r7=4,由于r1+r7=7+4=11<12,所以在子回路T1=0,1,8,0插入点7.将点7分别插入(0,1),(1,8),(8,0)中：(1)插入到(0,1)之间,A=c07+c