Route Search Method for Railway Replacement Buses Adopting Ant Colony Optimization

Kei Nagaoka^*, Kayoko Yamamoto

Graduate School of Informatics and Engineering, University of Electro-Communications, Tokyo, Japan.

DOI: 10.4236/jgis.2023.154020                

Abstract

In recent years, Japan, and especially rural areas have faced the growing problems of debt-ridden local railway lines along with the population decline and aging population. Therefore, it is best to consider the discontinuation of local railway lines and introduce replacement buses to secure the transportation methods of the local people especially in rural areas. Based on the above background, targeting local railway lines that may be discontinued in the near future, appropriate bus stops when provided with potential bus stops were selected, the present study proposed a method that introduces routes for railway replacement buses adopting ant colony optimization (ACO). The improved ACO was designed and developed based on the requirements set concerning the route length, number of turns, road width, accessibility of railway lines and zones without bus stops as well as the constraint conditions concerning the route length, number of turns and zones without bus stops. Original road network data were generated and processed adopting a geographic information systems (GIS), and these are used to search for the optimal route for railway replacement buses adopting the improved ACO concerning the 8 zones on the target railway line (JR Kakogawa line). By comparing the improved ACO with Dijkstra’s algorithm, its relevance was verified and areas needing further improvements were revealed.

Keywords

Local Railway Line, Railway Replacement Bus, Route Search Method, Ant Colony Optimization (ACO), Dijkstra’s Algorithm, Geographic Information Systems (GIS)

1. Introduction

According to Wang (2008), Sato (2011), Takeda (2018), Sato (2018), Shimazuka (2018) and Itaya (2023), in recent years, Japan, and especially rural areas have faced the growing problems of debt-ridden local railway lines along with the population decline and aging population ( [1] - [6] ). With the continuous aim of improving the management of national railways, Japan established the Act on Special Measures for Promoting the Reconstruction of Japanese National Railways (National Railway Reconstruction Act) in 1980. According to this act, local railway lines with a transport density under 8000 people require necessary measures to be taken. Furthermore, replacing local railway lines with a transport density of under 4000 people with buses was appropriately recognized, and discontinuing such lines was to be considered. The National Railway Reconstruction Act was repealed, and the Act for Enforcement of the Japanese National Railways Reform Act was enforced in 1986.

Based on the proposal of the current status of local railways from the perspective of the future of region and passengers in 2022 [7] , regarding current local Japan Railway (JR) lines with a transport density (the daily average passenger capacity per kilometer) of under 1000 people, a committee is set up in cooperation with the government, municipalities along the railway line and the railway company to discuss the discontinuation of the local railway line and the replacements such as the Bus Rapid Transit (BRT) as well as the review of management procedures. According to the guideline concerning the adaptation of local public traffic utilizing road space (2022) [8] , BRT refers to buses that use roads or lanes reserved for buses. Before the above proposal, the East Japan Railway Company announced that JR lines in the coastal area of Miyagi and Iwate Prefectures, which was affected by the Great East Japan Earthquake (2011), were discontinued and the BRT was introduced since 2012 [9] . As the population decline and aging population are progressing in such rural areas, it is best to consider the discontinuation of local railway lines and introduce replacement buses to secure the transportation methods of the local people.

The West Japan Railway Company released the “problems awareness and information disclosure concerning local lines” and published the balance of payments for lines with a transport density under 2000 people in 2022 [10] . According to the transport performance in 2019, 17 lines and 30 zones including the Kohama, the Etsumi-Hoku and the Oito lines are applicable. The West Japan Railway Company announced that “they are not sufficiently demonstrating the characteristics of trains concerning mass transportation” and have shown a willingness to work on the problems mentioned above.

Based on the above background, the present study considers local railway lines that may be discontinued in the near future. The present study aims to propose a method that introduces routes for railway replacement buses adopting the optimization algorithm called Ant Colony Optimization (ACO). In order to implement this, road network data (graph) with road intersections and ending points as the vertices (nodes), and roads as sides (edges) are generated adopting geographic information systems (GIS). Using this graph, a method that generates appropriate replacement bus routes after the discontinuation of local railway lines will be proposed.

2. Related Work

The present study is related to (1) studies on the problems related to local railway lines in rural areas, (2) studies on railway replacement buses, and (3) studies on the installation methods of bus stops. Regarding (1) studies on the problems related to local railway lines in rural areas, Ito (2008), Ooyama et al. (2012) and Futamura et al. (2022) described local residents’ attitudes and consciousness toward local railway lines [11] [12] [13] . Kohira (2022) and Araki et al. (2022) described the efforts of stakeholders in local communities to maintain local railway lines [14] [15] . Kurokawa et al. (2005), Taylor (2005) Fujii et al. (2006), Shaoul (2006), Takase et al. (2006), Sakamoto et al. (2012) and Tsuchitani (2013) evaluated the cost performance and values of local railway lines [16] - [22] . Kitazaki (2008), Imoto et al. (2017), Takeda (2018) and Shimazu et al. (2021) proposed the revitalization polices and strategies of local railway lines [23] [24] [25] [26] .

Regarding (2) studies on railway replacement buses, Kato (2005), Takayama (2012) and Kishi et al. (2021) considered the advantage and disadvantage to adapt replacement buses after the abolishment of local railway lines [27] [28] [29] . Axhausen et al. (2001), Alexandersson et al. (2008), Pflieger et al. (2009), Blainey (2010), Ryley et al. (2014) and Davidsson et al. (2016) discussed the possibility of replacing railway lines by buses [30] - [35] . Takemura (1997), Mouri (2013) and Kaneko et al. (2015) examined the possibility to adopt railway replacement buses in the damaged areas at the times of large-scale natural disasters [36] [37] [38] .

Regarding (3) studies on the installation methods of bus stops, Furth et al. (2000), Saka (2001), Izumida et al. (2005), Ohigashi (2005), Chien et al. (2007), Ibeas et al. (2010), Takakura et al. (2015) and Watanabe et al. (2023) considered bus lines and proposed automatic placement methods that would meet the requirements of bus stops [39] - [46] . Suzuki (1987) set the total commuting time required in addition to the total fare income of bus companies as the assessment criteria, and formulated the optimal placement of bus stops as a mathematical programming problem [47] . Yoshii et al. (2011) and Kojo et al. (2016) proposed methods to efficiently place bus stops on fixed routes [48] [49] .

(2) studies on railway replacement buses pointed out the necessity of replacing trains by buses especially in depopulated areas where the operation of local railway lines can be highly inefficient and unprofitable. However, all of the above preceding studies have not proposed any method that introduced routes for railway replacement buses and installed bus stops on the routes, targeting local railway lines that may be discontinued in the near future. Therefore, the present study will demonstrate its originality in comparison with preceding studies by deriving bus routes that pass through potential bus stops by manually placing potential stops that meet the requirements of railway replacement buses on the road network data adopting the improved ACO. In the present study, ACO was improved using the assessment functions concerning the route length, number of turns, road width, accessibility of railway lines and zones without bus stops.

3. Framework

3.1. Framework and Process

The following shows the framework and process of the present study.

1) Section 4: Multiple potential bus stops are placed on the road network data, and bus routes that pass through some of these stops are searched. Regarding potential bus stops, the conditions provided by Izumida et al. (2005) [41] were set as a reference, and locations that fit the requirements were selected. Buses did not have to pass through all of the potential bus stops when searching for both routes and bus stops. The improved ACO was designed and developed based on the requirements set concerning the route length, number of turns, road width, accessibility of railway lines and zones without bus stops as well as the constraint conditions concerning the route length, number of turns and zones without bus stops.

2) Section 5: The present study selected local railway lines that may be discontinued in the near future as the target. The geographical data concerning the surrounding areas of railway lines was gathered, and the road network data were generated and processed adopting GIS in order to apply the route search method for railway replacement buses.

3) Section 6: Regarding the target railway lines, route searches are conducted using the road network data mentioned above. In order to confirm the relevance of the improved ACO described in section 4, this is compared with Dijkstra’s algorithm that was proposed by Edsger Wybe Dijkstrra in Netherland in 1959 [50] , and can relatively easily derive the shortest travel routes between multiple locations.

3.2. Overview of ACO

ACO is the optimization algorithm proposed in the doctoral dissertation of Marco Dorigo in Italy in 1992 [51] . When ants find food, they will make repeated trips in groups to bring the food back to their nest. On shorter routes, ants will release a chemical substance called pheromones with a higher concentration as a guide when going back to their nest. Ants are more likely to travel on routes with a higher pheromone concentration. Additionally, ants are attracted to routes with more pheromones and they will also release pheromones. Therefore, the concentration of pheromones will continue to become higher on shorter routes, while the pheromones on longer routes will eventually evaporate. As a result, more ants will travel on the shortest route. ACO is the optimal solution search algorithm that turns this phenomenon into a mathematical model.

The applicable graph for ACO is made up of nodes that hold multiple location data and edges that represent the roads connecting the nodes. There are multiple routes that connect the nest and the food, and the routes used by ants are represented by connecting a few edges. When the node indicating the nest, which is also the starting point, is $v_S$ , and the node indicating the feeding area, which is also goal point, is $v_G$ . Additionally, the route used by ants is $\langle v_S,v_G\rangle$ and this is called the path. Each edge has heuristic information that changes the probability of ants passing through each edge to go to the next node. For example, the inverse number of the distance is used as heuristic information to increase the probability of shorter routes being selected. Additionally, the pheromone concentration is used as heuristic information to increase the probability of routes with a higher pheromone concentration being selected.

Figure 1 shows the basic algorithm of ACO. Based on Figure 1, each stage will be explained below.

1) Initialization of the pheromone of each edge

A pheromone concentration is provided for each edge. The default value is normally 0. Therefore, the process starts with cycle $t=0$ .

(2) Selection of routes used by each ant

From the edges connected to the node they are located on, each ant selects an edge they will travel on for each cycle and moves toward the other node on the same edge. Ants will select a route according to the heuristic information. Regarding the basic ACO, the function $p_{im}^k\left(t\right)$ of Equation (1) is used as a probability function of route selection, when ant k goes from node i to the next node m.

$p_{im}^k\left(t\right)=\frac{a_{im}^k\left(t\right)}{{\displaystyle {\sum }_{n\in \Omega }{a}_{in}^k\left(t\right)}}$ (1)

t: Number of Cycle;

k: Ant identity number;

${\tau }_{ij}$ : Pheromone concentration of edge i, j;

Ω: Collection of nodes adjoining i;

$a_{ij}^k\left(t\right)$ : Evaluation value of edges connecting nodes i, j.

$a_{ij}^k\left(t\right)=\frac{{\left[{\tau }_{ij}\left(t\right)\right]}^{\alpha }{\left[{\eta }_{ij}\right]}^{\beta }}{{\displaystyle {\sum }_{l\in \Omega }{\left[{\tau }_{il}\left(t\right)\right]}^{\alpha }{\left[{\eta }_{il}\right]}^{\beta }}}$ (2)

Figure 1. Basic algorithm of ACO.

${\eta }_{ij}$ : Inverse value of the distance of edge i, j.

α, β: Weight parameter.

As the probability function of route selection $p_{im}^k\left(t\right)$ and the evaluation value $a_{im}^k\left(t\right)$ changes according to cycle t, these are shown as a function of t. Additionally, as each ant remembers the nodes they have visited, Ω represents the collection of nodes ant A_k has never visited. Paths are saved until step t as ants remember the routes they have used as paths. However, as all edges included in the routes are selected based on the pheromone concentration, the pheromone concentration of the edges contained in the routes selected first becomes higher causing more ants to choose routes that are not the shortest. This may cause the pheromone concentration of routes that are not the shortest to become higher, resulting in a localized solution. In order to prevent this, the edges that ants travel to next are selected at random with a fixed probability that allows routes within the graph to be thoroughly searched.

When setting the output value to the shortest route, ant A_k that arrives at its goal or node $v_G$ first compares their current route to the shortest route that they have traveled on. Next, if ant A_k decides that the current route is shorter, this is determined to be the shortest route.

3) Update of the pheromone of each edge

Based on the principle that “the total pheromone amount released by 1 ant in 1 trip is constant”, a fixed amount of pheromones is distributed evenly to the edges that the ants have passed through. Regarding cycle t, the pheromone amount $\text{Δ}{\varphi }_{ij}^k\left(t\right)$ spread by ant A_k on edge $e_{ij}$ that connects node $v_i$ and node $v_j$ is calculated using Equation (3).

$\text{Δ}{\varphi }_{ij}^k\left(t\right)=\{\begin{array}{l}\frac{Q}{l_k\left(t\right)}\text{when}{A}_k\text{isonareturntripand}\text{passesthroughtedge}{e}_{i,j}\\ \text{which}\text{wasalsothelastedgeitpassed}\\ 0\text{otherwise}\end{array}$ (3)

t: n;

k: Ant identity number;

Q: Total pheromone amount spread by an ant in 1 cycle;

l_k: Route length of ant A_k for cycle t.

As described above, the pheromone amount from the previous cycle can be grasped in cycle t + 1, as the change in the pheromone amount of each edge for 1 ant is calculated. Therefore, the pheromone amount ${\varphi }_{ij}\left(t+1\right)$ of node $e_{ij}$ after all ants have passed it is calculated using Equation (4). In other words, Equation (4) is the pheromone updating equation indicating that the pheromones of edge $e_{ij}$ is evaporating at a fixed rate, and there is an increase in the amount of pheromones $\Delta {\varphi }_{ij}^k\left(t\right)$ after N number of ants pass.

$\left(t+1\right)=\rho {\varphi }_{ij}\left(t\right)+{\displaystyle \underset{k=1}{\overset{N}{\sum }}\Delta {\varphi }_{ij}^k\left(t\right)}$ (4)

ρ: Evaporation coefficient;

N: Number of ants.

4) Confirmation of ending conditions

After confirming the ending conditions, the process can move to (5) if the conditions are met. If the conditions are not met, the number of cycles must be increased from t to t + 1, and the process must be redone from (2). The examples of the ending conditions are shown below.

- The number of cycles t reaches a certain number of n times.

- n amount of ants in total arrive at the goal node.

- The path 〈v_s, v_G〉 passed by any of the ants between the start node and goal node must be under the threshold amount x of the length l of the optimal route.

5) Output of the pheromone of each edge or the shortest route

After meeting the ending conditions in (4), the output value is decided after finishing the process. The two cases of the output value are the output of the pheromone concentration of each edge in the graph of the cycle as well as the output of the shortest route obtained in (3).

3.3. Utilization Values and Issues Concerning ACO

Taking into consideration the ACO utilization values and issues, it is necessary to determine the methods and parameters. With the combination optimization issue as a target, ACO is an algorithm that obtains the optimal solution with fewer calculations. Representative issues to which ACO is applied include the traveling salesman issue and the transportation issue and all of these lead to the graph network. Additionally, with ACO, the characteristics of the desired route can be changed by altering the heuristic information such as route length and travel speed in order to make a stochastic selection based on the heuristic information of the next route.

However, as the routes are stochastically selected in ACO, this does not result in the same route every time. If the process of the number of cycles is not sufficient, this will result in routes that differ greatly every time. If this is the case, even if a good route is selected, there is a possibility that it was selected by chance. Therefore, ACO does not necessarily result in the optimal solution as the answers differ every time.

4. Route Search Method for Railway Replacement Buses Adopting ACO

4.1. Requirements of Railway Replacement Buses

With Izumida et al. (2005) [41] as a reference, the requirements of railway replacement bus routes were set as described below.

1) Selection of short routes

In order for bus users to reach their destinations faster, the shortest route should be selected as the railway replacement bus route.

2) Selection of routes with fewer turns

Waiting time occurs for traffic lights and pedestrian crossings, when there is right or left turns. Additionally, when buses turn right or left, there is more time and effort involved, as the bus must slow down or accelerate before and after the turn. Therefore, routes with fewer turns are ideal for buses. Moreover, if the angle of an intersection of 3 or more edges is 60 degrees or more, this is considered to require a turn.

3) Selection of wide roads

The article 5 in the Section 2 of the Vehicles Regulations Order (1961) states that “the width of vehicles on roads within the metropolitan areas must not be more than one-half of the width of the road with 0.5 m subtracted.” In other words, if the road width is w meters, the vehicle width of x meters must meet Equation (5).

$\frac{w-0.5}{2}\ge x$ (5)

W: Road width.

In the present study, the vehicle width of general buses that is 2.1 m is used. Therefore, the road width that buses can use is as described in Equation (6) when $x=2.1$ in Equation (5).

$w\ge 4.7$ (6)

W: Road width.

Accordingly, with the focus on roads that have a width of 4.7 m or more, the process is implemented on the road network made up of edges.

4) Generation of routes near target railway lines

Routes near the target railway lines are generated taking into consideration the convenience of the local residents. Therefore, bus stops are always placed at each station of the target railway lines.

5) Distance of no bus stop zones kept under a certain level

Based on the results of interview surveys for local residents, Izumida et al. (2005) [41] revealed that placing bus stops in a way that does not create large zones without bus stops should be a requirement for railway replacement buses. Therefore, it is necessary to derive short routes in zones without bus stops.

Regarding the requirements of railway replacement bus routes of (1) (2) (5), the constraint conditions are as described below.

1) Route lengths kept are under a certain level

Regarding the route generation, a weight is placed on the number of turns as a condition to prevent the route length from becoming too long. In the present study, a magnification is set with the threshold limit value being under n times (the value of n is 1 or higher) the route distance (shortest distance) is calculated adopting Dijkstra’s algorithm.

2) The number of turns kept under a certain number

Regarding the route generation, a weight is placed on the distance as a condition to prevent the number of turns being too high. In the present study, a magnification is set with the threshold limit value being under n times (the value of n is 1 or higher) the number of turns on the route (shortest distance) obtained adopting Dijkstra’s algorithm.

3) All zones without bus stops kept under a certain distance

Zones with no bus stops are limited to be under a certain distance taking into consideration the convenience of the local residents. Routes with zones without bus stops that exceed this threshold limit value will not be selected as the optimal route.

4.2. Design of the Route Search Algorithm for Railway Replacement Buses

Python 3.6.16 was used as the programming language in the design of the improved ACO used for the route search for replacement buses. The overview of each stage is as described below.

1) Initialization of the graph and ants

First, the graph is initialized based on the entered parameter. In the graph, the pheromones released at each edge as well as the shortest route to be ultimately output are initialized, and the ants are placed in the designated positions. Additionally, the routes and distances of zones without bus stops are initialized.

2) Route selection

Route selections are conducted for all ants. According to the requirements of railway replacement buses of (1) (2) in Section 4.1, when the ants arrive at the next node, an evaluation value is added to the surrounding edges taking into consideration the route lengths, and the ants will stochastically move. When the other conditions are the same, routes with a shorter distance can be easily selected. Additionally, when the other conditions are the same, routes that are straight are also more likely to be selected than routes with many turns.

3) Pheromone update

The pheromones of each edge are evaporated, added to the routes taken by ants, and updated.

4) Confirmation of the ending conditions

Whether the current situation meets the ending conditions is confirmed, and the process must be redone from selecting routes if the conditions are not met. The optimal route is output if the conditions are met. In the present study, the process is ended when the number of cycles exceeds the predetermined number.

5) Output of the optimal route

Finally, the optimal route is generated. While the fundamental aim of ACO is finding the shortest route, the present study uses it to find the optimal routes that can work as railway replacement bus routes. Taking into consideration the route length and number of turns that are among the requirements in Section 4.1, routes that meet the constraint conditions are selected as the optimal routes.

4.3. Route Search Algorism for Railway Replacement Buses

4.3.1. Initialization of the Number of Graphs and Ants

In this process, the graph and ants are initialized. The graph was implemented in the form of an undirected graph of the network x module. The graph and ants are initialized according to the parameters entered. Table 1 shows the overview of the input of each parameter.

Table 1. Overview of the input of each parameter.

The graph and ants are initialized. A parameter is referred to as a class in Python. When the graph is initialized, the current optimal route and its information as well as the number of times the amount of pheromones did not change are saved. Regarding the amount of pheromones, the minimum value (tau_min) of all edges is initialized. A flag is placed on edges that have a potential bus stop. Additionally, with the list of ants as instance variables, the designated number (num_of_ants) alone is positioned on the initial location. As the ants are called class, this is also initialized. The routes taken by ants and their information, the flags indicating that the ants are heading toward the nest, as well as the current locations are considered to be instance variables.

4.3.2. Route Selection

In the route selection, ants will stochastically select an unvisited node from among the current node and adjacent nodes. From the adjacent nodes, a random route selection will be conducted with a fixed probability (Ant_prob_random). This increases the probability of ants moving to nodes that are stochastically less likely to be selected that causes the graph to be searched thoroughly, preventing localized solutions. In the route selection of the present study, a different equation to the basic ACO is used. Though routes that are shorter and have fewer turns according to the requirements are obtained, this may become a trade-off. Therefore, the route selection probability of ants is calculated using Equation (1), while Equation (7) is used in place of Equation (2).

$a_{ij}^k\left(t\right)=\frac{{\left[{\tau }_{ij}\left(t\right)\right]}^{\alpha }{\left[{\eta }_{ij}\right]}^{\beta }{\left[tf\left(h,i,j\right)\right]}^{\gamma }}{{\displaystyle {\sum }_{l\in \Omega }{\left[{\tau }_{il}\left(t\right)\right]}^{\alpha }{\left[{\eta }_{il}\right]}^{\beta }{\left[tf\left(h,i,j\right)\right]}^{\gamma }}}$ (7)

t: Number of cycles;

k: Ant identity number;

h: Number of the previous node;

τ_ij: Pheromone concentration of edge (i, j);

Ω: Collection of nodes adjacent to i;

η_ij: inverse number;

α, β, r: of the distance of edge ij;

γ: Weight parameter;

$tf\left(h,i,j\right)$ : Function regarding the left/right turns when passing through nodes h → i → j.

Regarding function of $tf\left(h,i,j\right)$ , when the ants pass through the nodes in the order of h→i→j (h and i as well as i and j are adjacent nodes), the value is 1 if it is straight and 2 if there is a left or right turn. The determination method of turns and straight roads is as explained in section 4.1. Moreover, as there are no nodes that the ants have traveled through right after the initialization, it will be h = i and will be regarded as a straight line with the output value being 1.

If there are no unvisited nodes adjacent to the current location, the ant will be moved back to the previous position. Though the node visited before moving back 1 node will be deleted from the path, conducting this process alone can lead to the following problems. Figure 2 shows an example in which an ant is stuck in an infinite loop and cannot reach the goal.

As described in Figure 2, assuming the graph with the nodes A, B, C, D and E, A is the starting point and E is the goal. In this case, when an ant travels in the order of arrows 1, 2 and 3, there are no unvisited nodes adjacent to D. Therefore, the ant must return to C following arrow 4. In the next step in which the ant is at C, the ant must progress to D as this is the only unvisited node. In this way, the ant will continue to go back and forth between C and D.

In order to prevent this, a list-type instance variable called a backlist is used when an ant moves back a node. When an ant goes backward (when going in the direction of arrow 4 in Figure 2), the node is added to the backlist, and it is regarded as an unvisited node until the ant reaches the goal of node E. This method prevents ants from moving to dead-end nodes. Regarding Figure 2, after the ant moves in the direction of arrow 4, D is not selected in the route selection, as it is added to the backlist node causing the ant to return to B as C becomes a dead end.

The information on the route, route length, number of turns and zones without bus stops are updated. All ants have the attributes of the list (list of the zones without bus stops) of the route they have taken, the route length, number of turns and distance of zones without bus stops. First, nodes used by ants are added to the route list, while the distance of the edges is added to the distance attributes. Additionally, turns are determined by the turn flags, and the number of turns for the ant is increased by one when there is a turn. The list of zones without bus stops is a list of the distances of zones that have never had a bus stop. If the edges used by ants have no potential bus stops, the distance is added to the list of zones without bus stops. If there are potential bus stops, half the distance of the edges is added to the list of zones without bus stops. The edge is now considered to have a bus stop in the middle.

Figure 2. Case of being in an infinite loop and not being able to reach the goal.

Figure 3. Information update of the routes taken by ants.

As an example, Figure 3 shows the information update of the routes taken by ants. It is assumed that the ants start from node A and progress in 2 steps, A to B and B to C. The potential bus stop is on edge BC not AB. In this case, the information on the route, route length, number of turns and zone without bus stops are updated.

Furthermore, if the node that the ant reaches after going through the selected edge is the goal point, it is determined whether the route is optimal or not. As the route length and number of turns are the basis for the route selection, the converted distance of the number of turns is used to calculate the route length as described in Equation (8). The parameter of tns_weight is used for T. n represents the total number of turns in the route traveled. As described in Equation (8), the route length is calculated as a route with no turns.

$l=x+nT$ (8)

l: route length;

x: total distance of the bus;

n: number of turns in the route traveled on;

T: turns weight.

Ants that reach the goal head towards the opposite direction in order to reach the starting point. They continue moving until they reach the node that is the starting point. They are initialized once they reach the starting point, and they once again travel in the direction of the goal node.

4.3.3. Pheromone Update

The update process of pheromones is the same as the basic ACO and is conducted using Equations (3) and (4). After reaching their food on the selected route, ants will return to their nest using the exact same route and move by only 1 edge in 1 cycle. The amount of pheromones released by ants is determined according to the travel distance and total pheromone amount Q that is one of the parameters entered.

4.3.4. Confirmation of the Ending Conditions

In the present study, the ending condition is that the number of cycles exceeds the stipulated number (parameter max_iterations). It must return to the route selection if the number of cycles does not exceed the stipulated number, while it is determined to be the optimal route if it is exceeded.

4.3.5. Output of the Optimal Route

Finally, the optimal route confirmed in Section 4.3.4 is generated. In the present study, the simultaneous output of not only the optimal route but also the route length, number of turns, number of bus stops, maximum distance of zones without bus stops and the list of the distances of zones without bus stops was conducted in order to make a comparison with the routes obtained adopting Dijkstra’s algorithm.

5. Selection of Target Railway Line and the Gathering/Processing of Geographical Data

5.1. Selection of Target Railway Line

The JR Kakogawa line between Nishiwakishi station and Tanigawa Station in the center of Hyogo Prefecture in the western part of Japan was selected as the target railway line. The JR Kakogawa line is operated by the West Japan Railway Company, and the line length between these two stations is 17.3 km. 9 stations are located in this zone.

5.2. Selection of Potential Bus Stops along the Target Railway Lines

With Izumida et al. (2005) [41] as a reference, potential bus stops are placed according to the following conditions.

1) Potential bus stops are placed in areas with many people such as residential or commercial areas.

2) Potential bus stops are placed at large-scale facilities or stations.

3) Potential bus stops are not placed near intersections.

4) Potential bus stops are placed in a way that does not create long distances without bus stops.

5) Potential bus stops are placed on routes that are generated near the target railway line with the convenience of the local people in mind.

5.3. Utilized Data and Processing Method

Table 2 shows the overview of the utilized data and the processing methods in the present study. The utilized data were processed with GIS. As described in Table 2, vector tiles and road edge data of the basic map data provided by the Geospatial Information Authority of Japan were used to calculate the road width. Additionally, original road network data were generated using the vector tiles.

Table 2. Overview of the utilized data and the processing methods in the present study.

6. Route Search for Railway Replacement Buses

6.1. Overview of Route Search

In the present study, the route search for railway replacement buses is conducted adopting Dijkstra’s algorithm and the improved ACO. Next, the relevance of the improved ACO is verified by comparing the route search results. Specifically, the route length, number of turns, number of bus stops, maximum distance of zones without bus stops and the list of the distances of zones without bus stops were taken into consideration, when comparing the route search results. As the railway replacement bus always travels through 9 stations on the JR Kakogawa line, the zones between these stations are divided into 8 zones, and the route search results described above are compared. The parameters shown in Table 3 were used in the search for both routes and bus stops adopting the improved ACO. Figures 4-19 show the results obtained by adopting these route search methods. The starting and goal nodes are colored with yellow, the routes traveled are colored with red, and the edges with potential bus stops are colored with green. Additionally, the stations are denoted by blue points. Tables 4-11 shows the comparison results of routes derived adopting these route search methods.

6.2. Route between Nishiwakishi Station and Shin-Nishiwaki Station

Figure 4 and Figure 5 show the routes between Nishiwakishi Station and Shin-Nishiwaki Station obtained by Dijkstra’s algorithm and the improved ACO, and Table 4 shows the comparison results of these routes. From Figure 4, while the selected route in Dijkstra’s algorithm is shorter and has fewer turns, the zone without bus stops is longer. From Figure 5, the route in the improved ACO was longer than that of Dijkstra’s algorithm but had more bus stops. According to Table 4, in comparison with Dijkstra’s algorithm, the distance of zones without bus stops in the route selected in the improved ACO all met the constraint conditions of having a distance under 1000 m.

6.3. Route between Shin-Nishiwaki Station and Hie Station

Figure 6 and Figure 7 show the routes between Shin-Nishiwaki Station and Hie Station obtained by Dijkstra’s algorithm and the improved ACO, and Table 5 shows the comparison results of these routes. From Figure 6, the route in Dijkstra’s algorithm is mostly straight, similar to the route between Nishiwaki station and Shin-Nishiwaki Station shown in Section 6.2. From Figure 7, in comparison

Table 3. Parameters of the improved ACO.

Table 4. Comparison of the searched routes between Nishiwaki Station and Shin-Nishiwaki Station.

Table 5. Comparison of the searched routes between Nishiwaki station and Shin-Nishiwaki Station.

Table 6. Comparison of the searched routes between Hie Station and Nihonheso Park Station.

Table 7. Comparison of the searched routes between Nihonheso Park Station and Kurodasho Station.

Table 8. Comparison of the searched routes between Kurodasho Station and Honkuroda Station.

Table 9. Comparison of the searched routes between Honkuroda Station and Funamachiguchi Station.

Table 10. Comparison of the searched routes between Funamchiguchi Station and Kugemura Station.

Table 11. Comparison of the searched routes between Kugemura Station and Tanigawa Station.

Figure 4. Route obtained adopting Dijkstra’s algorithm between Nishiwaki Station and Shin-Nishiwaki Station.

Figure 5. Route obtained adopting the improved ACO between Nishiwaki Station and Shin-Nishiwaki Station.

Figure 6. Route obtained adopting Dijkstra’s algorithm between Shin-Nishiwaki Station and Hie Station.

Figure 7. Route obtained adopting the improved ACObetween (Shin-Nishiwaki Station and Hie Station.

Figure 8. Route obtained adopting Dijkstra’s algorithm between Hie Station and Nihonheso Park Station.

Figure 9. Route obtained adopting the improved ACO between Hie Station and Nihonheso Park Station.

Figure 10. Route obtained adopting Dijkstra’s algorithm between Nihonheso Park Station and Kurodasho Station.

Figure 11. Route obtained adopting the improved ACO between Nihonheso Park Station and Kurodasho Station.

Figure 12. Route obtained adopting Dijkstra’s algorithm between Kurodasho Station and Honkuroda Station.

Figure 13. Route obtained adopting the improved ACO between Kurodasho Station and Honkuroda Station.

Figure 14. Route obtained adopting Dijkstra’s algorithm between Honkuroda Station and Funamachiguchi Station.

Figure 15. Route obtained adopting the improved ACO between Honkuroda Station and Funamachiguchi Station.

Figure 16. Route obtained adopting Dijkstra’s algorithm between Funamchiguchi Statio and Kugemura Station.

Figure 17. Route obtained adopting the improved ACO between Funamchiguchi Statio and Kugemura Station.

Figure 18. Route obtained adopting Dijkstra’s algorithm between Kugemura Station and Tanigawa Station.

Figure 19. Route obtained adopting the improved ACO between Kugemura Station and Tanigawa Station).

with the route of Dijkstra’s algorithm, the route length in the improved ACO is mostly the same, while the maximum distance of zones without bus stops was shorter. According to Table 5, the route in Dijkstra’s algorithm was superior in terms of the route length and number of turns compared to the improved ACO. However, compared to Dijkstra’s algorithm, the improved ACO had a similar route length and a shorter maximum distance of zones without bus stops.

6.4. Route between Hie Station and Nihonheso Park Station

Figure 8 and Figure 9 show the routes between Hie Station and Nihonheso Park Station obtained by Dijkstra’s algorithm and the improved ACO, and Table 6 shows the comparison results of these routes. Figure 8 and Figure 9 show that the routes derived from the two route search methods were the same. Both methods selected a route that was partially straight and had few turns. Additionally, both met the constraint conditions introduced in Section 4.1 and the number of turns was minimized to 1 turn.

6.5. Route between Nihonheso Park Station and Kurodasho Station

Figure 10 and Figure 11 show the route between Nihonheso Park Station and Kurodasho Station obtained by Dijkstra’s algorithm and the improved ACO, and Table 7 shows the comparison results of these routes. From Figure 10, in Dijkstra’s algorithm, a central road was selected, the route prioritized the distance and the number of turns was low. From Figure 11, in comparison with Dijkstra’s algorithm, the number of bus stops had significantly increased in the improved ACO, while the maximum distance of the zones without bus stops was shorter, and the number of turns had increased. According to Table 7, in Dijkstra’s algorithm, the route length was shorter than the improved ACO by over 800 m, and it passed through a route that had no bus stops between the 2 stations. On the other hand, in the improved ACO, the number of bus stops had increased and the distance of zones without bus stops was short.

6.6. Route between Kurodasho Station and Honkuroda Station

Figure 12 and Figure 13 shows the routes between Kurodasho Station and Honkuroda Station obtained by Dijkstra’s algorithm and the improved ACO, and Table 8 shows the comparison results of these routes. Figure 12 and Figure 13 show that the routes derived from the two route search methods were the same. Both routes have no intersections requiring turns and the distance between bus stops was almost the same. As described in Section 4.1, in order to meet the constraint requirement of having a number of turns that is under 3 times that of Dijkstra’s algorithm (under 0 times for the area between these 2 stations), the improved ACO selected the same route as in Dijkstra’s algorithm.

6.7. Route between Honkuroda Station and Funamachiguchi Station

Figure 14 and Figure 15 show the route between Honkuroda Station and Funamashiguchi Station obtained by Dijkstra’s algorithm and the improved ACO, and Table 9 shows the comparison results of these routes. Figure 14 and Figure 15 show that the routes derived from the two route search methods were the same. The distance between bus stops was almost the same in both routes, and there were no zones without bus stops that were over 1000 m.

6.8. Route between Funamachiguchi Station and Kugemura Station

Figure 16 and Figure 17 show the route between Funamachiguchi Station and Kugemura Station obtained by Dijkstra’s algorithm and the improved ACO, and Table 10 shows the comparison results of these routes. From Figure 16, the distances between bus stops in the route of Dijkstra’s algorithm were equally spaced, and there were no zones without bus stops that were over 1000 m. From Figure 17, in comparison with Dijkstra’s algorithm, the route length in the improved ACO was significantly longer and the number of bus stops also greatly increased. According to Table 10, in comparison with the improved ACO, while the route length in Dijkstra’s algorithm was over 1000 m shorter, the zones without bus stops were very long. On the other hand, the route in the improved ACO had a great increase in bus stops and the maximum distance of zones without bus stops was also extremely short.

6.9. Route between Kugemura Station and Tanigawa Station

Figure 18 and Figure 19 show the routes between Kugemura Station and Tanigawa Station obtained by Dijkstra’s algorithm and the improved ACO, and Table 11 shows the comparison results of these routes. Figure 18 and Figure 19 show that the routes derived from the two route search methods were the same. Both routes had only 1 bus stop between the 2 stations and the zone without bus stops was extremely long. From Table 11, similar to the route between Kurodasho Station and Honkuroda Station, the improved ACO selected the same route as Dijkstra’s algorithm in order to meet the constraint condition of having a number of turns under 3 times that of Dijkstra’s algorithm (under 0 times between these 2 stations) as described in section 4.1. Though there are 2 locations that require a turn in Figure 18 and Figure 19, these can be regarded as being straight according to the angle measurement adopting the turn determination method used in the present study.

6.10. Summary of the Consideration Results

According to the comparison results described up until section 6.9, 4 out of 8 zones had the same routes obtained adopting Dijkstra’s algorithm and the improved ACO. However, in the other 4 zones, the improved ACO derived the optimal routes for railway replacement buses in comparison with Dijkstra’s algorithm. From these comparison results, the areas requiring improvement concerning the improved ACO can be summarized into the following 2 points.

1) Placement of potential bus stops

In both Dijkstra’s algorithm and the improved ACO, a route search is conducted with nodes as the starting and goal points instead of the edges. However, as bus stops cannot be located on intersections, they must be placed on the edges. Therefore, it is necessary to improve the road network data in order to enable the placement of all potential bus stops on the edges.

2) Determination methods for turns

As mentioned in Section 6.9, between Kugemura Station and Tanigawa Station, locations that require turns were mistakenly considered to be straight according to the angle measurement adopting the turn determination method adopted in the present study. In the present study, it was stipulated that turns are necessary when the angle of one of the 3 intersecting edges is 60 degrees or more. In order to solve this problems, the angle determining turns should be changed to an angle below 60 degrees. However, if the angle is too small, turns may be regarded as being straight. Therefore, a more accurate turn-determination method must be considered.

7. Conclusions

Regarding Section 4, with the assumption of the situation after the discontinuation of local railway lines that may happen in the near future, appropriate bus stops when provided with potential bus stops were selected, and method to search for railway replacement bus routes was designed and developed. ACO, which is a highly flexible algorithm, was improved and used as a route search method in the present study. Therefore, in Section 5, vector tiles and road edge data of the basic map data provided by the Geospatial Information Authority of Japan were used to generate and process the road network data only containing roads with widths that buses can travel on. In Section 6, the road network data was used to search for the optimal route for railway replacement buses adopting the improved ACO concerning the 8 zones on the target railway line (JR Kakogawa line). Additionally, by comparing the improved ACO with Dijkstra’s algorithm, its relevance was verified and areas needing further improvements were revealed.

The main findings of the present study can be summarized into the following 2 points.

1) Setting requirements with a focus on route length and the number of turns

As described in Section 4.1, the present study set the route length, number of turns, road width, accessibility of railway lines and zones without bus stops as the requirements for the railway replacement buses. Optimal routes were generated with a focus on the route length and number of turns. In order to meet these requirements, the number of turns was converted to the road length. This made it possible to search for the optimal routes, while meeting the requirements concerning both the route length and number of turns.

2) Setting constraint conditions

Whether the route between the starting node and goal node taken by ants was better than the temporary optimal route or not was determined according to the requirements of (1) in Section 4.1. In order to prevent routes that are long, have many turns and have long zones without bus stops from being selected as the optimal route, constraint conditions were set concerning the route length, number of turns and zones without bus stops as described in Section 4.1. After meeting the constraint conditions, the optimal route search could be conducted.

As described in Section 6.10, regarding the improved ACO, improving its accuracy with a focus on the placement of potential bus stops and the turn determination method as well as applying it to other railway lines can be raised as future research topics.

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1]	Whang, Y.J. (2008) One Consideration on Local Railway Policy of Japanese National Railway—Focusing on Development of Policy in Continuation and Abolishment of Local Railways. e-Waseda Public Management, 1, 99-119.
[2]	Sato, N. (2011) Perspective of Local Railways. Railway Journal, 45, 109-111.
[3]	Takeda, I. (2018) Proposal of the Role, Persistence and Revitalization of Local Railways in an Era of Depopulation: Based on the Problems of the Hokkaido Japan Railway Company. Jumin to Jichi Monthly, 663, 6-10.
[4]	Sato, N. (2018) Questions Concerning the Meaning of the Existence of Local Railways. Urban Problems, 109, 19-24.
[5]	Shimazuka, R. (2018) Reconstruction of Local Railway Companies and Local Revitalization. Urban Problems, 109, 39-43.
[6]	Itaya, K. (2023) Arrangement of Major Problems Concerning Local Railways. The Japanese Journal of Transportation Economics, 66, 11-22.
[7]	Ministry of Land, Infrastructure, Transport and Tourism (2022) Proposal of the Current Status of Local Railways from the Perspective of the Future of Region and Passengers. 70.
[8]	Ministry of Land, Infrastructure, Transport and Tourism (2022) Overview of Guideline Concerning the Adaptation of Local Public Traffic (BRT) Utilizing Road Space. 9.
[9]	East Japan Railway Company, Kesennuma Line BRT and Oofunato Line RBT. https://www.jreast.co.jp/railway/train/brt
[10]	West Japan Railway Company, Problems Awareness and Information Disclosure Concerning Local Lines. https://www.westjr.co.jp/press/article/items/220411_02_local.pdf
[11]	Ito, T. (2008) Trial of Mobility Management of Railway in a Local City Area. Infrastructure Planning Review, 25, 575-578. https://doi.org/10.2208/journalip.25.575
[12]	Ooyama, H., Midera, J. and Kawakami, Y. (2012) A Study on Various Values of the Local Railway through the Recognition of the Residents: A Case of Echizen Railway. Journal of the City Planning Institute of Japan, 47, 319-324. https://doi.org/10.11361/journalcpij.47.319
[13]	Futamura, S., Miyashita, T. and Kawamaoto, Y. (2022) Promoting the Use of the JR Kuzuryu Line from the Perspective of Students Attending High Schools in Ono City. Proceedings of the City Planning Institute of Japan, Vol. 33, 79-82. https://doi.org/10.11361/cpijchubu.33.0_79
[14]	Kohira, H. (2022) Present Local Railway: Focusing on the Problems Concerning the Maintenance of JR Ooito Line. Shinsyu Autonomy Studies, 370, 15-23.
[15]	Araki, I., Mtsumoto, K. and Sawaki, M. (2022) Role and Effect of Movement for Supporting Local Railway by Citizens. Proceedings of City Planning Institute of Japan, Vol. 20, 65-68. https://doi.org/10.11361/cpijkansai.20.0_65
[16]	Kurokawa, Y., Takase, T. and Koyama, K. (2005) On the Estimation of Monetary Values of the Local Railroad Ueda-Bessho Line Using the CVM. Journal of Construction Management, JSCE, 12, 183-192. https://doi.org/10.2208/procm.12.183
[17]	Taylor, Z. (2005) Railway Closures to Passenger Traffic in Poland and Their Social Consequences. Journal of Transport Geography, 14, 135-151. https://doi.org/10.1016/j.jtrangeo.2005.05.003
[18]	Fujii, Y. and Satake, W. (2006) Study on Social Economic Evaluation for the Use of Local Railroad in Local City. Journal of the City Planning Institute of Japan, 41, 43-48. https://doi.org/10.11361/journalcpij.41.3.43
[19]	Shaoul, J. (2006) Railpolitik: The Financial Realities of Operating Britain’s National Railways. Public Money & Management, 24, 27-36. https://doi.org/10.1111/j.1467-9302.2004.00390.x
[20]	Takase, T., Ohashi, K. and Koyama, K. (2006) Economical Analysis of a Local Railroad Using Time-Series Demand Curve. Journal of Construction Management, JSCE, 13, 43-50. https://doi.org/10.2208/procm.13.43
[21]	Sakamoto, J., Yamaoka, S. and Fujita, M. (2012) Study on Resident Attitude Formation toward Finance Support for Local Railway. Journal of the City Planning Institute of Japan, 47, 325-330. https://doi.org/10.11361/journalcpij.47.325
[22]	Tsuchitani, T. (2013) Problems of Local Railway Converting to the Third Sector: A Case Study of Hitachinaka Seaside Railway. Annals of the Association of Economic Geographers, 59, 111-135.
[23]	Kitazaki, H. (2008) Factors in Restoration of Local Railway: In the Case of “Echizen Railway”. Journal of Economics and Sociology, Kagoshima University, 71, 61-69.
[24]	Imoto, M., Iwasaki, Y. and Yamaguchi, Y. (2017) A Study on the Revival Condition and the Use Conditions of “Specified Local Lines”. Proceedings of the City Planning Institute of Japan, Kansai Branch, Vol. 15, 41-44. https://doi.org/10.11361/cpijkansai.15.0_41
[25]	Takeda, I. (2018) Proposal for the Role, Maintenance and Revitalization of Local Railways in an Era of Depopulation. Jumin to Jichi Monthly, 663, 6-10.
[26]	Shimizu, S., Nakagawa, D., Kanayama, Y., Honda, Y. and Murano, T. (2021) A Study on the Role of Citizen Organization in the Process of Building Consensus for Regeneration of Local Railway—Based on the Case in Fukui Prefecture. Journal of Japan Society of Civil Engineers, Ser. F5 (Professional Practices in Civil Engineering), 77, 101-111. https://doi.org/10.2208/jscejppce.77.1_101
[27]	Kato, K. (2005) Why Do Replacement Buses Decrease Passengers? A Consideration of the Problem Included in the Examination Process. Proceedings of Infrastructure Planning, Vol. 31, 129.
[28]	Takayama, J. (2012) A Consideration on the State of Replacement Buses after the Abolishment of Local Railway Lines. Proceedings of the Conference of Japan Society of Traffic Engineers, Vol. 32, 501-506.
[29]	Kishi, K. (2021) Establishment of Service Level of Railway Replacement Buses Adopting Prospect Theory. The Japanese Journal of Transportation Economics, 64, 155-162.
[30]	Axhausen, K.W., Haupt, T. and Heidl, U. (2001) Searching for the Rail Bonus. European Journal of Transport and Infrastructure Research, 1, 1567-7141.
[31]	Alexandersson, G. and Hultén, S. (2008) The Swedish Railway Deregulation Path. Review of Network Economics, 7, 18-36. https://doi.org/10.2202/1446-9022.1136
[32]	Pflieger, G., Kaufmann, V., Pattaroni, L. and Jemelin, C. (2010) How Does Urban Public Transport Change Cities? Correlations between Past and Present Transport and Urban Planning Policies. Urban Studies, 46, 1421-1437. https://doi.org/10.1177/0042098009104572
[33]	Blainey, S. (2010) Trip End Models of Local Rail Demand in England and Wales. Journal of Transport Geography, 18, 153-165. https://doi.org/10.1016/j.jtrangeo.2008.11.002
[34]	Ryley, J.T., Stanley, P.A., Enoch, M.P., Zanni, A.M. and Quddus, N.A. (2014) Investigating the Contribution of Demand Responsive Transport to a Sustainable Local Public Transport System. Research in Transportation Economics, 48, 364-372. https://doi.org/10.1016/j.retrec.2014.09.064
[35]	Davidsson, P., Hajinasa, B., Holmgren, J., Jevinger, A. and Persson, J.A. (2016) The Fourth Wave of Digitalization and Public Transport: Opportunities and Challenges. Sustainability, 8, Article No. 1248. https://doi.org/10.3390/su8121248
[36]	Takemura, M., Ieda, H. and Kaminishi, S. (1997) Effects and Subject of Railway Replacement Buses after the Earthquake. Papers of the Symposium on Infrastructure and Management, Tokyo, 10-12 September 1992, 465-470.
[37]	Mouri, K. (2013) Policy on the Passenger Transport Security during the Time of Recovery Railway after Large-Scale Disaster. NRI Public Management Review, 115, 7-12.
[38]	Kaneko, Y., Sano, A. and Muroi, T. (2015) Study on Bus Operation as Substitute for Railway after Earthquake in the Tokyo Metropolitan Area. Journal of Japan Society of Civil Engineers, Ser. F6 (Safety Problem), 71, I_199-I_204. https://doi.org/10.2208/jscejsp.71.I_199
[39]	Furth, P.G. and Rahbee, A.B. (2000) Optimal Bus Stop Spacing through Dynamic Programming and Geographic Modeling. Journal of the Transportation Research, 1731, 15-22. https://doi.org/10.3141/1731-03
[40]	Saka, A. (2001) Model for Determining Optimum Bus-Stop Spacing in Urban Areas. Journal of Transportation Engineering, 127, 195-199. https://doi.org/10.1061/(ASCE)0733-947X(2001)127:3(195)
[41]	Izumida, K., Kikuchi, D., Ikeda, T. and Takayama, T. (2005) Optimum Arrangement Method of Bus Stops in Regional Bus Route. Proceedings of the 67th National Convention of IPSJ, Vol. 1, 503-504.
[42]	Ohigashi, N. (2005) A Study for Arrangement of Bus Stop and Population Area of Distribution. Summaries of Technical Papers of Annual Meeting Architectural Institute of Japan. F-1, Urban Planning, Building Economics and Housing Problems, Osaka, 1-3 September 2005, 699-700.
[43]	Chien, S.I. and Qin, A. (2007) Optimization of Bus Stop Locations for Improving Transit Accessibility. Transportation Planning and Technology, 27, 211-227. https://doi.org/10.1080/0308106042000226899
[44]	Ibeas, A., dell’Olio, L., Alonso, B. and Sainz, O. (2010) Optimizing Bus Stop Spacing in Urban Areas. Transportation Research Part E: Logistics and Transportation Review, 46, 446-458. https://doi.org/10.1016/j.tre.2009.11.001
[45]	Takakura, M., Yoshida, T. and Soda, M. (2015) Solving Method of the Bus Stop Placement Problem of Community Bus “Notty” ITS. IEICE Technical Report, 115, 17-22.
[46]	Watanabe, K. and Yoshikawa, T. (2023) Optimal Location of Cycle-and-Bus-Ride Bicycle Parking Lots. Reports of the City Planning Institute of Japan, 22, 90-95. https://doi.org/10.11361/reportscpij.22.1_90
[47]	Suzuki, T. (1987) Optimum Locational Patterns of Bus-Stops for Many-to-One Travel Demand. Journal of the City Planning Institute of Japan, 22, 247-252. https://doi.org/10.11361/journalcpij.22.247
[48]	Yoshii, Y., Taira, H. and Goto, S. (2011) Optimal Placement of Bus Stops Using Voronoi Division Method. Proceedings of the Annual Meeting of Personal Computer Utilization Technology Society, Vol. 6, 57-59.
[49]	Kojo, T. and Yoshikawa, T. (2016) Basic Analysis of Bus Stop Placement Considering the Use of Private Car in Line Segment City. Summaries of Technical Papers of Annual Meeting, Summaries of Design Works of Annual Meeting, Architectural Institute of Japan, Fukuoka, 24-26 August 2016, 1883-9363.
[50]	Dijkstra, E.W. (1959) A Note on Two Problems in Connexion with Graphs. Numerische Mathematik, 1, 269-271. https://doi.org/10.1007/BF01386390
[51]	Dorigo, M. (1992) Ottimizzazione, Apprendimento Automatico, ed Algoritmi Basatisu Metafora Naturale (Optimization, Learning, and Natural Algorithms). Doctoral Dissertation, Systems and Information Engineering, Politecnico di Milano, Milano.