基于双区间索引最短路径问题研究

张红岩

摘要：物流配送行业的迅速发展，使得物流配送网络图的规模迅速增加，数据量增长较快。现有的最短路径问题大多基于传统的最短路径算法，在处理大规模网络图时存在计算较慢，甚至无法计算的问题。提出了基于双区间索引的最短路径算法，对图中每个顶点建立双区间索引，根据索引值对顶点的可达性进行快速判断，把可达性查询问题应用于物流配送网络中求解最短路径问题，可达到降低物流配送网络图规模，减少计算量，提高计算效率的效果。

关键词：物流配送网络；最短路径；双区间索引；可达性查询

中图分类号：TB文献标识码：Adoi：10.19311/j.cnki.16723198.2018.02.091

1引言

近年来，市场经济快速发展，物流行业作为企业之间和企业与客户之间联系的桥梁发挥着巨大的作用。此外，对于以利润最大化为最终目标的现代化企业来讲，物流配送行业的优化，成为企业增加利润的一个重要来源。因此，互联网信息技术下物流行业发展迅速，并占据越来越重要的地位。

物流配送业务不同于一般的运输业务，它是集运输行业、现代信息网络及后续加工管理等一系列活动于一体的综合业务领域。随着我国经济快速发展，物流配送业务活动内容逐渐丰富，整体功能增加，使得物流配送网络包含的物流节点越来越多，物流配送路线越来越复杂。因此，复杂物流配送网络中的路径优化问题成为现代物流运输领域中一个重点问题。

物流配送活动中最基本的问题即最短路径问题，旨在寻找一条从配送起始点到目标节点总距离最短的路径。传统的物流配送最短路径问题主要注重于计算配送中心到目标节点的最短距离，而忽略了现实配送活动中的费用等路径代价问题，应用到现实业务中具有一定的局限性。在现代物流配送活动中，对实际物流配送活动中的约束条件考虑更加全面，注重物流配送过程中的成本和代价的计算，在尽量满足这些条件的前提下来得到整体最优路径。

本文研究的内容是物流配送网络图中最短路径的快速求解问题，并与可达性查询问题相结合，提出了基于双区间索引的剪枝策略，来缩减物流网络图的规模，从而提高求解最短路径的效率。并参考文献中提出的双区间索引，应用于本文中的物流网络图上。在现有的求解最短路径算法的基础上，提出了结合剪枝策略的最短路径求解算法，并通过实例验证了本文算法的高效性。

2建立索引

双区间索引是指分别为图中的每个顶点建立先序索引区间和后序索引区间，分别记作Lu[x，y]和Ru[x，y]。基本思想为基于图的遍历方式，分别对图中顶点进行先序遍历和后序遍历，各顶点的索引值依据顶点在图中的遍历顺序得到，通过各顶点索引区间的包含关系，来判断图中顶点之间的可达性。

2.1先序索引区间方法

先序索引是指依据顶点从左到右的后根次序遍历，然后按照图中顶点的遍历次序，为图中的每一个顶点u，建立标签区间Lu[x，y]，其中Lu（y）表示顶点u在后根次序遍历网络图的过程中被访问的顺序，该遍历顺序从1开始，对图中的顶点按照先左后右的顺序依次访问，直到图中所有的节点都访问一次且仅能被访问一次为止。该方法保证每一个顶点的孩子节点的索引值Lt（y）都小于该顶点的索引值Lu（y），即每一个起始顶点的所有可达顶点的索引值 都小于该起始顶点索引值。

对于每一个顶点u的索引值Lu（x）是通过取该顶点的所有孩子节点的索引Lt（x）的最小值得到的，特殊的对于所有出度为0的顶点，其索引Lu（x）的值等于其索引Lu（y）的值。该方法可保证每一个顶点的父节点的索引值Lt（x）都是小于或等于该顶点的索引值Lu（x），即每一个起始顶点的可达顶点的索引值大于或等于该起始顶点的索引值。因此Lu（x）的计算方法如下：

Lu（x）=Lu（y）min {Lt（x）|t是u的孩子顶点}u的出度为0u的出度不为0（1）

2.2后序索引区间方法

与先序索引区间类似，后序索引区间是指依据顶点从右到左的后根次序遍历，然后按照图中顶点的遍历次序，为图中的每一个顶点u，建立标签区间Ru[x，y]，具体方法参照先序索引区间，这里不再赘述。

2.3图例说明

图1展示了该图中各顶点的双区间索引。

例1：以图1为例简要说明顶点的索引区间Lu[x，y]和Ru[x，y]是如何计算获得的。图中的顶点按照从左到右的后根遍历次序为：6、9、8、7、10、5、4、3、2、1、12…，首先对于出度为0的顶点，由于顶点6的访问次序为1，所以L6[x，y]=[1， 1]。其次，对于出度不为0的顶点，由于顶点8在上述访问序列的第3个位置，并且顶点8的出度为1，指向了顶点9，因此L8[x，y]=[2，3]；同理，顶点5在上述访问序列的第6个位置，并且顶点5的出度为3，分别指向了顶点6、顶点7和顶点10，又由于上述3个顶点的Lu（x）值L6x=1

图1先序/后序索引区間

3基于双区间索引的剪枝算法

根据双区间索引，可对图中顶点间的不可达性进行判断，并对不可达顶点进行剪枝，剪枝过程根据下述定理进行判断。

定理：对于图中的每一个顶点对（u，t），若LtLu或RtRu，则顶点u不可达顶点t（区间包含，不一定可达）。

证明：反证法。假定LtLu，且顶点u可达顶点t。根据双区间所索引建立的过程，可知顶点u可达顶点t时，Lt（x）Lu（x）且Lt（y）

SymbolcB@ Lu（y），因此可知顶点u和顶点t的索引区间LtLu，这与LtLu矛盾，因此LtLu时，顶点u不可达顶点t。同理，可证明当RtRu时，顶点u不可达顶点t。证毕。

例2：以图1为例，来说明基于双区间索引的剪枝算法的计算过程。在计算顶点15到顶点6的最短路径的过程中，应用剪枝定理进行不可达性判断，可以将1，2，3，9等13个顶点剪枝。在剪枝后的网络图上应用Dijkstra算法为例计算最短路径，最终可获得最短路径序列为15→5→6，最短路径距离为11，在这一计算过程中只需要计算16个顶点。然而，在原始的网络图上应用Dijkstra算法可求得最短路径序列仍为15→5→6，路径距离也为11，但该计算过程需要计算22个顶点。通过对比，不难发现应用基于双区间索引的剪枝算法可有效减少算法的计算量，提高了计算效率。

4结束语

本文把可达性查询问题应用于物流配送网络的最短路径求解问题中，提出了基于双区间索引的最短路径算法。对物流配送网络图中的每个顶点分别建立先序索引区间及后序索引区间，根据各顶点索引区间的包含关系，判断物流配送网络图中顶点间的不可达性，对不可达的顶点进行剪枝，在计算中不再考虑不可达的顶点，然后与传统的最短路径算法相结合，形成了基于双区间索引的最短路径算法，达到了缩减网络图规模，提高计算效率的效果。通过实例进行对比，证明了本文算法的高效性。

参考文献

[1]Agrawal S， Singh RK， Murtaza Q. Outsourcing decisions in reverse logistics： Sustainable balanced scorecard and graph theoretic approach[J].Resources， Conservation and Recycling， 2016，108： 4153.

[2]忻瑞婵.物流配送系统中大规模最短路径算法的研究[J].中国管理信息化，2008，（05）：6769.

[3]Van Schaik S J， De Moor O. A memory efficient reachability data structure through bit vector compression[C]. Proceedings of the 2011 ACM SIGMOD International Conference on Management of Data， 2011：913924.

[4]关菲，张强.模糊多目标物流配送中心选址模型及其求解算法[J].中国管理科学， 2013，21（S1）：5762.

[5]胡祥培，孙丽君，王雅楠.物流配送系统干扰管理模型研究[J].管理科学学报， 2011，14（01）：5060.

[6]韩世莲，李旭宏，刘新旺.物流运输网络模糊最短路径的偏好解[J].交通运输工程学报，2005，（02）：122126.

[7]唐晋韬，王挺，王戟.适合复杂网络分析的最短路径近似算法[J].软件学报， 2011，（10）：22792290.

[8]Sommer C.Shortest-path queries in static networks[J].ACM Computing Surveys （CSUR），2014，46（4）：45.

[9]Kuperstein I， Grieco L， Cohen D P A， et al. The shortest path is not the one you know： Application of biological network resources in precision oncology research[J]. Mutagenesis， 2015， 30（2）： 191204.

[10]王樹西，李安渝.Dijkstra算法中多邻接点与多条最短路径问题[J].计算机科学， 2014，41（06）：217224.

[11]Bader J S， Chaudhuri A， RothBerg J M. Gaining Confidence in High-through put Protein Interaction Networks[J]. Nature Biotechnology， 2003，22（1）：7885.

[12]Yildirim H， Chaoji V， Zaki M J. Grail： Scalable reachability index for large graphs[J]. The Proceedings of the VLDB Endowment （PVLDB） Journal， 2010，3（1）： 276284.endprint