电子商务配送中心运送路线规划研究

安阳师范学院本科学生毕业论文

电子商务配送中心运送路线规划研究

作 者 刘世明 系（院） 计算机与信息工程学院 专 业 信息管理与信息系统 年 级 2011级 学 号 110903038 指导教师 王瑞庆 论文成绩 日 期 2015年5月

诚信承诺书

郑重承诺：所呈交的论文是作者个人在导师指导下进行的研究工作及取得的研究成果。除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得安阳师范学院或其他教育机构的学位或证书所使用过的材料。与作者一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。

作者签名： 日期： 导师签名： 日期： 院长签名： 日期：

论文使用授权说明

本人完全了解安阳师范学院有关保留、使用学位论文的规定，即：学校有权保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存论文。保密论文在解密后遵守此规定。

作者签名： 导师签名： 日期：

目录

1 引言 ........................................................................................................................... 1 2 物流配送的功能与运送路线优化的意义 ............................................................... 2

2.1物流配送中心运输的功能 ................................................................................................ 2 2.2配送中心运输路线优化的意义 ........................................................................................ 2

3 物流配送中心运送线路优化方法 —节约里程法 ................................................. 2

3.1节约里程法概述 ................................................................................................................ 2 3.2节约里程算法基本原理 .................................................................................................... 3 3.3节约里程算法主要步骤 .................................................................................................... 3

4 以国美电器为实例应用研究 ................................................................................... 4 5 总结 ........................................................................................................................... 8 参考文献 ....................................................................................................................... 9

电子商务配送中心运送路线规划研究

刘世明

（安阳师范学院 计算机与信息工程学院 河南 安阳 455000）

摘 要：电子商务企业要在激烈的竞争中取得优势，就必须重视配送中心的作用，规划配送路线，减少运输成本。本文介绍了节约里程法在物流配送中心配送中的实际运用，对配送中心运输线路进行规划，以求选择最佳配送路线和车辆的综合调度。通过节约里程法求的运输线路省时、省费的完成了既定目标的实现，因此，节约里程法在路线规划的实现上取得了较好的效果。

关键词 ：电子商务；配送中心；运输线路；规划

1 引言

近年来电子商务的风起云涌，为我国经济的快速发展提供了契机。随着中国经济的快速发展，企业的市场占有率已近达到最大值，因此，现在企业的利润增长点主要放在如何有效降低成本中的物流费用。物流体系中成本比例最高的活动之一就是运输，伴随着国际油价的不断提高，致使我国成品油也不断上调，因此，降低运输成本已然成为企业获取更大利润的关键因素，而规划电子商务配送中心运送路线又是降低运输成本的关键[1]。目前电子商务得到各国政府和民众的大力支持，发展势头强劲，但是由于它是一套全新的技术和管理理念，所以其发展过程中必然存在一些问题。电子商务的迅速发展对物流运输的要求越来越高，物流配送体系是电子商务配送的重要环节，其配送效率的高低直接影响到电子商务行业，进而影响到企业的核心竞争力。

西方发达国家经济发展迅速，物流配送发展起步早，由于西方国家文化、科技的影响，其物流配送发展比国内要快，尤其是美国，在物流配送的发展上更是遥遥领先。美国人对运送货物的质量要求较高，对于物流配送中心提供服务的高效性、精确性及高质量研究较多。随着日本经济的发展，物流业也逐步发展起来，并且有自己独特的管理方法，在如何实现配送货物的准确性及时性等方面研究也比较多[2]。

目前我国的物流企业已经开始起步，车辆调度及配送路线问题也日益重要。但是由于我国物流业行业起步晚，发展缓慢，无法满足正常的社会需要，与此同时，对于通用的理论研究项目较少，应用型研究也不够宽泛。现在建设和营运的物流配送中心基本上是大型商场或连锁店内部服务型的，还基本上没有实现社会化的配送。我国大多数的连锁企业，不论其规模大小，多都在探索建设自己的配送中心路线问题。但是，就总体规模上来看，我国电子商

【3】

务配送中心建设仍然处于起步阶段，发展还不平衡。王静在《浅析我国市内物流配送发展》得出结论“要改变传统模式，优化配送路线”，“改变传统模式”就是打破一车一线路的送货方式，“优化配送路线”就是在原有模式下，将多条线路整合为一条，提出将配送路线过程归结为表述问题的模型，设计求解问题的算法，进一步求的配送路线的优化方案。

近几年来，我国政府和各省市政府已开始认识到物流对于推动经济发展、改善投资环境、提高地区经济和工商企业在国内外市场上的竞争能力的重要性，把发展现代物流作为一项涉及经济全局的战略性问题来抓，把发展现代物流作为经济腾飞的重要措施和支撑点之一。可

以说，当今中国，现代物流已经走到了中国经济发展的前台，成为社会的热点。 2 物流配送的功能与运送路线优化的意义 2.1物流配送中心运输的功能

配送作为一种新型的物流手段，伴随着生产的不断发展而日趋成熟。发展配送，无论对于物流系统的完善，企业的发展，还是整个经济社会效益的提高，都具有重要的作用。

（1）配送完善和优化了物流系统。第二次世界大战后，高水平的干线运输呼唤支线运输和小搬运配套，但支线运输和小搬运在适应性、灵活性、服务性上的欠缺，致使运力不合理、运输成本过高。配送的出现使干线运输、支线运输及小搬运统一，输送过程得以优化和完善。

（2）配送提高了末端物流的效益。配送通过大批量进货，集中发货，以及将多个小批量集中一起大批量发货，都能有效的节省运力，实现经济运输，降低成本，使末端的物流经济效益得到提高。

（3）配送通过集中库存使企业实现低库存或零库存。采取准时制配送方式之后，生产企业完全可以依靠配送中心的准时配送而不需保持自己的库存或保持少量安全库存而不必留有经常库存。

（4）配送简化事物，方便客服。采用配送的方式，客户只需向一处订购，或一个进货单位联系就可以订购到以往需要去许多地方才能订到的货物，因此大大的减轻了客户的工作量和负担，也节省了事务的开支。

（5）配送可以降低整个社会物资的库存水平。发展配送，实行集中库存，整个社会物资的库存总量必然低于各企业分散的库存总量。同时，配送有利于灵活高度，有利于发挥物资的作用。此外，集中库存可以发挥规模经济优势，降低库存成本。 2.2配送中心运输路线优化的意义

配送合理化与否是配送决策系统的重要内容，配送线路的合理与否又是配送合理化的关键。选择合理的配送路线，对企业和社会都具有很重要的意义。

对企业来说，(1)优化配送路线，可以减少配送时间和配送里程，提高配送效率，增加车辆利用率，降低配送成本。(2)可以加快物流速度，能准时、快速地把货物送到客户的手中，提高客户满意度。(3)使配送作业安排合理化，提高企业作业效率，有利于企业提高竞争力与效益。

对社会来说，它可以节省运输车辆，减少车辆空载率，降低了社会物流成本，对其他企业尤其是生产企业具有重要意义。与此同时，还能缓解交通紧张状况，减少噪声、尾气排放等运输污染，对民生和环境也有不容忽视的作用[4]。 3 物流配送中心运送线路优化方法 — 节约里程法 3.1节约里程法概述

节约里程法就是为完成既定的配送目标，在满足一定的约束条件下，使得运送货物所节约的距离最大即运输路线里程最短。车辆运送条件模型：

一般条件：配送中心有n辆相同车辆，要给n个客户配送货物，配送中心要派遣这些车辆到一个回路中去，在运送路线的安排和调度上，使得运送路线最短。

约束条件：订单必须全部完成；每辆车配送任务结束后必须回到配送中心；车辆的载重

量不能超过车规定的承重量。 3.2节约里程算法基本原理

节约里程算法的基本思想——设一家公司的配送中心（0）向他的两个配送点i , j批量送货，配送中心到这两个配送点的距离是已知的，分别为Coi., Coj ，i, j这两个配送点之间的距离是Cij， 并且往返所行驶的距离是相同的，则其配送总路程为：S=2（Coi+ Coj），如图1所示。

图1配送中心分别到配送点i，j距离

若采用一辆车在满足一定的限制条件的情况下连续地对i , j两个配送点批量送货，如图2所示，

图2配送中心对配送点i，j连续送货距离

这样的话就可以只需派发一辆车，即可完成配送任务，其所走路程为：S=Coi+ Cij + Coj 。根据三角形的两边之和必定大于第三边这一性质可知，Coi+ Coj > Cij 。因此，在满足限制条件的情况下，图2的配送货物方案明显要比图1的配送方案节约了配送距离，并且在同一条线路中连接的配送点越多，里程节约量就越大。其所对应的变化值，则称它为节约距离∆Cij，如式（1）所示

∆Cij=cio+coj-cji （1）

3.3节约里程算法主要步骤

已知条件:需求点集NR={1,2,„, n},各点需求量Ri,各点间最短距离cij。

第一步：确定每个用户的需求量是否超过运载车辆的承载量，若超过，则单独一辆车派送，直到小于一辆车的承载量为止，同时减去已派发车辆数目。

第二步：对节约距离进行计算。计算所有点所对应各点的节约度。

第三步：开始进行回路合并。节约距离越大，表明两个点在一条线路上总距离减少的越多，所以从第二步中的节约距离序列中的最大节约值（如果最大节约值有两个或两个以上出现相同时，可以任意选取其中一个）开始，进行回路合并。回路合并步骤:按照节约距离从大到小的顺序,分析客户i和j之间能否合并(是否满足车辆运载的约束条件、并且不在同一个路径内以及合并的次数不多于2次),可以合并的话，则把i, j连接起来,即可令Ii'=Ii⋃Ij;Ij=∅。如若不能合并,就从节约里程的队列中除去当前的节约里程，然后再分析下一个客户对物流配送中心的需求。

第四步：直到所有的配送用户均已在回路中，得到完整的配送路线，即可终止算法；否则，转至第三步；

4 以国美电器为实例应用研究

国美电器公司配送中心需要向周边九个分店用户送货，送货总量为20吨，且公司现有8吨车9辆，以公司配送中心(P0)为原点，配送中心到各个分店的路径及各点的需求量（吨）如下图、表所示，要求是设计出配送路线以完成电器到各分店的配送任务。

表 1 各用户的需求量

图 3 各用户之间的距离（单位：千米）

制定配送路线的第一步，首先安排直送，把大运送量用户用专车直送，剩下的小运量用户再统一安排配送。由图3可以看出，派一辆运载量为8吨的车为P1送8吨，剩下的4吨，与其余的小运量各用户一起安排。

表 2 新的用户需求量表

第二步，根据图3，利用节约里程算法公式∆Cij配送用户的节约里程数，如图4所示。

=cio+coj-cji，求出配送中心到各

图 4 各用户之间的节约里程数（单位：千米）第三步：具体组织回路时，总是从最大的节约里程数开始，连接用户。图4中，最大的节约里程数是20，有3个20，随便哪一个都可以，例如，我们选定P8和P9的交叉点上的20，这时候要考虑一下他们的需求量之和（1.2+1）是否小于可用车的载重量，如果大于一辆车的载重量就不能够连，如果小于一辆车的载重量就可以连。配送车辆载重量为8吨，而P8和P9的需求量之和只有2.2吨，所以可以连成一个回路即P0- P8- P9- P0，再将顶点P8和P9的节约

图 5 第一步优化结果

从上图中选出节约值最大为20，选P7和P9交叉点的20，如果连接P7和P9，则与上述线路合并，其总需求量为3，未超过一辆车的运输能力8，因此，连成回路P0- P8- P9- P7-O，再将顶点P7和P9的节约值赋为0。因为P9行的两端均已经牵上手了，所以P9行节约值全部赋值为0，结果如图6所示

图 6 第二步优化结果

继续选出最大节约值20，因为P7、P8均在上述回路中，将其节约值20赋为0。接下来最大节约值为16，将P1和P8连接，则和上述回路合并，其总需求量为7，未超过一辆车的运输能力8，因此，将P1合并到上述回路中，形成回路P0- P1- P8- P9- P7- P0，再将P1、P8节约

图 7 第三步优化结果

继续选出最大节约值15，若选定P1和P3交叉点15，则和上述回路合并，其总载重8.5吨，超过一辆车的运输能力8。因此，P1和P3不能相连，将P1、P3节约值15赋为0。再选节约值15，对应两个顶点P2和P3，P2和P3两处需求量之和为2.5吨，未超过一辆车的运输能

8所示 图 8 第四步优化结果

继续选最大节约值14，若选定P2和P4交叉点14，P2和P4可以和回路P0- P2- P3- P0合并，总需求之和为3吨，未超过一辆车的运输能力，因此，形成回路P0- P4- P2- P3- P0，且P2和P4节约值赋为0，P2行节约值赋为0。接着选最大节约值14，P4和P6交叉点，P4和P6可以和回路P0- P4- P2- P3- P0合并，总需求之和为4.5吨，未超过一辆车的运输能力，可形成回路P0- P6-

9所示 继续选最大节约值13，若选定P5和P6交叉点的13，P5和P6可以和回路P0- P6- P4- P2- P3- P0合并，则总需求之和为4吨，满足一辆车的运载量8，因此，形成回路P0- P5- P6- P

4- P2- P3- 图 10 第六步优化结果

至此，两条配送路线已经找出，分别是P0- P1- P8- P9- P7- P0和P0- P5- P6- P4- P2- P3- P0两条线路，再加上原来单独一辆车从配送中心发往P1处的路线P0- P1- P0，一共是三条路线把所需货物配送完毕。

通过节约里程法优化之后，可以得到配送的方案，即配送中心派三辆车，每辆车负责一条线路，把用户所需货物送达。这三条线路分别为：

（1）P0- P1- P8- P9- P7- P0总路程为12+14+18+17+17=78千米，总运载量为7吨。

（2）P0- P5- P6- P4- P2- P3- P0 总路程为13+16+17+12+9+13=80千米，总运载量为5吨。 （3）P0- P1- P0，总路程为12+12=24千米，总运载量为8吨。 优化之后的运输方案所行驶的总里程数为78+80+24=182千米，

没经过优化以前，如果配送中心给每个分店用户单独配送，车辆的总里程数为（12+12+11+13+15+13+16+17+18+20）*2=294千米。比经过优化之后所走路程多112千米，由此可见，通过节约里程法配送货物能够在很大程度上减少车辆的运输里程，节省运输成本，进而提高公司的利润。

通过C语言代码将各配送路线的用户合并到回路中，实现窗体如下图

图 11 程序运行截图

5 总结

求解车辆路径问题的方法非常丰富，本文采用节约里程算法虽然能够得到可行的配送运

输路径方案，但是只是求的一个较优路线而不是最优路线。节约里程算法比一般的运输方法节约了运输距离，也体现了电子商务配送网络的优势，思路简单清晰，执行较为方便。这类算法虽然能够比较快的解决有关问题，但其优劣往往取决于算法设计者的实际经验以及处理样本空间的大小。在实际求解过程中，还有许多别的因素会影响到配送优化问题的解决，如交通状况是否是单行道，各个用户对货物需求的急迫性，车辆的运载量等。因此，节约里程算法更适合需求较为稳定或者是需求时间较为宽松，这显然不能满足当今极具多变的市场环境。我们还应加强对这些方面的研究，寻找最适合的求解方法，找到最优配送路线，使解决问题的方案更实际，也更能运用到日常生产生活中去。

对于大部分企业来说，配送成本最低和满足客户对时间的高要求是配送中急需解决的问

题，这都需要研究物流配送路径优化模型和算法来解决。如果能通过比较科学的物流配送路径优化模型和算法，来实现企业的人工调度和车辆安排，使得物流中心本身运作效率更高，成本控制得当，企业的效益也会不断提升。

参考文献

[1] 冯耕中.物流配送中心规划与设计[M].西安:西安交通大学出版社，2011.11-14.

[2] 夏向阳.长江三角洲地区电子商务物流配送研究[J].商业研究，2010，（5）:15-19.

[3] 王静.浅析我国市内物流配送发展研究[M].中国劳动社会保障出版社，2013.12-20.

[4] 李陶.电子商务环境下我国物流业发展的问题和对策[J].物流科技，2012，（1）:8-11.

[5] 汪鸣.我国现代物流业发展政策及建议[J].宏观经济研究，2010，（1）:10-12.

[6] 李金凤.电子商务环境下的现代物流配送[J].科技信息(学术研究)，2011（3）:4-8.

[7] 宋玲.电子商务——21世纪的机遇与挑战[M].北京：电子工业出版社，2010.55-62.

[8] John Current.multiobjective analysis of facility location decisions[J]. European Journal of Operational Research，1990，49: 295-307.

[9] 汪寿阳.集成物流管理系统中的定位——运输线路安排问题的研究[J]. 管理科学学术论文，2000，（2）: 69-75.

[10] 陈子侠.杭烟物流送货线路的划分模式与算法研究[J].系统工程理论与实践，2004，24（4）:46-51.

Research on Route Planning of Ecommerce Distribution

Center

Liu Shi-ming

(Academy of Computer & Information Engineering, Anyang Normal University, Anyang, 455000)

Abstract: E-commerce businesses get advantage in the fierce competition, we must attach importance to the role of the distribution center, delivery route planning, reduce transportation costs. Save mileage method were introduced in this paper in the practical application of logistics distribution center and distribution, the distribution center transportation route planning, in order to choose the best distribution route and comprehensive control of the vehicle. By saving mileage method of transportation to save time, save cost of completed the realization of the goal, therefore, save mileage method in the realization of route planning good results have been achieved.

Key words：Electronic commerce, the allocation center, transports the line, the plan

代码附录

#include

int main()

{

int

juli[10][10]={{0,0,0,0,0,0,0,0,0,0},{12,0,0,0,0,0,0,0,0,0},{11,11,0,0,0,0,0,0,0,0},{13,10,9,0,0,0,0,0,0,0},{15,14,12,26,0,0,0,0,0,0},{13,12,15,25,15,0,0,0,0,0},{16,20,18,24,17,16,0,0,0,0},{17,18,20,23,19,17,21,0,0,0},{18,14,22,22,21,19,22,15,0,0},{20,16,24,21,23,18,20,17,18,0}};

int m,n;//m为行,n为列

printf("*************配送路线的优化*************\n");

printf("\n");

printf("各用户之间的距离：\n");

for(m=0;m

{

for(n=0;n

{

if(juli[m][n]!=0)

{

printf("%d ",juli[m][n]);

}

}

printf("\n");

}

printf("\n");

printf("\n");

int

youhua[10][10]={{0,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0,0}};

int

maopaopaixu[10][10]={{0,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0,0}};

int

youhuafubiao[10][10]={{0,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0,0}};

printf("各用户之间的节约量：\n");

printf("\n");

for(m=2;m

{

for(n=0;n

{

if(m>n) { if( juli[m][n]!=0) { youhua[m][n]=juli[m][0]+juli[n][0]-juli[m][n]; youhuafubiao[m][n]=youhua[m][n]; if(youhua[m][n]!=0) { printf("%d ",youhua[m][n]); } } } } printf("\n"); } for(int i=1;imax) { max=youhuafubiao[m][n]; } } } for(m=0;m0&&youhuafubiao[m][n]==max) { maopaopaixu[m][n]=i; youhuafubiao[m][n]=0; } } } //printf("%d\n",i); } printf("\n");

for(m=0;m8) { P[a]=P[a]-8; cheliangshu--; printf("配送线路: P0、P%d、P0\n",a+1); } } } double zongshu=0;//配送多个用户时的总需求 for(i=1;i0 && zongshu8) {

printf("、P0\n"); zongshu=0; cheliangshu--; } else { P[m-1]=0; maopaopaixu[m][n]=0;

}

}

}

}

printf("、P0\n");

printf("\n");

} printf("、P%d",m); } } if(P[n-1]!=0 && zongshu8) { printf("、P0\n"); zongshu=0; cheliangshu--; } else { P[n-1]=0; maopaopaixu[m][n]=0; printf("、P%d",n); } } if(zongshu>8) { printf("、P0\n"); zongshu=0; cheliangshu--; }