最短路标号法python_最短路问题与标号算法(label correcting algorithm)研究(1) - 开篇介绍...

忘是亡心i 2022-12-31 09:29 103阅读 0赞

作者：崔赞扬、李崇楠

指导老师：周学松教授

校对：邓发珩、周航、向柯玮

![Image 1][]

序言

本系列推文重在从算法基本原理、复杂度分析、优缺点、代码实现、算法扩展等方面科普Label Correcting Algorithm(最短路算法重要分支)，同时给出了下一步学习内容建议。

本文在周学松教授的指导下完成，特别感谢周学松教授的全程指导，感谢姚宇、牛志强、张宇丰在文章结构、内容安排、内容校对等方面提出的宝贵建议。

![Image 1][]

前言

最短路问题是图论理论的一个经典问题，其目的在于寻找网络中任意两个节点间的最短路径，这里的最短可以衍生为距离最短、费用最小、时间最短等一系列度量。

![Image 1][]

交通领域最短路径问题有着广泛应用场景，例如交通流分配问题可以看作一对多(one to all)的单源最短路问题，智能导航系统可以看作实时路况条件下一对一(one to one)的多源最短路问题。

通常在求解问题时我们不仅要关注结果，更要关注求解过程，即算法的效率，因为它关系到解决问题的成本。

F. Benjamin Zhan和Charles E. Noon\[1\]以实际路网数据做了大量数据实验，对15种最短路径算法的效率做出了客观评估，这里直接引用其研究成果(如表1-1，1-2)。

表1-1

Relative Performance Summary for Data Set2 with a Scaling Factor of 1000

![Image 1][]

表1-2

Relative Performance Summary for Data Set2 with a Scaling Factor of 1000

![Image 1][]

注释：

NE1,AL1,…GA1,LA2,MS2,…GA2为实际路网编号；

CPU TIME Of Minimum为最佳最短路径算法的最小平均CPU运算时间(单位：毫秒)，与算法对应的每一行给出了相应算法在求解不同路网最短路径时平均CPU运算时间与最小平均CPU运算时间的比值。例如表1-1中PAPE算法是求解NE1网络的最佳算法，其最小平均CPU运算时间为0.46毫秒，DIKF是求解NE1路网的最差算法，其平均CPU运算时间为0.46\*7.59=3.49毫秒；

Total Time列为算法求解所有路网单源最短路径的CPU运算时间之和，Ratio为每个算法的Total Time与最佳算法的Total Time比值，代表算法总体速度；

Average Max-to-Mean Ratio为在重复实验中最大CPU运算时间与平均运算时间的比值(该实验结果是由100次独立重复试验得到的)。

表1-1和表1-2是在不同实际路网上的统计结果，其中TWO\_Q又称Deque Label Correcting Algorithm，而DIXX则是不同版本的Dijkstra algorithm实现。

![Image 1][]

根据实验结果我们可以得知在两种不同的数据集上

TWO\_Q

都表现出了

较好的性能

，而

Dijkstra algorithm

的性能

不太令人满意

。

![Image 1][]

因此，我们有必要学习诸如TWO\_Q一样高效的算法来更好的解决实际问题。

此外，含有负环的网络在实际应用中也是极为常见(例如，鼓励拼车和使用不同类型的(负)拉格朗日乘数来确保每个乘客在车辆路径问题中只被服务一次\[2\])，因此在选择算法时也必须考虑算法对含有负环网络的适用性。

![Image 1][]

本系列推文将围绕Label Correcting Algorithm(标号更新法或标号更正法)展开，主要介绍一些基本的Label Correcting Algorithms，为读者后续深入学习网络最短路问题以及其他网络流问题提供支撑。

后续安排

本系列推文后续章节安排如下：

第二章节主要介绍最短路问题及其数学模型、最短路径求解算法及其分类；

第三章节主要介绍单源及多源Label Correcting Algorithms的核心内容与相应代码实现；

第四章节主要介绍如何利用本文介绍的算法求解多目标最短路径问题以及如何处理大规模网络；

在附录1部分补充了Label Correcting Algorithm如何处理含有负环的网络最短路径问题，附录2给出了本文所研究的简单有向图，附录3提供了由周学松老师开发的NeXTA软件，辅助最短路问题学习。

为了更好的理解本文所介绍内容建议读者具备一定的图论知识以及计算机编程能力(Python or Matlab)。

建议

完成本文内容学习以后，读者可以学习以下深层次最短路径的相关问题：

算法性能分析(Algorithm analysis);

最小费用流问题(Minimum cost flow)；

拉格朗日松弛问题(Lagrangian relaxation)；

多商品流问题(Multicommodity flows)

资源网站

Data and source code folder:

https://github.com/marcolee19970823/label\_correcting

https://github.com/PariseC/Shortest\_Path\_Algorithm/tree/master/label\_correcting\_algorithm

Our github sites:

https://github.com/marcolee19970823

https://github.com/PariseC

Nexta network editor:

https://github.com/xzhou99/NeXTA-GMNS

Advanced content learning materials：

https://ocw.mit.edu/courses/sloan-school-of-management/15-082j-network-optimization-fall-2010/assignments/

本文档内容主要参考《NETWORK FLOWS》\[3\]完成，另外上述进阶内容也可参考该文献进行学习。

另外，关于本文档介绍的基础算法也可参考《Development and testing of dynamic traffic assignment and simulation procedures for ATIS/ATMS applications》\[4\]进行学习。

指导老师介绍

Professor Xuesong Zhou(周学松)

周学松教授是亚利桑那州立大学(ASU)可持续工程与建筑环境学院教授，

目前是Transportation Research Part C的副主编，城市轨道交通urban

rail transit 执行主编，Transportation Research Part B的编委。

主要研究大规模多模式交通系统优化和仿真算法。

![Image 1][]

参考文献：

\[1\].Noon F B Z E . Shortest Path Algorithms: An Evaluation using Real Road Networks\[J\]. Transportation Science, 1998, 32(1):65-73.

\[2\].Yao Y, Zhu X, Dong H, et al. ADMM-based problem decomposition scheme for vehicle routing problem with time windows\[J\]. Transportation Research Part B: Methodological, 2019, 129: 156-174.

\[3\].Ahuja R K , Ahuja R K , Ahuja R K . Network Flows\[M\]. Optimization. Elsevier North-Holland, Inc. 1989.

\[4\].Mahmassani, Hani S. Development and testing of dynamic traffic assignment and simulation procedures for ATIS/ATMS applications\[J\]. 1994.

文案&编辑：崔赞扬、李崇楠(北京交通大学)

审稿人：邓发珩、周航、向柯玮(华中科技大学管理学院)

指导老师：周学松(Arizona State University)

如对文中内容有疑问，欢迎交流。(PS：部分资料来自网络)

如有需求，可以联系：

崔赞扬(北京交通大学博士：dr.zanyang@bjtu.edu.cn)

李崇楠(北京交通大学本科：chongnanli1997@hotmail.com)

周学松(Arizona State University Professor：  xzhou74@asu.edu)

邓发珩(华中科技大学本科三年级：  2638512393@qq.com、个人公众号：程序猿声)

周航(华中科技大学本科一年级：zh20010728@126.com)