计算机英文论文翻译

外文资料翻译原文

外文资料翻译原文部分：

Deterministic Time Table Transit Assignment

Abstract: The basic timetable based assignment problem is to find an optimal path

for a passenger, given an origin node, a destination node, and departure or arrival

time information. The deterministic transit assignment does not necessarily minim_

ize the total elapsed travel time, but rather uses weight factors and non-time-based

cost elements in determining the optimal path. Therefore, the algorithm tracks both

Isabelle Constantin, Linda James-Lefebvre and Gabriela Simonka.

Deterministic Transit Assignment

1 General problem definition

The timetable information for each transit line is specified via the following

attributes:

• The headway is the interval between successive runs of the line (in minutes).

• The offset is the departure time of the first run (in minutes after the beginning of

the period).

• The number of runs is the number of times the line operates.

• The segment time is the travel time on a transit segment.

The deterministic transit assignment problem is solved by using a least cost path

algorithm on a space-time network, given by the timetable information plus the

transit and auxiliary transit (walk) network. An efficient implementation of such an

algorithm must consider the following points:

• As the timetable information is based on repetitions (many runs of the same line),

the space-time network can become very large (even infinite for continuous

services).

• As walking (or using an auxiliary transit mode) is considered to have an infinite

frequency, the space-time network theoretically contains an infinite number of

corresponding links. Even if, in an optimal path, walking always starts immediately

memory space). The algorithm computes paths either forward (starting at the

origin), for trips with a desired departure time, or backward (starting at the

destination) for trips with a desired arrival time.

Description of the algorithm (for trips with a desired departure time)

• The basic space-time network element on which the assignment is based is an

event. An event is the combination of a place (node or segment) and a time. A path

From-event To-event Activity

node node walking

node segment waiting and boarding

segment segment riding

minimum cost at which an event can be reached from the origin.

• The algorithm successively retrieves the event with the least cost from the heap

and scans it, that is, it checks for all possible next activities (which depend on the

event type):

Event type Possible next activities

node • for all lines stopping at node, wait and board the next vehicle that

passes

• for all auxiliary transit links leaving node, “walk” to

neighboring node

segment • continue riding on the next segment of the same line

• If such an event r does exist, it dominates the potential new event p, so that the

latter does not even have to be created (see Event dominance on page -4).

• If no event r satisfies the above condition, the new event p is inserted into the

heap.

In other words, the above formula tests if the cost of the new event p is less than

the cost of an earlier event r plus the cost of waiting from tr to tp.

formula as above, to see whether they are dominated by the new event. All events

dominated by the new event can be removed from the heap and deleted, since they

cannot be part of the optimal path.

• The algorithm terminates if an event corresponding to the destination node has

case of several destination nodes (which allows the simultaneous assignment of

be explored. Since any dominated event does not need to be considered further:

• the algorithm does not include a dominated event (in the heap)

• when including a new element (in the heap), the algorithm discards (from the

heap) any element dominated by the new one.

For example, consider the following two events that occur at a given node or

segment:

E1 with time t1 and cost c1

E2 with time t2 and cost c2

The earlier event E1 (t1 < t2) dominates E2 if c1 + (t2 - t1)*w <=c2 where w is

In Figure 2, A, B, C, D, and E are existing events at a given node or segment. The

shaded region shows the area dominated by these events. The algorithm is now

considering the two new potential events X and Y.

• The potential event X is in the dominated area, so it does not have to be

considered any further. In this case, it is the events B and C which are dominating

X:

the existing events. So the event Y is created and inserted into the heap. Testing Y

against the later events D and E shows that Y dominates both of them:

cY + (tD - tY)*w <=cD and cY + (tE - tY)*w<=cE

so that they can both be discarded.

Figure 3 shows the new cost/time diagram, after event Y has been inserted into the

• Event B (for example, arriving with line B) occurs earlier than event X (for

example, arriving with line X). Also, the cost of event B plus the cost of waiting

until event X (arrival of line X) is less than the cost of event X. So event B

dominates event X.

• Event B also occurs earlier than event C (for example, arriving with line C). But

the cost of event B plus the cost of waiting until event C (arrival of line C) is larger

than the cost of event C. So event B does not dominate event C.