Transit Network Design Using GIS and Ant Colony Optimization in Sanandaj ()
1. Introduction
The purpose of transportation is to overcome the distance friction in space which is affected by physical and human constraints such as, geometric distance, time, topology of network, and administrative policies and decisions [1]. The specific purpose of transportation is to satisfy the mobility demand of people, goods, and information. The network-based routing methods in transportation are able to construct efficient routes for different types of vehicles traveling from an origin to a destination while considering several objectives and policies related to the user and the operator of the transportation system [2] [3] [4]. The transit network design (TND), the main components of the public transit planning, is a class of the network-based routing approaches. Increasing the accessibility for low and middle income individuals with limited access to private transportation is an objective of the transit networks [5].
Accessibility can be broadly described as “the ease with which activities at one place may be reached from another via a particular travel mode” [6]. Access can be defined as physical proximity to stops [5]. Transit planners generally have to deal with a tradeoff between increasing accessibility by using more stops in the design and design routes with reasonable travel time [7]. Multi-criteria decision analysis (MCDA) which is a set of methods and procedures for tackling decision problems involving a set of decision alternatives, can be used to find an optimal transit system based on the objectives of the TND [8] [9]. This study focuses on multi-objective optimization approach.
Public transit planning research is conducted with the aid of decision makers (DM) who are individuals or entities with the responsibility of making decisions [10]. DMs can be individuals, a group of experts, community, private or government organizations [8]. While the conventional decision analysis focuses on the human decision maker, recent approaches to computer-based modeling provide a broader description of decision maker to include the concept of decision making agent [11] [12].
An agent is a computer program characterized by such properties as autonomy (i.e., the capability of taking independent action), reactivity (i.e., the capability of sensing and reacting to its environment and other agents), and rationality (i.e., the capability of acting rationally to solve a problem at hand (Sengupta and Bennett, 2003)). Intelligent agents designed specifically for using geographic data and tackling spatial problems are referred to as geospatial agents.
This study contributes to urban transportation and GIS by offering an innovative approach for GIS-based transit network design (TND). In this research an attempt is made to connect swarm intelligence and GIS for solving the TND problem. The proposed approach contributes to GIS-based network analysis by implementing distributed and decentralized agent-based method for evaluating alternative transit network configurations.
The main goal of this research is to develop a GIS-based multi-objective procedure and apply the proposed approach to design the transit network in the City of Sanandaj. Three main research tasks (objectives) of this study are:
1) To provide a multi-objective model of the TND problem in the City of Sanandaj, Iran.
2) To develop a procedure for solving the TND problem.
3) To examine and evaluate the solutions (alternative transit networks) generated by ant colony optimization.
2. Methodolog
2.1. Ant Colony Optimization
Ant Colony Optimization (ACO) is a type of swarm intelligence with simple agents and lower level of complexity compared to ABM [13]. ACO consists of a collection of ants searching for food in nature. Ants try to find the shortest route to the food source by following the path created by pheromones on the ground from previous ants.
For complex optimization problems, the distribution or parallelization of this method reduces the time to generate solutions because ACO is a distributed method since ants are relatively independent. MOACO includes multi-colony ant procedures in which each subset of ants, separate from other colonies, works collectively to construct a solution set. Multi-colony methods can easily be parallelized [14]. Computational steps for ACO involves the following [15]: 1) representing the optimization problem by means of a weighted graph (network) on which ants (agents) can build their solutions, 2) modeling pheromone trails, 3) selecting an ACO algorithm and implement it to solve the problem, and 4) tuning ACO parameters. Ants in ACO are equipped with memory of former decisions and knowledge of important locations in their geographic area [4] [13] [16].
Although one ant is unable to communicate and solve complex problems, but interaction with other ants will enable them to solve complex optimization problems. In nature, ants travel randomly on the surface of the earth until encountering pheromone from another ant which can follow and leave their pheromone behind to reinforce the path. More ants choose one path; probability of next ant taking the similar path is higher. After a period of time, solutions with lower level of pheromone due to pheromone evaporation lose their attraction [16].
2.2. TND Model
Modelling TND problem involves a process of searching for efficient transit routes based on the preferences of transportation firms and users [3] [17] [18] [19] [20]. In the multi-objective network design, one would define several objectives in order to operationalize the operator’s and user’s preferences. A weight is assigned to each objective that represents the importance of the objective for the decision maker. Each decision maker, based on his/her preference, assigns different values to objectives’ weights. After weights have been determined, a distinct solution is generated. This study focuses on the following objectives: the number of stops in the transit network, the total walking distance to the transit stop, and the total travel time of passengers in the transit system.
The first objective is also based on the operator’s perspective to minimize the number of stops in the transit network. Optimal number of stops minimizes the long-run cost of transit system and provides complete access coverage in the operation area [21]. The objective’s formulation is as follows:
(1)
where Nrn is a decision variable, and Nrn = 1 if a stop n is located on the r-th route, and Nrn = 0 otherwise (r = 1, 2, 3, ∙∙∙, k; n = 1, 2, 3, ∙∙∙, m); w2 is the objective’s weight. The objective function is subject to some constraints. In order to limit the minimum and maximum number of stops, a distance constraint between two stops should be considered. The minimum and maximum distances between two stops can be 300 and 600 meters, respectively; these are based on the observed pattern of stops of radial transit networks in several cities [22]. Also, the number of stops on each route should be greater than zero.
The third objective is related to passengers’ preference to minimize the total walking distance to the transit station. An acceptable walking distance within a certain limit is crucial in order to persuade the user to take a trip using the transit system [3] [23]. There is an inverse relationship between walking distance to the stop and accessibility of transit system [23]. Different minimum and maximum walking distance constraints have been proposed previously. Farwell and Marx [24] suggest that walking distance more than 400 meter is very inconvenient for transit users. Therefore, in this study the range of possible values for walking distance is limited. The objective function takes the following form:
(2)
where WDrn is a decision variable of walking distance to the stop n on the r-th route, 0 ≤ WDrn ≤ 400 meters, and w3 is the weight of importance assigned to the objective.
In order to minimize the total travel time of passengers in the transit system (i.e., the total cost for user) another objective is proposed. It is known that travel time between two stops on the shortest path is the minimum [3]. It is necessary to consider travel time or distance in TND because of its influence on the user’s satisfaction. The objective is to minimize the difference of travel time between two stops and the shortest path time. The objective function is expressed as follows:
(3)
where
is the decision variable; it is the difference between
(travel time between stops l and n on the r-th route that includes waiting time, in-vehicle time and transfer time) and
(the shortest path between stops l and n on the r-th route),
[3];
is the travel demand between stops l and n on the r-th route; w4 is the weight of importance assigned to the objective.
3. Study Area
Kurdistan province with 28,203 square kilometer area between 34.44'N and 36.30'N latitudes, and 45.31'E and 48.16'E longitudes which makes up 1.7 percent of country’s land. The province mainly consists of plains and valleys in Zagros mountains. From north the province is neighboring Azarbaijan, from the east Hamedan and Zanjan, and from the south Kermanshah provinces. Kurdistan province is also on the Iraqi border, it is connected to Iraq from West.
The City of Sanandaj is the capital of the Kurdistan province in Iran. Sanandaj population was 432,330 in 2011 and it has a transit plan which is a part of the “official” plan [25]. Official plan includes comprehensive plan, general plan and tourist plan [25]. Main goal of the transit plan is to reduce the congestion in the city core of Sanandaj. Traffic can be attributed to the process of migration from smaller population centers, insufficient transportation infrastructure development, the compact structure of road/street network [25] [26] (see the following Figure 1), and the structure of trips by transportation mode (a very low share of bus system of trips and very high share of private car trips) [25]. Transportation policies such as construction of fast and competitive public transit system can facilitate movement and reduce congestion in cities with radial pattern similar to Sanandaj [22].
The population data is from 2011 census data which is a detailed information about the number of the residents in each block in Sanandaj and the type of jobs they have [25]. The population data is later used to create a Kernel population density map in order to find out which area has a dense population and therefore should be considered in the transit network design in the city.
4. Results
In order to find the optimal transit solution in Sanandaj several transit networks have been designed based on the objectives proposed. Each bus line in the designs connects central and peripheral terminals and passes through high population density areas. The transit networks have been displayed in Figures 2-12. Most of these designs consist of radial bus lines and beltways to increase the coverage of the bus system. Because of the importance of walking distance for the passengers compared to the distance of travel, beltway routes are suitable and travelers prefer to take a bus on the beltway to go to a radial route than direct access by walking to the stops on the radial line [27].
The 1st scenario: It has radial routes without beltway because of CBD importance in Sanandaj [25]. It provides coverage for most of the important destinations.
The 2nd scenario: It provides a cartwheel design that includes beltway lines around downtown area. The ring lines can transport passengers in the peripheral districts. They also connect the radial lines to transfer between the radial lines [28]. This design has not included any external ring line in the peripheral towns. This results in lower network size.
![]()
Figure 1. Road Network in the City of Sanandaj, Iran (Kurdistan, 2011).
![]()
Figure 2. Overlay map of the first scenario and Kernel population density.
![]()
Figure 3. Overlay map of the second scenario and Kernel population density.
![]()
Figure 4. Overlay map of the 3rd scenario and Kernel population density.
![]()
Figure 5. Overlay map of the 4th scenario and Kernel population density.
![]()
Figure 6. Overlay map of the 5th scenario and Kernel population density.
![]()
Figure 7. Overlay map of the 6th scenario and Kernel population density.
![]()
Figure 8. Overlay map of the 7th scenario and Kernel population density.
![]()
Figure 9. Overlay map of the 8th scenario and Kernel population density.
![]()
Figure 10. Overlay map of the 9th scenario and Kernel population density.
![]()
Figure 11. Overlay map of the 10th scenario and Kernel population density.
![]()
Figure 12. Overlay map of the 11th scenario and Kernel population density.
The 3rd scenario: It is also a cartwheel design that introduces beltway lines for the bus system. People currently use these beltways to drive to their destinations in the peripheries while they can avoid the traffic of downtown core [25].
The 4th scenario: It consists of several internal ring lines near CBD that connects radial lines. Passengers can take the bus on these bus lines to move around the CBD area without going through downtown core.
The 5th scenario: It offers several external ring lines that link peripheries and towns in outer areas. Passengers can use the beltways to travel in the peripheral districts and take a transfer bus to downtown from another district [28].
The 6th scenario: It includes more beltways, compared to the previous designs. This network design provides more routes for passengers on the ring lines to avoid the traffic congestion in the peak hours of day.
The 7th scenario: This network includes two parallel beltways moving through the western districts of the city. These ring lines connect several radial bus lines from CBD with transfer locations located in busy locations in Sanandaj.
The 8th scenario: It is a star network and to increase the coverage extra ring lines are added to the design with no bus route passing through the downtown [29]. The radial bus lines start from the ring line outside of downtown to avoid the traffic of downtown area.
The 9th bus network: It consists of several radial routes which they have been linked by beltway routes. In the design several bus lines have been removed, compared to the previous designs to reduce the density of bus lines near downtown.
The 10th scenario: It has a trunk line from CBD to the remote areas in the peripheries. Also, parallel lines moving from east to west through busy locations of the city can transfer more passenger from one side of the city to the other.
The 11th scenario: It is proposed based on having a lower number of bus lines in the peripheral areas. In the 11th scenario, only one external beltway is proposed to lower the cost of operation [30]. The radial bus lines start outside of CBD area in order to avoid the traffic congestion.
4.1. Coverage of the Proposed Bus Network Designs
The coverage of proposed TNDs is measured based on the walking distance to the network. Using GIS, access to the bus system in different neighborhoods of the city and peripheral towns have been analyzed. Since Sanandaj is a city with compact urban structure and high population density, short walking distance such as 100 and 300 meters is preferred for bus system. The proposed networks cover a significant portion of the census blocks within their 300 meters. Coverage of the TNDs considering the walking distance of 100 meters and 300 meters is calculated and displayed in the following Figure 13.
Analysis of the diagrams generates mixed results. While the 10th scenario offers highest access to the bus system for the potential passengers in 300 meters walking distance, it performs poorly for shorter distance of 100 meters. The 6th and 5th TNDs produce relatively similar coverage for 100- and 300-meters
![]()
Figure 13. Population covered (in thousands) by each network design for 100 (left) and 300 (right) meters walking distance and major destinations within 300 meters of the networks.
walking distances. Based on the result, these two scenarios generate better access to the bus service, compared to other networks.
One of critical factors in designing the transit network is access to the major destinations in the city and peripheries. The 5th and 6th network designs have the highest coverage and the 3rd and 7th network designs are the second-best scenarios. Also, 2nd, 4th and 10th networks provide similar results and rank third considering access to the popular destinations. The 11th scenario, offers lower access to the major destinations in the city because of dispersed routes and lack of enough bus lines passing through the downtown core. Also 8th TND is similar because of exclusion of CBD from the bus system and routes due to high traffic congestion.
Based on the results, the 6th scenario generates a low total travel distance and number of stops. Also, the first scenario which is a small sized network with a small number of stops has the lowest coverage of population and cost of operation without having enough service in the peripheries due to lack of beltway routes.
4.2. Comparison of Prosposed Networks Using ACO
Optimizing the travel distance is one of the objectives proposed here. Travel distance is affecting the operational cost and the user cost of travel. Radial networks, such as first scenario reduce the operational cost and user cost by minimizing the total travel distance. Ant Colony provides an estimate of total travel distance for a tour of the proposed networks. Also, the number of stops is directly related to the operational cost of the transit networks. Reducing the number of stops reduces the operational costs. The number of stops is calculated by ACO method for each scenario.
For each cost or objective, such as number of stops and travel distance, a pheromone function has been considered in the ACO. Ant colony method calculates the total travel distance and the number of stops on the network in each iteration by using several ants starting from random locations on the network. Higher amount of pheromone is laid on more desirable path based on the objective used for the pheromone functions. The following Figure 14 displays the assessment of proposed networks by ACO.
5. Conclusions
This study displays the importance of considering several objectives in transit network design by pointing to the relationship between these objectives and how they can help in evaluation of the networks. Each objective is related to one critical aspect of transit network design. Single objective solutions do not satisfy the users and operators of the transit system simultaneously. Therefore, two sides of the public transit planning which is costs-related to the operator such as travel distance (can be considered for operator and user as well) and number of stop, and costs-related to the user of the system such as walking distance should be considered in order to find the better solutions.
In this research several issues such as access to the bus system in peripheries and coverage of the bus network have been addressed. It is discussed that the radial design which is more efficient in the operator perspective cannot provide the best access to the transit system in the peripheral areas. Therefore, beltway routes need to be added to the next transit network designs proposed. Also, access to the network is measured by population blocks access to the networks proposed.
![]()
Figure 14. Total travel distance (in kilometers) and number of stops of the proposed bus networks.
There is a clear trade-off between access to the bus network and travel distance. Creating a balance between two views that are the operator’s view to reduce the cost and the user’s view to have access to the bus system in the city and shorter walking distance, is the core of the transit network design. Radial designs such as the first scenario are more favorable for operators because of lower operation costs, but they also reduce the level of service provided for the population in the peripheries. Therefore, a radial network is not a favorable design for the users of the transit system. Other TNDs with more beltways are costly to operate, but they provide better access to the transit system for the population in Sanandaj, the city used as an example in this study. The choice of TND for Sanandaj depends on the budgetary restrictions of the city administration, because adding beltways to the bus system generate better access with higher cost.
6. Recommendations
Several recommendations for future research can be proposed here. Extra work can be performed in order to find out the how the population interacts with the bus system and how the walking distance and length of the bus lines affect the usage of the bus system by people. Also, how frequency of the buses in the network can affect the number of passengers in Sanandaj that use the bus system can be studied. Ignoring the frequency and impact of different walking distances in this study are two limitations of these researches.