GIS在绥化城区烟草物流配送路线优化中的应用

薛大维，黄宏阳，刘玉伟，王凯忠

(黑龙江工程学院 汽车与交通工程学院，黑龙江 哈尔滨 150050)



GIS在绥化城区烟草物流配送路线优化中的应用

薛大维，黄宏阳，刘玉伟，王凯忠

(黑龙江工程学院 汽车与交通工程学院，黑龙江 哈尔滨 150050)

摘要：根据绥化市烟草配送和设计要求，结合当地的路网情况，对黑龙江省绥化市烟草配送初步设计，从而达到加快配送时间，降低成本的目的。运用GIS软件对绥化市烟草配送进行配送现状分析、配送区域重构、配送方案优化、优化方案分析。对单配送中心和多个配送点的物流配送线路选择问题进行深入研究，并用绥化市实例验证此方法简单可行，对提高企业配送效率具有重要的意义，整个物流成本中，运输成本占比很大，本设计内容针对绥化市市区内烟草配送现状，实现配送节点的矢量化标注，分析存在的问题与不足，整合配送资源，完善研究区域路网，合理划分线路配送区域，提高配送能力，给出合理配送方案。

关键词：GIS；烟草物流配送；配送路线优化；配送成本

1绥化城区配送现状分析

根据绥化市城区需求总量汇总表及各区域的配送里程柱状图，可以看出城区各区域的配送里程情况，如图1所示。

图1　2013年绥化市烟草需求总量

从图1可以看出，配送区域划分为5个区。在划分区域中，城一、城五区明显配送量高于其他几个区，而城三区则配送量较少，这是绥化市城区烟草配送所出现的问题之一。配送区域划分不够合理，车辆配送可能就存在货多车少、货少车多的问题，因此，本文首先将绥化市北林城区进行区域重构，从而实现合理的配送安排，在合理的区域重构情况下减少配送车辆，提高企业配送效率。

根据绥化市城区配送里程汇总表及各区域的配送里程柱状图和时间柱状图，可以看出城区各区域配送里程情况和配送时间现状，如图2、图3所示。

图2　2013年城区烟草配送里程现状

图3　2013年绥化市城区配送时间

通过绥化市城区配送里程与时间，可以分析出2013年绥化市烟草配送现状，由图3可见绥化市配送区域划分为5个区域，每个区域为5条路线，从里程上可以看出从配送中心抵达城五区的配送距离较远，导致所需时间较长，配送总量最大，在里程、需求都较大的情况下，应加强对城五区路线的安排，从而节省时间，提高使用效率。而减少城三区的配送路径，从2013年配送现状可以看出，城三区需求量、里程都较低，而配送车辆却与需求量较高城区相同，因而本次设计对这种情况进行了优化。

2车辆路径算法原理

2.1最短路径算法

算法具体的形式包括：

1)确定起点的最短路径问题：即已知起始结点，求最短路径的问题。

2)确定终点的最短路径问题：与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转地确定问题起点。

3)确定起点终点的最短路径问题：即已知起终点，求两结点之间的最短路径。

4)全局最短路径问题：求图中所有的最短路径[1-2]。

用于解决最短路径问题的算法被称做“最短路径算法”，有时被简称作“路径算法”。最常用的路径算法有：迪克斯特拉 (Dijkstra)算法、Bellman-Ford算法、Floyd-Warshall算法、Johnson算法[3-5]。

2.2Dijkstra算法

Dijkstra算法是典型最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直至终点为止。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。

Dijkstra算法思想为：设G=(V,E)是一个带权有向图，把图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合(用S表示，初始时S中只有一个源点，以后每求得一条最短路径 ，就将 加入到集合S中，直到全部顶点都加入到S中，算法就结束了)。第二组为其余未确定最短路径的顶点集合(用U表示)，按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中，保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点距离就是从v到此顶点的最短路径长度，U中顶点的距离是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度[6-7]。

2.3Dijkstra步骤

1)初始时，S只包含源点，即S=v的距离为0。U包含除v外的其他顶点，U中顶点u距离为边上的权(若v与u有边)或u不是v的出边邻接点。

2)从U中选取一个距离v最小的顶点k，把k加入S中(该选定的距离就是v到k的最短路径长度)。

3)以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u(u U)的距离(经过顶点k)比原来距离(不经过顶点k)短，则修改顶点u的距离值，修改后的距离值的顶点k的距离加上边上的权。

4)重复步骤2)和3)直到所有顶点都包含在S中。如图4所示，设点A为源点，求点A到其他各顶点(B，C，D，E，F)的最短路径。线上所标注为相邻线段之间的距离，即权值(此图为随意所画，相邻顶点间的距离与图中目视长度不能一一对等)[7-8]。

图4　Dijkstra无向图

3GIS在绥化城区烟草物流配送系统线路优化中的应用

GIS的技术路线及使用流程如下：

1)整个项目开展过程前，会对所有工作人员进行GPS培训，熟悉后进行点数据的采集工作，对送烟工作人员进行GPS现场定位，对路网交叉点、配送点等进行一一采集，采集工作结束后会通过GIS软件将GPS采集到的点数据传输到电脑软件中，形成网上具体数据[9]。

2)图层的建立以及描点工作的开展。在GIS软件内导入绥化城区电子地图，构建相关的道路图层、商店图层等，如图5所示。在相关带有图层的电子地图上显示出相关的线数据、当地的道路走势，同时进行相关描点工作，如图6所示，并输入各个卖烟地点的相关信息，包括客户编码、店名、负责人、销量完成停靠点的图层。

图5　电子地图

图6　描点图

3)配送区域的重构，得出优化路线。如图7所示，将所有描点图进行分区处理，将城区分为20个配送区域，配送网点的分区处理按照一定的原则进行人工分区，此处为人工互换实现，人为按照分区原则，各个区之间总量必须均匀；相关地域的地理地貌也在考虑范围之内；各区之间配送里程要有一个均匀值；配送网点要尽量分布均匀，通过这样的人为分区能够保证送货时间、工作量大致相同。

4)对各个区域选择不同的颜色加以区分，这样就能得到每个城区区域的所有网点汇总，同时要求每一个区要确保配送网点在10个左右，使得配送过程中配送运量、配送满载率都相差较小。通过新建车辆路径求解得出一个相对合理的配送网点配送方案，但在实际操作中还存在一些问题，所以要手动进行调整，依次将网点在Network Analyst窗口中提前，从而实现更改顺序。最后，将绥化市区20条线路依次按顺序导入地图并通过Network Analyst 新建路径方式计算出每个区域相应配送路径，这是通过GIS软件自身即能够根据相应条件在已有的算法下实现的，最后得出相关路径[10-12]。

图7　重新分区及优化路径

4配送优化后分析

图8是绥化市城区优化后的配送里程表柱状图，从图中可以看出优化后城区送货路径为20条，配送区域都是相对平均的，并且配送里程最高的城六区与最低的城一区只相差15 km，这样可以使配送时间保持相对一致，配送里程相比较优化前配送现状已经有了很大改善，最大与最小配送里程在缩小，而且已经趋于稳定。

图9为绥化市城区优化后配送时间表柱状图，由于司机不可连续工作6 h以上,但优化前可以清楚地看出大部分工作时间为4 h以内，这样大量浪费人力资源，给企业产生不必要的开支，员工应该保持在4～6 h的工作时间才会不浪费人力资源，而优化之后配送时间几乎保持在4 h以上，从而降低成本，同时各区域配送时间趋于稳定，与优化前有了很大的改善，更好地解决了车辆配送时间存在较大差异的不公平现象。

图10为绥化市优化后配送总需求量柱状图，可以看出优化后每个区域安排一辆配送车辆，不仅大大减少配送中所存在的误差，同时使优化后的车辆配送量稳定，车辆的满载率得到了提升，减少了企业运营成本的投入。

图8　优化后城区配送里程

图9　优化后配送时间

图10　优化后城区配送需求量

5优化方案评价

1)配送网点覆盖率100%。根据优化前后的数据分析，所有的用户都在优化路线上，包含所有配送网点，同时没有出现配送错误，因此，达到了配送要求以及配送目标，网点的覆盖率达到100%。

2)配送总里程节约20%以上。基于城区优化前和优化后的数据分析，可以得到优化前的车辆总配送里程为891.1 km，优化后的车辆总配送里程为411.3 km，配送总里程节约53.8%，满足配送总里程节约20%以上。

3)配送车辆数减少20%及以上。根据绥化城区优化前的线路数为25条，优化后的线路数为20条。所以配送车辆数减少20%，满足配送车辆数减少20%及以上的要求。

6结束语

现有的研究成果是假设每天各区的配送量不变的情况下进行的，并且本文的结果是经过实际验证的。随着烟草物流配送市场的壮大，为了提高企业的市场竞争力，GIS软件应运而生，其灵活、适用性强的车辆优化方法得到了越来越多配送企业的青睐，尤其是随着配送市场的扩大，配送网点的数目不断增加，各配送网点的需求情况存在越来越大的差异性，且地理分布不集中，因此，通过GIS软件中的车辆配送功能模块，新建车辆配送以及路径，设计出经济合理的车辆配送方案，从而减少烟草配送企业运营成本的投入[13-15]。基于GIS软件在配送流程中的应用，给配送企业创造了一个可视化的信息平台,为企业做出相关的决策与分析提供基本依据,并为企业提供了良好的管理信息模块。

参考文献

[1]金江军.第三方物流发展状况分析[M].北京：中国物资出版社,2013：25-30.

[2]王子平.现代物流烟草业获取利润的新亮点[M].北京：中国烟草出版社，2013:23-24.

[3]陈继冶.贺州烟草优化访销配送模式提高服务质量[N].中华合作时报，2010-6-12.

[4]赵刚,张永锋.冷链物流配送路径优化研究[C].[出版者不详],2011：30-45.

[5]黄阿醒,李志勇.浅析GIS在物流配送的运用[J].漳州职业技术学院学报,2009,15(3)：20-26.

[6]王变利.GIS在物流配送系统中的应用研究[D].焦作：河南理工大学,2010.

[7]STUDLAR D T.Tobacco control: comparative politics in the United States and Canada[J].Broadview Press Ltd,2012,120(9):411-425.

[8]TEUNTER R.Lot-sizing for inventory systems with product recovery[J].Computes and Industrial Engineering,2012,120(46):431-441.

[9]白竹，金晓红.出租车GPS数据的应用研究[J].黑龙江工程学院学报，2014，19(4)：27-30.

[10] 张文宏.GIS在物流配送中的运用[D].成都：西南交通大学,2012.

[11] 符卓,陈斯卫.车辆路径问题的研究现状与发展趋势[C].香港：Global-Link Publishing Company,2010:15-30.

[12] 金真,王小丽.物流信息管理[M].北京:北京电子工业出版社,2008:15-25.

[13] 邓涛,陈瑶.基于专家系统的物流配送智能仿真系统探析[J].西南农业大学学报,2012,15(52):19-28.

[14] 莫韦嶙,谭勇,张宝华.烟草配送系统中路径优化问题[M].北京：中国物资出版社，2009：26-31.

[15] 王焕,兰洪杰,张凯.企业配送线路的优化分析[C].北京：中国铁道出版社，2011：35-40.

[责任编辑：郝丽英]

Application of GIS to tobacco logistics distribution route optimization in Suihua City

XUE Dawei，HUANG Hongyang，LIU Yuwei ，WANG Kaizhong

(College of Automobile and Traffic Engineering，Heilongjiang Institute of Technology，Harbin 150050，China)

Abstract：In this paper,tobacco distribution in Suihua City,Heilongjiang Province,is preliminarily designed according to the local tobacco distribution and design requirements,and combined with the local road network,so as to speed up the time of distribution and reduce the cost of the purpose.By using GIS (Geographic Information System)software,the distribution status analysis,distribution area reconstruction,distribution scheme optimization and optimization scheme analysis are carried on for the tobacco distribution in Suihua City.The problems of single distribution center and distribution route selection of multiple distribution points are in-depth study,and one example in Suihua City is used to verify that the method is simple and feasible,which has a important significance in improving the efficiency of enterprise distribution so that the quality of service can be improved.In the whole logistics,transportation costs account for a large part of the cost of logistics.The design aims at tobacco distribution situation in Suihua City to achieve the distribution nodes vector tagging,analyze the existing problems and shortcomings,integrate the distribution resources,perfect the regional road network and arrange the distribution line region,in order to improve the ability of distribution and give a reasonable delivery scheme.

Key words：geographic information system; logistics and distribution of tobacco; delivery route optimization; distribution costs；delivery status

DOI:10.19352/j.cnki.issn1671-4679.2016.03.010

收稿日期：2015-12-17

基金项目：黑龙江工程学院大学生创新项目(201411802055)

作者简介：薛大维(1972-)，男，副教授，研究方向：物流配送.

中图分类号：P208

文献标识码：A

文章编号：1671-4679(2016)03-0037-06