Efficient Route Planning on Public Transportation Networks: A Labelling Approach

本文主要是介绍Efficient Route Planning on Public Transportation Networks: A Labelling Approach,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

EfficientRoute Planning on Public Transportation Networks:A Labelling Approach

sigmod-2015

1.    问题定义

本文是基于公交网络的有效的路径规划。

1)           EAP:Earliest Arrival Path 最早到达时间路径

2)           LDP:Latest Departure Path 最晚离开路径

3)           SDP:Shortest Duration Path 最短持续时间路径

对于EAP最早到达时间路径,给定一个开始时间,即在起始点的时间,计算最早到达终点的路径。对于最晚离开时间路径给定一个到达终点的时间计算从开始点离开最晚的路径。用标签来表示,标签的格式如下:<u,w,v,b,startTime,endTime> 一共6个元素,u,w,v分别是开始点,中间点,结束点;startTime,endTime分别是这条路径的开始时间和结束时间。b是公交的类型。

我们要求的就是EAP,LDP,SDP这三种路径,以便于人们的查询。

2.    问题求解

1)首先了解什么是受控制路径。

受控制的路径:一条路径A,开始时间比路径B开始时间晚,但结束时间不晚于路径B的结束时间。或者路径A开始时间不早于B,而结束时间早于路径B的结束时间。

我们要访问的是不受控的路径,受控的路径不去访问。

2)我们要对每一个结点建立一对标签,标签分别是Lin,Lout,记录从一个顶点的in标签和out标签。先访问哪个结点开始建立呐呢?对于访问结点有一个排名,从各个结点中找一个覆盖路径条数最多的。例如:下图中 v1 6条路径(<1,2,2,3><1,2,3,4><1,2,4,5><2,3,3,4><2,3,4,5><3,4,4,5>),v29条(<1,2,2,3><1,2,3,4><1,2,4,5><2,3,3,4><2,3,4,5><3,4,4,5>;<2,3>;<3,4>;<4,5>),v36条路径。

2015年10月17日 - 雨竹清风 - 雨竹清风的博客

 将这个覆盖较多的结点给出一个最大值,然后连同其边删除后,计算剩余结点所包含的的路径的条数,则获得相应的分数。这样每个结点的排名就出来了。例如上图中将v2的排名赋为3,删除v2以及相关连的边,得到的v1,v3路径为0,所以随便给定一个互异的分数即可,只要比v2的小就可以。

然后根据结点的访问顺序开始访问,从开始点v出发的边中选出一个最晚开始时间(为什么呐?)的路径。从一个点出发,可能不止一条路径,因此建立一个小顶堆(按到达时间排列,时间晚的入堆时间也晚)。堆中的格式如下:2015年10月17日 - 雨竹清风 - 雨竹清风的博客 开始点,结束点,开始时间,结束时间,公交类型。

 

2015年10月17日 - 雨竹清风 - 雨竹清风的博客

首先入堆的是1,2,10,11,a; 用一个表来记录相应的信息,t是到达时间,b是公交类型,p代表的是转折点,即通过的结点,如下图所示。然后将从v2出发找到对应的出边<11,12>,<11,13>将其入小顶堆。随后一直找下去,直到没有出边为止。这是处理从<10,11>这条边出发的路径,因此下一次找的是从<9,10>边出发的路径。。。。。。

 2015年10月17日 - 雨竹清风 - 雨竹清风的博客

 最终处理完<10,11>开始的路径,获得的这张表的数据如下:

 2015年10月17日 - 雨竹清风 - 雨竹清风的博客

 从这张表开始建立inout标签,标签中元素有<开始点/终点,开始时间,结束时间,公交类型,转折点>,如图所示:2015年10月17日 - 雨竹清风 - 雨竹清风的博客
 

null代表的是公交类型不一致,或者没有转折点。

将从开始点出发的每一条边的路径全部做完上述操作后,inout标签就建立完了。这是对于一个结点出发的,下一步就是将这个结点以及边删掉后剩余的结点出发重复上述建立标签的过程,直到所有的结点全部建立完毕结束。整个算法的时间复杂度是(为什么呢?)。

怎么找上述3种路径呢?

SDP为例:从in,out标签中查找即可,查找开始点的out标签, 结束点的in标签,若有重叠的点,那么就是一条路径。还有一种情况就是通过某个结点进行了转折,则查找某个结点的inout标签中有没有从开始点入,out标签中有没有到达结束点的,这样也是一条路径。从这些路径中选择持续时间最小的即可。

    下图中红色区域便是找到的标签。

2015年10月17日 - 雨竹清风 - 雨竹清风的博客

对于开始点结束点相同的标签可以压缩成一种形式,如下,以v1开始,v2结束的标签:   2015年10月17日 - 雨竹清风 - 雨竹清风的博客压缩后为:r1代表的是对公交类型的压缩。2015年10月17日 - 雨竹清风 - 雨竹清风的博客


也可以通过转折点压缩:

2015年10月17日 - 雨竹清风 - 雨竹清风的博客

 压缩后:

 2015年10月17日 - 雨竹清风 - 雨竹清风的博客

 在查询的时候有可能是从压缩找到另一个压缩的标签,所以直到找到一个不是压缩的为止。

3.总结

通过建立标签的形式来查询SDP,LDP,EAP的路径,所以可以对于某些问题建立索引是一个好的方法。本文提出了两种压缩方式:一个基于路径压缩,一个基于转折点压缩。对于标签进行压缩,也是一种处理方式。

 

这篇关于Efficient Route Planning on Public Transportation Networks: A Labelling Approach的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/284300

相关文章

DBeaver 连接 MySQL 报错 Public Key Retrieval is not allowed

DBeaver 连接 MySQL 报错 Public Key Retrieval is not allowed 文章目录 DBeaver 连接 MySQL 报错 Public Key Retrieval is not allowed问题解决办法 问题 使用 DBeaver 连接 MySQL 数据库的时候, 一直报错下面的错误 Public Key Retrieval is

[论文笔记]QLoRA: Efficient Finetuning of Quantized LLMs

引言 今天带来LoRA的量化版论文笔记——QLoRA: Efficient Finetuning of Quantized LLMs 为了简单,下文中以翻译的口吻记录,比如替换"作者"为"我们"。 我们提出了QLoRA,一种高效的微调方法,它在减少内存使用的同时,能够在单个48GB GPU上对65B参数的模型进行微调,同时保持16位微调任务的完整性能。QLoRA通过一个冻结的4位量化预

Transportation-POJ 1040

DFS练习题,直接暴力吧,600+MS过的。。。。不能DP,有后效性,还有以后少用memcpy了,复杂度好大。。。。。 #include<cstdio>#include<cstring>#include<iostream>using namespace std;int max_size,n,m;#define MAXD 100 + 10#define max(a,b) (a >

A Comprehensive Survey on Graph Neural Networks笔记

一、摘要-Abstract 1、传统的深度学习模型主要处理欧几里得数据(如图像、文本),而图神经网络的出现和发展是为了有效处理和学习非欧几里得域(即图结构数据)的信息。 2、将GNN划分为四类:recurrent GNNs(RecGNN), convolutional GNNs,(GCN), graph autoencoders(GAE), and spatial–temporal GNNs(S

c++ public、protected 、 private访问修饰符详解

在 C++ 中,访问修饰符用于控制类的成员(数据成员和成员函数)的访问权限。主要的访问修饰符有三个:public、protected 和 private。每种修饰符的访问规则如下: 1. public 定义:public 修饰符表示该成员对所有代码都是可见的,任何对象都可以访问和修改。作用:允许类外部的代码访问这些成员。 class Example {public:int publicVa

访问修饰符public、protected、private,基于C++

一、基本概念 公有(public)成员   公有成员在程序中类的外部是可访问的。您可以不使用任何成员函数来设置和获取公有变量的值, 私有(private)成员  私有成员变量或函数在类的外部是不可访问的,甚至是不可查看的。只有类和友元函数可以访问私有成员。 默认情况下,类的所有成员都是私有的。例如在下面的类中,width 是一个私有成员,这意味着,如果您没有使用任何访问修饰符,类的成

JAVA反射使用父类的非public方法(getMethods()和getDeclaredMethods()区别)

getMethods()和getDeclaredMethods()区别 虽然是老生常谈了,但是还是要先说一下两者的区别。 getMethods():能够获取类的所有public方法,包括自身定义的以及从父类继承的。 getDeclaredMethods():能够获取类本身的所有方法,包括private方法,实现的接口方法,但是不能获取从父类继承的非public方法。 因此getDeclaredM

Complex Networks Package for MatLab

http://www.levmuchnik.net/Content/Networks/ComplexNetworksPackage.html 翻译: 复杂网络的MATLAB工具包提供了一个高效、可扩展的框架,用于在MATLAB上的网络研究。 可以帮助描述经验网络的成千上万的节点,生成人工网络,运行鲁棒性实验,测试网络在不同的攻击下的可靠性,模拟任意复杂的传染病的传

Convolutional Neural Networks for Sentence Classification论文解读

基本信息 作者Yoon Kimdoi发表时间2014期刊EMNLP网址https://doi.org/10.48550/arXiv.1408.5882 研究背景 1. What’s known 既往研究已证实 CV领域著名的CNN。 2. What’s new 创新点 将CNN应用于NLP,打破了传统NLP任务主要依赖循环神经网络(RNN)及其变体的局面。 用预训练的词向量(如word2v

【机器学习】生成对抗网络(Generative Adversarial Networks, GANs)详解

🌈个人主页: 鑫宝Code 🔥热门专栏: 闲话杂谈| 炫酷HTML | JavaScript基础 ​💫个人格言: "如无必要,勿增实体" 文章目录 生成对抗网络(Generative Adversarial Networks, GANs)详解GANs的基本原理GANs的训练过程GANs的发展历程GANs在实际任务中的应用小结 生成对