物流配送路径优化研究

摘要

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

[关键词]：帝峰模具配送路径优化最近插入法扫描法节约算法

[Abstract]

Reasonableandefficientdistributionistheinsuranceofasmoothrunninglogisticssystem,distributionlinearrangementisreasonableornothasagreatinfluenceonthespeedofdelivery,costsandbenefits.Therefore,toarrangeareasonableandcorrectdeliverylineforvehicleandachieveareasonabletransportlinecanenableenterprisestoachievescientificlogisticsmanagement,whichisoneoftheeffectivewayforanenterprisetoimproveitscompetitiveness.ThispapertakeDifengMoldCo,Ltd.distributionasanexampletoanalysisoftheproblemsexistinginthestatusofitsdistribution,throughthesavingalgorithm,theimprovedinsertmethodandscanningmethodofthesethreemethodsareoptimizedfordistributionlines,logisticsdistributionrouteoptimizationschemeisputforward,andarelativelysatisfactoryresultsareobtained.Optimizeddistributionlineseffectivelyimprovethegravelslogisticscompany'sefficiency,reducelogisticscosts,therebyimproveenterpriseeconomicbenefits,andgravelscaninthefiercemarketcompetition,atthesametime,alsocanprovideareferenceforsimilarenterprises.

[Keywords]DifengMoldCo,LtdDistributionrouteoptimizationscanningmethodtheimprovedinsertmethodthesavingalgorithm

目录

第1章绪论

1.1研究背景6

1.2国内外研究现状7

1.2.1国外研究现状7

1.2.2国内研究现状9

1.3研究目的、意义和方法11

1.3.1研究目的11

1.3.2研究意义11

1.3.3研究方法12

1.4本文研究内容12

第2章相关理论概述

2.1物流配送14

2.1.1物流配送的概念14

2.1.2物流配送的功能14

2.1.3物流配送的要素15

2.2配送路径优化问题16

2.2.1配送路径优化的目标16

2.2.2配送路径优化问题的分类18

2.2.3配送路径优化问题的解法分类19

2.3本文配送路径优化方法20

2.3.1建立VRP模型20

2.3.2最近插入法21

2.3.3扫描法22

2.3.4节约算法23

节约里程算法主要步骤：24

第3章帝峰模具公司物流配送路径现状分析

3.1公司简介25

3.2公司物流配送路径现状25

3.3公司物流配送路径存在的问题路径分析28

3.3.1路径迂回28

3.3.2对流运输29

3.3.3经验化操作过多30

第4章帝峰模具公司物流配送路径优化策略

4.1建立VRP模型优化配送路径31

4.2公司物流配送路径的优化31

4.3.1运用最近插入法优化31

4.3.2运用扫描法法优化35

4.2.3运用节约算法优化39

4.4三种优化方案比较分析44

结论

致谢

参考文献

第1章绪论

1.1研究背景

物流是为了满足消费者需要而进行的从供应地到接收地的原材料、中间产品、最终产品及相关信息的有效流动和储存计划、实施和控制的管理过程。其功能是通过运输、仓储、装卸搬运、包装、流通加工、配送、信息处理等活动过程有机结合起来实现的。其中配送对于物流的运行和发展有着深刻的社会根源和历史背景。在市场经济体系中，物流配送犹如人体的血管，把国民经济各个部分紧密地联系在一起。物流配送是物流的基本功能，作为直接面向最终客户提供的物流服务，在满足现代化的物流需求方面发挥着极其重要的作用。如果没有配送就会影响物流的经济效益和社会效益，可以说物流成果主要是通过配送来实现的。著名管理大师彼得德鲁克说“美国人花费的每美元中，大概有美分是花在产品制成以后的活动上，即在产品己经完工的以后……从经济学角度看，配送是将事物的物质特性转换成经济价值的过程，它为产品带来了客户。”由可见配送活动及配送管理的重要性。物流配送一般处于物流末，是直接面向用户提供服务的环节，它具有提高物流经济效益，优化、完善物流系统，改善物流服务，降低物流成本等功能，在物流系统中占有重要的地位。随着市场经济的繁荣，企业业务规模日益扩大，物流配送作为现在现代企业一个重要环节，其效率高低直接影响企业的服务质量、配送成本，而配送路径优是物流配送的核心问题，因此物流配送路径优化问题是成为当前物流研究中的一个重要课题,所以它是一项特殊的、综合性的物流运动，其主要包括集货作业、配货作业、车载货物的配装、配送线路的确定[1]。配送实际上是一个局部物流，是大物流在小范围内的运作，配送是物流系统的终端。是否具备及时的配送时间影响服务水平的高低，这需要对车辆配送路径的合理优化和配送时间的掌控。

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

武汉帝峰模具是一家集设计、生产、销售、配送于一体的经营五金模具和塑胶模具的有限责任公司。作为一家以生产为主的企业，其在配送运输方面存在一定的不足之处，配送工作效率较低，配送成本较高。从车辆路径优化方面考虑配送优化，对运输路线进行合理规划，寻找一条符合实际情况的优化路径，这样才能从实际上节省配送费用，缓解交通的压力，使配送工作顺利进行，从而节省配送过程中运输费用耗费，而且使配送服务水平提高，并提高用户的满意度，以致提高工作效率，减少运营成本。

1.2国内外研究现状

1.2.1国外研究现状

很多国外学者对仓储货位优化的问题进行了研究，比如以下几位：

Clarke和Wright（1964）对Dantzig和Ramser提出VRP

问题模型的求解算法进行了改进，提出了更为有效的启发式算法Clarke-Wright节约法，后来该算法成功的用于求解车辆路径优化问题[2]；

Miller&Gillet(1974)提出扫描法(SweepMethod),目的在于求解车辆调度问题,并针对当时几个求解相似问题的算法进行比较,证明该算法所求得的解较优于其它的方法[3]；

wialldr(1989)首先将禁忌搜寻法应用于车辆路线问题上,设计重复的虚拟物流中心,将车辆路线问题转换成旅行商问题(TSP),利用2-opt或3-opt方法求解车辆路线；

Dorigo，Maniezzo和Colorni（1991）等意大利人将蚁群算法用于求解旅行商问题，并取得了很好的效果，后来，Dorigo在基本蚁群系统的模型的基础上又提出蚂蚁群系统(Ant

ColonySystem，ACS)模型，该模型改进了蚂蚁系统模型的信息素更新方法和路径选择方式，并使用了一种随机选择和最优选择混合的路径选择方式，而信息素更新采用全局更新和局部更新的方式，提高了算法的全局收敛能力，相比于蚂蚁系统模型的性能有较大的提高，收敛速度明显加快。后来很多学者对基本的蚁群算法进行改进，求解不同的问题模型；

Gendreau,HertZandL即orte(1994)使用插入法求解旅行商问题,再用贪婪法(GreedyMethod)进行路线切割,从而产生初始解；

Kennedy和Eberhart（1995）等美国博士，提出了粒子群算法，Eberhart博士等人对基本粒子群算法进行了改进，该算法被成功的用于求解物流路径规划问题；

Renaud（1995）等意大利博洛尼亚大学的博士对多配送中心的车辆路径规划问题(MultipleDepotVehicleRoutingProblem，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）把城市快递配送路径问题看作是简单的旅行商问题（TravelSalesmanProblem，TSP），针对该问题模型除了考虑了一般性的约束之外，仅仅只额外考虑了容量约束。当问题规模不大时，可以得到全局最优解。丁洁（2012）则将城市快递配送路径问题转化为多重旅行商问题（MultiTravelSalesmanProblem，MTSP），同时考虑到MTSP

问题求解难度较大，故先将其转化为TSP问题，接着结合最小生成树的深度优先搜索算法来确定快递员最终的行车路线，以求得到该问题的近似最优解；

何俊生（2013）针对同城快递配送路径问题，提出了两个模型，一个不考虑时间窗约束仅考虑容量约束，另一个同时考虑，采用Dijkstra遗传优化算法求解并进行了比较对比分析。姜艳和关雪（2008）提出了一个线性混合整数规划模型，该模型主要考虑时间窗约束和单车快件数目上限约束；

杨从平（2014）针对快递物流配送车辆路径问题，考虑了容量约束和单车最大行程距离约束，采用蚁群算法对桂林市某快递网络的配送路径进行了优化。李炳会（2008）则用超时惩罚对时间约束进行了替代，即快递超过预定时间需要赔偿以进行惩罚；

张迅和刘海东（2013）根据快递配送的特点，研究了采用快件递送和揽收同时服务的配送策略的车辆路径问题。他们假设车辆在配送中心与客户点之间或客户点之间行驶的时间服从正态分布，各客户点均带有有软时间窗约束，以及快件揽收数量服从泊松分布，依此建立一个线性混合整数规划的多目标模型，目标函数包括：行驶路程最短，时间惩罚值最小和快件揽收数量最大。同时他们提出了一种遗传算法：该遗传算法采取种群个体适应度值排序和最佳个体保留的选择策略，以及通过参数控制自适应交叉概率来保证所求结果的优良性，通过设计算例并采用Matlab软件进行编程运算，实验结果证明了该遗传算法的可行性；

陈敏（2009）研究了如何快速响应动态信息的车辆调度问题，并将其描述成是一个实时带时间窗车辆路径问题（Real-timeVehicleRoutingProblemwithTimeWindows，RT-VRPTW）。针对实际调度问题的规模、复杂度和特性，将动态问题转化成静态问题，提出了一种混合禁忌搜索算法，该算法分为两个阶段：第一阶段，首先采用插入法生成初始方案；第二阶段，引入改进的禁忌启发式搜索算法对全局进行优化，实验结果表明该算法行之有效；

胡明伟和唐浩（2010）则研究了快递服务相关的动态车辆路径问题，并将其描述成带时间窗的动态旅行修理员问题（DynamicTravelingRepairmanProblemwithTimeWindows，DTRPTW），建立多目标优化模型，该模型包括服务客户数量最大、客户等待时间最小以及总运行时间最短三重优化目标。他们采用基于词典式的排序方法，同时改进了Or-opt局部搜索算法。根据仿真实验结果显示，与单目标模型相比，多目标优化模型能够明显降低被拒绝服务的客户数量和客户等待时间，同时总运营时间未发生明显增长；

吴海东（2011）针对城市快递服务问题，重点研究了服务质量相似性和快递车辆交接行为这两大新的快递服务趋势，同时建立两阶段模型，在满足随机客户需求的条件下，还能够保证快递配送的路径得到最优。

目前国内对VRP问题的研究很多都停留在理论研究阶段，实验成果并没用广泛的进行实际应用，而且研究的问题模型都有一定的条件约束，约束条件不同，则对应的问题模型也不一样，求解的算法也不太一样，这样算法就有一定的局限性。

1.3研究目的、意义和方法

1.3.1研究目的

为了提高物流配送系统的服务质量和节省配送费用,对物流车辆配送路径的优化和行程时间的预测所进行的研究，本文通过制定较为合理化、人性化的物流车辆配送路径,满足实际的物流配送要求,从而能将货物迅速、安全地送到客户手中,达到提高服务水平的要求；与此同时，加快物流系统对客户需求的物流配送路径优化和行程时间预测响应速度,提高服务质量,增强客户对物流环节的满意度,降低服务商的运作成本使整体的服务水平提高[7]。

1.3.2研究意义

第一，本文结合实际的配送情况，对配送车辆路径优化理论与方法进行系统研究是物流集约化发展、建立现代调度指挥系统、发展智能交通运输系统和开展电子商务的基础。同时,优化后的物流配送路径,有利于缓解交通压力；

第二，规划好物流配送的行进路线,有利于节省配送费用,而对行程时问精确的预测反过来有利于指导物流规划的行进路线,引导车辆沿途配送物资；

第三，物流配送路径优化,是物流配送优化中关键的一环。对货运车辆进行路径优化,可以提高物流经济效益、社会效益、实现物流科学化[8]；

第四，优化配送路径问题对提高物流企业配送效率，降低物流配送成本，促进经济的快速发展都具有重要的作用，从而对物流配送路径规划的研究具有非常高的应用价值。

1.3.3研究方法

（1）文献参考：本文主要是通过对互联网上的相关文献、资料以及图书进行详细的阅读和思考，并参考其中相关有用的文字以及解决问题的思路及方法。

（2）实地考察：在武汉帝峰模具有限公司实习期间，将搜集的资料进行大致的提炼，对于物流配送路径的各项考虑因素进行主次分类，并带着这些疑问在公司实习之余对配送路径方案进行大致的理解与总结。

（3）定量分析法：依据近三个月物流单据结合运筹学相关知识，运用节约算法、扫描法和改进的最近插入法进行必要的分析与运算，并比较三种方法的结果以得到较优路径的设计方案。

1.4本文研究内容

本文以武汉帝峰模具有限公司为例，在对物流配送业务进行研究的基础上,针对物流配送中对成本影响较大的车辆路径问题(VRP)进行集中研究,在车辆载重限制、时间限制、客户需求量限制和指定地点的条件下建立了VRP数学模型,并利用启发式算法中的三种方法优化配送路径，并选出较优方案[9]。

本文的研究内容如下:

第一章阐述本文的研究背景，国内外研究现状，研究意义、目的和方法；

第二章对物流配送和配送路径优化问题进行了相关理论的概述，并介绍了节约算法、扫描法和最近插入法的原理及步骤；

第三章主要介绍了本人实习所在公司，描述了其在物流配送路径方面的现状以及存在的问题；

第四章是本文的重点部分,首先介绍了关于改进公司配送路径的基本思路，其次运用节约算法、扫描法以及改进的最近插入法优化配送路径，然后比较三者得出的结论并选出较优方案。

△Cij，然后对计算结果进行升序排列。

（4）从升序排列的节约度序列中的最上面的值开始，直到节约里程△Cij的队列空为止,重复下列步骤:按照节约里程△Cij队列从大到小的顺序,分析客户i和j之间合并的可能性(是否满足装载限制条件、不在同一路径内以及合并次数不超过2),将i,j连接起来,即可令Ii＇=Ii∪Ij;Ij=∅，如果不是这样,则从节约里程队列中去除当前的节约里程，分析下一个客户对[22]。

第3章帝峰模具公司物流配送路径现状分析

3.1公司简介

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

3.2公司物流配送路径现状

公司的客户主要位于其所在地的周边县市，共有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各客户点的配送距离

（资料来源：帝峰模具公司信息系统）

目前，对小客户公司采用的配送线路如图3-2所示。

9

1

0

8

2

7

5

3

6

4

图3-2公司现有配送路线

各配送线路的里程，所需司机数量的基本情况如表3-2所示。

表3-2配送信息表

（资料来源：帝峰模具公司信息系统）

由上表可知，公司每月需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对流运输

对流运输亦称相向运输、交错运输，是指同一种货物，或彼此间可以互相代用而又不影响管理、技术及效益的货物，在同一线路上或平行线路上作相对方向的运送，而与对方运程的全部或一部分发生重迭交错的运输称对流运输。已经制定了合理流向图的产品，一般必须按合理流向的方向运输，如果与合理流向图指定的方向相反，也属对流运输。

如图3-5中，从4号地区回到起点的路线与从起点到5号地区的路线（图中用圆圈画出）虽然不是一条回路中的配送路径，但是它在平行线路上作相对方向的运送，属于对流运输的情况，同样情况的还有2→0与0→5（图中用斜线画出），2→0与0→3（图中用菱形画出）两对路线，这种现象会导致人力、物力等资源的浪费。

9

1

0

8

2

7

5

3

6

4

图3-3现有路径中的对流运输现象

3.3.3经验化操作

经调查，由于企业建立时招聘的人员大多具有多年物流经验，不免会根据以往的工作经验进行工作，其设计的运输配送路径经验化操作过多，从而导致企业增加目标地区之后，他们不会积极地重新去计算和安排配送的运输路径，而是凭以往经验操作此过程。

如图3-6中，客户点3和客户点4是最近与公司合作的客户，距离公司胶原且两点相离较近，物流部门便仅把两点归于一条回路当中，并没有将九个客户点放在一起重新计算作合理安排。

0

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运用最近插入法优化

第一条路径：

令T={0},N={0，1，2……,9}，比较表4-1中从0出发的所有路径大小。因为min{c0i│i∈N，1≤i≤9}=c01=61.4km，所以就有顾客点0，1构成一个子回路，T1={0，1，0}，此时r1=5,L1=122.8km。

然后在剩余客户点（2，3，4，5，6，7，8，9）中寻找到0和1中某一点的最小距离，min{c0i，c1i│i∈N，1≤i≤9且i≠1}=c08=77km，r8=2，因为r1=r1+r8=7＜12，所以在子回路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）之间，Δ=c07+c71-c01=100.4+159-61.4=198km。

（2）插入到（1，8）之间，Δ=c17+c78-c18=159+41.4-136.7=63.7km。

（3）插入到（8，0）之间，Δ=c87+c70-c80=41.4+100.4-77=64.8km。

比较得：插入到（1，8）中增量最小，所以将客户点7加入到（1，8）间，结果为T1={0，1，7，8，0}，r1=11，L1=338.8km。

第二条路径：

再次对剩余的客户点（2，3，4，5，6，9）按照上诉方法进行优化，比较表4-1中从0出发的所有路径大小。因为min{c0i│i∈N，1≤i≤9且i≠1,7,8}=c06=92.6km，所以就有顾客点0，6构成一个子回路，T2={0，6，0}，此时r6=3,L2=185.2km。

然后在剩余客户点（2，3，4，5，9）中寻找到0和6中某一点的最小距离，min{c0i，c6i│i∈N，1≤i≤9且i≠1,6,7,8}=c05=96.7km，r5=3，因为r2=r6+r5=6＜12，所以在子回路T2={0，6，0}插入点5。由于对称性，无论将5插入到0和6之间往返路径中，结果都是一样的，这样，构成了一个新的子回路T2={0，5，6，0},r2=6，L2=337.6km。

再次寻找剩余客户点到0，5，6中某一点的最小距离：可知最小距离为c25=48.1km。此时，r2=4,因为r2+r7=6+4=10＜12，所以在子回路T2={0，5，6，0}插入点2。将点2分别插入（0，5），（5，6），（6，0）中：

（1）插入到（0，5）之间，Δ=c02+c25-c05=136.5+48.1-96.7=87.9km。

（2）插入到（5，6）之间，Δ=c52+c26-c56=48.1+195.9-148.3=95.7km。

（3）插入到（6，0）之间，Δ=c62+c20-c60=195.9+136.5-92.6=239.8km。

比较得：插入到（0，5）中增量最小，所以将客户点2加入到（0，5）间，结果为T2={0，2，5，6，0}，r2=10，L2=425.5km。

第三条路径：

再次对剩余的客户点（3，4，9）按照上诉方法进行优化，比较表4-1中从0出发的所有路径大小。因为min{c0i│i∈N，1≤i≤9且i=3,4,9}=c09=112.6km，所以就有顾客点0，9构成一个子回路，T3={0，9，0}，此时r9=4,L3=225.6km。

然后在剩余客户点（3，4）中寻找到0和9中某一点的最小距离，min{c0i，c9i│i∈N，1≤i≤9且i=3，4}=c03=221.4km，r3=5，因为r3=r9+r3=64+5=9＜12，所以在子回路T3={0，9，0}插入点3。由于对称性，无论将3插入到0和9之间往返路径中，结果都是一样的，这样，构成了一个新的子回路T3={0，3，9，0},r3=9，L3=436.7km。

最后一个客户点4，c04=263.2，r4=3因为r3+r4=9+3=12，所以可以将点4分别插入（0，3），（3，9），（9，0）中：

（1）插入到（0，3）之间，Δ=c04+c43-c03=263.2+89.4-221.4=131.2km。

（2）插入到（3，9）之间，Δ=c34+c49-c39=89.4+371.7-327.9=133.2km。

（3）插入到（9，0）之间，Δ=c94+c40-c90=371.7+263.2-112.6=522.3km。

比较得：插入到（0，3）中增量最小，所以将客户点4加入到（0，3）间，结果为T3={0，4，3，9，0}，r3=12，但因为L3=793.1km＞650km，所以点4不可以插入T3，故T3={0，3，9，0},r3=9，L3=436.7km。

第四条路径：

只剩最后一个客户即点4，c04=263.2，r4=3，所以T4={0,4,0}，r4=3，L4=526.4km。

利用最近插入法优化线路结果如图4-5所示.

9

1

0

8

2

7

5

3

6

4

图4-5最近插入法求解线路结果

得到优化结果如表4-7所示。

表4-7最近插入法优化结果

由上表可知，公司每月需40吨货车4车次司机7人次，所需工资1400元，运输总里程为1727.4千米，消耗的柴油777.33升，所需燃油费4042.12元，一共花费7542.12元。

此算法比公司现有方案相比，没有优越性，需要考虑其他的启发式算法[24]。

4.3.2运用扫描法法优化

对帝峰模具周边的9个县市采用扫描算法进行配送线路的优化。

首先建立极坐标系：以帝峰模具有限公司所在地武汉市作为原点O，并以处在点1位置的孝感市与原点的连线为零角度建立极坐标系如图4-2所示。

9

1

0

8

2

7

5

3

6

4

图4-2扫描算法的扫描过程

各点的货运量及极坐标的角坐标值如表4-6所示。

表4-6运量和极坐标的角坐标值

然后分组：从角度为零向逆时针方向进行扫描。

第一个被分组的是客户1，r1=5；继续转动，下个被分组的是客户2，r1=5+4=9；继续转动，下个被分组的是客户3，9+5=14＞12，由于超过了限制，按分组规则，需要一个新的组，这样在第一组里只有客户1，2，r1=9。

进行第二组扫描，最先扫描到的是客户3，r2=5；继续转动，下个被分组的是客户4，r2=5+3=8；继续转动，下个被分组的是客户5，r2=8+3=11；继续转动，下个被分组的是客户6，r2=11+3=14＞12，超过限制，所以需要一个新的组，这样在第二组中只有客户3,4,5，r2=11。

第三组中从客户6开始，r3=3:；继续转动，下个被分组的是客户7，r3=3+4=7；继续转动，下个被分组的是客户8，r3=7+2=9；最后一个被分组的是客户9，r3=9+4=13＞12，超过限制，所以需要一个新的组，这样在第二组中只有客户6,7,8，r3=9。

第四组只剩一个客户9，故顾客9单独在一组，r4=4。

这时，可以得到如图4-3所示的分组结果。

9

1

0

8

2

7

5

3

6

4

图4-3扫描算法求解结果

最后对各子回路内的线路优化：对上面的3个组，都已经是一个单回路运输问题，对每个组进行线路优化。供应点0是任何一个组的TSP问题的起点和终点，用最近插入法分别对三个客户组进行求解。

对第一组进行求解。比较表4-1中从0出发的所有路径大小，

min{c0i│i∈N,1≤i≤2}=c01=61.4km

这样，就有客户点0，1构成一个子回路T1={0,1,0}。

由于对称性，无论将2插入到0和1之间往返路径中，结果都是一样的，所以第一组的结果为T1={0,1,2,0},总行驶距离为：L1=287.3km。

对第二组进行求解。比较表4-1中从0出发的所有路径大小，

min{c0i│i∈N,3≤i≤5}=c05=96.7km

这样，就有客户点0，5构成一个子回路，T2={0,5,0}。

然后考虑剩下客户点3，4到0和5中某一点的最小距离：

min{c0i，c5i│i∈N,3≤i≤5，且i≠5}=c35=127.9km

由于对称性，无论将3插入到0和5之间往返路径中，结果都是一样的，这样，构成了一个新的子回路T2={0,3，5,0}。

接下来考虑剩下的客户点4到0，3，5中某一点的最小距离：

min{c0i，c3i，c5i，│i∈N,3≤i≤5，且i≠3，5}=c34=89.4km

客户点4有3个位置可以插入，现在分析将点4加入到哪里合适。

插入到（0，3）之间，Δ=c04+c43-c03=263.2+89.4-221.4=131.2km。

插入到（3，5）之间，Δ=c34+c45-c35=89.4+158.6-127.9=120.1km。

插入到（5，0）之间，Δ=c54+c40-c50=158.6+263.2-96.7=325.1km。

比较可知，插入到（3，5）之间增量最小，所以将客户点4加入到（3，5）间，结果为T2={0,3，4，5，0}。总行驶距离为：L2=566.1km。

对第三组进行求解。比较表4-1中从0出发的所有路径大小，

min{c0i│i∈N,6≤i≤8}=c08=77km

这样，就有客户点0，8构成一个子回路，T3={0,8,0}。

然后考虑剩下客户点6，7到0和8中某一点的最小距离：

min{c0i，c8i│i∈N,6≤i≤8，且i≠8}=c78=41.4km

由于对称性，无论将7插入到0和8之间往返路径中，结果都是一样的，这样，构成了一个新的子回路T2={0,7，8,0}。

接下来考虑剩下的客户点6到0，7，8中某一点的最小距离：

min{c0i，c7i，c8i，│i∈N,6≤i≤8，且i≠7，8}=c60=92.6km

客户点6有3个位置可以插入，现在分析将点6加入到哪里合适。

插入到（0，7）之间，Δ=c06+c67-c07=92.6+102.4-100.4=94.6km。

插入到（7，8）之间，Δ=c76+c68-c78=102.4+113.7-41.4=174.7km。

插入到（8，0）之间，Δ=c86+c60-c80=113.7+92.6-77=129.3km。

比较可知，插入到（0，7）之间增量最小，所以将客户点6加入到（0，7）间，结果为T3={0,6,7,8，0}。总行驶距离为：L3=313.4km。

对第四组进行求解，可得T4={0,9,0}，总行驶距离为：L4=225.2km。

最后得到的优化线路图如图4-3所示。

9

1

0

8

2

7

5

3

6

4

图4-4扫描算法求解线路结果

最优结果如表4-7所示。

表4-7扫描算法优化结果

由上表可知，公司每周需40吨货车4车次配送，司机5人次，所需工资1000元，运输总里程为1392千米，消耗的柴油626.4升，所需燃油费3257.28元，一共花费5757.28元。

虽然扫描法简单易行,对线路优化具有较大优势,目前很多中小企业仍釆用扫描法来完成配送线路的规划，但是扫描法过于注重分区分组运输,而对于运输里程因素和车辆装载量欠缺考虑,使人力物力资源浪费，总成本增加。因此需要另外寻找方法进行路线规划。

4.2.3运用节约算法优化

利用节约法确定配送路线的主要出发点是，根据公司物流部门的的运输能力和公司到各个客户以及各个客户之间的距离来制定使总的车辆运输的吨公里数最小的配送方案。另还需满足以下条件：

（1）所有用户的要求；

（2）不使任何一辆车超载；

（3）每辆车每天的总运行时间或行驶里程不超过规定的上限；

（4）用户到货时间要求。

首先，确定各县市间的最短距离，县市间最距离表4-1所示。

表4-1各县市间最短距离表（单位：千米）

数据来源：高德地图

然后计算各点相互之间最短距离，根据表4-1中的帝峰模具有限公司至各客户之间、各个客户间的距离，得出最短配送路线距离矩阵。如表4-2所示。

表4-2最短配送路线距离矩阵

其次，求节约里程。根据最短距离表和式（1）计算出各个客户之间的节约里程,计算出各分公司之间的配送路线节约行程表，如表4-3所示。

表4-3配送路线节约行程表

对节约行程按大小顺序进行排列，编制节约里程QUOTE△Cij顺序表，如表4-4所示。

表4-4配送路线节约行程排序表

然后，形成一初始解，，令Ii={i}，（i=1,2，…9），最短路径Li=2c0i(i=1,…9)，且Li≤650公里，载货量ri=Ri，且ri≤12，对9个客户点进行标记B1=B2=…=B9=0，且Bi≤2。

（1）ΔC34=462：r3+r4=8＜12，L3+L4-ΔC34=2221.4+2330-462=640.8＜650，B3=B4=0，合并3、4点，则I1=I3∪I4={3,4}，r1=8,L1=640.8，B3=B4=1，I3∪I4=∅。

（2）ΔC24=303.3：r1+r2=8+4=12＝12，L1+L2-ΔC24=640.8+2136.5-303.3=610.5＜650，B2=0，B4=1，合并2、4两点，I2=I1∪I2={2，3，4}，r1=12，L1=610.5，B2=B3=1，B4=2，I2=I3=I4=∅。

由于r1=12，货运量达到载重40吨卡车的最大载货量，故回路0-2-3-4-0不能再与其他点合作，接下来的讨论跳过与点2,3,4,相关的ΔCij。

（3）ΔC78=136：r7+r8=6＜12，L7+L8-ΔC78=2100.4+277-136=218.8＜650，B7=B8=0，合并7、8点，I3=I7∪I8={7，8}，r3=6，L3=218.8，B7=B8=1，I7=I8=∅。

（4）ΔC89=98.6：r3+r9=6+4=10＜12，L3+L9-ΔC89=218.8+2112.6-98.6=345.4＜650，合并8、9点，I4=I3∪I9={7,8,9}，r4=10，L4=345.4，B8=2，B7=B9=1，I7=I8=I9=∅。

余下各点的货运量均大于2，故回路0-7-8-9-0不能再与其他点合并。接下来的讨论将跳过与点7,8,9相关的ΔCij。

（5）ΔC15=57.1：r1+r5=8＜12，L1+L5-ΔC15=61.42+96.72-57.1=259.1＜650，B1=B5=0，合并1、5点，I5=I1∪I5={1，5}，r5=8，L5=259.1，B1=B5=1，I1=I5=∅。

（6）ΔC56=41：r5+r6=8+3=11＜12，B5=1，B6=0，L5+L6-ΔC56=259.1+292.6-41=310.7＜650，B5=1，B6=0，合并5、6点，I6=I5∪I6={1，5，6}，r6=11，L6=310.7，B1=B6=1，B5=2，I1=I5=I6=∅。

至此，合并结束。

节约算法优化线路图如图4-1所示。

9

1

0

8

2

7

5

3

6

4

图4-1节约算法求解路径结果

最后得到的最优结果如表4-5所示。

表4-5节约法优化结果

由上表可知，公司每周需40吨货车3车次配送，司机4人次，所需工资800元，运输总里程为1266.6千米，消耗的柴油569.97升，所需燃油费2963.84元，一共花费4963.84元。

通过实例验证，节约算法原理简单、易于理解，能够起到一定的优化作用[26]。它一方面体现出优化运输过程，与一般方法相比缩短了运输路程；另一方面，它也体现了物流配送网络的优势，实现了企业物流活动的整合，而且思路简单清晰、便于执行，表明节约式算法在配送运输过程中，可以为现实决策提供参考[27]，它比其他运算方法更加适合企业尤其是科技薄弱、规模较小的中小企业应用于车辆路径问题的优化应用中[25]。

4.4三种优化方案比较分析

由上文可知，通过节约算法，扫描算法和改进后的最近插入法分别对配送线路进行优化，可得到三种不同的优化方案，因此我们需要通过一系列指标来评价方案的优劣性。本文将以所需车辆数，行驶总里程，总油耗，人力资源和总费用这些指标，对三种优化后的方案进行评价分析，如表4-8所示。本文假设40吨的车每公里油耗为0.45升，司机的工资每车次200元,柴油价为5.2元每升。

表4-8三种方案优化结果对比分析表

根据上表的纵向比较得知：

我们发现改进后的插入法节约里程数为1727.4km，每项指标都不比优化前节省。

扫描算法可节约里程数为157.5km，可算出可节约油耗70.88升，所以每月总共可节约368.58元。

节约算法的节约里程数为282.9km，可算出可节约油耗127.31升，节约算法可少雇用一个司机，所以每月总共可节约1162.02元。

根据上表的横向比较得知：

从车次需求数的角度来看，只有运用节约算法优化后的方案与优化前方案相比较节约了25％的车次需求。优化后的方案使用更少的车次，减少了用车紧张进而租车情况的出现，使公司车辆安排使用上具有更大弹性。因此，在用车角度上考虑，节约算法优化后的方案比其他方案合理。

从总运输里程角度考虑，优化后的三种方案的总运输里程分别为1266.6千米，1392千米，1727.4千米，与原方案的1549.5千米相比较，只有前两种方案减少了车辆行驶的里程数，可以减少公司车辆的损耗和资源的浪费，给公司带去更多的效益。因此，从运输里程的角度考虑，优化后的方案节约算法最优，扫描法次之，改进后的最近插入法不可取。

从燃油消耗的角度考虑，优化后的三种方案的消耗分别为569.97升，626.4升，777.33升，与原方案的697.28升相比较，只有前两种方案降低了油耗量，而运用改进后的插入法优化后的方案消耗更多的油耗。配送线路优化后，不仅能减少公司燃油费用的支出，还能降低社会资源的浪费。因此，从燃油消耗的角度上考虑，节约算法最优，扫描法次之，改进后的最近插入法不可取。

从公司人力资源消耗角度来考虑，优化后的方案所需司机依次为4，5，7人次，减少人力的消耗为1，0，-2人次。只有节约算法能使公司在人员安排上将更具有弹性，还能降低公司费用的支出。因此，从人力资源消耗的角度考虑，节约算法最优，扫描算法次之，改进后的最近插入法不可取。

从支出的总费用角度来考虑，优化后的方案的费用支出依次7542.12元，5757.28元，4963.84元，与原方案的6125.86元相比较，改进后的插入法优化后的方案花费更多的费用支出。因此，从支出总费用的角度考虑，节约算法最优，扫描法次之。

结合车次需求数，总运输里程，燃油消耗，人力资源消耗，支出的总费用五个角度的分析，节约算法最优。但是，本文的配送距离略有超出配送最佳范围，模型存在着一定的缺陷。在计算过程中也将一些因素理想化了，与实际情况不完全相符。例如，并未考虑具体的道路信息，运输规章，车辆的成本及日常维护等。因此，帝峰模具还应该根据实际情况合理选择配送方案。

结论

帝峰模具为了推广品牌，扩大市场，对小客户实施了进行送货上门服务。但随之而来的就是配送成本的问题，公司为保持正常的盈利，降低配送成本则势在必行，这就意味着公司要对原配送路线进行优化。

本文针对帝峰模具有限公司9个县市配送状况进行了线路规划，应用了节约算法、扫描算法及改进的最近插入法三种方法进行了计算分析，经过比较3种结果，选择出了一个最优方案，经过效益分析，证明经过优化后的配送里程数缩短了282.9km，节约燃油127.31升，从而降低了运输费用大概862.02元，除此以外，减少发车次数1次，司机1人次，辆闲置下来的货车和司机还可以应对一些紧急情况，提高了公司的服务质量。

求解车辆路径问题的方法非常丰富，本文采用了3种方法虽然都能够得到可行的配送运输路径方案，但是只能是可行解而不是精确解。节约算法，扫描算法和改进后的最近插入法都是解决VRP模型的算法。这类算法虽然能够比较快的解决有关问题，但其优劣往往取决于算法设计者的实际经验以及处理样本空间的大小。在实际求解过程中，应根据各类算法的使用范围，并针对配送优化问题的具体情况，寻找最适合的求解方法，找到最优配送路路线。

对于大部分企业来说，配送成本最低和满足客户对时间的高要求是配送中急需解决的问题，这都需要研究物流配送路径优化模型和算法来解决。从配送中心到客户位置的物流在配送领域是一个负载的调度问题。如果能通过比较科学的物流配送路径优化模型和算法，来实现企业的人工调度和车辆安排，使得物流中心本身运作效率更高，成本控制得当，企业的效益也会不断提升。

在物流快速发展的大背景下，帝峰模具有限公司要充分运用物流理论，与实践相结合，同时考虑到时代赋予产品特殊的意义，积极拓展自己的经营方式，与第三方物流公司保持积极地合作，给企业注入新的血液和活力。在实际运用中，一个理智的企业往往会考虑各种影响因素，这就需要用多种因素加权组合的方法来进行运输路线的优化。企业考虑的影响因素有非常重要、重要、次重要、不太重要等划分。企业可以根据自己的需要，调整后作出决策，以反映企业优化运输路线时的评价标准。这篇文章只介绍了基于距离和时间的优化问题，如果考虑多种影响因素，也可以对多种因素设定限制条件的方法来解决[28]。

致谢

这篇文章的选题、撰写和修正都得到了指导老师的倾心指导和多次修正，借此机会向尊敬的老师道一声感谢。在此期间，她渊博的知识、执着的学术追求、和蔼的态度、豁达的胸怀总是能使我在困惑的时候柳暗花明、如沐春风。从她身上不仅学会了知识，也学会了怎样更好的做人，那就是真诚待人、乐观宽容。还要感谢管理学院的诸多老师，四年的时间使我们之间有了深厚的感情，有了他们的辛苦付出才有我们的健康成长，在此衷心的道一声：你们辛苦了！

此外，还要向武汉帝峰模具有限公司的前辈和同事们道一声感谢！感谢他们在我实习这段时间里对我的帮助和照顾，是他们在我理论联系实际的道路上指明了方向，给了我无私的建议和指导，令我受益匪浅。

经过几个月来的广泛搜集资料，参考大量文献，归纳总结写出了这篇论文，也向有关专家表示感谢。

参考文献

[1]王华东，李巍.粒子群算法的物流配送路径优化研究[J].计算机仿真,2012年5月第29卷第5期

[2]HaixingWang,GuipingXiao,ZhenWei,TingguiChen.OptimizingRouteforHazardousMaterialsLogisticsBasedonHybridAntColonyAlgorithm[J].DiscreteDynamicsinNatureandSociety,2013,2013:.

[3]许星.物流配送路径优化问题的研究[J].浙江大学硕士学位论文，2006

[4]YaohuaDeng,XialiLiu,ZhihangZheng,QiaofenZhang,LimingWu.ANewActiveContourModelingMethodforProcessing-pathExtractionofFlexibleMaterial[J].Optik-InternationalJournalforLightandElectronOptics,2016,:.

[5]FranoisNicot,LucSibille,Pierre-YvesHicher.Micro–macroanalysisofgranularmaterialbehavioralongproportionalstrainpaths[J].ContinuumMechanicsandThermodynamics,2015,271-2:.

[6]杨志清.城市快递配送条件下的多目标车辆路径优化研究[D].哈尔滨工业大学硕士学位论文，2015.

[7]张志宏.物流路径选择与企业收入的关系建模过程仿真[J].计算机仿真2014年3月第31卷第3期

[8]赵世安.带装载量约束的物流配送车辆路径优化研究[J].长春师范大学学报,第34卷第8期2015年8月.

[9]张文华.基于节约里程法的物流配送路线优化[J].物流工程与管理,2012年第34卷第3期总第213期.

[10]李珍萍，周文峰.物流配送中心选址与路径优化问题——建模与求解[M].机械工业出版社，2014.

[11]石兆.物流配送选址-运输路径优化问甄研究[D].中南大学博士学位论文，2014

[12]王洪川.基于改进蚁群算法的物流路径优化问题研究[D].东北大