德邦物流配送线路优化研究
[摘要] 伴随着国内经济的快速发展，作为国家重点扶持的物流产业也快速成长起来。物流市场在壮大的同时也面临着金融危机来袭、市场竞争日趋激烈等不利因素，这既是我国物流企业带来机遇，又是巨大的挑战。本文用首先简短的文字介绍了德邦物流公司的基本情况及在配送线路中存在的问题，对物流配送线路优化目标和方法进行了简单概述，然后对物流配送线路优化的方法进行了简单的概述，最后通过节约算法，改进后的插入法，扫描法这三种方法对配送线路进行了优化，提出物流配送线路优化的方案，并且得到了相对满意的结果。优化后的配送线路有效提高了德邦物流公司的作业效率，降低物流成本，从而提升企业的经济效益，并让德邦能够在激烈的竞争市场立足，同时，也可以给同类企业乃至行业提供参考。
[关键词]：德邦物流 配送线路优化 节约里程法
Research on logistics distribution routing optimization Debang
[Abstract] Along with the rapid development of domestic economy, as the national key support of the logistics industry also rapidly grow up. Logistics market in growing at the same time is faced with the financial crisis hit, the unfavorable factors such as market competition becomes more intense, it is the opportunity of logistics enterprises in our country, is a huge challenge. Gravels with brief text first introduced the basic situation of the logistics company and the problems existing in the distribution line, the goal and the methods of logistics distribution route optimization has carried on the simple overview, and then to the logistics distribution route optimization method to carry on the simple summary, finally through the saving algorithm, the improved insert method and scanning method of these three methods are optimized for distribution lines, logistics distribution route optimization scheme is put forward, and a relatively satisfactory results are obtained. Optimized distribution lines effectively improve the gravels logistics company's efficiency, reduce logistics costs, thereby improve enterprise economic benefits, and gravels can in the fierce market competition, at the same time, also can provide a reference for similar enterprises and even the industry.
[keyword]: Debang logistics Distribution route optimization Save mileage method
目录
引言
城市物流因其在城市经济和居民生活中的重要作用，越来越受到广大学者的关注，成为当前物流研究的一种重要领域。城市物流配送体系的构建主要是以城市道路网为载体，以主要的物资生产地、集散地为依托，通过构建具有合理规模、优良服务、先进技术的网络，为居民生活、城市管理、商业贸易等提供高效的、优质的物流配送服务，实现物流配送的快速化、专业化，配送过程的的规模化、集约化、多样化。
物流产业作为现代社会的新兴产业，已经成为社会发展不可或缺的主要动力，而货物的配送是各个物流企业运作的重要环节，如何优化配送线路，为企业节约时间成本和人力物力，更是企业研究的重中之重，因此本文就德邦物流的配送线路优化问题进行了简单的概述和研究，文中以德邦物流公司为例，旨在提高德邦物流公司的作业效率，降低物流成本，从而提升企业的经济效益，并让德邦能够在激烈的竞争市场立足，同时，也可以给同类企业乃至行业提供参考。
本论文针对德邦物流配送线路优化进行研究，一共分为四部分介绍。第一部分是引言；第二部分是对德邦物流公司的简介，其中介绍了德邦物流公司的概况、德邦物流公司的业务简介、德邦物流公司配送线路的情况，第三部分是配送线路优化的方法综述；第四部分是对德邦物流公司配送线路的优化方案计算，包括基于节约里程法的德邦物流公司厦门市内运输分析、改进后插入启发式算法和扫描算法的配送优化方案计算，通过多种方法结合，来研究德邦物流公司的配送线路优化问题，系统通过系统的定量计算方法来探索出德邦物流企业配送线路的较满意方案。
第1章 德邦物流公司简介
1.1德邦物流公司概述
德邦是国家“AAAAA”级物流企业，主营国内公路零担运输业务，创始于1996年。截止2013年3月，公司已在全国31个省级行政区开设直营网点 2900多家，吸纳就业人员达27000人，日均货物流通量达到三万吨的大型物流企业。服务网络遍及全国，自有营运车辆5400余台，全国转运中心总面积超过85万平方米。
公司始终以客户为中心随时候命、持续创新，始终坚持自建营业网点、自购进口车辆、搭建最优线路，优化运力成本，为客户提供快速高效、便捷及时、安全可靠的服务体验，助力客户创造最大的价值。
公司秉承“承载信任、助力成功”的服务理念，保持锐意进取、注重品质的态度，强化人才战略，通过不断的技术创新和信息化系统的搭建，提升运输网络和标准化 体系，创造最优化的运载模式，为广大客户提供安全、快速、专业、满意的物流服务。一直以来，公司都致力于与员工共同发展和成长，打造人企双赢。在推动经济 发展，提升行业水平的同时，努力创造更多的社会效益，为国民经济的持续发展，和谐社会的创建做出积极贡献，努力将德邦打造成为中国人首选的国内物流运营商，实现“为中国提速”的使命。
目前，德邦物流公司的业务主要以汽运为主，占到75%以上，空运占的比例不足25%，并且近年来，汽运业务增长快速，空运业务增长缓慢。为此，德邦物流公司陆续开发了“精准卡航、精准城运、精准汽运、精准空运”等品牌产品，此外还有保价运输、代收客户货款、安全包装等辅助业务，增加企业利润。
面对国内广阔的物流市场，德邦物流公司仅仅瞄准了物流行业的一小块区域零担物流，核心的地方定位在30公斤—1吨的货量。因为，30公斤以下的货物，快递公司做得更专业，1吨以上的整车运输做的更专业，而德邦是把30公斤—1吨这种比较零散的货物的运输作为企业的一个专长进行发展。明确目标，发挥自己的特点，抓住发展的机遇，德邦物流公司才会发展如此迅速。
1.2德邦物流配送线路现状
目前德邦物流公司在全国30个省、市、自治区开设营业网点3000多家，服务网路遍及国内500多个城市和地区，覆盖全国90%的经济中心和人口，但相对集中在东部沿海发达城市，中西部偏远山区因为经济发展程度相对落后，货量较小，架设网点收益较低。因此，中西部薄弱地区的网点稀疏，不利于企业配送货场的建设，同时，开往此地的车辆空载率偏高，造成了浪费。本文以德邦物流在厦门市的配送线路现实情况进行分析。
已知厦门德邦物流公司公司位置为0点，分别向周围编号为1、2、3、4、5、、6、7、8、9共9个小客户点配送汽车配件，其拥有一辆7吨的车和两辆11吨的车，7吨卡车最大容量为300个汽车配件，11吨卡车最大载量为500个。设各点间的距离为
，节约距离为
。各点需求量为
，每辆车的行驶里程为
，
公里，客户点1，2，…，9。如表1-1
表1-1 各点的需求量和配送距离
|
客户 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
需求量（个/日） |
180 |
120 |
120 |
60 |
80 |
220 |
70 |
90 |
200 |
|
配送距离（km） |
7.59 |
8.92 |
18.67 |
17.03 |
5.7 |
15.38 |
8.7 |
8.15 |
8.25 |
（资料来源：厦门德邦物流信息系统）
各配送线路的里程，所需司机数量的基本情况如表1-2所示
表1-2 配送信息表
|
路线 |
运距 |
运货量 |
车型 |
司机 |
|
0-1-2-0 |
21.37km |
300 |
7吨货车 |
1 |
|
0-3-4-0 |
37.34km |
180 |
7吨货车 |
1 |
|
0-5-6-0 |
31.54km |
300 |
7吨货车 |
1 |
|
0-7-8-0 |
20.27km |
160 |
7吨货车 |
1 |
|
0-9-0 |
16.50km |
200 |
7吨货车 |
1 |
（资料来源：厦门德邦物流信息系统）
由上表可知，公司每日需7吨货车5车次配送，司机5人次，运输总里程为127.02千米。
1.3德邦物流企业配送过程中存在的问题
从当前我国物流配送的现状来看，厦门德邦物流公司的业务流程的信息化程度还是比较高的，实现了下游客户的电子要货，企业内部也实现了信息化管理。但是从供应链管理的角度来看，也仅仅是处于物流配送供应链管理的理论阶段，还有很多需要完善的环节。我们今天主要来介绍厦门德邦物流在配送和配送线路上存在的问题。
1. 对流运输。对流运输亦称相向运输、交错运输，是指同一种货物，或彼此间可以互相代用而又不影响管理、技术及效益的货物，在同一线路上或平行线路上作相对方向的运送，而与对方运程的全部或一部分发生重迭交错的运输称对流运输。已经制定了合理流向图的产品，一般必须按合理流向的方向运输，如果与合理流向图指定的方向相反，也属对流运输。
2. 返程或起程空驶空车无货载行驶，可以说是不合理运输的最严重形式。在实际运输组织中，有时候必须调运空车，从管理上不能将其看成不合理运输。但是，因调运不当，货源计划不周，不采用运输社会化而形成的空驶，是不合理运输的表现。
3. 迂回运输。迂回运输是舍近取远的一种运输。可以选取短距离进行运输而不办，却选择路程较长路线进行运输的一种不合理形式。
4. 重复运输。它是指本来可以直接将货物运到目的地，但是在未达目的地之处，或目的地之外的其他场所将货卸下，再重复装运送达目的地，这是重复运输的一种形式。另一种形式是，同品种货物在同一地点一面运进，同时又向外运出。重复运输的最大毛病是增加了非必要的中间环节，这就延缓了流通速度，增加了费用，增大了货损。
5. 倒流运输倒流运输。它指的是指货物从销地或中转地向产地或起运地回流的一种运输现象。其不合理程度要甚于对流运输，其原因在于，往返两程的运输都是不必要的，形成了双程的浪费。倒流运输也可以看成是隐蔽对流的一种特殊形式。
6. 过远运输过远运输是指调运物资舍近求远，近处有资源不调而从远处调，这就造成可采取近程运输而未采取，拉长了货物运距的浪费现象。过远运输占用运力时间长、运输工具周转慢、物资占压资金时间长、远距离自然条件相差大。
当然德邦物流也还存在着：诚信度不高，不够负责；机械化程度不高；物流工作人员的工作效率低；物流成本过高的问题不作为本文的重点研究对象。
1.4 配送线路优化的意义
配送运输由于配送方法的不同，其运输过程也不尽相同，影响配送运输的因素很多，如车流量的变化、道路状况、客户的分布状况和配送中心的选址、道路交通网、车辆定额载重量以及车辆运行限制等。配送线路优化就是整合影响配送运输的各种因素，适时适当地利用现有的运输工具和道路状况，及时、安全、方便、经济地将客户所需的商品准确地送达客户手中。在配送运输线路设计中，需根据不同客户群的特点和要求，选择不同的线路设计方法，最终达到节省时间、运距和降低配送运输成本的目的。选择合的理配送路线，对德邦物流和社会都具有很重要的意义。
配送线路优化对德邦物流来说，(1)优化配送路线，可以减少配送时间和配送里程，提高配送效率，增加车辆利用率，降低配送成本。(2)可以加快物流速度，能准时、快速地把货物送到客户的手中，提高客户满意度。(3)使配送作业安排合理化，提高企业作业效率，有利于德邦物流在同行中的提高竞争力与效益。
配送线路优化对社会来说，它可以节省运输车辆，减少车辆空载率，降低了社会物流成本，对其他企业尤其是生产企业具有重要意义。与此同时，还能缓解交通紧张状况，减少噪声、尾气排放等运输污染，对民生和环境也有不容忽视的作用。
第2章 配送线路优化的方法综述
通过查找资料和咨询论文指导老师，了解了关于线路优化的方法有以下几种精确优化方法，启发式算法，模拟方法，交互优化法，吞圈法，插入法，扫描法，当然还有一些我不知道的，从以上方法中我采用个人比较了解和熟悉的方法是节约里程法、改进后的最近插入法和扫描法。我用这三种方法对德邦物流公司配送系统的优化方案进行优化，其基本原理、优缺点。适用范围、计算方法如下文介绍。
2.1节约算法
2.1.1 节约算法的原理
节约算法（Saving Algorithm）是用来解决运输车辆数目不确定的VRP问题，它是目前用来解决VRP模型最有名的启发式算法。
节约算法的优点：是一种简便易行的方法，一方面体现出优化运输的过程，与一般方法对比缩短了运输路程；另一方面。它也体现了物流配送网络的优势，实现了企业物流活动的整合，而且思路清晰简单，便于试行。
节约算法的缺点：①过于强调节约路程，而没有考虑行程中的时间因素。②不能对顾客的需求进行灵活多变的处理，节约算法更适合需要需求稳定或需求的时间不紧迫，这显然不能满足现代多变的市场环境。
节约算法的核心思想是将运输问题中存在的两个回路（0，… ，i，0）和（0，j，… ，0）合并成一个回路（0，… ，i，j，…，0）。在上面的合并操作中，整个运输问题的总运输距离会发生变化，如果变化后总运输距离下降，则称节约了运输距离。相应的变化值，叫做节约距离
，如式（1）所示。
（1）
调整过程如图2-1所示。
|
j |
|
0 |
|
i |
|
0 |
|
i |
|
j |
|
|||||||||||||
|
|||||||||||||
|
|
|
|||||||||||
|
|
||||||||||||
调整前 调整后
图2-1 节约算法的图像描述
2.1.2 节约里程算法主要步骤
已知条件:需求点集
={1,2,…, n},各点需求量
,各点间最短距离
。
第一步,形成一个初始解。确定各车辆配送点集
令
, 
=1,2,…,n (先采取单点配送)。
第二步,进行节约度的计算。计算所有点对的节约度 
，然后对计算结果进行升序排列。
第三步，进行回路的合并。从升序排列的节约度序列中的最上面的值开始，直到节约里程
的队列空为止,重复下列步骤:按照节约里程
队列从大到小的顺序,分析客户i和j之间合并的可能性(是否满足装载限制条件、不在同一路径内以及合并次数不超过2),将i, j连接起来,即可令
。如果不是这样,则从节约里程队列中去除当前的节约里程，分析下一个客户对。
2.2 改进后的最近插入法
TSP模型是单回路运输问题的最为典型的一个模型，它的全称是Traveling Salesman Problem1，中文叫做旅行商问题。它是一个典型的NP-Hard问题，对于大规模的线路优化问题，无法获得最优解。最近插入法就是一种解决此问题的启发式算法。
最近插入法是Rosenkrantz和Stearns等人在1977年提出的一种用于解决TSP(旅行商)问题的算法。
基于参考点的插入法对参考点的选择有很大的依赖性，一个简单的改进方法是基于多个随机参考点进行的多次搜索，进而选出性能最好的解，但这显然势必会大大增加搜索量，另外对于大规模问题参考点的位置的改变对性能的改进也很有限。
最近插入法由四步完成：
（1）找到
最小的节点
，形成一个子回路（subtour），
。
（2）在剩下的节点中，寻找一个离子回路中某一节点最近的节点
。
（3) 在子回路中找到一条弧（i，j）,使得
+
-
最小，然后将节点
插入到节点
，
之间，用两条新的弧(i，k)，（k，j）代替原来的弧（i，j），并将节点
加入到子回路中。
（4）重复步骤（2）、（3），直到所有的节点都加入到子回路中。
这样，子回路就演变为了一个TSP的解。
由于最近插入法解决的是单回路运输问题，故在此方法基础上进行改进和修正，使其能解决多回路运输VRP问题。有改进的方法如下：
（1）找到
最小的节点
，形成一个子回路（subtour），
。
（2）在剩下的节点中，寻找一个离子回路中某一节点最近的节点
。若此时回路的总货运量未超过车的载重限制，则继续步骤（3），否则，转（1）寻找新的一条回路。
（3）)在子回路中找到一条弧（i，j）,使得
+
-
最小，然后将节点
插入到节点
，
之间，用两条新的弧(i，k)，（k，j）代替原来的弧（i，j），并将节点
加入到子回路中。若此时该回路的总路程为未超过车辆的行程限制，则继续步骤（4），否则转步骤（1），寻找新的一条回路。
（4）重复步骤（2）和（3），直到每一个节点都被归入某一个子回路中。
2.3 扫描算法
扫描算法（Sweep Algorithm）是Gillett和Miller在1974年首先提出来的，它也是用于求解车辆数目不限制的CVRP问题。扫描法分为先分组后路径和先路径后分组两种，本文采用的是先分组后路径的方法。
扫描法是一种逐次逼近法，该方法不一定能求得物流配送车辆路劲优化问题的最优解，但是能有效的求得问题的满意解。对于某个具体的物流配送车辆路径优化问题，由于存在多种客户编号方法，当仅选择一种客户编号方案用扫描法求解时，其计算量相对较小，但相应的解的质量可能不会很高；当选用多种客户编号方案用扫描法求解时，一般能得到质量很高的满意解，但相应的计算量会成倍增加。研究表明，对于物流配送车辆线路优化问题，当每条线路上的客户数目大体相同且配送路线不太多时，用扫描法求解是非常有效的。
扫描算法分四个步骤完成：
（1）以起始点
作为极坐标系的原点，并以连通图中的任意一顾客点和原点的连线定义为角度零，建立极坐标系。然后对所有的顾客所在的位置，进行坐标系的变换，全部都转换为极坐标系。
（2）分组。从最小角度的顾客开始，建立一个组，按逆时针方向，将顾客逐个加入等到组中，直到顾客的需求总量超出了负载限制，然后建立一个新的组，继续按逆时针方向，将顾客继续加入到组中。
（3）重复（2）的过程，直到所有的顾客都被分类为止。
（4）路径优化。对各个分组内的顾客点，就是一个个单独的TSP模型的线路优化问题，可以用前面介绍的TSP模型的方法对结果进行优化，选择一个合理的线路。
第3章 德邦物流配送线路优化设计
3.1 线路优化基础数据处理
根据上文德邦物流的配送线路现状，我们已知n=9,m=3,W1=7,W2=W3=11，L1=L2=L3=60，令W4 =W5 =W6 =W7 =W8 =W9 =7，L4 =L5 =L6 =L7 =L8 =60
下图3-1为德邦物流与顾客分布的连通图
|
15.38 |
|
3.42 |
|
9.14 |
|
12.68 |
|
8.15 |
|
11.57 |
|
8.33 |
|
5.7 |
|
8.25 |
|
7.59 |
|
8.92 |
|
10.72 |
|
12.01 |
|
1.6.4 |
|
9.73 |
|
4.86 |
|
15.47 |
|
0 |
|
1 |
|
2 |
|
3 |
|
4 |
|
5 |
|
6 |
|
8 |
|
7 |
|
9 |
图3-1 德邦与顾客点分布的连通图
解：（1）通过各点之间的最短距离计算,我们得到了个点间的最短距离,如下表3-1中所示：
表3-1 各点间的最短距离表
|
县市 |
V0 |
V1 |
V2 |
V3 |
V4 |
V5 |
V6 |
V7 |
V8 |
V9 |
|
V0 |
0 |
7.59 |
8.92 |
18.06 |
16.42 |
5.70 |
15.38 |
11.57 |
8.15 |
8.25 |
|
V1 |
|
0 |
4.86 |
14.59 |
16.23 |
13.29 |
22.97 |
19.16 |
15.74 |
15.47 |
|
V2 |
|
|
0 |
9.73 |
11.37 |
14.62 |
23.38 |
20.49 |
17.07 |
17.17 |
|
V3 |
|
|
|
0 |
1.64 |
12.36 |
13.65 |
21.98 |
25.22 |
26.31 |
|
V4 |
|
|
|
|
0 |
10.72 |
12.01 |
20.34 |
23.58 |
24.67 |
|
V5 |
|
|
|
|
|
0 |
21.08 |
17.27 |
13.85 |
13.95 |
|
V6 |
|
|
|
|
|
|
0 |
8.33 |
11.57 |
20.71 |
|
V7 |
|
|
|
|
|
|
|
0 |
3.42 |
12.68 |
|
V8 |
|
|
|
|
|
|
|
|
0 |
9.14 |
|
V9 |
|
|
|
|
|
|
|
|
|
0 |
3.2 基于节约算法的企业配送路线优化
利用节约法确定配送路线的主要出发点是，根据配送中心的运输能力和配送中心到各个用户以及各个用户之间的距离来制定使总的车辆运输的吨公里数最小的配送方案。另还需满足以下条件；（1）所有用户的要求；（2）不使任何一辆车超载；（3）每辆车每天的总运行时间或行驶里程不超过规定的上限；（4）用户到货时间要求。
节约里程数是由公式
，i,j=0,1,2,3,4...9计算得出，计算结果如下所示：
0 11.65 11.06 7.78 0 0 0 0 0.37
0 17.25 13.97 0 0.92 0 0 0
0 32.84 11.4 19.79 7.65 0.99 0
0 11.4 19.79 7.65 0.99 0
= 0 0 0 0 0
0 18.62 11.96 2.92
0 16.3 7.14
0 7.26
0
（1）将
按从小到大的顺序排列如下表3-2所示：
表3-2 
排序表
|
Vi ，Vj |
|
Vi ，Vj |
|
Vi ，Vj |
|
|
3-4 |
32.84 |
1-2 |
11.65 |
7-9 |
7.14 |
|
3-6 |
19.79 |
3-5 |
11.4 |
6-9 |
2.92 |
|
4-6 |
19.79 |
4-5 |
11.4 |
3-8 |
0.99 |
|
6-7 |
18.62 |
1-3 |
11.06 |
4-8 |
0.99 |
|
2-3 |
17.25 |
1-4 |
7.78 |
2-6 |
0.92 |
|
7-8 |
16.3 |
3-7 |
7.65 |
1-9 |
0.37 |
|
2-4 |
13.97 |
4-7 |
7.65 |
|
|
|
6-8 |
11.96 |
8-9 |
7.26 |
|
|
（2）按
从大到小合并路径
①对
, 
, 
令
,
,
，
②对
，
，
，
，
，
，
，
，
③对
，
，
，
，∴不满足合并条件
④对
，
，
，
，
，
，
，
，
⑤对
，
，
，∴不满足合并条件
⑥对
，
，
，
∴不满足合并条件
⑦对
，
，
，
∴不满足合并条件
⑧对
，
，
，与⑥同理，不满足合并条件
⑨对
，
，
，
，
，
，
⑩对
，
∴不满足合并条件，同理
时，也不符合满足条件
⑪对
，
，
，
∴不满足合并条件，同理
也不满足合并条件
⑫对
，
与
已经在同一个回路中，
同理
，
与
也已经在同一条回路中
⑬对
，
，
，
令
，
，
，
⑭对
，
不符合合并条件，同理
，
，
，
也不符合合并条件
⑮对
，
，
，
∴不满足合并条件
∴最终的配送路径为
，即
，
，
，即
，
，
，即
，
，
，即
，
，
最后得到的最优结果如表3-3所示。
表3-3 节约法优化结果表
|
路线 |
运距 |
运货量 |
车型 |
司机 |
|
0-3-4-6-7-0 |
51.61km |
470 |
11吨货车 |
1 |
|
0-1-2--0 |
21.37km |
300 |
7吨货车 |
1 |
|
0-8-9-0 |
25.54km |
290 |
7吨货车 |
1 |
|
0-5-0 |
11.4km |
80 |
7吨货车 |
1 |
由上表可知，需4车次配送，司机4人次，运输总里程为109.92km。如图3-2所示
|
0 |
|
1 |
|
2 |
|
3 |
|
4 |
|
5 |
|
6 |
|
8 |
|
7 |
|
9 |
图3-2 优化线路图
3.3 基于改进的最近插入法的企业配送路线优化
插入法用于求解车辆路线问题的方法，其结合最邻近法与节省法的观念，依序将顾客点插入路径中以构建配送路线。该方法首先将节省值的观念应用于循序路线建立上，首先以离场站最近的需求点作为路线的种子点，再根据最邻近点插入法的概念，以插入值最小者作为下一个插入点，最后再用一般化节省值公式，以其中节省值最大者來决定插入的位置，重复进行选取与插入的步骤，直到超过车辆容量或路程限制时，再建立另一条路线。
插入法的计算步骤如下：
① 令T={0},N={0，1，2……,9}，比较表4-2 中从0出发的所有路径大小。因为，所以就有顾客点0，5构成一个子回路，
，此时
，
。
② 在剩余顾客点（1，2，3，4，6，7，8，9）中寻找到0和5中某一点的最小距离，
，
,因为
，所以在子回路
插入点1。由于对称性，无论将1插入到0和5之间往返路径中，结果都是一样的，这样，构成了一个新的子回路
，
，
。
③ 再次寻找剩余顾客点到0，1， 5中某一点的最小距离：可知最小距离为
，此时, 
，因为
，所以在子回路
插入点2。
④ 将点2分别插入（0，1），（1，5），（5，0）中，比较得：插入到（1，5）中增量最小，
。
此时构成了一个新的子回路
，
，
。
⑤ 再次对剩余的顾客点按照上诉方法进行优化，可构成另子回路
和子回路
利用改进的最近插入法得到优化结果如表3-4所示，优化线路结果如图3-3所示。
表3-4 改进的最近插入法优化结果
|
路线 |
运距 |
运货量 |
车型 |
司机 |
|
0-1-2-5-0 |
32.77km |
380 |
11吨货车 |
1 |
|
0-3-4-6-0 |
43.84km |
470.9 |
11吨货车 |
1 |
|
0-7-8-9-0 |
29.51km |
323.8 |
11吨货车 |
1 |
由上表可知，需司机3人次，运输总里程为106.12km。优化以后得线路如图3-3所示。
|
0 |
|
1 |
|
2 |
|
3 |
|
4 |
|
5 |
|
6 |
|
8 |
|
7 |
|
9 |
图3-3 优化线路图
3.4 基于扫描算法的企业配送路线优化
扫描法分为两阶段性步骤：
第一阶段：利用极坐标来表示各需求点的区位，然后任取一需求点为起点，以车辆容量为分群的约束，再以该需求点为零度按顺时针或逆时针的方向，进行顾客的扫描分群。
第二阶段：依据求解旅行商问题的算法，求解各顾客群的排程。
关于扫描算法的企业配送线路优化，我们通过以不同客户为起始点进行扫描计算分析并比较，我们得到的最优方案是以1为起始点的方案，计算如下图3-4所示：
|
0 |
|
1 |
|
2 |
|
3 |
|
4 |
|
5 |
|
6 |
|
8 |
|
7 |
|
9 |
图3-4 优化线路图
< >建立极坐标系，以O为极坐标系的原点分组。从角度为零向逆时针方向进行扫描，第一个被分组的是顾客1，Load1=180；继续转动，下一个被分组的是顾客2，Load1 =300。由于负载还没有超过限制Loadlimit =500，继续转动。下一个被分组的是顾客5，Load1 =380，继续转动；下一个被分组的是顾客3，，Load=500；于是这段路径已经达到最大限度，需要一个新的组，这样在第一个组里面只有顾客1、2、5、3。在第二组中有顾客4、6、7、8，Load2 =440。继续上面的步骤，第三组中有顾客9，Load3 =200，至此所有的顾客都被分配完毕。分组结果如下图3-5：
|
0 |
|
1 |
|
2 |
|
3 |
|
4 |
|
5 |
|
6 |
|
8 |
|
7 |
|
9 |
图3-5 扫描法分组图
< >组内的线路优化。对上面三个组都已经是一个单回路运输问题，下面用最近邻点启发式算法进行路径优化：先令
，
，
，
，
路线为0—1—2—3—5—0
由表3-1可知3、4、5、9之间的距离。则
先令
，
，
，
，
路线为0—4—6—7—8—0
由表3-1可知0、9之间的距离。则
路线为0—9—0
优化线路结果如下表3-6所示。
表3-6 改进的最近插入法优化结果图
|
路线 |
运距 |
运货量 |
车型 |
司机 |
|
0-1-2-3-5-0 |
40.24km |
500 |
11吨货车 |
1 |
|
0-4-6-7-8-0 |
48.33km |
440 |
11吨货车 |
1 |
|
0-9-0 |
16.5km |
200 |
7吨货车 |
1 |
由上表可知，需司机3人次，运输总里程为105.07km。
3.5 三种配送线路优化分案比较分析
关于德邦物流的线路优化研究，我们用了节约算法、改进后的插入算法、扫描算法三种方法进行计算，我们通过表3-7进行了简单的比较，并选出较为满意的配送方案。
表3-7 3种方案比较分析表
|
状态 |
优化前 |
优化后 |
|||
|
节约算法 |
改进后的最近插入法 |
扫描算法 |
|||
|
各车型车次(次) |
7t |
5 |
3 |
0 |
1 |
|
11t |
0 |
1 |
3 |
2 |
|
|
总运输里程(km) |
127.02 |
109.92 |
106.12 |
105.07 |
|
|
节约里程数（km） |
|
17.1 |
20.9 |
21.95 |
|
|
司机（次） |
5 |
4 |
3 |
3 |
|
|
节约人力（次） |
|
1 |
2 |
2 |
|
根据上表3-7我们结合车次需求数，总运输里程，人力资源消耗等角度综合比较分析，本文假设11吨的车与7吨的车油耗相等，每公里油耗为0.12升，司机的工资为每月为3500元,柴油价为7.3元每升，,。
我们发现节约算法的日节约里程数为17.1km，可算出每日可节约14.98元，每月节约449.39元，节约算法可少一个司机，所以每月总共可节约3949.39元。
改进后的插入法节约里程数为20.9km，可算出每日节约18.31元，每月为549.25元，可少2个司机，所以每月总共可节约7549.25元。
扫描算法可节约里程数为21.95km，可算出每日节约19.23元，每月为576.85元，可少2个司机，所以每月总共可节约7576.85元。
通过三者的对比我们发现扫描法优化的配送路线方案较为满意，每月可为厦门德邦物流节省7576.85元。但是，本文的配送距离略有超出配送最佳范围，模型存在着一定的缺陷。在计算过程中也将一些因素理想化了，与实际情况不完全相符。例如，并未考虑具体的道路信息，运输规章，车辆的成本及其日常维护等。
结论
在国民生产总值中，流通、物流所占的比例达到20%，就业人口的比例约占50%。在我们购买的商品的价格中，物流费用约有10%。从此也可看出物流活动对我们生活的重要性。事实与实践已经证明，由于物流能够大幅度降低企业的总成本，加快企业资金周转，减少库存积压，促进利润率上升，从而给企业带来可观的经济效益，国际上普遍把物流称为“降低成本的最后边界”，排在降低原材料消耗、提高劳动生产率之后的“第三利润源泉”，是企业整体利润的最大源泉。
本文通过对德邦物流在厦门市网点进行对调研和实地考察，对德邦物流公司配送系统的现状进行了分析，主要涉及了配送系统中的配送线路和网络、车辆调度、配送信息系统，以及操作人员等存在的问题；最后，采用定性和定量相结合的研究方法，对德邦公司的配送线路路规划、车辆调度、配送信息系统、操作人员等方面提出了优化方案，提高企业运作效率，增强了德邦在物流行业的竞争力，为企业在国内的扩张打下坚实的基础。由于本人知识有限，所以研究还不完善，尚有不少问题有待进一步研究，希望能有更多的机会学习物流知识，并学以致用。也希望老师能在我大学里的最后一份作业精心指导，为我的大学生活画下圆满的句号。
致谢语
本论文是在兰老师的悉心指导下，于2013年5月完成的，值此论文完稿之际，掩卷回首，感慨万千。一路走来，有过艰辛，有过收获，有过成长，恍然间二年本科生涯即将结束，缅怀过去，记忆中总是充满着感恩。
首先我要衷心地感谢兰老师。本论文的形成得益于老师的精心指导和帮助，论文的选题、课题研究及论文撰写、修改的全过程中无不凝聚着老师的心血，在此谨向李老师表示深深的敬意和由衷的感谢。
此外，还要感谢各位任课老师在本科学习阶段给予我的指导，对我养成科学严谨的治学作风有很大的帮助，使本人在不断提高理论研究水平过程中受益匪浅。各位老师不仅授我予文，而且教我做人，给予我终生受益无穷之道，学生由衷的感谢老师！在本论文成文之际，谨表示诚挚的感谢。
最后，我要特别感谢我的父亲，在我漫长的求学生涯中，无论生活压力有多巨大，我的父亲，这位中国千千万万人中最普通却最坚强的父亲，为我的学习和生活撑起了一方天地，让我得以顺利完成学业，他对我的支持和鼓励是我不断前进和进步的动力。此外对本论文所有参考文献的作者表示感谢。
谨以此文献给所有关心、爱护、支持和帮助过我的老师和同学们，以表达我对他们衷心的感谢和深深的祝福!
参考文献
[1] 黎鹰. 电子商务环境下物流配送问题与策略[J]中国管理信息化, 2009,(9)：71-73．
[2] 黄静. 我国连锁零售业物流配送中心发展研究[J]. 中小企业管理与科技(上旬刊), 2009,(02)：14-20．
[3] 全英华. 我国连锁企业配送中心建设存在的问题和对策[J]. 当代经济(下半月), 2006, (06)：03-05．
[4] 唐扬,刘鲁. 基于Petri网的企业业务流程集成的研究[J]北 (社会科学版), 2009,(03)：75-79．
[5] 汤世强,吴忠,陈心德. 电子商务物流配送瓶颈及解决方案[J]商业研究, 2010,(02)：51-63．
[6] 陈辉，刘春草，朱志军.物流配送管理中的路径优化问题研究[J].西安电子科技大学学报(社会科学版)，2006，16(5): 16-20.
[7] Laporte G., Nobert Y.. Exact algorithms for the vehicle routing problem.[M].Amsterdam: North-Holland.1987：45-48．
[8] 蒋琦玮，陈治亚.物流配送最短径路的动态规划方法研究[J].系统工程，2007，25（4）：27-29.
[9] 王俊珺，夏华丽，田源.物流配送路线规划中的最短路径研究[J].农业网络信息(网络与电子商务/政务)， 2007，5: 60-62.
[10] 钱颂迪.运筹学[M].北京：清华大学出版社，2002：131-163.
[11] Luis G. A result on projection for the vehicle routing problem [J]. European Journal of Operational Research, 1995(85): 610-624.
[12] 孙学农，徐辉增.物流配送车辆调度问题方法综述[J].科学信息（学术研究），2007，（12）：225-226.
[13] 谬慧芬，邵小兵.动态规划算法的原理及应用[J].中国科技信息，2005,（21）：23-30.
