Multiob jective design of sustainable public transportation systems

Abstract

The design of the bus network is a complex problem in modern cities, since di erent con icting objectives have to be considered, from both the perspective of bus companies and the citizens. This article presents a multiobjective model for designing a sustainable public transportation network that simultaneously optimizes the covered travel demands by passengers, the total travel time, and the generated pollution. The proposed model is solved using exact weighted sum and a heuristic procedure based on the standard shortest path problem. Preliminary tests were performed in small real-world instances of Montevideo, Uruguay. Experiments allowed obtaining a set of compromising solutions that in turn allow exploring di erent trade-o among the optimization criteria. The proposed heuristic was competitive, being able to nd a good compromising solution in short computing times.

1. Introduction

The expansion of urban population in the last century has put pressure on decision-makers to provide e cient public services to the citizens. Among these services, having an e cient public transportation system is of paramount importance in order to diminish the impact of private cars. In the recent past, this system had to ful l two main goals: provide a good Quality of Service (QoS) to the citizens and burden the operating costs for the operators of the system [ 1 ]. However, in the last decades, sustainability has also been integrated as an important criterion in public transportation system [ 2 ]. Public transportation can be an important contributor to air pollution [ 3 ], a ecting the environment and quality of life of the citizens. In this sense, several cities have implemented diverse policies for reducing the impact of this vital service. For example, in the last years, the City Hall of Montevideo has increasingly acquired a number of electric and hybrid buses [ 4 ].

Among the diverse decision-making problems involved in public transport, the Bus Transit Network Design Problem (TNDP) is a common computationally complex [ 5 ] problem that arises in transportation planning in modern cities. It includes the de nition of bus lines layouts in an urban area while enhancing some desired criteria.

2. Related work

The Bus Transit Network Design Problem (TNDP) has been addressed in several works in the related literature. A recent review of the topic was performed by Ibarra et al. [ 1 ]. Among the diverse authors that used mathematical programming to deal with this problem, it is relevant the work performed by Cancela et al. [ 6 ], who revised di erent formulations from the literature and proposed a new one that modelled the waiting time of users and the behaviour of users when multiple lines are available. Wan and Lo [ 7 ] proposed a formulation that minimizes the cost of the operator company considering the capacity of the bus. Szeto and Jiang [ 8 ] have proposed a bi-level formulation. The upper level determines the routes path and bus frequencies with the objective of minimizing the number of transfers subjected to constraints on the maximum number of routes, eet size, minimum frequency and enough line capacity. In the second level, the model proposed in Spiess and Florian [ 9 ] that applies strategies to improve the travel time is used. However, the improvements over the travel time in this second level are limited by the decisions taken on the rst level [ 6 ]. More recently, Liang et al. [ 10 ] proposed a two-step model framework to design the bus transit network. Firstly, a column generation method is applied to identify the candidate set of path of the buses lines. Then, they used stochastic linear programming to optimize the bus frequency considering uncertain demand and travel times.

In last decade, with the rise of environmental awareness, societies have started to require public transport systems that are not only economically e cient and respond to the transport needs of citizens but also that they are environmentally sustainable [ 2 ]. In this line, Duran et al. [ 5 ] have proposed a mathematical model for the TNDP which simultaneously considers the minimization of travel time and CO2 emissions. Articles from our group also studied the paradigm of sustainable mobility and speci c case studies in Montevideo, addressing the characterization of recent sustainable initiatives developed for the public transportation of Montevideo, Uruguay [ 4 ]. In turn, recommendations based on a speci c analysis of quantitative (e.g., coverage, accessibility, a ordability) and qualitative (e.g., public nance, integration, comfort and pleasure) were proposed for the development of sustainable mobility in Parque Rodo neighborhood [ 11 ]. The design of an optimized backbone for the public transportation network (i.e., using light railway trams) considering combinatorial optimization approaches was analyzed in Risso and Nesmachnow [ 12 ]. The approach integrated real demands, travel and waiting times, and deployment costs, to provide a proper design for sustainable mobility in Montevideo, to improve quality of service. Data analysis plays a major role to characterize the mobility needs and the current reality, and it has been a subject of study by applying urban informatic approaches [ 13 ].

According to the World Health Organization, air pollution is a signi cant-top health hazard in the cities due to its impact on the citizens' health [14, 15]. Understanding the phenomena that have implications for the production and dissipation of air pollutants has attracted the interest of the scienti c community [16]. Thus, there is an important eld of research on modelling and forecasting ambient air pollution [17, 18]. Physics-based approaches have been applied to address air pollution modeling [19]. However, these methods are computationally expensive. During the last years, with the rapid development of arti cial neural networks and deep learning and their successful use for forecasting applications, several researchers have proposed them to deal with air outdoor pollution modelling, prediction, and forecasting [20, 21]. Most of these methods predict the air pollution concentration giving the previous pollution concentration and other external conditions, such as the weather. It has been shown that Urban road mobility a ects air quality [22, 23]. Thus, di erent approaches based on ANNs model the air pollution according to the current road tra c density [24].

This article introduces a new mathematical formulation that aims at de ning a bus network considering the simultaneous maximization of the number of passengers and minimization of the total travel time and the pollution generated. The formulation is solved by means of an exact solver. As far as we are concerned, these three objectives have not been simultaneously considered in an exact resolution for the TNDP. For the sake of comparison with the exact solver, we also present a fast heuristic approach. In this initial work, we predict the pollution generated considering the population density and the type of bus (electric, hybrid or diesel). In future approaches, as TNDP impacts the overall road tra c, it is expected to used the aforementioned ANNs models based on the road tra c density as we implemented in Jamal et al. [25].

3. Mathematical formulation

The TNDP is addressed with a mixed-integer programming model. This model aims at optimizing three di erent objectives: minimizing the travel time, minimizing the pollution generated by the buses and maximizing the number of passengers served by the buses. The network is designed as a set of paths for each bus from a starting node up to the end node. It is assumed that the bus return through the same path, a simpli ed idea that has been used in the related literature [ 7 ]. In this model, the capacity of buses is not considered, since it is supposed to be adjusted in a posterior decision-making process when considering the frequencies setting of buses lines [ 1, 26 ]. Thus, a bus line captures all the demand of the neighbourhoods that it connects. In this model, the neighbourhoods coincide with the administrative divisions of the city (census segments). Thus, the model considers the following sets: a set of ordered buses K = (k0 : : : ke; ke+1 : : : ke+h; ke+h+1 : : : ke+h+d), where the rst e buses are electric buses, the following h are hybrid buses and the nal d buses are diesel buses; a set of census segments (hereafter segments) I = i0 : : : ijIj .

Given a set of segments, a speci c notation is used for the set of edges between adjacent segments: A( ), such that: A(I) = f(i; j)ji 2 I; j 2 I; i 6= j; i 2 NI (j); j 2 NI (i)g where NI (i) represents the subset of neighbors of segment i among the segments of set I. Additionally, superset Isg = I [ is [ ig is de ned, where is is the base from which buses start their paths and ig is the terminal from which buses end their forward trip and start their return trip.

The parameters of the proposed model are: wk, the pollution generated by the bus k on i segment i; pij , the estimated demand (number of passengers) that are willing to travel from segment i to j; tij , the travel time going from segment i to j; and T Lk maximum travel time of bus k. All variables are binary: xikj indicates if bus k does the trip between arc (i; j) 2 A(I), yij k indicates if bus k does the trip between nodes i and j, and fij indicates if any bus does the trip between nodes i and j. The problem proposes nding a set of layout functions Xk = fxij g stating k for each bus the path that simultaneously maximizes the passengers served by the network and minimizes the travel time of the used buses and the generated pollution.

minimize

T T = maximize minimize

P = subject to

X

X ij2A(Isg) k2K

xikj (tij + tji)

X i2NI (j)

X j2NI (i) D = X

X (fij (pij + pji)) ij2Isg k2K

X

X ij2A(Isg) k2K

k k wj xij xikj =

X i2NI (j) xikj = 1; 8 k 2 K; i 2 Is xjki; 8 k 2 K; j 2 I (1a) (1b) (1c) (1d) (1e) tij xikj

k tjixij ij2A(I)

X ij2A(I)

X j2NI (ig)

X j2NIsg (j)

X j2NIsg (m) X yim

k k2K x; f 2 B 0

k xij

k xjm

T Lk; 8 k 2 K

T Lk; 8 k 2 K k xjig =

X xiksj ; 8 k 2 K NI (is) yikm; 8 k 2 K; i; m 2 Isg; i 6= m

yikm; 8 k 2 K; i; m 2 Isg; i 6= m fim; 8 i; m 2 Isg; i 6= m y 1 (1f) (1g) (1h) (1i) (1j) (1k)

Equations (1a) and (1b) are the total travel time and the number of passengers served by the buses, respectively, considering the contribution of both directions of traversed arc since the bus is supposed to travel the same trip in the return path. Eq. (1c) is the estimated generated pollution by buses. Regarding constraints, Eq. (1d) establishes that if a bus enters a node, it has to leave it. Eq. (1e) sets that at most one segment can be visited once by each bus. Equations (1f) and (1g) limit the maximum travel time of each bus in the forward and return trip. Equations (1i){(1k) establish that fim is one if an only if neighborhoods i and m are visited by the same bus. Eq. (1h) enforces that if a bus has departed from the starting node, it reaches the ending point. Due to the mathematical structure of the model, the binary nature of variable y can be relaxed{i.e, to a real value in [ 0,1 ]{without a ecting the validity of the model.

4. Experimental evaluation

The proposed model was validated on two problem scenarios from Montevideo, Uruguay, de ned over zones including one hundred census segments of the city, each. The two zones are depicted in Figure 1: the red scenario is located near downtown and has densely populated small segments; the yellow scenario is located in a peripheral zone of the city, where segments are relatively large. The red scenario considers three buses: one electric, one hybrid, and one diesel, and yellow scenarios consider ve buses: two electric, one hybrid, and two diesel. Passengers demand between segments was retrieved from a public database of origin/destination of trips in Montevideo [27, 28]. The pollution generated by a bus on a segment is estimated considering two aspects: the type of bus, i.e., if it is electric, hybrid or diesel, and the population density of the segment. Travel times were measured using the method proposed by Vazquez for OSRM [29].

Ten di erent instances were solved for each scenario. Three instances correspond to singleobjective versions of the problem presented in Section 3: SO-TT considers only the optimization problem of Eq. (1a), SO-P considers the optimization problem of Eq. (1b) and SO-D considers the optimization problem of Eq. (1c). In turn, seven instances consider the multiobjective problem, using the weighting sum approach [30], in which the sum is normalized using the single-objective results as in our previous work [31]. Seven di erent weight vectors of the form (wT T ,wP ,wD) were used (wT T , wP , and wD are the respective weights assigned to Eq. 1a, Eq. 1b, and Eq. 1c in the multiobjective weighted sum). The rst three correspond to highly biased instances in which the weight of one of the objectives is much larger than the others. Thus, MO-TT* instance uses (0.98,0.01,0.01), MO-D* uses (0.01,0.98,0.01) and MO-P* uses (0.01,0.01,0.98). The other four multiobjective instances aim at computing more balanced compromise solutions. MO-TT instance uses (0.6,0.2,0.2), MO-P uses (0.2,0.6,0.2), MO-D uses (0.2,0.2,0.6), and MO-CS uses (0.33,0.33,0.33).

In turn, a fast heuristic (FH) procedure is proposed as a baseline for comparing exact solutions computed by the proposed model. FH solves a simpli ed version of the model presented in Section 3. The schema of FH is outlined in Algorithm 1. The objective function minimizes the impedance of the used arcs, which is calculated as a random weighted sum of the normalized travel time of the arc and the pollution generated at the destination segment. The impedance function is optimized within a simpli ed linear programming model SP only considering constraints Eqs. (1d)-(1h).

Algorithm 1 Global procedure of the fast heuristic FH . Gets the maximum travel time . Gets the minimum travel time

. For each bus . Gets the maximum pollution generation . Gets the minimum pollution generation . For each edge in the adjacency matrix . Build impedance matrix 8: 9: 10: 11: 12: 13: 1: procedure Heuristic(I; K; wki; tij ) 2: maxt max(tij ) 3: mint min(tij ) 4: maxwk ; minwk 0 5: for k 0; k + +; k K do 6: maxw :append(max(wki[k])); 7: minw :append(min(wki[k]))

Create impedance matrix imp for each (i; j) 2 A(I) do for k 0; k + +; k K do

random(0; 1) impij tmija[ix;tj] mmiinntt (1 ) Solve SP with cost

P(i;j)2A(I) impij wki[k;j] minw[k] maxw[k] minw[k]

k xij

Solutions were obtained using Pyomo [32] as the modelling language and Gurobi [33] as the exact solver. The experimental analysis was performed on a computer with Intel Processor i7-4790 CPU @3.60GHz and 32GB RAM, using a time limit of 2400 seconds for the solver.

Table 1 presents the experimental results. For each instance the Table reports: the value of each objective (TT, P, and D ); the deviation from the ideal solution , computed as the distance to the ideal solution with the L2 norm (Equation 2, where O = fT T; P; Dg is the set of objectives and besto and worsto are the best and worst value achieved for each objective); the computing time in seconds; and the optimality gap estimated by Gurobi gapG. For the FH heuristic gapG is not reported, since the solution is not obtained by an exact approach. v u uX t o2O value worsto besto besto 100% 2 Instance

T T

P

D time (s)

gapG yellow scenario (2) SO-TT SO-P SO-D MO-TT* MO-P* MO-D* MO-TT MO-P MO-D MO-CS FH SO-TT SO-P SO-D MO-TT* MO-P* MO-D* MO-TT MO-P MO-D MO-CS FH

Results in Table 1 show that the proposed model was able to obtain a set of solutions with di erent trade-o among the optimization criteria. In the case of the yellow scenario, the instance with the smallest deviation was MO-TT* (108.11%); in the red scenario, it was MO-D (88.40%). The instance with the largest deviation was SO-D (200% percentage deviation) in both cases. Regarding the heuristic procedure (FH), it was able to compute good compromising solutions, since the overall deviation is not far from the instance with the smallest deviation: about 16.94% (compared to MO-TT*) in the yellow scenario and 32.76% (compared to MO-D) in the red scenario.

Another important outcome of the experimentation is the impact that the number of relevant integer variables of the model has on the resolution e ciency. Related to this issue, the increment in the integer variables is usually negatively correlated to the computational complexity of the problem [34]. In line with this concept, SO-TT and SO-P{in which the objective function Eq. (1c) is not involved and, thus, Eqs. (1i)- (1k) (and integer variable f ) become irrelevant since they are not part of the optimization criteria{are easily solved by Gurobi. On the other hand, in all the time-consuming instances (those for which the time limit is reached without obtaining the optimal solution and those for which no solution is found) Eq. (1c) is included. In these cases, Eqs. (1i)- (1k) (and integer variable f ) become relevant for the optimization process{since they participate in the objective function{and, thus, the problem has a larger number of relevant integer variables.

5. Discussion and future work

The Bus Transit Network Design Problem arises in the context of public bus transportation in modern cities and basically consists in the de nition of buses lines layouts in an urban area while aiming at enhancing some desired criteria. In this article, a novel multiobjective mathematical formulation is presented for this problem which simultaneously optimizes two traditional objectives, i.e., the number of passengers that are served by the network and the total travel time of the buses, and a less conventional objective related to the pollution generation of the network. This model was solved with exact and heuristic procedures for two realistic scenarios of Montevideo city, Uruguay, obtaining di erent compromising solutions that allow exploring the trade-o among the objectives.

The main lines for future research include the application of more advanced exact multiobjective approaches for the exact resolution, such as augmented "-constraint method. Another feature that will be addressed to enhance the model is to consider uncertainty in the pollution generation since this parameter can be a ected by several elements (e.g., the season of the year, the weather and tra c conditions, economic activities that are performed in the segment, and buildings skyline a ecting air circulation). In this sense, we are developing a model based on arti cial neural networks to estimate more accurately the pollution generation of a bus that transits a certain area of the city. This network will be trained with data gathered by air-quality monitors displaced in Montevideo.

Acknowledgements This research was partially funded by European Union's Horizon 2020 research and innovation program under the Marie Sklodowska-Curie grant agreement No 799078, by the European Union H2020-ICT-20193 and UMA18-FEDERJA-003, and the Systems that Learn Initiative at MIT CSAIL. [14] World Health Organization 2018 Ambient (outdoor) air quality and health https://www.who.int/en/news-room/fact-sheets/detail/ambient-(outdoor)-air-quality-and-health Accessed: 2019-07-07 [15] Lebrusan I and Toutouh J 2020 Air Quality, Atmosphere & Health 14(3) 333{342 [16] Jorquera H, Montoya L D and Rojas N Y 2019 Urban Air Pollution (Cham: Springer International

Publishing) pp 137{165 [17] Venkatram A 2015 Lectures on air pollution modeling (Springer) [18] Zannetti P 2013 Air pollution modeling: theories, computational methods and available software (Springer

Science & Business Media) [19] Chuang M T, Zhang Y and Kang D 2011 Atmospheric environment 45 6241{6250 [20] Cabaneros S M, Calautit J K and Hughes B R 2019 Environmental Modelling & Software 119 285{304 [21] Toutouh J, Lebrusan I and Nesmachnow S 2020 International Conference on Optimization and Learning (Springer) pp 115{127 [22] Lebrusan I and Toutouh J 2019 Ibero-American Congress on Information Management and Big Data (Springer) pp 9{24 [23] Lebrusan I and Toutouh J 2020 Smart Cities 3 456{478 [24] Toutouh J 2021 Smart Cities ed Nesmachnow S and Hernandez Callejo L (Cham: Springer International

Publishing) pp 90{105 ISBN 978-3-030-69136-3 [25] Toutouh J, Nesmachnow S and Rossit D G 2020 1st International Workshop on Advanced Information and

Computation Technologies and Systems (AICTS) (Irkutsk, Russia) [26] Nesmachnow S, Muran~a J and Risso C 2020 Smart Cities (Communications in Computer and Information

Science vol 1359) (Springer International Publishing) pp 183{198 [27] Massobrio R and Nesmachnow S 2020 Applied Sciences 10 1{20 [28] Massobrio R Origin-destination transport matrices of the city of Montevideo, Uruguay https://www.fing.edu.uy/ renzom/msc/od-matrices.md Accessed: 2020-11-26 [29] Vazquez Brust A 2018 Rpubs by RStudio https://rpubs.com/HAVB/osrm [30] Zadeh L 1963 IEEE transactions on Automatic Control 8 59{60 [31] Rossit D G, Toutouh J and Nesmachnow S 2020 Waste Management 105 467{481 [32] Hart W E, Laird C D, Watson J P, Woodru D L, Hackebeil G A, Nicholson B L and Siirola J D 2017

Pyomo{optimization modeling in python 2nd ed vol 67 (Springer Science & Business Media) [33] Gurobi Optimization L 2021 Gurobi optimizer reference manual URL http://www.gurobi.com [34] Glover F 1984 Journal of Information and Optimization Sciences 5 69{71

References

[1] Ibarra-Rojas O J , Delgado F , Giesen R and Mun~ oz J C 2015 Transportation Research Part B : Methodological 77 38 { 75

[2] Miller P , de Barros A G , Kattan L and Wirasinghe S 2016 KSCE Journal of Civil Engineering 20 1076 { 1083

[3] Reisi M , Aye L , Rajabifard A and Ngo T 2014 Ecological Indicators 43 288 { 296

[4] Hipogrosso S and Nesmachnow S 2019 Communications in Computer and Information Science 1152 93 { 108

[5] Duran J , Pradenas L and Parada V 2019 Public Transport 11 189 { 210

[6] Cancela H , Mauttone A and Urquhart M E 2015 Transportation Research Part B : Methodological 77 17 { 37

[7] Wan Q K and Lo H K 2003 Journal of Mathematical Modelling and Algorithms 2 299 { 308

[8] Szeto W Y and Jiang Y 2014 Transportation Research Part B : Methodological 67 235 { 263

[9] Spiess H and Florian M 1989 Transportation Research Part B : Methodological 23 83 { 102

[10] Liang J , Wu J , Gao Z , Sun H , Yang X and Lo H K 2019 Transportation Research Part B : Methodological 126 115 { 138

[11] Hipogrosso S and Nesmachnow S 2020 Smart Cities 3 479 { 510

[12] Risso C and Nesmachnow S 2020 Smart Cities pp 228 { 243

[13] Nesmachnow S , Ban~a S and Massobrio R 2017 EAI Endorsed Transactions on Smart Cities 2 153478