基于电子地图的城市配送线路设计

开篇：润墨网以专业的文秘视角，为您筛选了一篇基于电子地图的城市配送线路设计范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘要： 城市交通环境的变化，直接影响到城市配送的效率。利用电子地图、节约里程算法可以快速解决多辆车多客户的VRP问题。为达到对实际行驶线路的真实模拟，可通过百度地图确定超市（如家乐福-保龙仓）各门店及配送中心的位置与往返距离，并区分道路畅通状况、往返线路的差别，然后采用有向图中的节约里程算法进行车辆的调度。

Abstract： The change of urban traffic environment directly affects the efficiency of urban distribution. The use of electronic map， saving algorithm can quickly solve the problem of multi vehicle multi customer VRP. In order to achieve simulation of the actual route， we can determine the location of the supermarket stores （such as Shijiazhuang Carrefour） and distribution centers through Baidu-Map， and from the distance， and distinguish road unimpeded condition， commuter lines of the difference. Then， through the improvement of the saving algorithm in the network， we can find out the corresponding vehicle scheduling scheme.

关键词： 节约里程法；配送线路；地图测距

Key words： saving algorithm；distribution line；map ranging

中图分类号：U121；F570.6 文献标识码：A 文章编号：1006-4311（2016）01-0100-03

0 引言

伴随着石家庄城市共同配送试点的深入，“货的”已为众多市民所熟知。众所周知，城市居民出行感觉最为方便的仍是小汽车、自行车，且公交出行比例也正如城市发展速度那样快速增长；与之相对应的货运车辆出行，在各种城市交通限行政策影响下，如何才能有效地将居民所需求的货物送至商铺门店、乃至千家万户，仅靠“货的”还是远远不行的，还必须大力发展各种形式的共同配送。显然，车辆行驶路线越短、速度越快，配送效率也就越高，那么如何利用电子地图、车辆导航、移动互联网等技术，充分了解客户分布、道路畅通情况，实时计算最佳配送路线则是本文所要研究的问题。

1 城市配送的线路

一般来说，配送车辆的出行主要由配送中心送货到配送节点或商铺、配送节点到零散门店或顾客或末梢节点、末梢节点至顾客、门店至顾客。一条配送线路是指一辆配送车辆离开配送中心，按照一定顺序访问若干顾客点后返回起点的行驶路线。在配送线路设计中，需根据客户类型选择合适的线路设计方法，以最少的时间完成、最低的成本完成配送任务。实际中配送规划所能运用的前置时间仅有1～2小时而已，必须借助计算机系统完成配送规划，应该开发一套以人为判断为主、计算机系统为辅的配送规划决策支援系统，以期在最短的时间内规划出最合理的配送线路。

①直送式配送线路。直送式配送运输是指由一个供应点对一个客户的专门送货，其主要是针对那些需求量接近或大于可用车辆装载量的客户。这时的配送线路应是最短、或最最快的，其主要的优化途径便是寻找最短路径。求解最短路径的典型算法有Dijkstra、“帚”型法等，也可以利用百度地图、高德地图直接计算最佳线路。

②分送式配送线路。分送式配送是指由一个供应配送点往多个客户的配送，即在单个客户需求不足于装满整个货运车辆时，则可把同一条线路上相关客户的需求进行整合，然后由一辆车沿着一条优选的线路，依次将货物送到各个货物接收点。解决此类问题的典型算法便是节约里程算法。

现实配送过程中，单个客户的需求往往很难达整车配送的要求，同时每个客户又都分布在不同的区域（或节点），这就需求将多个客户集中起来实行共同配送，即通过集合、分拣、配货等环节，使送货达到一定规模，利用集群优势降低送货成本。一般来说，客户的配送需求以及货品类型都是多样化的，配送中心应该按照货品类型、配送目的地对货品进行分配配送，以优化资源配置，降低运输成本。

2 节约里程算法

VRP（Vehicle Routing Problem，车辆路径问题）是由Danting和Ramser于1959年提出的，现已经成为由多辆车给多个客户配送的一类问题的简称。经典VRP有多个货物配送点点，已知每个客户点的位置及需求量，且每个配送点只能由一辆车进行一次配送，每辆车的载货量不得超过其最大载重量。安排车辆路径至多用M辆车从中心仓库送货，以期最大限度的满足所有客户点的配送要求。我们可以将这类问题视为单目标问题，如距离最短、费用最少，也可以是多目标问题，如在规定时间内配送距离最短、城市交通时段和路段限制下的费用最小，还有可能是具有某种优先级（如客户的特殊需求）的单或多目标问题。

2.1 基本思路

节约里程的基本思路如图1所示。假设P为配送中心，A和B为客户接货点，各点相互的道路距离分别用a、b、c表示。比较两种运输路线方案：一是派两辆车分别运往客户A、B两点，总的运输里程为2（a+b）；一是将A、B两地的货物装在同一辆车上，采用巡回配送方式，总的运输里程为a+b+c。若不考虑道路特殊情况等因素的影响，第二种方式与第一种方式之差为a+b-c；按照三角形原理可知，两边之和大于第三边。

两个节点间的距离可以通过Dijkstra算法、Floyd算法等求出，但如何将两节点间的所有路段进行准确测量，显然需要应用现代电子地图的测距功能。另一方面，利用城市的电子地图完全可以找出起点至终点的路线，包括时间最短、距离最短等；而且许多地图还能显示交通路线各个路段的畅通情况。可见，直送式的配线路完全可以交给电子地图来解决，而分送式配送的线路则是在电子地图、节约里程算法的基础上进行的配载运输问题。

2.2 计算步骤

通过合理的车辆调度和最短的路线选择，尽量使运输车辆多载，尽量节约总配送时间和总配送里程。具体步骤如下：

①通过电子地图（如百度地图）找出各配送点间的最短线路。

②计算节约里程，即计算a+b-c的值。

③对节约里程进行降序排序。

④在满足车辆限载、客户需求量、时间限制、客户地理位置等条件下，根据①所找出的线路对配送点进行一对一地直送式配送，得到所需配送车辆和行程。

⑤进行回路的合并，得出配送优化方案。从节约里程排序表找出产生该节约里程的两个配送点i、j，再判断连接i、j的回路是否存在合并的可能性。如果一个回路以（p，i）开始，一个回路以（j，p）结束，且满足需求量和车载量等约束条件，则该回路可以合并，并进行下面的合并操作：删除两个回路中的部分路径（i，p）和（p，j），然后引入新的连接（i，j），得到新的回路（p，…，i，j…，p）。重复上述过程，直至没有可以合并的回路，从而得出配送优化方案。

⑥确定最优方案。重复上一步的合并过程，得出多个优化方案，并对得出的优化方案进行比较，得出最终优化方案。

3 超市配送中的应用

家乐福超市成立于1959年，是大卖场业态的首创者，是欧洲第一大零售商，世界第二大国际化零售连锁集团。石家庄保龙仓超市作为省会第一家开业的超级市场，曾经有过非常辉煌的发展历程，但随着石家庄北国超市的超速布局，保龙仓与家乐福于2010年7月走向了合作之路。截止2014年底，家乐福-保龙仓超市在石家庄城区内有7家，业务范围几乎涵盖了整个石家庄市区，如图2所示。

3.1 节点间距离的测算

家乐福-保龙仓当前采用的配送模式是通过配送中心进行统一配送，这种自营模式也是多数大型连锁超市所选择的配送方式。这里以润丰物流园石家庄城市配送中心作为P点（即配送中心），然后通过百度地图的查询功能，统计出P点至各个门店、及各门店间的距离，如表1所示。因为单行线、禁止掉头、立交桥等道路限制，配送车辆可能不能原来返回，虽然差距并不会太大，但是为了更接近真实，这里还是将其区别对待。

根据石家庄市家乐福-保龙仓各个门店的地理分布图和往返配送里程表，可以画出配送中心至各门店的简单方位图，如图3所示。其中，图中离箭头较近的数字表示其它点到该点的距离。

3.2 配送路线的优化

传统的里程节约法没有考虑货车往返里程的不同，而是假设往返里程相等。但车辆行驶在城区道路时，往返距离常常是不同的，若遇到单向通行限制时，二都可能会相差很大。因此，为了更好地模拟现实路况，需对公式进行相应地改进，即将P1=2（a+b），调整为P1′=（PA+AP）+（PB+BP）；将P2=a+b-c，调整为P2′=PA+AB+BP和P2″=PB+BA+AP；此时，则有ΔP′=P′1-P′2=AP+PB-AB，ΔP″=P′1-P″2=PA+BP-BA。这里采用改进的公式计算里程节约量，并按照节约里程降序排列。

假设配送中心运力充足且拥有额定载重6吨和8吨的两种货车，货车单次的最远配送里程不作要求。因为配送中心每次配送任务不同，现选取配送中心某一次的配送任务为研究对象，经调查知道某次配送中各门店的需求量如表2所示。

假定目标是使总运输费用最小，为简化计算，将其假设为总配送里程最小。根据节约里程法的基本原理，最终优化方案绘制出最终配送线路图，如图4所示。其中第1、3条线路用6吨配送车，第2条线路用8吨配送车。

值得说明的是，在配送实施过程中，可能会遇到因交通环境而调整线路的问题。这时若还是到达指定的下一节点，可利用地图导航直接查找最新的合适路线；但若要对配送的先后次序进行变更时，则可以通过节约里程的基本公式、结合地图进行路线重新规划。当然，变更配送次序还需要所装载货物的允许，同时也只能在原有配送点间进行次序的变更。

4 结语

在客户位置极度分散性、且数量较多时（如家庭配送），就需要先将城市划分为不同的配送区域，比如可将石家庄分为桥西、桥东、开发区，车辆由配送中心出发先通过干道（如二环路）进行指定配送区域，然后再在配送区域内采用节约里程算法进行配送。即对于某区域内配送，采用的是先由干线进入服务区域、区域内的顾客连接、再沿干线返回。

参考文献：

[1]姜樱梅，王淑云.乳品逆向物流及其VRP模型应用[J].企业经济，2014（2）：60-63.

[2]王汉新.城市共同配送的组织与管理――以石家庄为例[J]. 生态经济，2015（1）：126-129.

[3]徐晓杰，黎建国，丛英娜.多媒体技术与电子地图[J].石河子科技，2000（02）.