Geoscience Reference
In-Depth Information
(Mesa and Boffey
1996
; Díaz et al.
2004
), more precisely that of locating paths and
networks. Cast in the framework of graph theory, the problem is to select a path
between two nodes (which could be fixed a priori) and some of the intermediate
nodes to be stations, in order to optimize an objective function subject to certain
constraints. In the continuous setting, the problem is that of selecting a straight-
line, a broken line (polygonal segment) or a curved segment and some points on it.
If the rapid transit line is planned to be at grade, it is almost always necessary to
work with a discrete setting, but if the network is to be constructed underground,
then a mixed network-continuous space fits better. Here we consider the problem
of locating a path and the points on it, leaving the case of locating the stations on
a given alignment to Sect.
22.4
. Therefore, the decision variables of the problems
considered in this section are those of the coordinates of the stations and of the links
connecting adjacent stations.
In order to realistically model the problem of locating an alignment, it is
necessary to consider several features in addition to those encountered in covering-
path problems (Current et al.
1985
). These include interstation spacing constraints,
competition or intermodality with other means of transportation, demand allocated
to pairs of points instead of single points, etc. The early paper of Gendreau et al.
(
1995
) proposes a simple algorithmic approach to the problem of locating a transit
line, but without any computational implementation. To our knowledge, Dufourd
et al. (
1996
) provide the first real attempt to solve the problem of locating a
transit line taking into account maximum and minimum station interspacing and the
number of allowed stations to be located. In that paper, the objective is to maximize
the population covered by the stations. This is computed by using several levels of
catchment with the use of the Manhattan or `
1
metric. The authors solve the problem
by means of tabu search. The paper by Bruno et al. (
1998
) incorporates the more
realistic criterion of maximizing trip coverage, as opposed to population coverage.
In order to introduce real-world features into their model, the authors consider a
private mode of transportation competing with the bimodal pedestrian-public transit
mode. Each mode uses its respective network and the demand is assigned to the
mode with the least travel cost. The problem consists of computing non-dominated
solutions with respect to cost and trip coverage objectives. Bruno et al. (
2002
)
consider the same model as in Dufourd et al. (
1996
), except for the use of the `
2
metric instead of the `
1
metric for interstation distances. They develop a heuristic
consisting of two phases: the construction of the path and the iterative improvement
of it. This heuristic is shown to produce better solutions in less time than the tabu
search approach of Dufourd et al. (
1996
).
A similar approach was used in Laporte et al. (
2005
) to solve the more complex
problem of maximizing trip coverage in the presence of an alternative mode of
transportation. Instead of considering a binary variable to decide to which mode the
demand pair should be allocated, the authors use a continuous variable representing
the distribution of the demand between each mode, according to a logit function
which depends on the difference between travel times (or costs) of both modes.
