CSIS Discussion Paper No. 126

Computer-aided design of bus route maps

Yukio Sadahiro*, Takahito Tanabe**, Maxime Pierre***, & Koichi Fujii**

May 2014* Center for Spatial Information Science, The University of Tokyo** NTT DATA Mathematical Systems Inc.
*** National School of Geographical Sciences, The Université Paris Diderot

Center for Spatial Information Science, The University of Tokyo

5-1-5, Kashiwanoha, Kashiwa-shi, Chiba 277-8568, Japan
E-mail: sada@csis.u-tokyo.ac.jp

Computer-aided design of bus route maps
Abstract
The bus route map is a diagram that aims to convey necessary information for map readers
to find an appropriate way of moving from an origin to a destination. Design of bus route map is acomplicated and time-consuming task that requires careful consideration of visibility and aesthetics.
This paper proposes a new computational method for designing bus route maps. The method helps
us to reduce the six types of undesirable elements in bus route maps, i.e., intersection, gap, shift,
overlap, misalignment, and acute bend. The method consists of two phases: the topological phasedetermines the relative order of bus routes on each road segment and the cartographic phasecalculates the actual location of bus routes drawn on a map. This paper applies the method to thedesign of bus route maps of Chiba City, Japan. The result supports the effectiveness of the method
as well as reveals open topics for future research.
Keywords: bus route maps, computational procedure, mathematical optimization,
cartographic design-2-Introduction
The bus route map is a diagram that visualizes the bus route network as a schematic map.
Figure 1a illustrates a part of hypothetical bus route map. Similar to the metro map, it aims to convey
necessary information for map readers to find an appropriate way of moving from an origin to a
destination. The bus route map emphasizes the network structure of bus routes, i.e., the topologicalrelationship between bus routes, terminals, and junctions, without drastically changing theirgeometrical structure. Design of bus route map is a complicated task that requires carefulconsideration of visibility and aesthetics. Assistance of computational method is highly desirable
and useful for improving the efficiency of this time-consuming manual process.
Few methods are available for computational design of bus route maps at present. However,efficient algorithms of metro map design have been developed in computer science and operations
research. The metro map visualizes metro lines as a diagram that provides an effective way ofnavigating the metro network (Ovenden 2003). Existing algorithms can be broadly classified into
cartographic methods and topological methods, each of which focuses on the cartographic andtopological aspect of metro map, respectively.
Cartographic methods focus on the geometrical properties of metro network, i.e., angle,
length, and arrangement of metro lines and stations. The earliest example is Beck's Underground
Map of London published in 1931 (Garland 1994). This schematic metro map utilizes only
horizontal, vertical, and diagonal lines to indicate metro lines and locates metro stations evenly on
the lines. Following the rules of Beck’s map, Hong, Merrick, and Nascimento (2005) and Hong,
Merrick, and do Nascimento (2006) develop five automated methods for generating metro maps.
They formulate map design as a mathematical programming problem to find a compromise between
conflicting rules. Stott and Rodgers (2004) and Stott et al. (2005) also take a similar approach though
they consider some additional conditions. Nöllenburg and Wolff (2006) utilizes a different
optimization problem that strictly ensures the octilinearity of metro lines.
Topological methods stress the topological structure of metro network. The topology ofmetro map primarily depends on the topology of actual metro network. However, when more thana single line share the same section between stations, the arrangement of metro lines in the section
can be determined flexibly to some extent on a map. Inappropriate arrangement causes unnecessaryintersections of metro lines, which reduces the aesthetics and readability of the map. To avoid thisproblem, Benkert et al. (2007) formulates the metro map design as an optimization problem thatminimizes the intersections of metro lines. The paper proposes a computational algorithm that solves
the problem in O(|L|2) time by using dynamic programming. Bekos et al. (2008) calls the problem
the Metro-Line Crossing Minimization problem (MLCM) and extends it to the Metro-Line Crossing
Minimization problem with terminals at fixed station ends (MLCM-Fixed SE) where the location ofsome lines is fixed at their terminals. Asquith, Gudmundsson, and Merrick (2008) proposes a faster
algorithm that solves the MLCM-Fixed SE in polynomial time. The algorithm developed by-3-

Argyriou et al. (2009) and Argyriou et al. (2010) runs in O((|E|+|L|2)|E|) time for the MLCM
problem in a limited case. Nöllenburg (2010) considers three variants of the MLCM (MLCM-P,
MLCM-PA, and MLCM-T1) that can be computed in a shorter time.
The above methods are also applicable to the design of bus route maps since they share thesame objective with metro maps. Bus route maps, however, are usually far more complicated thanmetro maps so that their design involves a wider variety of problems to be solved. Figure 1b isanother bus route map indicating the same bus routes shown in Figure 1a. It contains the six typesof undesirable elements in map design, i.e., intersection, gap, shift, overlap, misalignment, and acutebend. They reduce not only the aesthetics but also the readability of bus route maps. Intersectionsof bus routes should be kept minimal as discussed in existing studies. Gaps between bus routes
increase the space required to locate all the bus routes on a single map. Shifts of bus routes on astreet cause the visual complexity of the map. Overlaps of bus routes make us difficult to distinguishbus routes running on different streets. Misalignments of bus routes and road network occur when
they are drawn simultaneously on a single map. Acute bends clutter the map especially when manybus routes are running in parallel.
The techniques developed for the metro map cannot fully resolve these six types ofproblems. Combining existing methods, we may avoid intersections, overlaps and acute bends.
However, existing methods do not consider gaps, shifts, and misalignments explicitly. There is no
integrated framework tailored for the design of bus route maps that treat the six types of undesirable
elements simultaneously. To answer this demand, this paper proposes a new computational methodfor designing bus route maps. Our focus is on the bus route map that is not highly schematized as
Beck’s map. Bus routes basically keep their geometrical structure as shown in Figure 1a. The
arrangement of bus stops is out of the scope of the paper since it is primarily determined by thelocation of bus routes. We describe our method in the next section, which is followed by several
applications. We finally summarize the result with discussion.
MethodOur method consists of two phases: topological phase and cartographic phase. The
topological phase aims to reduce the intersections, gaps, and shifts of bus routes. To this end, thisphase focuses on the topological structure of bus routes, or more specifically, determines the orderof bus routes on each link of road network. Using the obtained result, the cartographic phasecalculates the position of bus routes on a map. This phase aims to avoid the overlaps, misalignments,
and acute bends of bus routes. We describe the two phases successively in the following.
Topological phase
Table 1 summarizes the notations for spatial objects, constants, and variables used in the
topological phase. Suppose a road network on which a set of K bus routes R={R1, R2, ..., RK} are-4-

running. Figure 2a shows a part of road network, where white and black points indicate end nodes
and intermediate vertices of the network, respectively. Figure 2b shows bus routes and bus stops on
the network. We define a topological road model based on the road network to describe thetopological structure of bus routes. The model focuses only on the topological structure of road
network by omitting its geometrical properties such as the angle and length of each element. The
model neglects the roads without bus routes, intermediate vertices, and end nodes where bus routes
do not branch. Instead, the model adds extra nodes and links to represent the terminals of bus routes
explicitly. The nodes and links of the topological road model are simply called nodes and links,
denoted by N= and L={L1, L2, …, LM}, respectively. Figure 2c shows the topological road model
defined based on the road network and bus routes shown in Figures 2a and 2b. Nodes N1 and N3
indicate the branches of bus routes, while N2 and N4 correspond to terminals. Extra nodes and links
added at terminals such as N5, N6, L10 and L11 are called terminal nodes and terminal links,
respectively. The set of terminal links is denoted by L'={LM+1, LM+2, …, LM+Q}. Let Ei1 and Ei2 be thefirst and second end nodes of link Li, respectively. In Figure 2c, for instance, we may define E21=N1,
E22=N2, E31=N2, and E32=N3.
Here, we introduce the concept of street. A street is a sequence of connected links on which
bus routes should be drawn smoothly without locational shifts. One definition is that two links
belong to the same street if they are connected at an angle larger than a threshold value . In thisdefinition, the value of  is given a priori based on a cartographer's aesthetic sense. An alternative
is to adopt the definition of streets in the real world as they are. However, this choice is often
problematic since streets in the real world do not always run straight.
Bus routes are represented as sets of links in L+L'. Let pri be a binary function that indicates
whether route Rr is running on link Li:
1 if Rr is running on Li.
(1)pri  otherwise
0
Using this function, we represent route Rr as Rr={pr1, pr2, …, pr, M+Q} (r=1, ..., K). In Figure 2, forinstance, routes R1 and R2 are represented as
R1   p11 , p12 , p13 , p14 , p15 , p16 ,...

(2)

 1, 0, 0, 0,1, 0,...

andR2   p21 , p22 , p23 , p24 , p25 , p26 ,...
 1,1,1,1, 0, 0,...

,(3)

respectively.
Using the topological road model, we describe the arrangement of bus routes on a map.
Our focus is on the relative order of bus routes on each link. We define tracks to represent the-5-candidate location of bus routes on each link. Each track can be assigned at most a single route.
Link Li has a set of ni tracks denoted by Ti={Ti1, Ti2, ..., Tini}. Figure 3a illustrates tracks defined forbus routes shown in Figure 2. We prepare enough number of tracks on each link except terminal
links to keep the flexibility of bus route arrangement. On terminal links, the number of tracks isequal to that of bus routes terminate at the node.
To derive the arrangement of bus routes, we define the following variables (they also appear
in Table 1).
1) sij (1i, jM)
It is a binary function that becomes one if links Li and Lj belong to the same street:1 if Li and L j belong to the same street
sij  .
otherwise
0(4)2) ciejl (1rK, 1i, jM, 1e2, 1lnj)
This variable indicates the relative location of track Tjl around end node Eie counted
clockwise from Ti1 except the tracks of terminal links. Figure 4a illustrates the numbering of tracks
around node N3 counted from T61, where N3=E32=E41=E61=E72. In this case, for instance, c6161=1,
c6141=5, and c6173=10. If we evaluate the location of tracks in relation to L3, we have c3261=5, c3241=9,
and c3273=14. If Li is not connected with Lj at Eie, ciejl=0 for any l.
The above two variables act as constants in the derivation of bus route map since they are
given a priori. We then introduce variables to be determined through the arrangement of bus routes.
1) xrikjl (1rK, 1i, jM+Q, 1kni, 1lnj)
This is a binary variable that becomes one if route Rr is assigned to tracks Tik and Tjl, wherelinks Li and Lj are directly connected at a node. Figure 3b presents an assignment of routes to tracks.
The assignment of route R1, for instance, is represented as
1x1ikjl   0 i, j , k , l   1, 5, 2,1 ,  5,1,1, 2  .
 i, j , k , l   1, 5, 2,1 ,  5,1,1, 2 (5)Similarly, the assignment of route R3 is represented as
1x3ikjl   0 i, j , k , l   10, 3,1, 2  ,  3,10, 2,1 ,  3, 6, 2, 2  ,  6, 3, 2, 2  .
 i, j , k , l   10, 3,1, 2  ,  3,10, 2,1 ,  3, 6, 2, 2  ,  6, 3, 2, 2 2) yike (1iM, 1kni, 1e2)
-6-

(6)

This variable indicates the relative location of the track with which a route assigned to track
Tik at end node Eie is connected. It is defined byyike     ciejl xrikjl .
r

j

(7)

l

Figure 4b illustrates an assignment of bus routes. Route R3, for instance, is assigned to tracks T32
and T62. Consequently, we obtain y322=c3262=6 and y621=c6232=15. Similarly, since R2 is assigned to
tracks T33 and T43, y332=c3343=11 and y431=c4333=10.
3) zike (1iM+Q, 1kni, 1e2)This is a binary variable indicating the termination of the route assigned to track Tik at end
node Eie. It is defined byzike  rj L ', connected to Eie

x

rikjl

.

(8)

l

This variable becomes one only if the route assigned to track Tik terminates at end Eie. In Figure 3b,route R3 terminates at node N2 (=E22=E31=E10,1), and consequently, z321=1.
4) ike (1iM+Q, 1kni, 1e2)This is a binary variable indicating the connection of track Tik with another track at Eie bysharing the same route. It is defined by ike  1  r

j , connected to Eie

x

rikjl

.

(9)

l

In Figure 3b, tracks T12 and T51 share route R1 at node N1 (=E12=E21=E51). We thus obtain 122=511=1.
Similarly, route R3 yields 10,1,1=321=322=621=1.
5) ikme (1iM, 1k, mni, 1e2)This variable evaluates the undesirable arrangement of two bus routes, each of which is
assigned to track Tik and Tim at Eie, respectively. It is based on the number of gaps and intersectionsin the arrangement of bus routes. In general, a tradeoff relationship exists between the twoundesirable elements, i.e., reduction of gaps inevitably increases intersections. Since they are notcompletely avoidable, we need to seek a compromise. Variable ikme is defined by the following
inequality in such a way that cancels the gaps and intersections at Eie:
yime  yike  C  ikme    zike  zime   1    ike   ime  k , m, e, cieik  cieim  ,(10)where C is a constant larger enough than the number of tracks of Li, and  is the weight of gaps
compared with intersections ranging from zero to one. If gaps are more undesirable thanintersections, we adopt a large  to reduce gaps. If gaps are relatively acceptable, a small  reduces
intersections though it may increase gaps.
-7-

Using the above variables, we formulate the arrangement of bus routes as a mathematicaloptimization problem. The problem aims to minimize the undesirable arrangement of bus routes
measured by the summation of ikme.
Problem RA (Route Assignment):
minimize   
xrikjliekm , cSTiik  cSTiim

ikme

.

subject to1:

xrikjl  xrjlik

2:

xrikjl  r , i , j , k , l  xj  ,l  j ,l r , i , j , k , l rj l ik

 r , i , j ,   k  l 

3:

sij xrikjl  0

4:

pri     xrikjl     xrjlik
j i

k

5:

l

x

rikjl

1

 r , i  L ', k 



x

rikjl

1

 r , j  L ', l i , connected to link j

7:


r

 r , i l

j , connected to link i

6:

j i

k

l

l



x

rijkl

j , connected to link i

 i , k 

1

l

8:



zike   
xrijkl 
xrjilk 




r 
jL ', connected to Eie l jL ', connected to Eie l9: ike  1  r

j , connected to Eie i , k 

x

rikjl

l

10: yike     ciejl xrikjl
rjl

11: yime  yike  C ikme    zike  zime   1    ike   ime 
12:  ikme  0 k , m, e, cieik  cieim  i , k , m , e 

Table 2 briefly describes the above constraints. Among the three problems in the
topological phase, gaps and intersections are evaluated in the objective function while shifts are-8-considered in the third constraint. The problems can be either strictly prohibited or permitted to acertain extent. We can avoid gaps or intersections by setting  to 1or 0, respectively. A value
between 0 and 1 represents a compromise between gaps and intersections. If no shift is permissible,
we set  to zero. If a shift of one degree is acceptable, we adopt =1. One may even remove thethird constraint if shifts are not problematic at all.
Problem RA is a variant of the MLCM that aims to minimize the intersections of metro
lines. It is a binary integer programming problem whose global optimum cannot be obtained in apractical time. We thus employ a heuristic approach to solve Problem RA.
Cartographic phase
The topological phase yields the set of xrikjl’s that represents the topological arrangementof bus routes on a map, i.e., the relative order of bus routes on each link. Using the result, thecartographic phase calculates the actual position of bus routes drawn on a map.
We define a cartographic road model that indicates the location of road segments on a map.
The model is based on the original road network data such as shown in Figure 2a. The cartographic
road model neglects the roads without bus routes while adding extra nodes to represent the terminals
of bus routes. It involves both topological and locational information of road network, the latter ofwhich indicates the location of road segments on a map. Figure 5 displays the cartographic roadmodel of the road network shown in Figure 2. As seen in the figure, an extra node is added torepresent a terminal of bus routes. To distinguish the links of this model from those of topologicalroad model, we call the links of cartographic road model road sections hereafter. When roads are
represented as polygons in spatial data, road sections are given by the center lines of road polygons
as shown in Figure 5. If roads are already represented as a network, the cartographic road model isdefined based on the network data.
Each bus route is drawn as a collection of line segments, which we simply call segments.
Each road section is assigned a set of segments of the same length running in parallel at the sameinterval v. The number of segments of each section is equal to that of the tracks between the mostouter tracks that are assigned bus routes. On a street, the most outer tracks are defined based on all
the tracks of the sequence of sections. We initially locate segments in such a way that the center ofthe most outer segments is exactly located on each road section. If a track is not assigned a bus route,the place of its corresponding segment is kept empty. On a street, we place segments in such a waythat the summation of the distance between each road section and the center of the most outer
segments is minimized.
Figure 6a shows a part of a cartographic road model, where streets are indicated by boldlines. Figure 6b shows the initial location of segments on the network. The center of the most outer
segments basically fits road sections, though the segments are not centered on streets.
Given a set of segments, we connect them at each end. When two neighboring segments of-9-

a bus route intersect, we simply shorten the segments to connect them. If segments do not intersect,
we extend the segments until they connect. As a result, we obtain a map such as shown in Figure 6c.
This simple procedure, however, does not always work successfully. Problems often occur including
acute bends, overlaps, and misalignments.
Figure 6c shows an example of acute bends. Acute bends are acceptable when only a single
bus route is running. However, acute bends of many bus routes running in parallel degrade the visualquality of bus route maps. To avoid the problem, we calculate the angle between neighboring
segments and add extra segments if the angle is smaller than a predetermined threshold min. We
locate extra segments at intervals v at the same angle with the neighboring segments except for themost inner bus route. Figure 6d shows the result of this revision applied to the bus routes shown in
Figure 6c.
Overlaps of bus routes occur in dense road networks. Figure 7a shows the road sections on
which bus routes are running. Figure 7b is the initial location of segments of bus routes, whichcauses overlaps as shown in Figure 7c. We resolve the overlaps of bus routes by translating thesegments of one of the sections until the outer segments are clearly separated. In Figure 7b, forinstance, we translate segments of road section RS1 until segments S15 and S21 are clearly separated
as shown in Figure 7d.
Figure 8 shows the misalignments of road sections and bus routes. Misalignments occur
only on streets when bus routes and road network are displayed simultaneously on a single map.
Figures 8a and 8b shows road sections and the initial arrangement of bus routes, respectively. Twobus routes running from east to west are located away from road sections in Figure 8b. Since extreme
misalignments are clearly misleading, we calculate the distance between each road section and theclosest segment. If the distance is larger than a predetermined value d, we translate the ends ofsegments so that their center is exactly located on the road section. Figure 8c shows the result of
this revision applied to the segments in Figure 8b.
The above three revisions can be implemented as computational procedures. The
computational cost of simple algorithms is O(M'c), O(Mc2), and O(Mc), respectively, where M'c andMc are the number of intermediate vertices and road sections. The complexity of the second step canbe improved to O(Mc log Mc+Ic) by the algorithms proposed by and Chazelle and Edelsbrunner(1992), Mulmuley (1990), and Chazelle and Edelsbrunner (1992) where Ic is the number ofintersections. Since M'c< Mc, the complexity of the overall procedure is O(Mc log Mc+Ic).
The cartographic phase contains three parameters to be given, i.e., v, min, and d. Theinterval of segments v depends on the line width of bus routes w. In metro maps in Ovenden (2003),
metro lines running between the same stations are drawn as either v=w, i.e., contiguous to each other,or 1.2wv2.0w in many cases. This also holds for bus route maps provided on the Internet. The
other parameters min and d are not considered explicitly in existing metro maps. Acute bends andmisalignments are not serious problems in metro maps since only a few lines are running in parallel.
- 10 -

In bus route maps, on the other hand, min is usually between /4 and /2. Concerning d, there does
not seem to exist a common standard.
Manual adjustment of parameters and editing of bus route map
The above computational procedure does not always yield satisfactory bus route maps.

Adjustment of parameter values and manual editing of generated map are usually necessary to obtaina final product.
Both topological and cartographic phases contain parameters to be given by a cartographer,i.e.,  and  in the topological phase, and v, min, and d in the cartographic phase. Though they need
to be determined before the computational procedure, the initial setting does not assure the best
result. We recommend trying various values interactively with checking the obtained result.
Manual editing is also necessary in various situations. We illustrate two cases in thefollowing.
Figure 9 shows a case where two overlaps of bus routes interact with each other. Figures
9a and 9b are road sections and the initial arrangement of bus routes obtained in the cartographic
phase. Since the segments on sections S1 and S2 overlap, the computational procedure translates
those on S2 downward, which results in the overlap of segments on S2 and S3 as shown in Figure 9c.
In such a case, we need to translate segments on S1 and S3 simultaneously by hand to resolve all theoverlaps of segments as shown in Figure 9d.
Figure 10 shows another case where human decision is helpful. Figures 10a and 10b showroad sections and the initial locations of segments, respectively. Since the segments on S1 and S3
overlap, the computational procedure translates the segments on S3 to obtain Figure 10c. In this case,however, several other options are also available. We may translate the segments of all the sections
S1, S2, and S3 (Figure 10d), those of only S2 (Figure 10d), or omit several segments of S2 to connect
directly the segments of S1 and S3 (Figure 10f). Figures 10c, 10e, and 10f are safer than Figure 10d
because they translate the segments of only a single section so that the effect is locally limited.
Figure 10e looks well-balanced since the segments of longer sections S1 and S3 are both centeredwith respect to road sections. We can also choose Figure 10f if the angle between S1 and S3 is not
too acute. Final decision clearly requires the evaluation of a professional cartographer.
Applications
This section tests the effectiveness of the proposed method by generating bus route mapsof Chiba City, Japan. Source data are provided in GML format from the Ministry of Land,
Infrastructure, Transport and Tourism. We converted the data into text format to use in the
topological phase. We employed a mathematical programming software NUOPT ver.16 (NTTDATA Mathematical Systems Inc.) for solving Problem RA. NUOPT employs the tabu search
proposed in Nonobe and Ibaraki (1998) and Nonobe and Ibaraki (2001) to solve integer- 11 -

programming problems. Using the outcome of the topological phase, the cartographic phase
generates bus route maps by using Java language. We set  and  to 1 and 0, respectively, in all thecases except that shown in Figure 12a. This implies that we strictly prohibit shifts and gaps in ourapplications. The interval of bus routes v is 1.5w. Acute bends are defined by =/2. We set
parameter d to w, the maximum gap between bus routes and road network.
Figure 11 illustrates a part of bus route map obtained by the proposed method. The dottedlines indicate the initial result generated in the cartographic phase, where misalignments occur
between bus routes and road network. Since the gap is larger than d=w, the computational proceduretranslated the ends of segments to obtain the final result shown by solid lines.
Figure 12 shows the tradeoff between gaps and intersections in a bus route map. We set 
to 0 and 1 in the two figures, respectively. As a result, Figure 12a contains a gap between bus routes,
which is not observed in Figure 12b. On the other hand, the latter has more intersections of bus
routes; bus routes indicated by red and dark blue lines intersect three times in Figure 12b while they
do not intersect at all in Figure 12a.
Figure 13 shows a case where a manual editing was necessary. We revised the map in therectangular area of Figure 13, which is enlarged in Figure 14. Figure 14a shows the road sections
and their ends that correspond to bus stops. Nine bus routes terminate at bus stop B1. Figure 14b
shows a part of bus route map obtained by the automated procedure. Short black lines indicate theinitial location of segments assigned to bus routes of orange, red, and dark green lines. Since roadsection RS 1 is very short, the segments of the three bus routes on RS1 and RS 2 do not intersect at
adequate positions. The computational procedure thus removed the three segments on RS 1 togenerate the result shown in Figure 14b. This map, however, is misleading since the nine bus routes
do not seem to terminate at the same bus stop. We thus moved the segments on RS1 upward andthose on RS 2 downward by hand in such a way that they intersect appropriately to reach the result
shown in Figure 14c. Manual editing becomes necessary especially when many bus routes aredensely running.
Concluding discussion
This paper has developed a computational method for designing bus route maps. The

method is effective for resolving the six types of undesirable elements in map design, i.e.,intersections, gaps, shifts, overlaps, misalignments, and acute bends of bus routes. The method
consists of topological and cartographic phases each of which resolves three problems, respectively.
The paper applies the proposed method to the design of bus route maps in Chiba, Japan. The result
supports the effectiveness of the method as well as revealing situations where manual editing is stillnecessary.
We finally discuss some limitations of the paper and potential directions for future research.
First, bus route maps generated by the proposed method still requires manual editing.
- 12 -

Problems tend to occur especially when many bus routes are running on a dense road network. We
should further improve the method to reduce the time-consuming manual processes.
Second, implementation of the proposed method as an integrated computational package
should be considered. We need to run NUOPT, ArcGIS, and Java scripts separately to obtain the
final product at present. Conversion and transfer of spatial data between different platforms decrease
the efficiency of overall procedure. An integrated package that generates bus route maps directlyfrom spatial data in a standard format such as XML should be developed.
Third, the proposed method does not fully schematize bus routes as done in Beck's
Underground Map of London. If further schematization is necessary, we may use the existing
methods developed for metro maps mentioned in Section 1. The methods, however, may not work
successfully for bus route maps since they are far more complicated than metro maps. We may needto develop a new method for further schematizing bus route maps.
Fourth, the present paper does not consider the arrangement of bus stops. It is because thearrangement of bus routes is more crucial in map design. Bus stops are usually located by simply
following the arrangement of bus routes. This method, however, may not work especially whenmany bus stops are located along many bus routes. Bus stops may overlap with each other, which
requires a revision of the arrangement of bus routes. Simultaneous arrangement of bus routes andbus stops should be examined.
Fifth, color assignment of bus routes is an important topic. Unlike metro lines, bus routes
usually do not have their own colors that are consistently used in route maps, at bus stops and inside
vehicles. Since the choice of color scheme is flexible, we can choose a color scheme that minimizes
visual conflicts such as the close location and intersection of similar colors. We should incorporate
color design into the proposed method in future research.
References
Argyriou, E., M. A. Bekos, M. Kaufmann, and A. Symvonis. 2009. "Two Polynomial Time

Algorithms for the Metro-line Crossing Minimization Problem." In Graph Drawing, edited
by I. G. Tollis and M. Patrignani, 336-47. Springer Berlin Heidelberg.
———. 2010. "On Metro-Line Crossing Minimization." Review of. Journal of Graph Algorithms andApplications 14 (1):75-96.
Asquith, M., J. Gudmundsson, and D. Merrick. 2008. "An ILP for the metro-line crossing problem."
In Proceedings of the fourteenth symposium on Computing: the Australasian theory - Volume77, 49-56. Wollongong, NSW, Australia: Australian Computer Society, Inc.
Bekos, M. A., M. Kaufmann, K. Potika, and A. Symvonis. 2008. "Line Crossing Minimization on
Metro Maps." In Graph Drawing, edited by S.-H. Hong, T. Nishizeki and W. Quan, 231-42.
Springer Berlin Heidelberg.
Benkert, M., M. Nöllenburg, T. Uno, and A. Wolff. 2007. "Minimizing Intra-edge Crossings in- 13 -

Wiring Diagrams and Public Transportation Maps." In Graph Drawing, edited by M.
Kaufmann and D. Wagner, 270-81. Springer Berlin Heidelberg.
Chazelle, B., and H. Edelsbrunner. 1992. "An optimal algorithm for intersecting line segments inthe plane." Review of. J. ACM 39 (1):1-54. doi: 10.1145/147508.147511.
Garland, K. 1994. Mr. Beck's Underground Map. Harrow, UK: Capital Transport Publishing.
Hong, S.-H., D. Merrick, and H. A. D. do Nascimento. 2006. "Automatic visualisation of metro
maps." Review of. Journal of Visual Languages & Computing 17 (3):203-24. doi:
10.1016/j.jvlc.2005.09.001.
Hong, S.-H., D. Merrick, and H. A. D. Nascimento. 2005. "The Metro Map Layout Problem." In
Graph Drawing, edited by J. Pach, 482-91. Springer Berlin Heidelberg.
Mulmuley, K. 1990. "A fast planar partition algorithm, I." Review of. Journal of Symbolic
Computation 10 (3–4):253-80. doi: http://dx.doi.org/10.1016/S0747-7171(08)80064-8.
Nöllenburg, M. 2010. "An Improved Algorithm for the Metro-line Crossing Minimization
Problem." In Graph Drawing, edited by D. Eppstein and E. R. Gansner, 381-92. Springer
Berlin Heidelberg.
Nöllenburg, M., and A. Wolff. 2006. "A Mixed-Integer Program for Drawing High-Quality Metro
Maps." In Graph Drawing, edited by P. Healy and N. S. Nikolov, 321-33. Springer Berlin
Heidelberg.
Nonobe, K., and T. Ibaraki. 1998. "A tabu search approach to the constraint satisfaction problem asa general problem solver." Review of. European Journal of Operational Research 106 (2–3):599-623. doi: http://dx.doi.org/10.1016/S0377-2217(97)00294-4.
———. 2001. "An improved tabu search method for the weighted constraint satisfaction problem."Review of. INFOR 39 (1).
Ovenden, M. 2003. Metro Maps of the World. Harrow, UK: Capital Transport Publishing.
Stott, J. M., and P. Rodgers. 2004. Metro map layout using multicriteria optimization. Paper
presented at the Information Visualisation, 2004. IV 2004. Proceedings. Eighth International
Conference on, 14-16 July 2004.
Stott, J. M., P. Rodgers, R. A. Burkhard, M. Meier, and M. T. J. Smis. 2005. Automatic layout ofproject plans using a metro map metaphor. Paper presented at the Information Visualisation,
2005. Proceedings. Ninth International Conference on, 6-8 July 2005.

- 14 -

List of Figures
Figure 1. Bus route maps. Grey-shaded areas indicate road network. (a) A desirable map. (b) An

undesirable map that contains the six types of elements to be avoided: intersections, gaps, shifts,
overlaps, misalignments, and acute bends.
Figure 2. Generation of topological road model. (a) Actual road network. White and black points
indicate end nodes and intermediate vertices, respectively. (b) Bus routes and bus stops. (c)Topological road model defined based on the topological structure of bus routes.
Figure 3. Mapping of bus routes on a map. (a) Tracks defined on each link. (b) Assignment of bus
routes to tracks.
Figure 4. Evaluation of the relative location of tracks around a node. (a) Numbering of tracks withrespect to T61. (b) Assignment of routes to tracks.
Figure 5. Cartographic road model of the road network shown in Figure 2. The dotted circle
indicates an extra node that indicates a terminal of bus routes.
Figure 6. Cartographic phase of route map design. (a) Road sections. Bold lines indicate streets.
(b) Initial location of segments. (c) Bus route map obtained by simply shortening and extending
segments. Dotted circle indicates undesirable acute bends. (d) Bus route map obtained after adding
extra segments.
Figure 7. Elimination of overlaps of bus routes. (a) Road sections. (b) Initial location of segments.
(c) Arrangement of bus routes initially obtained in the cartographic phase. (d) Arrangement of bus
routes obtained after translation of segments.
Figure 8. Treatment of misalignments on a street. (a) Road sections. (b) Arrangement of bus routes
initially obtained in the cartographic phase. (c) Arrangement of bus routes obtained after thetranslation of segments.
Figure 9. Conflict of overlaps of bus routes. (a) Road sections. (b) Initial arrangement of bus
routes obtained in the cartographic phase. (c) Arrangement of bus routes obtained after thetranslation of segments on section S2. (d) Arrangement of bus routes obtained after the translationof segments on sections S1 and S3.
Figure 10. Treatment of segments on short links. (a) Cartographic road model. (b) Candidate
location of segments. (c) Detection of the intersection of segments. (d) Translation of segments onlinks L1, L2, and L3. (e) Translation of segments on L2. (f) Direct connection of the most innersegments on L1 and L3.
Figure 11. An example of bus route map obtained by the proposed method. Misalignments of bus
routes observed in dotter lines are resolved in solid lines.
Figure 12. Tradeoff between gaps and intersections in bus route maps. (a) A bus route map that
contains a gap but fewer intersections. (b) A bus route map that contain does not contain a gap but
more intersections.

- 15 -

Figure 13. An example of bus route map obtained by the proposed method.
Figure 14. Manual revision of bus route map. (a) Bus stops and bus routes. (b) Bus route map
obtained by the computational procedure. (c) Bus route map after revision.

- 16 -

List of Tables
Table 1 Notations for spatial objects, constants, and variables used in the topological phase.

Table 2 Constraints of Problem RA.

- 17 -

Church Street

North Avenue(a)Church Street

shift

North Avenue
intersection
shift
misalignment

overlap
gap
shift and intersection

gap

acute bendintersection(b)

Figure 1- 18 -

(a)

R3

R1
R2

R4
R5
R7
R8

R6

(b)

N5
L5
L1

L10

L6

N1 L2 N2 L3

N3 L4

L7
N4
L8

L9

L11
N6

(c)

Figure 2- 19 -

T51 T52

T61

T64

T11

T21

T10,1
T31

T41

T14

T24

T34

T44

T71

T74

T81

T91

T85

T11,1

T11,2

T61

T64

R3
T10,1

R4

T95

(a)
T51 T52

T11

R1

T14

R2

N5

N1

T85

T44

N2 N3
T71

T81

T41

T74

N4

R5

T91

R6
T11,1

T11,2
N6

(b)

Figure 3- 20 -

R7
T
R8 95

L6
T64

T61

1 2 3 4L3

T31 1615
14
T34 13

5 T41
6
7
8 T44

N3

L4

N3=E32=E41=E61=E72
12 11 10 9
T74
T71
L7

(a)

L6
T61

T64

R3

R4

T31

T41

L3

L4
T34

R2

T44

N3=E32=E41=E61=E72
T71

T74
L7

(b)
Figure 4- 21 -

T51 T52

T61

T64

R3

R4

N5
T10,1
T11

R1

T21

T31

T14

R2

N1 T24 N2

T34

T41
N3

T71

T74

N1=E12=E21=E51
N2=E22=E31=E10,1
N3=E32=E41=E61=E72
N5=E10,2

Figure 5- 22 -

T44

Figure 6- 23 -

min
(a)

(b)

(c)

Figure 7- 24 -

(d)

S11

RS 1

S15
S21

RS 2

S26

(a)

(b)

(c)

Figure 8- 25 -

(d)

(a)

(b)

Figure 9- 26 -

(c)

S1
S2
S3

(a)

(b)

(c)

Figure 10- 27 -

(d)

S3

S1

S2

(a)

(b)

(c)

(d)

(e)

(f)

Figure 11- 28 -

Figure 12- 29 -

(a)(b)
Figure 13- 30 -

Figure 14- 31 -

B1

B2

RS1

RS2
(a)

(b)

(c)

Figure 15- 32 -

Table 1
Spatial objects
Rr

rth bus route (1rK)Li

ith link (1iM+Q)Nj

jth node (1jM'+Q)

Eie

eth end of link i (1i2)Tikkth track of link iConstantspri

Indicator of route Rr on link Li (1rK, 1iM+Q)

sij

Indicator of a street shared by Li and Lj (1i, jM+Q)

ciejl

Relative location of Tjl around Eie (1rK, 1i, jM, 1e2, 1lnj)

Variables
xrikjlIndicator of assignment of Rr to Tik and Tjl (1rK, 1i, jM, 1e2, 1lnj)

yike

Relative location of track to which the same route is assigned as Tik at Eie (1iM, 1kni, 1e2)

zike

Indicator of a terminal of the route assigned to Tik at Eie (1iM+Q, 1kni, 1e2)

ike

Indicator of a route shared by Tik and a track connected at Eie (1iM+Q, 1kni, 1e2)

ikme

Measure of undesirable arrangement of routes assigned to Tik and Tim at Eie. (1iM, 1kni, 1m2, 1e2)- 33 -

Table 2
1:

Route assignment needs to be symmetrical at every node.

2:

Route assignment needs to be consistent at every node.

3:

This constraint limits the shift of routes on streets. Every route cannot be assigned to tracks separated

further distance  on the same street at each node of the cartographic road model.
4:

Every route needs to be fully represented by a set of tracks.

5:

Every track of terminals needs to be assigned a single route.

6:

Every track of terminals needs to be assigned a single route.

7:

Every track can be assigned at most a single route.

8:

zike should be zero if the route assigned to Tik does not terminate at Eie.

9:

Definition of ike.

10:

Definition of yike.

11:

Definition of ikme.

12:ikme needs to be non-negative.

- 34 -