ABSTRACT

Path planning has been applied in many fields, especially in logistics management. This paper takes logistics distribution in the process of online shopping as the background, the aim is to find a shortest path in the process of distribution. Considering the case of shipping from a warehouse to one of the districts with multiple distribution centers, such a problem is considered as the path planning problem of the specified starting point and ending point set on the network. And using Dijkstra algorithm to design a optimal algorithm to solve such a problem, it provides a new way to solve such problems.

Keywords:Path Planning, Shortest Path, Dijkstra Algorithm

网络上指定起点与终点集的路径规划问题

㱔思敏，李伟，杨花

云南民族大学，数学与计算机科学学院，云南 昆明

收稿日期：2018年12月3日；录用日期：2018年12月31日；发布日期：2019年1月7日

摘 要

路径规划在很多领域都有应用，特别是物流管理方面。本文以网购过程中的物流配送为背景，以找出配送过程中的最短路为目的。考虑从一个仓库发货到有多个分拨中心的地区中的某一个的情况，将这样的问题看做网络上指定起点与终点集的路径规划问题。并运用Dijkstra算法设计出一个最优算法来解决这样的问题，为这样的问题提供求解新思路。

关键词 :路径规划，最短路，Dijkstra算法

Copyright © 2019 by author(s) and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY).

http://creativecommons.org/licenses/by/4.0/

1. 引言

近年来随着互联网的发展，人们生活水平的提高，生活节奏的加快，网上购物成为人们购物的一大趋势。我们在网上几乎可以买到现实生活中我们需要的一切用品，并且网上的物品比起实体店来说性价比很高，又方便，动动手指就等着快递员送货上门了。因此，网购成为了人们消费的一大热门。由此加速了快递行业的发展，因为网购最重要的环节就是商品配送的环节。

对于商家来说，希望实现最低的配送费，我们知道在配送的过程中路径的长短往往和配送费用成正比，也即路径越长配送费用越多。因此，商家需要寻找一条最短的配送路径来实现最低配送费用。而对于消费者来说，有时候急需使用购买的商品，当然是希望越快收到货物越好，这时候当然需要一条最短的配送路径来满足需求。综上所述，对物流配送的过程进行合理的路径规划 [1] 是十分有必要的，并且有一定的实际应用价值。

路径规划是运动规划 [2] 的主要研究内容之一。运动规划由路径规划和轨迹规划组成，连接起点位置和终点位置的序列点或曲线称之为路径，构成路径的策略称之为路径规划。路径规划在很多领域都具有广泛的应用。在高新科技领域的应用有：机器人的自主无碰行动；无人机的避障突防飞行；巡航导弹躲避雷达搜索、防反弹袭击、完成突防爆破任务等。在日常生活领域的应用有：GPS导航；基于GIS系统的道路规划；城市道路网规划导航等。在决策管理领域的应用有：物流管理中的车辆问题(VRP)及类似的资源管理资源配置问题。通信技术领域的路由问题等。凡是可拓扑为点线网络的规划问题基本上都可以采用路径规划的方法解决。

在物流配送的环节中，有时候会出现这样的情况，货物从总仓出发的时候要配送到某一个地区，该地区有多个分拨中心，需要将货物配送到多个分拨中心的其中一个即可，需要找到一条最短配送路径。我们将这样的的问题看做网络上指定起点与终点集的路径规划问题。

2. 问题描述

问题(网络上指定起点与终点集的路径规划问题)给定一个赋权有向图 $G=\left(V,E;c\right)$，权 $c:E\to R^{+}$ 。给定一个起点 $s\in E$，一个终点集 $T\subset E$，且 $s\notin T$ 。目标是寻找一条从起点s到终点集T中的某个顶点的最短路。

在解决这个问题之前我们首先给出Dijkstra算法 [3] ，该算法是求解单源最短路问题中的有效算法，它是由计算机科学家Edsger W. Dijkstra在1956年构造出来的。Dijkstra算法在很多领域都有应用，比如物流配送、铁路运输、公交换乘等方面。近年来，国内外对此算法的研究已经相对完善，主要针对Dijkstra算法本身和应用进行改进。例如，余震江研究的基于最短路径Dijkstra算法的铁路客运中转路径优化研究 [4] ；Joseph Kirk使用Dijkstra算法计算沿着图的边的最短(最少成本)路径 [5] ；韩慧玲、胡红萍研究的Dijkstra算法在公交换乘最短路径中的应用 [6] ；李健研究的基于Dijkstra最短路径算法的优化研究 [7] 等。

Dijkstra算法具体过程如下：

算法1 Dijkstra算法

Input：一个有赋权向图 $G=\left(V,E;c\right)$，权 $c:E\to R^{+}$，以及一个顶点 $s\in V$

Output：从s到图中所有顶点 $v\in V$ 的最短路及其长度

Begin

Step1 标记所有未被访问的节点，建立一个所有未被访问的节点的集合，叫做未被访问节点集，记做Q；

Step2 给每个节点分配一个暂定的距离值:初始节点设为 $l\left(s\right):=0$，对所有 $v\in V\backslash \left\{s\right\}$，令 $l\left(v\right):=\infty$，令 $R:=\varnothing$ 是已访问的节点集合；

Step3 对于当前节点 $v\in V\backslash \left\{s\right\}$，考虑它所有未访问的邻近的顶点，并计算它们通过当前节点的暂定距离。将新计算的暂定距离与当前分配的值进行比较，并修改当前标号为较小的值，使得 $l\left(v\right)=\underset{w\in V\backslash R}{\min }l\left(w\right)$ ；

Step4 当我们考虑到当前节点的所有未访问邻点时，将当前节点标记为已访问，并将其从未访问集合中删除，也即令 $R:=R\cup \left\{v\right\}$ ；

Step5 对所有使得 $\left(v,w\right)\in E$ 的 $w\in V\backslash R$，执行

若 $l\left(w\right)>l\left(v\right)+c\left(\left(v,w\right)\right)$，则

令 $l\left(w\right):=l\left(v\right)+c\left(\left(v,w\right)\right)$，且 $p\left(w\right):=v$ ；

Step6 若 $R\ne V$，则转向Step3。

End

3. 算法设计与分析

在这个问题中，我们需要找到一条从一个指定的起点到一个指定的终点集中某个顶点的一条最短路。这里设计的算法思路是，在第一阶段先利用Dijkstra算法找出从源点s到终点集T中每一个顶点的最短路；第二阶段是从这些最短路中找出一条最短的输出。

算法2

Input: 一个赋权有向图 $G=\left(V,E;c\right)$，权 $c:E\to R^{+}$，以及一个顶点 $s\in V$，一个顶点集 $T\in V$，且 $s\notin T$

Output: 从s到T中所有顶点的最短路中最短的一条及其长度

Begin

Step1：置起点 $S:=\left\{s\right\}$，终点集 $T:=\left\{v_1,v_2,\cdot \cdot \cdot ,v_{\left|T\right|}\right\}$ ；

Step2：利用算法1找出从起点s到 $v_1$ 的一条最短 $s-v_1$ 路；

Step3：再分别找出从起点s到 $v_2,v_3,\cdots ,v_{\left|T\right|-1}$ 的最短 $s-v_2,s-v_3,\cdots ,s-v_{\left|T\right|-1}$ 路；

Step4：最后找出从起点s到 $v_{\left|T\right|}$ 的最短 $s-v_{\left|T\right|}$ ；

Step5：比较这 $\left|T\right|$ 条最短路的长度，输出其中最短的一条。

End

定理1 网络上指定起点与终点集的问题是NP-难的。

证明：最短路问题已被证明是NP-难的，而网络上指定起点与终点集的问题是最短路问题中的一种，因此也是NP-难的。

定理2 算法2是网络上指定起点与终点集的路径规划问题的最优算法。

证明：由于算法1是一个最优算法，在算法2中每次利用算法1找出的路径都是最短的，因此最后得到的解是一个最优解，所以算法2是一个最优算法。

4. 应用举例

如图1所示，货物总仓位于s处，某地有5个分拨中心 $\left\{t_1,t_2,t_3,t_4,t_5\right\}$，现在要将货物从总仓配送到这5个分拨中心中的某一个，目的是找到一条从总仓到这5个分拨中心中的最短路。

图1. 某地区物流配送网络

根据算法3.4依次找出从起点s到终点集 $\left\{t_1,t_2,t_3,t_4,t_5\right\}$ 中的5条最短路 $s\to t_1,s\to t_2,s\to t_3,s\to t_4,s\to t_5$，最后比较这5条最短路的长度，输出其中最短的一条即可。

根据Dijkstra算法：

$l\left(v_1\right)=c\left(s,v_1\right)=3$

$l\left(v_2\right)=c\left(s,v_2\right)=2$

$l\left(v_3\right)=c\left(s,v_3\right)=4$

$l\left(v_4\right)=l\left(v_1\right)+c\left(v_1+v_4\right)=3+2=5$

$l\left(v_5\right)=l\left(v_4\right)+c\left(v_4,v_5\right)=5+2=7$

$l\left(v_6\right)=l\left(v_3\right)+c\left(v_3,v_6\right)=4+2=6$

$l\left(v_7\right)=l\left(v_2\right)+c\left(v_2,v_7\right)=2+5=7$

$l\left(v_8\right)=l\left(v_6\right)+c\left(v_6,v_8\right)=6+1=7$

$l\left(v_9\right)=l\left(v_4\right)+c\left(v_4,v_9\right)=5+3=8$

$l\left(v_{10}\right)=l\left(v_2\right)+c\left(v_2,v_{10}\right)=4+5=9$

$l\left(v_{11}\right)=l\left(v_8\right)+c\left(v_8,v_{11}\right)=7+2=9$

$l\left(v_{12}\right)=l\left(v_9\right)+c\left(v_9,v_{12}\right)=8+5=13$

$l\left(v_{13}\right)=l\left(v_9\right)+c\left(v_9,v_{13}\right)=8+\text{3}=\text{11}$

$l\left(v_{14}\right)=l\left(v_8\right)+c\left(v_8,v_{14}\right)=7+2=9$

$l\left(t_1\right)=l\left(v_{12}\right)+c\left(v_{12},t_1\right)=13+4=17$

$l\left(t_2\right)=l\left(v_{13}\right)+c\left(v_{13},t_2\right)=\text{11}+\text{2}=1\text{3}$

$l\left(t_3\right)=l\left(v_{14}\right)+c\left(v_{14},v_3\right)=9+3=12$

$l\left(t_4\right)=l\left(t_3\right)+c\left(t_3,t_4\right)=12+1=13$

$l\left(t_5\right)=l\left(t_5\right)+c\left(t_4,t_5\right)=13+2=15$

由上述过程可知，从起点s到终点集 $\left\{t_1,t_2,t_3,t_4,t_5\right\}$ 的5条最短路的长度分别为17，13，12，13和15，其中最短的一条是从起点s到终点 $t_{\text{3}}$ 的最短路。因此从总仓s到这5个分拨中心的一条最短路为 $s\to v_{\text{3}}\to v_{\text{6}}\to v_{\text{8}}\to v_{1\text{4}}\to t_{\text{3}}$，并且长度为12。如图2虚线所示，即为所求最短路。

图2. 一条最短的配送路径

5. 结论

本文以网购中的物流配送环节为背景，考虑配送过程中的一个仓库对应多个分拨中心的情况，运用Dijkstra算法设计了一个最优算法，该算法能有效的解决这种类型的问题，能够找出最优解。

基金项目

云南民族大学研究生创新基金项目(2018YJCXS228)。

文章引用

㱔思敏,李 伟,杨 花. 网络上指定起点与终点集的路径规划问题
A Path Planning Problem for Specified Starting Point and Ending Point Set on the Network[J]. 应用数学进展, 2019, 08(01): 1-6. https://doi.org/10.12677/AAM.2019.81001

参考文献