基于Dijkstra算法的地铁出行路线规划系统的设计与实现

马静 刘江岳

摘要：城市地铁已经成为许多居民出行的首选交通工具，但在一些大城市中，复杂庞大的地铁网络给出行者的线路选择和换乘带来了许多不便[1]。为了解决在日趋复杂的地铁网中找出最优路径这一问题，文章介绍的项目基于改进的Dijkstra算法，充分考虑了用户需求，设计了地铁出行线路规划系统，实现了多种路线规划模式，能够科学、高效地规划出最优路线。

关键词：改进Dijkstra算法;轨道交通;地铁;路线规划;最优路线

中图分类号：G434      文献标识码：A

文章编号：1009-3044（2022）13-0058-05

1 引言

最短路径问题在计算机科学、运筹学、地理信息科学等领域中是一个研究热点，并占有极其重要的地位[2]。随着经济的发展，越来越多的城市建设了地铁作为缓解交通压力的重要公共交通设施。但是，对于外来出行者来说，面对自己不熟悉的城市和复杂的城市地铁线路网，乘坐地铁会是一个难题;对于城市的本地居民来说，如何选择最佳的地铁乘车方案来节约宝贵的时间资源也是一个难题。明确地指引乘客乘车，有效地疏导客流在地铁的日常运营中是十分重要的。在大城市地铁线路网络庞大复杂的情况下，解决上述问题的关键在于如何根据用户的需求，快速且明确地指引乘客选择最佳出行线路[3]，因此在地铁出行路线规划的情景下研究最短路径算法是非常有必要的。本研究基于改进的Dijkstra算法，设计并实现了能在多种情形下查询地铁最优路线的地铁出行路线规划系统。

2 地铁出行路线规划软件功能需求与可行性分析

2.1 功能需求分析

現在国内市场上不乏出行路线规划软件，它们有的是针对某一个城市的地铁路线的，有的地铁、公交等多种公共交通工具。其中它们多数为移动端应用或网页，它们几乎都包含了以下相似的基本模块：1）地铁线路图：该模块提供各个线路的信息，方便乘客对单条线路进行研究、查询，同时提供高清晰的地铁线路图以及线路图的放大缩小功能[4];2）乘车查询功能：乘车查询功能要求在众多可行路线方案中默认提供到达目的地的最优路线方案，并将查询结果以多媒体的方式呈现，操作程序需简洁明了易上手[4]。该功能还包括丰富多样的站点输入方式，多种线路方案的选择。

2.2 可行性分析

1）硬件可行性分析：硬件配置需求：计算机选型为配备触摸屏的一体机，具有网络接口、麦克风和音响设备。CPU至少为1.8GHz Intel处理器，内存至少为1GB，硬盘具有30MB以上空余。其安装的操作系统最低为64位的Windows 7系统，并且.Net framework的版本最低为4.5.1。

2）软件可行性分析：地铁出行路线规划系统的后台数据，即站点数、站点名称、站点坐标、地铁线路及其包含的各个站点等信息存储于外部txt格式文件中，程序将按行从中读取数据。这样的外部存储方式使得本系统有很高的灵活性和扩展性，用户可以自定义扩充新的地铁线路图，让程序为用户提供个性化的路线规划服务。其中地铁站点坐标取自于地铁线路图片上站点的x，y坐标。

数据存储方式如表1所示。

文件名：城市名英文-subway.txt

该系统的软件程序用C++编写而成，由GUI界面、程序算法、后台数据三个部分组成，程序结构如图1所示。

该系统的前端包含语音输入功能，包含路线查询结果的语音播放功能，该功能调用了科大讯飞智能语音平台，能够在线使用语音输入和语音播放，界面支持多种语言。如图2所示，前端界面显示了高清地铁地图，操作方式为手持触屏的方式，可直接在地图上通过单击站点的方式设置起点与终点;可移动、放大、缩小地图;具有语音输入、语音播放的按钮;当前版本有三种路径规划方式可选，路线规划结果能够详细地列在输出框内，同时地图上也会直观地用标记出规划好的最佳路线。

系统的程序算法部分为改进的迪杰斯特拉算法，提供少停站优先、少换乘优先、周游一圈这三个模式，适应用户的多样化需求。

系统的后台数据为扩展文件，可从本地文件中读取地铁路线信息，可从中央服务器动态获取地铁路线信息。

3 Dijkstra算法简介

“最短路径算法”用于解决最短路径问题，其原理为：首先在路线拓扑图中找出地点作为结点，其次将节点编号并计算出所有结点间的最短路径，最后查找线路拓扑中两个目标结点的最短路径[5]。目前用于解决最短路径问题的比较成熟的算法有Dijkstra算法、A-Star 算法、Bellman-Ford算法和Floyd算法等[2，5]。四种最短路径算法的优缺点比较如表2所示。

其中，Dijkstra 算法由荷兰计算机科学家狄克斯特拉于1959 年提出，是在实际中应用最多的具有代表性的最短路径算法[3]。该算法针对具有非负权值的图。它采用标记法按照路径长度递增的顺序寻找最短路径，然后通过对路径长度迭代得到从源点到其他各目标节点的最短路径[7]。

Dijkstra算法的基本思想是：

1）设置两个节点的集合S和T，集合S是已经标记节点集，表示已经找到最短路径的节点，集合T是未标记节点集合，表示未找到最短路径的节点[7]。

2）初始状态时，集合S中只包含源点Vo[7]。

3）不断从未标记节点集合T中选取到节点Vo路径长度最短的节点Vj加入集合S中，集合S每加入一个新的节点Vj都要比较计算更新源点Vo到集合T中剩余各节点的最短路径长度值。不断重复此过程，直到集合T的节点全部加入集合S[7]。

为了解决Dijkstra算法的时间复杂度较高的缺点，以及为了满足遍历图中所有的点这一需要，本系统做了以下改进：

1）系统使用C++语言编写，通过C++程序运行的高效性的特点来弥补Dijkstra算法较高的时间复杂度。

2）拓展Dijkstra算法的思路，从解决两点之间最短路径的问题拓展到解决遍历图中的所有点的问题。遍历地图中所有站点的基本思路为，首先预处理任意两站点间的最短距离，然后每次选择一个尚未走过的站点，从当前点以最短路径走到选中的这个尚未走过的站点。在选站点时需要注意在当前站点和选中站点之间不能有其他的未选站点。

4 软件功能实现方案

综合以上分析，本系统采用Dijkstra算法进行可靠的路径规划运算，利用C++语言编程实现提高程序运行效率，弥补Dijkstra算法时间复杂度较高的缺陷，并且根据出行者乘坐地铁时的特殊情况进行规划模式上的优化改进。

本系统还增添了多媒体接口，用户能够在线使用语音输入和语音播放的功能。该语音功能采用了业界领先的科大讯飞智能语音平台。

1）语音功能技术难点分析

语音功能部分分为三个模块：讯飞云模块、语音录入模块、语音播放模块。

讯飞开放平台是开放的智能交互技术服务平台，提供了语音识别、声纹识别、自然语言处理等多项服务，让应用产品具备 “听说读写”的功能[8]。

在讯飞云模块，首先通过引入讯飞SDK的lib文件来间接调用语音函数：

#ifdef _WIN64

#pragma comment（lib，"../libs/msc_x64.lib"） //x64

#else

#pragma comment（lib，"../libs/msc.lib"） //x86

#endif

然后include以下几个头文件：

#include "qisr.h"

#include "qtts.h"

#include "msp_cmn.h"

#include "msp_errors.h"

SoundPlayer^ player = （gcnew SoundPlayer（text））;//音频播放器

player->SoundLocation = text;

player->Load（）;

player->Play（）;

m_soundFormat.cbSize = 0;

waveInOpen（&m_hWaveIn， WAVE_MAPPER， &m_soundFormat， （DWORD_PTR）（waveInProc）， 0， CALLBACK_FUNCTION）;

在语音录入模块，首先采集PCM音频流，再将其封装为wav格式的音频。该模块使用了回调函数的方法：

该模块采集音频的格式为：

在语音播放模块，直接使用了System：：Media命名空间下的类SoundPlayer：

memset（&m_soundFormat， 0， sizeof（m_soundFormat））;  //设置声音格式

m_soundFormat.wFormatTag = WAVE_FORMAT_PCM;  //声音格式为裸流PCM

m_soundFormat.nChannels = 1;  //采样声道数

m_soundFormat.nSamplesPerSec = 22050;   //采样率 22050次/秒

m_soundFormat.nAvgBytesPerSec = 22050 * 1 * 16 / 8;   //每秒的数据率

m_soundFormat.nBlockAlign = 1 * 16 / 8;   //一个块的大小

m_soundFormat.wBitsPerSample = 16;  //采样比特

m_soundFormat.cbSize = 0;

2）路径规划功能

本地铁路径规划系统有三种路径规划方式，分别是少换乘、少停站和周游一圈。

实现这三种功能的具体步骤是：

第一步：把一条地铁线路上相邻两站点之间的边设为二元组，并且这两个站点之间用（0，1）的边相连。

第二步：把n条地铁线路交叉产生的一个站点看作是n个位置重合的站点，并且这些站点之间用（1，0）的边相连。

第三步：选择“少换乘”模式时，以整个二元组为键，进行Dijkstra计算，得出起点与终点间换乘次数最少的最优路径;选择“少停站”模式时，以二元组的第二元为键，进行Dijkstra计算，得出起点与终点之间站点数量最少的最优路径。

选择“周游一圈”模式时，首先预处理任意两点间的最短距离，然后每次选择一个尚未走过的点，从当前点以最短路径走到选中的这个尚未走过的点。在选点时需要注意在当前点和选中点之间不能有其他的未选点。

少停站规划模式的实现代码：

int do_lessstop （std：：string s， std：：string t） {

//如果没有设置起点或没有設置终点，直接返回1，不继续执行少停站的算法

if （this->mp.find（s） == this->mp.end（） || this->mp.find（t） == this->mp.end（））

{

return 1;

}

//如果设置了起点和终点，继续执行少停站的算法

int src = this->mp[s]; //起点

int tar = this->mp[t]; //终点

//少停站模式下做dijkstra计算

PA &tmp = this->bfs（src， tar， planMode：：pm_Short）;

this->print_plan（tmp）; //输出方案

return 0;

}

少换乘规划模式的实现代码：

int do_lesstrans（std：：string s， std：：string t） {

//如果没有设置起点或没有设置终点，直接返回1，不继续执行少换乘的算法

if （this->mp.find（s） == this->mp.end（） || this->mp.find（t） == this->mp.end（））

{

return 1;

}

//如果设置了起点和终点，继续执行少换乘的算法

int src = this->mp[s]; //起点

int tar = this->mp[t]; //終点

//少换乘模式下做dijkstra计算

PA &tmp = this->bfs（src， tar， planMode：：pm_convi）;

this->print_plan（tmp）; //输出方案

return 0;

}

程序路径规划功能模块的UML类图如图4所示。

3）软件测试用例及测试结果

在上海地铁地图上，将起点设置为上海火车站，将终点设置为常熟路。

如图5所示，使用少换乘模式规划路线时，程序计算出的规划方案为：换乘0次、经过6站到达目的地，程序的运算时间为0.1秒。

如图6所示，使用少停站模式规划路线时，程序计算出的规划方案为：换乘2次、经过4站到达目的地，程序的运算时间为0.1秒。

如图7所示，使用少换乘模式规划路线时，程序计算出的规划方案为：换乘0次、经过6站到达目的地，程序的运算时间为0.1秒。

如图8所示，使用少停站模式规划路线时，程序计算出的规划方案为：换乘2次、经过4站到达目的地，程序的运算时间为0.1秒。

结果表明，使用二元组改进的Dijkstra算法能够正确地且高效地计算出少换乘和少停站模式下的最优路线。

如图9所示，在苏州地铁地图上，以苏州火车站为起点进行周游一圈模式的路线规划，程序计算的规划方案为：经过166站，换乘10次，遍历了所有站点，同样以苏州火车站为终点结束苏州地铁周游，程序的运算时间为0.3秒。

结果表明，程序能够正确且高效地遍历地图上所有站点。

5 应用前景

本系统当前应用于地铁出行的路线规划，也可以扩展成任何公共交通系统的出行路线规划工具，如公交、地铁、电车、高铁等等。只要用户按照存储地铁信息的外部txt文件的格式导入新的公共交通系统地图，即可让该系统提供更多的最优路线规划服务，从而应用在更多的公共交通情景下。

本系统扩展自定义地图后，还可以应用于停车场空车位的最优路线导航[9]，找出最优泊车路径， 从而大大提高停车效率，改善泊车感受[10]。本系统甚至可以应用在景区、大商场、博物馆中，提供“周游一圈”的服务，让游客能够游览全部景点、门店或文物展品。

6 地铁出行线路规划系统特点与优势

1）科学。本系统采用优化改进的Dijkstra算法进行最短路线规划运算，程序具有科学性、可靠性。

2）高效。程序采用C++语言编写，运行效率高，少换乘、少停站两种规划模式的运算均可在0.1秒完成。在具有大量站点的密集地铁网络中（如上海地铁，共329站）使用周游一圈模式遍历所有站点时，程序的运算可在10秒内完成。这说明程序在大量数据集下依旧有良好的表现，具有推广到城市公交等大型公交网络线路的潜力。

3）稳定。本系统不闪退、死机，加入了对于可能出现的错误的提示反馈机制，可以连续工作，为城市出行者提供不间断的路线规划服务。

4）便捷。本系统加入了多媒体接口，用户可实现语音输入，对于已完成规划的路线，不仅可以在地图上用图例展现出具体路线方案，还可以声音输出具体的路线方案。本系统还可通过接入硬按键，捕获用户按下的快捷键来实现对应的语音输入功能、路线规划功能、语音播放功能等等，进而为盲人等弱势群体提供便捷、可靠的出行路线规划服务。

5）应用广泛。本系统通过导入存储站点信息的本地txt文件，可以扩展成任何公共交通系统的出行路线规划工具，如公交、地铁、电车、高铁等，用途多样、广泛。

6）支持触摸屏。本系统以手持设备的方法设计并实现了相关功能，使软件可以在公共触摸查询台上提供更人性化的服务。

7）功能齐全。本系统提供三种路线规划模式，少换乘、少停站和周游一圈。其中周游一圈模式可供出行者城市观光时使用。

8）研发历程与项目实践。本项目经历了超过8个月的研发与多次的测试，并在多个地铁出入口让路人进行测试，目前可正式投入使用。

7 结束语

本系统通过对Dijkstra算法的合理利用与改进，将Dijkstra算法引入了地铁查询领域，实现了科学、稳定、高效的路线规划功能，并且根据地铁出行用户的特殊需求提供了三种不同的路径规划模式，能够有效节约地铁出行者的时间资源，助力低碳出行。系统还提供了语音输入和语音播放功能，使地铁线路查询变得更加智能化、人性化。该项目参加了2018年的iTeach全国大学生数字化教育创新大赛，并获得一等奖。

参考文献：

[1] 陈东银，宋艳敏.Dijkstra算法在地铁换乘中的应用[J].信息系统工程，2012（10）：83-84，108.

[2] 花玲玲.基于GIS空间分布特征的Dijkstra最短路径算法研究[D].重庆：重庆大学，2007.

[3] 江嘉健.基于改进Dijkstra算法的地铁线网应急乘车导引系统的设计与实现[D].广州：华南理工大学，2013.

[4] 苑禹晨，李岩，陈琪晟，等.基于Dijkstra优化算法的多媒体地铁综合信息查询系统[J].铁路通信信号工程技术，2013，10（3）：44-48.

[5] 吕琼艺.基于改进的Dijkstra算法的旅游规划线路研究与实践——以鼓浪屿景区为例[J].柳州职业技术学院学报，2017，17（2）：32-36.

[6] 张本俊，周海娇，刘淑琴.改进Dijkstra算法在公共交通出行的研究[J].物联网技术，2018，8（11）：45-48.

[7] 韩慧玲，胡红萍.Dijkstra算法在公交换乘最短路径中的应用[J].硅谷，2011，4（21）：111，126.

[8] 魏佳.基于讯飞云的儿童语言行为发育评估系统的设计与实现[D].南宁：广西大学，2017.

[9] 程小凤.Dijkstra改进算法在停车场内部路径引导中的应用[J].交通科技与经济，2016，18（5）：26-29.

[10] 王维，盖之华.基于Dijkstra算法的停车场泊车引导路径设计[J].网络安全技术与应用，2018（9）：52-53.

【通联编辑：谢媛媛】