The Design of Urban Traffic in Ferizaj through Operational Research

Bashkim Çerkini, Fakije Zejnullahu, Dhuratë Hyseni

Faculty of Engineering and Informatics, University of Applied Sciences in Ferizaj, Ferizaj, Kosovo.

DOI: 10.4236/jcc.2020.812004                

Abstract

Cities are undergoing rapid changes continuously due to the high demands of this era, and simultaneously affect several life fields, namely urban transport. High demands are triggering people to travel more frequently than ever; thus, they utilize public transportation more and private transportation less as the latter ceased to fulfill all the transportation needs. Thus, public transportation demand has been increasing greatly alongside citizens’ needs. Nonetheless, many cities lack proper urban traffic planning and organization, while some lack an urban transport service. Ferizaj, a city in Kosovo, is one of the cities that lacks an urban traffic designation; hence, this paper presents a designed urban traffic model, precisely suitable to fulfill the urban transportation need for Ferizaj city. This model is designed under the utilization of applied mathematics’ techniques and operational research. Several factors have been considered, following the geographical distribution of the population, existing roads, and residents’ needs. Consequently, the Solver program has been used as an optimization tool to find the shortest path and most economical paths, added in the discussion part. Besides, the likelihood of the designed urban traffic model’s application in Ferizaj is discussed, considering its viability and application conditions. This study presents mathematical constraints to design a model of the bus network in Ferizaj through Solver. We have used mathematical optimization methods, graph theory, the simulation model through the Solver computer program for network minimal distances and presenting the first model of the Urban traffic network in Ferizaj.

Keywords

Transport, Solver, Algorithm, Optimization and Nodes

1. Introduction

The development of public urban transport is an important topic in modern society. As cities grow, so do people’s need for transportation, and not all of these trips can be made by private transportation. Therefore, there is a need to provide a well-organized urban public transport to efficiently meet the demands of citizens. Planning and optimization of public urban transport is needed to make the best possible use of economic resources, better functionality for citizens, and preserve the environment. Thus, the requirement of this paper constitutes basic information for proper transport planning using operational research techniques.

Sustainable and integrated transport is associated with several challenges, especially in urban public transport within cities and peripheral regions. Many regions worldwide face the problems of increasing individual motorized transport, causing many negative phenomena such as traffic jams, parking problems in city centers and increased pollution from the number of emissions. Governments and local authorities are trying to solve these problems by making various investments in public transport.

The research in urban public transport aims to optimize urban traffic lines, find shorter routes, and reduce travel time that overall brings economic and environmental benefits. A combination of mathematical models and operational research techniques are used to optimize the urban public transport network.

Ferizaj has not had an urban bus transportation network within the city yet.

Traveling in an urban network represents an interaction between the demand for transport and means of transport, road networks, population distribution as well as the existing road infrastructure. In this research paper, Solver is used to finding a solution that satisfies the constraints and minimizes the objective cell value. The mathematical relationships between the objective and constraints and the decision variables are used to get the solution for optimized Urban Traffic in Ferizaj. With the Simplex LP Solving method, we could find a globally optimal solution given enough time [1].

Many researchers have analyzed the urban public transport service problems using various mathematical and operational research methods.

In [2] an optimization model is developed for the bus transit network based on the road network and the origin-destination area (OD). The model aims to achieve minimum transfers and maximum passenger flow for line length and non-linear rates as constraints. The Coarse-Grain Parallel Ant Colony Algorithm (CPACA) was used to solve this problem. To effectively search for optimal global solutions, we use a pheromone distribution orientation rule to regulate ant path search activities according to objective value. Parallel Ant Colony Algorithm (ACA) is used to shorten the computation time. The model was tested with Dalian city survey data. The results show that in an optimized bus network with fewer transfers and travel time, the application of CPACA effectively increases the calculation speed and quality.

[3] Ant Colony Optimization algorithms are used for more efficient road traffic. In traffic management, these algorithms have growing popularity, with their ability to find optimal solutions in situations where traditional methods fail to find any good solution. A transport system where ACO has been used to help with the transport network problems is on the London Underground network. The network consists of 270 connected stations along with a combined total of 250,000 miles of roads and transports around 1.107 million people to London each year. With this size and volume of users, disturbances in specific areas can greatly impact the network. Therefore, finding an effective diversion around any particular problem in a short period of time is vital to prevent blockages that can spread throughout the system.

In [4] the problem of finding the shortest path is solved through the Ant Colony Optimization algorithm (ACO), which is based on the Ant Colony metaheuristic method. One of the most important elements of any algorithm based on the Ant Colony paradigm system’s use is the rules for creating paths leading from a starting point to the endpoint.

[5] optimizes the distribution of bus routes in Wuhan duke to alleviate or solve the problems exposed by the extension of existing roads in the city, e.g., reducing overlapping roads, increasing network coverage, and reducing the main road’s burden. This research has used a method for designing various transit routes based on stops, which treats some railway routes as constraints. Genetic algorithms have been applied to search for the optimal combination of candidate pathways. Evaluation based on optimization results is generated to analyze whether the expected improvements have been achieved, especially in the short term.

In [6] some of the basic line planning models, identification of their characteristics, mathematical approaches, and line planning algorithms are presented. Furthermore, similar topics are highlighted, such as current and future research directions, and the line planning process is examined. It is assumed that the infrastructure has already been provided and introduced as a public transport network. In particular, it is assumed that the stations are fixed, and the set of possible node pairs will be given. These can be roads (by bus) or the rail system (rail, tram, or underground). Line planning includes the defined number of lines and line routes. They also include determining the frequency of lines, i.e., how often these services should be provided. The problem of line planning is finding the line system, ensuring that urban public transport is convenient for passengers and small costs.

[7] proposes a methodology for the optimal development of transit networks, which minimizes transit transfers and total user costs while maximizing service coverage, the information provided on transit demand and the transit network road network area. Research provides an effective mathematical and computer tool with minimal support of the heuristic method. The methodology includes the representation of road transit networks and the solution of search spaces, the objective functions that represent the user’s total costs, and the users’ lack of willingness to make transfers. The methodology has been tested with solutions to problems published at this stage and has been implemented on a large scale in network optimization in Miami-Dade County, Florida.

2. Methodology

The methodology used in this paper is the collection and processing of data related to urban transport and the definition of optimization criteria [8], the use of mathematical methods, and the Solver program for the design of urban transport, which has not yet been implemented in the city of Ferizaj. Mathematical optimization methods, graph theory, and solver programs are used. Sustainable and integrated transport is associated with several challenges, especially in urban public transport within cities and peripheral regions.

The paper is based on the following objectives:

• Minimize the length of roads between origin and destination for certain paths

• Proposal for the urban public transport network in Ferizaj.

In Figure 1, the Map of Ferizaj is presented from Google Map. We have

Figure 1. Ferizaj roads with intersection with numbers.

placed the numbers at each intersection and measurements between the points obtained in the geoportal. The geoportal is a web portal used to find and access geographic information via the Internet. Each intersection has been assigning a random number that we will consider from now on as nodes.

In Figure 2 all nodes are connected based on existing paths, and we have created the graph where all the work from now on is based on this graph through graph theory.

All paths between nodes are measured, and we have at our disposal the values of the lengths of all the paths for use in this paper. Using mathematical constraints, we have placed all this data in the Solver program to find the shortest possible routes and, consequently, the urban traffic network model in general in the city of Ferizaj.

Figure 2. Directed graph with nodes with numbers.

3. The Design of Bus Transportation Network in Ferizaj with Solver

Solver is an optimization tool used through Microsoft (MS) Excel that uses genetic algorithms (GA) and linear programming technology that quickly solves various problems in finance, distribution, resource allocation, manufacturing, engineering, etc [9]. Virtually any type of problem that can be modeled in MS excel can be solved with Solver, including the impossible ones and complex nonlinear problems [10].

Solver represents optimization through the fastest and most advanced genetic algorithms ever used. Through the most powerful application of optimization techniques based on algorithms, the solver can find optimal solutions to problems that are considered unsolvable for linear and nonlinear optimizers. [11]. Optimization is a process of finding the best solution to a problem that can have many possible solutions.

The transport network is presented with a graph G(V, E) with a set of nodes and of streets [12]. Notice the number of joints with |V| = n and the number of roads |E| = m [13]. We will define the variables 0 and 1 for u_ij:

$u_{ij}=\{\begin{array}{cc}1，& \text{If}\text{there}\text{is}\text{a}\text{path}\text{between}\text{nodes}i\text{and}j\\ 0，& \text{others}\end{array}$

If there is a path between nodes v_i and v_j then this is applied:

$u_{ij}+u_{ji}=1$

Since there is a starting and a final node, the eventual solution of the shortest path is a direct path between them [14]. Nodes x_i and x_jmay be limited as below:

$u_{ij}+u_{ji}\le 1$

$i,j\in V$

Every bus line has only one starting node described as “line in” and one end node described as “line out”. Joints in between have both “line in”, and “line out” and off-road nodes have neither the “line in” nor “line out”. So, we define “net flow” as “line out” minus “line in”. Because of the nodes in the applicable path there is an “out line” and the nodes in the applicable path have no “line in”, so we have:

${\displaystyle {\sum }_j{u}_{ij}}\le 1,\forall i\in V$

In order to calculate the distance of each applicable road we need to find the shortest path:

$\min S={\displaystyle {\sum }_i^n{\displaystyle {\sum }_j^n{l}_{ij}{u}_{ij}}}$

We can present the problem of the shortest road model as follows:

$\text{s}\text{.t}\text{.}{\displaystyle \underset{j}{\sum }{u}_{ij}}-{\displaystyle \underset{j}{\sum }{u}_{ji}}=\{\begin{array}{cc}1,& \text{is}\text{starting}\text{node}\\ -1,& i\text{is}\text{last}\text{node}\\ 0,& \text{others}\end{array}$

$u_{ij}\in \{0,1\},\forall \left(i,j\right)\in E,$

The new model of the Urban Traffic Network in Ferizaj will contain eight bus lines. All these nodes with the corresponding numbers can be found in the maps of Figure 1 and Figure 2 to find all the bus lines.

In Table 1 are shown eight bus lines with origin and destination nodes.

After we enter all needed data’s we will start to find shortest path between origin and destination nodes for all eight bus lines.

The objective in this case is to minimize total costs and is placed in the Target Cell which we call “Optimization Goal”. In Table 2 is shown the net flow of the starting node is 1 and the last node is −1.

The column “Road Selected by Solver” have all results presented with “0” or “1”. “0” is when the Solver does not select the road, whereas “1” is selected by the Solver [15]. Out of eight bus lines, we have shown results only for bus line 1 between nodes 1 and 40 in Table 3. This table shows results with “1”, which is the road selected by the Solver, and none of the results with “0”. The total minimum length for bus line 1 is 4456 meters.

Similar action was conducted for all eight bus lines, the obtained results of which are presented in Table 4 through the Solver.

Table 1. Bus lines with origine and destination nodes.

Table 2. Starting and end point.

Table 3. Path between node 1 and 40 selected by Solver.

Table 4. Selected urban transport bus network in Ferizaj through Solver.

4. Conclusions

As stated already, public urban transport is a critical modern society topic nowadays. It facilitates the daily transport of citizens providing services that private transport cannot. In this regard, since no public transport is available in Ferizaj yet, only some independent bus lines from city to villages around trips, this called for a designation of public transport. Hence, this paper presented a designation of a public transport model for Ferizaj by considering the existing roads and citizens’ needs. This public transport model was designed under mathematical optimization methods, graph theory, and solver program as an optimization tool to find the shortest and most economical paths. The designation process has been presented through several graphics above, in detail, results of which are promising to fulfill and facilitate the citizens’ transportation needs. Essentially, public transportation in Ferizaj can play an important role in improving and providing different benefits, including direct benefits to the passengers and indirect benefits to society.

Nonetheless, this research had its own limitations. The actual bus station location has not been studied to collect data on whether it meets the requirement to have the new public urban transport design applied. Nevertheless, this paper, despite bringing an innovative solution to Ferizaj’s public transport, paves the way for future studies regarding the analysis of bus station location.

Conflicts of Interest

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

References

[1]	Optimizimi i Rrjetit tё Transportit Urban (Rasti i Prishtinёs) (2016) Bashkim Çerkini. https://docs.google.com/a/fshn.edu.al/viewer?a=v&pid=sites&srcid=ZnNobi5lZHUuYWx8ZnNobnxneDo1N2ZlNDNlYzg1ZDdmZWY3
[2]	Yu, B., Yang, Z.Z., et al. (2005) Optimizing Bus Transit Network with Parallel Ant Colony Algorithm. Proceedings of the Eastern Asia Society for Transportation Studies, 5, 374-389.
[3]	Burrows, P., Reed K., Templer, K. and Walker, J. (2012) Efficient Traffic Routing Using ACO. https://www.semanticscholar.org/paper/Efficient-Traffic-Routing-using-ACO-Burrows-Reed/ace5876581abc06e1fc48cfa9ead675b4ad695fa
[4]	Glabowski, M., Musznicki, B., Nowak, P. and Zwierzykowski, P. (2012) Shortest Path Problem Solving Based on Ant Colony Optimization Metaheuristic. Image Processing & Communication, 17, 7-18. https://doi.org/10.2478/v10248-012-0011-5
[5]	Ning, Z. (2011) Bus Routes Optimization in Wuhan, China. http://essay.utwente.nl/84980/1/ning.pdf
[6]	Schöbel, A. (2012) Line Planning in Public Transportation: Models and Methods. OR Spectrum, 34, 491-510.
[7]	Zhao, F. (2006) Large-Scale Transit Network Optimization by Minimization User Cost and Transfers. Journal of Public Transportation, 9, 107-129. https://doi.org/10.5038/2375-0901.9.2.6
[8]	Klier, M.J. and Haase, K. (2008) Line Optimization in Public Transport Systems. In: Kalcsics, J. and Nickel, S., Eds., Operations Research Proceedings 2007, Springer, Berlin, 473-478. https://doi.org/10.1007/978-3-540-77903-2_73
[9]	Salini, R., Xu, B. and Lenngren, C.A. (2015) Application of Artificial Intelligence for Optimization in Pavement Management. International Journal of Engineering and Technology Innovation, 5, 189.
[10]	Çerkini, B., Kosova, R. and Prifti, V. (2014) Transportation Cost Optimization using Evolver, IP-Solver and MS Foundation. Durrës, Albania, 7 November 2014, 23-31. https://knowledgecenter.ubt-uni.net/conference/2014/all-events/55/
[11]	Fan, W. and Machemeh, R.B. (2006) Optimal Transit Route Network Design Problem with Variable Transit Demand: Genetic Algorithm Approach. Journal of Transportation Engineering, 132, 40-51. https://doi.org/10.1061/(ASCE)0733-947X(2006)132:1(40)
[12]	Çerkini, B. and Mitre, T. (2016) Design of Public Urban Transport Network through Software Evolver in Pristina. Journal of Multidisciplinary Engineering Science and Technology, 3, 4103-4106. http://www.jmest.org/wp-content/uploads/JMESTN42351409.pdf
[13]	Çerkini, B., Bajrami, R., Kosova, R. and Shehu, V. (2015) Transportation Cost Optimization. Academic Journal of Interdisciplinary Studies, 4, 42. https://doi.org/10.5901/ajis.2015.v4n2s1p42
[14]	Mason, A.J. (2012) Opensolver-An Open Source Add-in to Solve Linear and Integer Progammes in Excel. Operations Research Proceedings 2011, Springer, Berlin, 401-406. https://doi.org/10.1007/978-3-642-29210-1_64
[15]	Fylstra, D., Lasdon, L., Watson, J. and Waren, A. (1998) Design and Use of the Microsoft Excel Solver. INFORMS Journal on Applied Analytics, 28, 29-55. https://doi.org/10.1287/inte.28.5.29