智能多模态公交路线规划算法：大型网络优化策略

需积分: 9 166 浏览量更新于2024-07-22 收藏 2.32MB PDF 举报

本篇论文标题为《多模态公交路线规划》，是2009年在德国卡尔斯鲁厄大学（TH）计算机科学学院提交的硕士学位论文，由Thomas Pajor撰写。论文主要探讨了在处理大型交通网络中的公交路线规划问题，尤其是在空间和时间维度上进行有效整合的算法设计。论文首先介绍了研究背景和相关工作。当前的挑战在于传统的将空间和时间简单地融合到一个图中来解决路线规划的问题，在面对大规模的交通网络时效率低下。作者提到，已有的研究并未提供理想的解决方案，因此他们的工作旨在提出更智能的策略来应对这种复杂性。论文的核心部分涵盖了基础理论，如图论和语言与自动机的概念。图论是理解网络结构和关系的关键，它在这里用于构建和分析公交路线的连接性。另一方面，语言和自动机理论可能被用来处理时间依赖性因素，如列车时刻表，以确保合理的时间间隔和准时性。接下来，论文定义了两种模型：一是时间独立模型，强调的是静态的路线连接；二是时间依赖模型，考虑了动态因素，如交通流量、班次调整等，这对于实时公交路线规划至关重要。这两种模型的区别和相互作用是研究的重点，因为实际的公交系统通常需要在这两者之间找到平衡。此外，论文还提到了研究方法和贡献。作者可能采用启发式搜索、优化算法或组合数学中的技术来设计高效的公交路线规划算法。他们可能会探讨如何通过减少搜索空间、引入预计算数据或者利用并行计算来加速计算过程。最后，论文可能包含了一些具体的应用实例和实验结果，以验证其算法的有效性和性能。这包括对不同规模网络的测试，以及与现有算法的对比分析，以证明新方法在处理大规模公交路线规划问题上的优势。这篇论文深入探讨了在多模态公交系统中实施智能路线规划算法的重要性，以及如何克服传统方法在处理大规模网络时的局限性。它不仅涵盖了理论基础，还涉及到了实际应用中的策略和优化技术，为未来的交通规划提供了有价值的研究成果。

Chapter 2. Foundations

span. For that reason, all functions have to fulﬁll the FIFO-property, i.e., for any two

, τ

∈ R

with τ

< τ

it must hold that f (τ

) + τ

< f (τ

) + τ

. The FIFO-property

guarantees that along an edge it is never possible to depart later but arrive earlier. If it

holds for all τ ∈ R

that f (τ) = c for some c ∈ R

then f is called a constant function.

Let f , g ∈ F be two functions, then we deﬁne f ⊕ g := f + g ◦ ( f + id) as link-

operation. Here, id denotes the identity function. If both f and g are constant functions

we shall simply write f + g. This operation is used to cascade functions, i.e., to com-

pute the travel time along two or more subsequent edges. Please note that linking

is neither associative nor commutative, hence, the order of evaluation is important.

The minimum operation of two functions f , g ∈ F, denoted by min( f , g), is obtained by

taking the minimum value from f and g for each input τ ∈ R

. Sometimes, we also

refer to this operation as merge-operation since it merges two functions together.

The lower bound of a function f is the minimum value of f for any τ ∈ R

, denoted

by f := min

τ∈R

f (τ). Analogously, the upper bound of a function is the maximum

value of all its values: f := max

τ∈R

f (τ).

A time-independent lower/upper bound graph G/G can be obtained from G by

replacing each edge function with their lower/upper bounds.

Paths. A path P in G is a sequence of nodes [v

, v

, . . . , v

] such that for each 1 ≤ i < k

the condition (v

, v

i+1

) ∈ E holds. If additionally v

= v

, then we call P a cycle. Note

that a path may contain certain nodes multiple times without being a cycle. A subpath

S ⊂ P is a path itself which is fully contained in P. By |P| we denote the number of

edges along the path.

The length of a path P is the sum of its edge weights along the path and is denoted

len(P) :=

k−1

∑

i=1

+1)

= f

)

⊕ f

)

⊕ · · · ⊕ f

k−1

)

(2.1)

Note that len(P) yields a function which can be interpreted as the travel time along

the path at any given time point τ. However, if all edge weights along the path are

constant, then len P is constant as well.

Often we are only interested in the length of a path for a given departure time

τ ∈ R

. In this case len(P, τ) is deﬁned recursively as follows.

• For |P| = 1: len(P, τ) := f

)

( τ),

• for |P| > 1: len(P, τ) := len(P − v

, τ) + f

k−1

)

( τ + len(P − v

, τ)).

2.2. Languages and Automata

In other words, len(P, τ) is obtained by walking along the path starting at time τ

and evaluating each edge function at time τ plus the distance already covered along

the path. For that reason, the result obtained by len(P, τ) is a scalar value.

The distance between two nodes u, v ∈ V, written by dist(u, v, τ), for a given depar-

ture time τ, is the minimal length of all paths P from u to v. Note that it is possible

that there might be more than one minimal path from u to v. A minimal path P be-

tween two nodes u and v at time τ is called shortest path from u to v. The travel time

function representing the length of all shortest path over all times of day is denoted

by dist

∗

( u, v).

We call two nodes u, v ∈ V connected, if there exists a path from u to v. If this is true

for all pairs of nodes u, v ∈ V, we call the whole graph connected. For a non-connected

graph G, a connected subgraph G

⊆ G is called strong connected component of G.

2.2. Languages and Automata

Languages. Let Σ be a ﬁnite set of symbols often called alphabet. A sequence w :=

[σ

, σ

, . . . , σ

] of symbols from Σ is called a word. For simplicity, we just write w =

. . . σ

. The length of a word is the number of symbols it is composed of. The

empty word is denoted by ε and has length 0. For two words w

:= σ

. . . σ

and

:= σ

k+1

. . . σ

the concatenation of the two words w := w

is obtained by simply

appending the second word to the ﬁrst, hence w = σ

. . . σ

A not necessarily ﬁnite set L of words over Σ is called a language over Σ. All opera-

tions on sets like union, intersection and difference also apply to languages. If L is an

arbitrary language, then the i’th power set of L is deﬁned recursively by

• If i = 0: L

:= {ε} and

• if i > 0: L

:= {wv | w ∈ L

i−1

and v ∈ L}.

With this notion, we introduce an additional operation. The Kleene-Closure of a lan-

guage L is deﬁned by

∗

[

i≥0

. (2.2)

In the special case of L = Σ, the Kleene-Closure yields all possible words (includ-

ing the empty word) that can be created by the alphabet of Σ. Finally, for two lan-

guages L

, L

⊆ Σ

∗

the concatenated language L

· L

is obtained by L

· L

:= {vw | v ∈

and w ∈ L

It turns out that for our purposes general languages are too powerful. Therefore,

we restrict ourselves to regular languages for which we give a detailed deﬁnition.

Chapter 2. Foundations

c r

Figure 2.1.: A simple ﬁnite automaton given by its transition graph with 4 states from which 2 are

initial states and 3 are ﬁnal states.

Deﬁnition 1 (Regular Languages). Let Σ be an alphabet. Then a language L over Σ is

regular if and only if it conforms to the following construction rules.

• The empty language ∅ is regular.

• For each σ ∈ Σ the singleton language {σ} is regular.

• If L

and L

are regular languages, then L

∪ L

, L

· L

and L

∗

are also regular lan-

guages.

Besides using regular expressions, another way to describe regular languages is by

deﬁning a ﬁnite automaton.

Finite Automata. A non-deterministic ﬁnite automaton A := (Q, Σ, δ, S, F) consists of

a ﬁnite set Q of states, an alphabet Σ , the transition function δ : Q × Σ → P(Q), a

set S of initial states and a set F of ﬁnal states. Most of the time, we describe a ﬁnite

automaton visually by its transition graph: States q ∈ Q are drawn as nodes and for

each state q ∈ Q and every symbol σ ∈ Σ we draw an edge from q to q

labeled by σ

if and only if q

∈ δ(q, σ). Initial states are marked by an incoming edge-tip whereas

ﬁnal states are twin-framed. Figure 2.1 shows a simple example of a ﬁnite automaton.

Let L ⊆ Σ

∗

be an arbitrary language. We say that a word w ∈ L is accepted by A,

if there is a path in the transition graph starting at an initial state q

∈ S, leading

to a ﬁnal state q

∈ F and where the subsequent edges on the path are labeled by

the subsequent symbols of w. If no path fulﬁlling these properties exists, the word

is rejected. If it holds for every word w ∈ L that w is accepted by A, we say that the

language L is accepted by A.

By Kleene’s Theorem [Kle, RS59] each regular language L can be described by a

(non-deterministic) ﬁnite automaton A in the sense that for every word w ∈ Σ

∗

holds that A accepts w if and only if w ∈ L. On the other hand it is true that for

every ﬁnite automaton A the set of words accepted by A has the properties of being

a regular language. Hence, the terms regular language and ﬁnite automaton can be

interchanged.

Chapter 3. Models

on the departure time at the source.

3.1.1. Time-Independent Models

Time-independent routing has been studied in great detail [DSSW09a] and is mostly

used in road networks. In a time-independent network each edge e is assigned one

constant value w(e) which may be travel time, geographical distance or any other met-

ric that we like to minimize. Suppose we have an edge reﬂecting a road segment in a

road network. If we assign this edge a constant value, our query will always produce

the same result when using this edge. While this is perfectly sufﬁcient for certain met-

rics like geographical distance (The geographical distance of a road segment does not

depend on the time), it might not be realistic enough for others. If we use travel time

as metric, imagine using a motorway during rush hour in contrast to off hours. We are

much slower on the same motorway during the rush hour due to trafﬁc congestions.

Not having time-dependencies makes the model simpler. To solve shortest path

queries on such a network, we can use Dijkstra’s algorithm with only minor modiﬁ-

cations (See also Section 4.2.1). For that reason lots of research focused toward acceler-

ating shortest path queries on time-independent models (mostly road networks) which

resulted in very impressive speed-up techniques. An overview is given in [DSSW09a].

While in a road network the absence of time-dependency still yields useful queries,

other models like those for railway timetables most certainly do not. The prob-

lem of time-dependency is inherent to these models, because trains only operate at

certain times and therefore the choice of the quickest route highly depends on the

departure time of the journey. Although, there are approaches for eliminating the

time-dependency in the model, namely by time-expansion (See Section 3.3), the more

canonical approach is to generalize the time-independent model itself to incorporate

the concept of time-dependency.

3.1.2. Time-Dependent Models

In time-dependent routing we do no longer have constant weights assigned to the

edges. To accommodate for time-dependency, we replace the edge weights by arbitrary

functions f from some function space F. The shortest s-t-path in a time-dependent

model then depends on the departure time τ

of the source node. This might result in

shortest paths of different length for different departure times or—in general—even a

completely different route.

In Section 2.1 we restricted ourselves to periodic functions f : R

→ R

. However,

using arbitrary periodic functions is not adequate for an efﬁcient implementation of

the query algorithm.

剩余170页未读，继续阅读

DawsonSally

粉丝: 130
资源: 18

智能多模态公交路线规划算法：大型网络优化策略

RoutePlan.zip

算法可视化AlgorithmVisualizer.zip

https://github.com/zhoushiwei/GeneticAlgorithm/blob/master/GA_single_robot_path_planning.m打开这个网站

open /usr/local/algorithm/docker/tmp/docker-import-415978328/repositories: no such file or directory

无法打开 源 文件 "pinocchio/algorithm/frames.hpp"C

如何调用algorithm visualizer接口

algorithm visualizer怎么用

最新资源

无法打开源文件 "pinocchio/algorithm/frames.hpp"C