# Hybrid Differential Evolution-Particle Swarm Optimization Algorithm for Multiobjective Urban Transit Network Design Problem with Homogeneous Buses

Authors: Ahmed Tarajo Buba; Lai Soon Lee
Journal: Mathematical Problems in Engineering
 (2019)

---

## Abstract

This paper considers an urban transit network design problem (UTNDP) that deals with construction of an efficient set of transit routes and associated service frequencies on an existing road network. The UTNDP is an NP-hard problem, characterized by a huge search space, multiobjective nature, and multiple constraints in which the evaluation of candidate route sets can be both time consuming and challenging. This paper proposes a hybrid differential evolution with particle swarm optimization (DE-PSO) algorithm to solve the UTNDP, aiming to simultaneously optimize route configuration and service frequency with specific objectives in minimizing both the passengers’ and operators’ costs. Computational experiments are conducted based on the well-known benchmark data of Mandl’s Swiss network and a large dataset of the public transport system of Rivera City, Northern Uruguay. The computational results of the proposed hybrid algorithm improve over the benchmark obtained in most of the previous studies. From the perspective of multiobjective optimization, the proposed hybrid algorithm is able to produce a diverse set of nondominated solutions, given the passengers’ and operators’ costs are conflicting objectives.


---

## Body

## 1. Introduction

The rapid growth of many cities in the world as a result of urbanization as well as concern over the environment impact requires systematic planning to address the corresponding increase in travel demand, pollution, and energy consumption. The solution to these problems is to utilize an efficient public transport system. Adequately designed transit network with appropriate vehicle frequency is capable of raising the utilization of the public transportation system, as well as reducing the overall system costs.Urban transit network design problem (UTNDP) consists of determining route networks and schedules of an urban public transport system [1]. Ceder and Wilson [2] decomposed the UTNDP into a sequence of five activities: network design, frequency setting, time table development, bus scheduling, and driver scheduling. Because of its combinatorial complexity, multiobjective nature, use of assignment submodel, and spatial route layout, solving the UTNDP becomes more complex and time consuming [3, 4]. Most of the research efforts attempted to treat each of the activities in a sequential manner.Solving the UTNDP requires several criteria to be considered to efficiently account for the quality of service offered to the passengers while at the same time reducing the cost of running the service. For instance, the passengers would prefer cheap, fast, and reliable services, while the operators need to consider the cost of running the services [1]. Hence, the different viewpoints of passengers and operators can result in different criteria for evaluating efficiency. Specifically, the UTNDP involves several conflicting objectives, such as the total passenger travel time and the number of vehicles required to operate the routes. Because of the complex nature of the components of the transit travel time, comprising in-vehicle travel time, waiting time, transfer time, and transfer penalties, to optimize the transit networks has been a challenging task [5].With the improvement in search algorithms and computing technology, a variety of metaheuristic approaches have been utilized to tackle the UTNDP. Apart from solution methods using sole algorithms, Farahani et al. [6] noted that solution methods can also be developed for new and existing network design problems based on hybrids of different metaheuristics. In addition, the combination of two powerful search algorithms has been considered by several authors to achieve better quality results, particularly when one algorithm complements the other (see [7–8]).Recent studies on UTNDP focus primarily on metaheuristics as a result of high-quality solutions produced and computational performance. All the researchers in the UTNDP literature have attempted to calibrate their studies either on real-life or theoretical networks. Several authors employed a genetic algorithm (GA) with diverse formulations and coding schemes with the objective to optimize either the passenger or operator cost or both. In particular, Ngamchai and Lovell [10] and Fan and Machemehl [11] utilized a GA on theoretical networks, while Arbex and da Cunha [12] experimented on Mandl’s Swiss network. Furthermore, Gundaliya et al. [13] and Tom and Mohan [14] studied medium-size network in Chennai, India, while Amiripour et al. [15] studied a network in Iran. More recently, Owais and Osman [16] experimented a GA on a transportation network in Rivera City, Northern Uruguay.Over the last decade, other metaheuristic approaches such as particle swarm optimization (PSO), bee colony optimization (BCO), and differential evolution (DE) are also applied to solve the UTNDP. Blum and Mathew [17] developed an intelligent agent optimization system for the UTNDP. Bagherian et al. [18] formulated a mixed integer model and applied a discrete PSO to determine the optimal bus lines. Kechagiopoulos and Beligiannis [19] developed a PSO for tackling the urban transit routing problem (UTRP). Nikolić and Teodorović [20] developed an efficient algorithm based on BCO for UTNDP. Zhao et al. [21] proposed a mimetic algorithm (MA) to solve the urban transit network. Buba and Lee [22] proposed a DE for UTRP. Buba and Lee [23] proposed a DE to solve the UTNDP by simultaneously determining the transit network configuration and the associated frequency of service. These studies experimented on the benchmark Mandl’s Swiss network and have been extensively reviewed in Buba and Lee [23]. Ruano-Daza et al. [24] studied a transit network design and frequency-setting problem in the context of bus rapid transit system (BRTS) using a global-best harmony search coupled with a simulation model for discrete events. In the bilevel multiobjective approach, the external level handled the problem of selection of the best transit route configurations, while the internal level selected the best frequencies generated by the first level. The proposed approach is applied to a real-life BRTS of the city of Pereira, Columbia. Most recently, Jha et al. [25] studied the transit network design and frequency-setting problem for public buses. The authors used a multiobjective PSO with a number of search strategies to tackle the problem. The proposed algorithm has also experimented on the benchmark Mandl’s Swiss network.Furthermore, Canca et al. [26] formulated an optimization model that addresses the integrated network design, line planning, and fleet investment. Later, in 2017, Canca et al. [27] formulated a model to solve the integrated rail rapid transit network design and line planning problem. An adaptive large neighborhood search metaheuristic is used to tackle the network design and line planning problems simultaneously. López-Ramos et al. [28] proposed an optimization-based approach to simultaneously solve the network design and the frequency-setting phase in the context of railway rapid transit networks. A combined lexicographic goal programming technique and a line splitting algorithm is used to solve the model. Gutiérrez-Jarpa et al. [29] investigated the rapid transit network design with modal competition in the case of a real city through a multiobjective mathematical model for a rapid transit network at a strategic level. In addition, an approach that can address modal competition for realistic size instances is also presented by the authors.Over the decades, the hybridization approaches for UTNDP are gaining attention from the researchers. Zhao and Zeng [7] applied a hybrid SA-GA algorithm to optimize the transit route network design problem. Subsequently, Zhao and Zeng [30] extended their method to determine the public transport network layout and headways. Liu et al. [8] proposed a hybrid SA-GA strategy to solve the problem of bus route design and frequency setting. Szeto and Wu [9] proposed a hybrid approach to solve a transit network design problem for a suburban residential area in Hong Kong. Szeto and Jiang [31] proposed a model for solving UTNDP with the objective of minimizing the weighted sum of the number of transfers and the total travel time of users through a hybrid enhanced artificial BCO. Later, in 2014, Szeto and Jiang [32] developed a hybrid artificial BCO to solve a bilevel UTNDP where transit route design and frequency settings are determined simultaneously.In this paper, we consider the UTNDP aiming to determine a set of transit routes with associated service frequencies simultaneously for transit networks with homogeneous buses, with the objective of minimizing the conflicting interests of passengers and operators. There are a few research efforts that have used the hybrid differential evolution with particle swarm optimization (DE-PSO) to solve a range of continuous optimization problems (see [33–35]). However, to the best of our knowledge, no such research has been reported in the UTNDP literature. Hence, the main motivation is to propose a hybrid DE-PSO to solve effectively and efficiently the UTNDP. The proposed hybrid algorithm is an extension from our previous study [23], which is designed to adapt the strength of both the approaches in solving the discrete problem aiming to achieve better quality results.The remainder of the paper is organized as follows: the problem formulation is presented in Section2, while the details of the proposed hybrid DE-PSO framework for UTNDP is described in Section 3, followed by the experimental design in Section 4. Comparisons of results are presented in Section 5. Lastly, conclusions and future research are addressed in Section 6.


## 2. Problem Formulation

The problem considered in this article comprised two sequences of activities: (i) bus network design and (ii) frequency setting. The network design aspect consists of constructing a feasible set of transit routes on a given urban road network with predetermined stop points purposely to achieve an efficient transit network that optimizes passengers’ total travel time as well as the operator cost. The frequency setting aspect involves assigning service frequencies to transit routes so that several parameters including waiting times, flow capacities for transit routes, and the fleet size required for overall network operation are established.The UTNDP is modeled as a multiobjective optimization problem so that an efficient set of transit routes and the associated frequencies are established that simultaneously produce a minimum total passenger and operator costs while all the requirements and constraints are being satisfied. In a real-life scenario, a number of constraints need to be included in the formulation such as bus line feasibility, bus capacity, and fleet size. The same design approach in Nikolić and Teodorović [20]; and Zhao et al. [21] is considered in this study. The problem can be defined as follows.LetG=V,E be a weighted graph representing the candidate transportation network with vertex set V (demand points) and edge set E (street segment). E is the set of feasible edges (i,j∈E) that links the vertices and P⊆i,j∈V×V:i≠j satisfying origin-destination (OD) pairs. Each edge is linked to a pair of vertices i,j, where i is the source and j is the sink of the edge. A symmetric matric of passenger travel demand and overall travel time associated with each OD pair i,j∈P are known. Consequently, G should be connected to enable passengers to traverse the path between node i and node j through an undirected path in G. The optimization model is as follows:(1)minCp=∑i∈N∑j∈Ntinv,ij+twt,ij+ttr,ijdij+α∑i∈N∑j∈Nudij,(2)Co=12∑rk∈SRvk,(3)subject toLmin≤Lk≤Lmax,∀k∈SR,(4)fk≥fmin,∀k∈SR,(5)ϕkmax=maxϕks,∀k∈SR,(6)2fktk=vk,∀k∈SR,(7)∑kvk≤Vmax,∀k∈SR,(8)trij≤trmax,(9)M≤Mmax,where SR = set of transit routes in a solution to UTNDP; tinv,ij = in-vehicle time for travel from nodes i to j; twt,ij = waiting time for travel from nodes i to j; ttr,ij = transfer time for travel from nodes i to j; dij = demand for travel from nodes i to j; udij = unserved demand for travel from nodes i to j; α = penalty factor of the unserved passengers; rk = transit route/bus line k; vk = fleet size on route k; Lmin = minimum length of a route for travel; Lk = length of route k for travel; Lmax = maximum length of a route for travel; fk = frequency of buses plying on route k ; fmin = minimum allowable frequency of buses operating on a route; ∅kmax = maximum flow occurring on any link of route k ; ∅ks = flows on the critical link of route k ; tk = round trip time on route k ; Vmax = fleet size available for operation on the route network; trij = number of transfers for travel from nodes i to j; trmax = maximum allowable transfer; M = number of routes in the given route set; Mmax = maximum number of routes allowed in a given solution; N = number of nodes in the route set (graph size).The objective functions (equation (1)) represent generalized passenger cost, Cp, in terms of total travel time of all passengers plus the unmet demand, whereas equation (2) is the operator cost, Co, (total fleet size), respectively. Constraint (3) provides the lower and upper limits of the route length in a given solution. Constraint (4) ensures that service frequency should not be lower than the minimum value. Constraint (5) limits the maximal flows on the critical link of transit routes. Constraint (6) defines the relationship between fleet sizes and frequencies of transit routes. Constraint (7) ensures that the sum of fleet size does not exceed the maximum allowable value from the operators’ point of view. Constraint (8) restricts the number of transfers to be below a given maximum value. Lastly, constraint (9) restricts the maximal number of routes from the operator’s perspective.


### 2.1. Decision Variables and Input Data

The decision variables considered in the proposed model can be categorized as either continuous or integer variable. The continuous variables include the travel time between nodesi and j; tij, in-vehicle travel time between nodes i and j; tinv,ij, waiting time between nodes i and j; twt,ij, transfer time between nodes i and j; and ttr,ij, round trip time of route k, tk. On the other hand, the integer variables include the frequency of the route k; fk, the number of vehicles to be assigned to route k; vk, length of route k; and Dk, the maximum flow occurring on the route k, ∅kmax.The same input data of the UTNDP used by the previous approaches in the literature are utilized in this study. There comprises (i) the road network structure available for the vehicle routes including the designation of nodes and the available edges in the network, (ii) the travel times of each edge in the network indicating how long it takes for a vehicle to travel between any two nodes of the road network, (iii) travel demand by transit between every O-D pair (origin-destination matrix), and (iv) the design parameters that include penalty per transfer, the minimum frequencies of bus service on each route, the bus seating capacity (assumed all buses are homogeneous in terms of seating capacity), and the maximum load factor allowed on any transit routes [23].


### 2.2. Passenger Assignment

When the transit route networks are constructed, the passengers travel demand should be distributed on the candidate routes to evaluate the fitness of the vector/particle as explained in Section3.3. We [23] have described in detail how to determine the flow of passengers on paths selected by the passengers for every OD pair on the basis of the passenger assignment procedure in Baaj and Mahmassani [3]. We also assume that transit users can use a maximum of two bus lines to get to their destination (i.e., at most one transfer) similar to Mauttone and Urquhart [36]; Yan et al. [37]; and Nikolić and Teodorović [20]. The passenger assignment is briefly performed as follows:(i)
The passengers look for a direct route (i.e., a route without transfer) that would serve a given pair of OD nodes.(ii)
If direct route(s) is/are located, then the routes are screened on the basis of in-vehicle travel time such that any route with in-vehicle travel time greater than the smallest value by 50% is avoided.(iii)
The demand is shared with the candidate routes that scale through the screening process.(iv)
However, if it is not possible to find the direct route(s), the passengers will then try to look for a set of one transfer routes with the smallest travel time to meet the travel demand.(v)
If one transfer route(s) is/are found, then the total travel time is evaluated for each possible path involving one transfer, and a screening process is invoked to determine the candidate paths similar to the zero transfer, in such a way that, all paths between OD pair whose total travel time is greater than the smallest value produced by any path by more than 10% are also avoided.(vi)
If it is not possible to find any path, then the demand is regarded as unserved.We assign randomly the initial service frequencies of all routes in the solution taking into account that the least frequency of service allowed on any route is one vehicle per hour. After the first iteration, frequencies are updated and demand is allocated. The iteration process is repeated until the stopping criterion is met: (i) a fixed number of iterations, (ii) the system converges to a solution [17], or (iii) no significant improvement in frequencies attained. Consequently, the four basic properties associated with a given route are determined: nodes list, service frequency, turnaround trip times, and link-flows list [23].


### 2.3. Bus Line Characteristics and Travel Time Calculation

It is essential to calculate the values of basic quantities (frequency of service, required number of buses, bus headway, etc.) that is associated with any considered solution after performing the passenger assignment (Section3.3). These parameters can be expressed mathematically. The same mathematical expressions as in [23] are adopted in this study. Additionally, we included the following equations (equation (10)–(13)) to calculate the values of the maximum and average route headways.The passenger waiting time:(10)twt=12h=T2∑kfk,where h is the bus headway at route kThe bus headway at the routek:(11)hk=Tfk.Maximum route headway:(12)hmax=maxTf1,…,Tfk.Average route headway:(13)Ave⋅h=∑khkM,where ∑khk is the total route headway.


## 2.1. Decision Variables and Input Data

The decision variables considered in the proposed model can be categorized as either continuous or integer variable. The continuous variables include the travel time between nodesi and j; tij, in-vehicle travel time between nodes i and j; tinv,ij, waiting time between nodes i and j; twt,ij, transfer time between nodes i and j; and ttr,ij, round trip time of route k, tk. On the other hand, the integer variables include the frequency of the route k; fk, the number of vehicles to be assigned to route k; vk, length of route k; and Dk, the maximum flow occurring on the route k, ∅kmax.The same input data of the UTNDP used by the previous approaches in the literature are utilized in this study. There comprises (i) the road network structure available for the vehicle routes including the designation of nodes and the available edges in the network, (ii) the travel times of each edge in the network indicating how long it takes for a vehicle to travel between any two nodes of the road network, (iii) travel demand by transit between every O-D pair (origin-destination matrix), and (iv) the design parameters that include penalty per transfer, the minimum frequencies of bus service on each route, the bus seating capacity (assumed all buses are homogeneous in terms of seating capacity), and the maximum load factor allowed on any transit routes [23].


## 2.2. Passenger Assignment

When the transit route networks are constructed, the passengers travel demand should be distributed on the candidate routes to evaluate the fitness of the vector/particle as explained in Section3.3. We [23] have described in detail how to determine the flow of passengers on paths selected by the passengers for every OD pair on the basis of the passenger assignment procedure in Baaj and Mahmassani [3]. We also assume that transit users can use a maximum of two bus lines to get to their destination (i.e., at most one transfer) similar to Mauttone and Urquhart [36]; Yan et al. [37]; and Nikolić and Teodorović [20]. The passenger assignment is briefly performed as follows:(i)
The passengers look for a direct route (i.e., a route without transfer) that would serve a given pair of OD nodes.(ii)
If direct route(s) is/are located, then the routes are screened on the basis of in-vehicle travel time such that any route with in-vehicle travel time greater than the smallest value by 50% is avoided.(iii)
The demand is shared with the candidate routes that scale through the screening process.(iv)
However, if it is not possible to find the direct route(s), the passengers will then try to look for a set of one transfer routes with the smallest travel time to meet the travel demand.(v)
If one transfer route(s) is/are found, then the total travel time is evaluated for each possible path involving one transfer, and a screening process is invoked to determine the candidate paths similar to the zero transfer, in such a way that, all paths between OD pair whose total travel time is greater than the smallest value produced by any path by more than 10% are also avoided.(vi)
If it is not possible to find any path, then the demand is regarded as unserved.We assign randomly the initial service frequencies of all routes in the solution taking into account that the least frequency of service allowed on any route is one vehicle per hour. After the first iteration, frequencies are updated and demand is allocated. The iteration process is repeated until the stopping criterion is met: (i) a fixed number of iterations, (ii) the system converges to a solution [17], or (iii) no significant improvement in frequencies attained. Consequently, the four basic properties associated with a given route are determined: nodes list, service frequency, turnaround trip times, and link-flows list [23].


## 2.3. Bus Line Characteristics and Travel Time Calculation

It is essential to calculate the values of basic quantities (frequency of service, required number of buses, bus headway, etc.) that is associated with any considered solution after performing the passenger assignment (Section3.3). These parameters can be expressed mathematically. The same mathematical expressions as in [23] are adopted in this study. Additionally, we included the following equations (equation (10)–(13)) to calculate the values of the maximum and average route headways.The passenger waiting time:(10)twt=12h=T2∑kfk,where h is the bus headway at route kThe bus headway at the routek:(11)hk=Tfk.Maximum route headway:(12)hmax=maxTf1,…,Tfk.Average route headway:(13)Ave⋅h=∑khkM,where ∑khk is the total route headway.


## 3. Hybrid DE—PSO for the UTNDP

### 3.1. Representation

Each vector (in DE) or particle (in PSO) is a candidate route set from the given transit network configuration. A list data structure is used to represent the vectors (particles) as shown in Figure1, which are the permutations of the m transit lines with m transit routes and their associated frequencies. A transit line k,1,2,…,m comprises an adjacent sequence of transit nodes stored in a transit route list, rk, and its associated frequency, fk, stored in a sublist rk,fk. A separator “∗” is used to demarcate the set of transit lines. These frequencies are randomly initialized to individual routes of every vector/particle of the population (see [23]. For example, Figure 1, shows that route 1 has a service frequency of 5 vehicles per hour, while route 2 has a service frequency of 4 vehicles per hour in the sublist, etc.Figure 1
A sample vector/particle.


### 3.2. Initialization

The route construction heuristic proposed by Mumford [38] is utilized to generate the initial population of vectors/particles. In this heuristic algorithm, several parameters need to be defined: (i) the number of routes per route set to be predefined by the user (i) the minimum and maximum length of individual routes, and (iii) the population size of the route sets. In the UTNDP, at least two routes emanating from a list of nodes should constitute a complete route set. The routes are constructed one at a time with vertices added one after the other. However, we observe that the construction heuristic does not always produce feasible route sets (i.e. not all the nodes are connected). Hence, we [22] recently proposed an improved subroute reversal repair mechanism (iSRR) to deal with the infeasible route sets. In the literature, some requirement concerning each typical route of the route set is specified by the operator. For instance, each typical route must contain a minimum of two or three nodes and a predefined number of maximum nodes fora feasible route set. Note that a fixed population size is maintained during the implementation of the proposed algorithm.


### 3.3. Fitness Evaluation

The solution is evaluated when the demand is assigned and the frequency determined through the assignment model (see Section2.2). The objective functions (1) and (2) for an individual vector/particle are considered as the fitness functions. Consequently, the overall passenger cost, as well as the operator cost, could be evaluated to be the fitness value. The passenger cost consisting of two terms in objective function (1) is calculated by summing the travel cost and the unmet demand for every OD pair. The required fleet for each bus line can be obtained from equation (6). Finally, summing the buses of all routes gives the total fleet.


### 3.4. Mutation and Crossover

Two mutation schemes are used in the proposed hybrid algorithm: (i) identical point mutation, which is a modified form of the mutation operator by Ngamchai and Lovell [10] and (ii) mutation operator proposed in Kechagiopoulos and Belligiannis [19]. The identical point mutation is utilized in the DE to create a noisy random vector, Vi,G, as follows: a random node that has at least two identical nodes from the random vector (route set) is selected. Then, two routes that contain the random node are selected and the substrings preceding the random node in the routes interchange their position between the two routes to create a noisy random vector (see Figure 2). The second mutation operator is utilized in the PSO to update the personal and global best of the swarm (see Figure 3). However, in our case, if there is a cycle after the modification of the particle, then the repair is attempted using iSRR. The steps of the mutation are as follows:(i)
Select two routes randomly: one from the particle to be modified and the other from the personal or global best.(ii)
A common node is searched between these pairs of routes.(iii)
If the common node is found, then copy substring (route parts) from the personal or global best between the selected nodes to modify the current particle.(iv)
If a cycle is identified, then repair with iSRR.Figure 2
Identical point mutation.Figure 3
Modified identical point mutation.In the case of no common node being found between the pair of the selected routes, a new pair of routes is selected by the algorithm, again randomly, in an attempt to locate a common node for swapping parts of routes. However, if a candidate node is located, then the process terminates and a new particle is selected from the swarm to undergo modification.The crossover is applicable only to the DE. Specifically, the uniform route crossover (interstring crossover operation) inspired by Beasley et al. [39] is utilized. This crossover is performed as follows: each subroute in the trial vector is generated by interchanging the corresponding subroute either from the target or noisy random vector on the basis of a randomly generated binary crossover mask whose length is equal to the number of routes in the solution. When there is a “1” in the crossover mask, the subroute is copied from the target vector, but when there is a “0” in the mask, the subroute is copied from the noisy random vector. The process is repeated with the target and noisy random vector exchanged to yield the second trial vector (see Figure 4). Note that for each pair of vectors, it is required to generate a new crossover mask [40]. It is advisable to ensure that the trial vectors are feasible; otherwise, attempt to repair the infeasible trial vectors with iSRR.Figure 4
Uniform route crossover.


### 3.5. Replacement

The population for the next generation is constructed through elitism selection for the DE, such that the best vector between thetarget vector and the trial vector is selected for the next generation. This is to maintain the average fitness of the population [41]. For the PSO, the fitness value is updated for the personal and global best, provided the fitness of the current particle is better than the fitness of its personal best and global best after the application of the mutation operator (see Figure 3).The proposed framework of the proposed hybrid DE-PSO is structured as follows: the population (for DE) or swarm (for PSO) is initialized using a construction heuristic proposed by Mumford [38]. The DE algorithm (see Algorithm 1) is run for a finite number of generations, I (e.g., 20) to initialize the swarm for the PSO. The PSO is the main algorithm to search for the optimal solution. Note that it is not appropriate to use the velocity vector of the classical PSO due to the discrete nature of the problem. Instead, a new mutation scheme is utilized to update the personal and global best (see Figure 3). The proposed algorithm will only alternate once, and both of the objective functions will start with the same initial population that has been recorded earlier. At the end of each DE-PSO iteration, the nondominated solution is accumulated and isolated by discarding all the dominated solutions. The detailed framework of the proposed DE-PSO is provided in Algorithm 2.Algorithm 1:DE for multiobjective UTNDP.
(1)
GenerateNp candidate route set using construction heuristic with iSRR repair mechanism
(2)
for i≔1toNp
(3)
fitness evaluation using passenger assignment model
(4)
end for
(5)
for n≔1toG
(6)
for i≔1toNp
(7)
setTarget vector =Xi,n
(8)
select randomly a vector (except the selectedTarget vector, Xi,n) in the population
(9)
apply identical point mutation to generate aNoisy Random vector, Vi,n (repair if infeasible)
(10)
apply uniform route crossover betweenXi,n and Vi,n to generate a pair of Trial vectors, Ui,n (repair if infeasible)
(11)
fitness evaluation ofUi,n using passenger assignment model
(12)
elitism selection
(13)
ifTrial vector fitness ≤ Target vector fitness
(14)
new_populationi  = Trial vector, Ui,n
(15)
else
(16)
new_populationi = Target vector, Xi,n
(17)
end for
(18)
Np= new_population
(19)
end for
(20)
return BESTAlgorithm 2:Hybrid DE-PSO for multiobjective UTNDP.
(1)
Initialize the swarm using DE (Algorithm1)
(2)
for i≔Np
(3)
fitness evaluation using passenger assignment
(4)
fp1,fp2,…,fpn
(5)
Setpg∗=argminfp1,fp2,…,fpn
(6)
end for
(7)
for n≔1toG
(8)
for i≔1toNp
(9)
set current particle = 1st particle in swarm
(10)
select a particle randomly (except the selected 1st particle) in the swarm
(11)
apply particle modification scheme to generate a modified particle (repair if infeasible)
(12)
fitness evaluation using passenger assignment on the modified particle
(13)
if modified particle is better than personal best
(14)
update personal best and its fitness
(15)
else if modified particle is better than global best
(16)
update global best and its fitness
(17)
end if
(18)
end for
(19)
Np= new_population
(20)
end for
(21)
return Best


## 3.1. Representation

Each vector (in DE) or particle (in PSO) is a candidate route set from the given transit network configuration. A list data structure is used to represent the vectors (particles) as shown in Figure1, which are the permutations of the m transit lines with m transit routes and their associated frequencies. A transit line k,1,2,…,m comprises an adjacent sequence of transit nodes stored in a transit route list, rk, and its associated frequency, fk, stored in a sublist rk,fk. A separator “∗” is used to demarcate the set of transit lines. These frequencies are randomly initialized to individual routes of every vector/particle of the population (see [23]. For example, Figure 1, shows that route 1 has a service frequency of 5 vehicles per hour, while route 2 has a service frequency of 4 vehicles per hour in the sublist, etc.Figure 1
A sample vector/particle.


## 3.2. Initialization

The route construction heuristic proposed by Mumford [38] is utilized to generate the initial population of vectors/particles. In this heuristic algorithm, several parameters need to be defined: (i) the number of routes per route set to be predefined by the user (i) the minimum and maximum length of individual routes, and (iii) the population size of the route sets. In the UTNDP, at least two routes emanating from a list of nodes should constitute a complete route set. The routes are constructed one at a time with vertices added one after the other. However, we observe that the construction heuristic does not always produce feasible route sets (i.e. not all the nodes are connected). Hence, we [22] recently proposed an improved subroute reversal repair mechanism (iSRR) to deal with the infeasible route sets. In the literature, some requirement concerning each typical route of the route set is specified by the operator. For instance, each typical route must contain a minimum of two or three nodes and a predefined number of maximum nodes fora feasible route set. Note that a fixed population size is maintained during the implementation of the proposed algorithm.


## 3.3. Fitness Evaluation

The solution is evaluated when the demand is assigned and the frequency determined through the assignment model (see Section2.2). The objective functions (1) and (2) for an individual vector/particle are considered as the fitness functions. Consequently, the overall passenger cost, as well as the operator cost, could be evaluated to be the fitness value. The passenger cost consisting of two terms in objective function (1) is calculated by summing the travel cost and the unmet demand for every OD pair. The required fleet for each bus line can be obtained from equation (6). Finally, summing the buses of all routes gives the total fleet.


## 3.4. Mutation and Crossover

Two mutation schemes are used in the proposed hybrid algorithm: (i) identical point mutation, which is a modified form of the mutation operator by Ngamchai and Lovell [10] and (ii) mutation operator proposed in Kechagiopoulos and Belligiannis [19]. The identical point mutation is utilized in the DE to create a noisy random vector, Vi,G, as follows: a random node that has at least two identical nodes from the random vector (route set) is selected. Then, two routes that contain the random node are selected and the substrings preceding the random node in the routes interchange their position between the two routes to create a noisy random vector (see Figure 2). The second mutation operator is utilized in the PSO to update the personal and global best of the swarm (see Figure 3). However, in our case, if there is a cycle after the modification of the particle, then the repair is attempted using iSRR. The steps of the mutation are as follows:(i)
Select two routes randomly: one from the particle to be modified and the other from the personal or global best.(ii)
A common node is searched between these pairs of routes.(iii)
If the common node is found, then copy substring (route parts) from the personal or global best between the selected nodes to modify the current particle.(iv)
If a cycle is identified, then repair with iSRR.Figure 2
Identical point mutation.Figure 3
Modified identical point mutation.In the case of no common node being found between the pair of the selected routes, a new pair of routes is selected by the algorithm, again randomly, in an attempt to locate a common node for swapping parts of routes. However, if a candidate node is located, then the process terminates and a new particle is selected from the swarm to undergo modification.The crossover is applicable only to the DE. Specifically, the uniform route crossover (interstring crossover operation) inspired by Beasley et al. [39] is utilized. This crossover is performed as follows: each subroute in the trial vector is generated by interchanging the corresponding subroute either from the target or noisy random vector on the basis of a randomly generated binary crossover mask whose length is equal to the number of routes in the solution. When there is a “1” in the crossover mask, the subroute is copied from the target vector, but when there is a “0” in the mask, the subroute is copied from the noisy random vector. The process is repeated with the target and noisy random vector exchanged to yield the second trial vector (see Figure 4). Note that for each pair of vectors, it is required to generate a new crossover mask [40]. It is advisable to ensure that the trial vectors are feasible; otherwise, attempt to repair the infeasible trial vectors with iSRR.Figure 4
Uniform route crossover.


## 3.5. Replacement

The population for the next generation is constructed through elitism selection for the DE, such that the best vector between thetarget vector and the trial vector is selected for the next generation. This is to maintain the average fitness of the population [41]. For the PSO, the fitness value is updated for the personal and global best, provided the fitness of the current particle is better than the fitness of its personal best and global best after the application of the mutation operator (see Figure 3).The proposed framework of the proposed hybrid DE-PSO is structured as follows: the population (for DE) or swarm (for PSO) is initialized using a construction heuristic proposed by Mumford [38]. The DE algorithm (see Algorithm 1) is run for a finite number of generations, I (e.g., 20) to initialize the swarm for the PSO. The PSO is the main algorithm to search for the optimal solution. Note that it is not appropriate to use the velocity vector of the classical PSO due to the discrete nature of the problem. Instead, a new mutation scheme is utilized to update the personal and global best (see Figure 3). The proposed algorithm will only alternate once, and both of the objective functions will start with the same initial population that has been recorded earlier. At the end of each DE-PSO iteration, the nondominated solution is accumulated and isolated by discarding all the dominated solutions. The detailed framework of the proposed DE-PSO is provided in Algorithm 2.Algorithm 1:DE for multiobjective UTNDP.
(1)
GenerateNp candidate route set using construction heuristic with iSRR repair mechanism
(2)
for i≔1toNp
(3)
fitness evaluation using passenger assignment model
(4)
end for
(5)
for n≔1toG
(6)
for i≔1toNp
(7)
setTarget vector =Xi,n
(8)
select randomly a vector (except the selectedTarget vector, Xi,n) in the population
(9)
apply identical point mutation to generate aNoisy Random vector, Vi,n (repair if infeasible)
(10)
apply uniform route crossover betweenXi,n and Vi,n to generate a pair of Trial vectors, Ui,n (repair if infeasible)
(11)
fitness evaluation ofUi,n using passenger assignment model
(12)
elitism selection
(13)
ifTrial vector fitness ≤ Target vector fitness
(14)
new_populationi  = Trial vector, Ui,n
(15)
else
(16)
new_populationi = Target vector, Xi,n
(17)
end for
(18)
Np= new_population
(19)
end for
(20)
return BESTAlgorithm 2:Hybrid DE-PSO for multiobjective UTNDP.
(1)
Initialize the swarm using DE (Algorithm1)
(2)
for i≔Np
(3)
fitness evaluation using passenger assignment
(4)
fp1,fp2,…,fpn
(5)
Setpg∗=argminfp1,fp2,…,fpn
(6)
end for
(7)
for n≔1toG
(8)
for i≔1toNp
(9)
set current particle = 1st particle in swarm
(10)
select a particle randomly (except the selected 1st particle) in the swarm
(11)
apply particle modification scheme to generate a modified particle (repair if infeasible)
(12)
fitness evaluation using passenger assignment on the modified particle
(13)
if modified particle is better than personal best
(14)
update personal best and its fitness
(15)
else if modified particle is better than global best
(16)
update global best and its fitness
(17)
end if
(18)
end for
(19)
Np= new_population
(20)
end for
(21)
return Best


## 4. Experimental Design

Two sets of experiments are conducted to assess the effectiveness of the proposed hybrid algorithms. In the first experiment, the computational results obtained by hybrid DE-PSO and PSO-DE are compared to verify that the hybrid DE-PSO yields better solutions. In the second experiment, the computational results obtained from the hybrid DE-PSO algorithm are compared with other approaches reported in the literature. All experiments are performed on the well-known benchmark Mandl’s Swiss network [42]. The road network consists of connected edges, edge weights (i.e., travel times of link), and feasible locations of the bus stop, and others (see Section 4.1). It is also assumed that each route must contain at least three nodes (stations) as in Nikolić and Teodorović [20] and Arbex and da Cunha [12]. The proposed algorithms are coded in Python 2.7.6.4 on a computer with 1.60 GHz Intel Core™i5-4200 CPU with 4.00 GB of RAM.


### 4.1. Benchmark Data

Mandl’s Swiss network [42] is a realistic transportation network in Switzerland (see Figure 5). The graph comprises 15 vertices, the shortest travel time between the two farthest vertices is 33 minutes, 21 undirected edges, and overall passenger travel demand is 15570. The highest travel demand between a node pair is 880 passengers. The network is small and dense. In this matrix, the nonzero demand is 82% of the node pairs. The network information for the transit operator includes travel demand and existing road network data. The demand is often represented by a symmetric OD matrix whose elements may include the time, day of the week, boarding point, alighting point, and potential coverage of transit passengers. The road network information includes connectivity of link, lengths of link, travel times of link, and feasible locations of a bus stop.Figure 5
Mandl’s Swiss road network.


### 4.2. Parameter Configuration and Performance Metrics

A population of 30 vectors and a computation time of 200 iterations are performed for the computational experiment. Five scenarios are considered to investigate the nondominated solutions: route sets consisting of 4, 6, 7, 8, and 12 bus lines, respectively. To make a fair comparison with other approaches in the literature, the standard parameter configuration and the performance metrics used by Nikolić and Teodorović [20]; Arbex and da Cunha [12]; and Zhao et al. [21] are provided in Tables 1 and 2, respectively.Table 1
Parameter configuration.
Description
Value
Transfer penalty for 1-transfer trips
5 min
Maximum number of transfers allowable for demand to be satisfied
1 transfer/passenger
Penalty factor for unmet demand
0.2
Load factor
1.25
Bus capacity
50 passengers (40 seat bus)
Minimum allowable frequency of buses operating on any routefmin
1 per hour
Maximum allowable frequency of buses operating on any routefmax
Unlimited
Maximum allowable fleet size
99 busesTable 2
Performance metrics.
Performance metric
Description
d
0
Percentage of demand satisfied with zero transfer
d
1
Percentage of demand satisfied with one transfer
d
un
Percentage of demand unsatisfied (more than one transfer)
C
o
Fleet size
C
p
Total travel time of all passengers
T
inv
In-vehicle time of all passengers
T
wt
Waiting time of all passengers
T
tr
Transfer time of all passengers


## 4.1. Benchmark Data

Mandl’s Swiss network [42] is a realistic transportation network in Switzerland (see Figure 5). The graph comprises 15 vertices, the shortest travel time between the two farthest vertices is 33 minutes, 21 undirected edges, and overall passenger travel demand is 15570. The highest travel demand between a node pair is 880 passengers. The network is small and dense. In this matrix, the nonzero demand is 82% of the node pairs. The network information for the transit operator includes travel demand and existing road network data. The demand is often represented by a symmetric OD matrix whose elements may include the time, day of the week, boarding point, alighting point, and potential coverage of transit passengers. The road network information includes connectivity of link, lengths of link, travel times of link, and feasible locations of a bus stop.Figure 5
Mandl’s Swiss road network.


## 4.2. Parameter Configuration and Performance Metrics

A population of 30 vectors and a computation time of 200 iterations are performed for the computational experiment. Five scenarios are considered to investigate the nondominated solutions: route sets consisting of 4, 6, 7, 8, and 12 bus lines, respectively. To make a fair comparison with other approaches in the literature, the standard parameter configuration and the performance metrics used by Nikolić and Teodorović [20]; Arbex and da Cunha [12]; and Zhao et al. [21] are provided in Tables 1 and 2, respectively.Table 1
Parameter configuration.
Description
Value
Transfer penalty for 1-transfer trips
5 min
Maximum number of transfers allowable for demand to be satisfied
1 transfer/passenger
Penalty factor for unmet demand
0.2
Load factor
1.25
Bus capacity
50 passengers (40 seat bus)
Minimum allowable frequency of buses operating on any routefmin
1 per hour
Maximum allowable frequency of buses operating on any routefmax
Unlimited
Maximum allowable fleet size
99 busesTable 2
Performance metrics.
Performance metric
Description
d
0
Percentage of demand satisfied with zero transfer
d
1
Percentage of demand satisfied with one transfer
d
un
Percentage of demand unsatisfied (more than one transfer)
C
o
Fleet size
C
p
Total travel time of all passengers
T
inv
In-vehicle time of all passengers
T
wt
Waiting time of all passengers
T
tr
Transfer time of all passengers


## 5. Results and Discussions

### 5.1. Comparison of Hybrid DE-PSO and Hybrid PSO-DE

Computational experiments on benchmark Mandl’s Swiss network are conducted to assess the effectiveness of the two proposed hybrid algorithms: hybrid DE-PSO and hybrid PSO-DE. The initial population of both hybrid algorithms are obtained by the route set generation heuristic by Mumford [38], embedded with iSRR mechanism. The iSRR mechanism is used to repair the resulting infeasible candidate route sets. For hybrid DE-PSO, the DE algorithm is initially run for a finite number of generations, I (e.g., 20) to initialize the swarm population for the PSO. The PSO is the main algorithm to search for the optimal solution in hybrid DE-PSO. On the other hand, for hybrid PSO-DE, the PSO algorithm is initially run for a finite number of generations, I (e.g., 20) to initialize the vector population for the DE. DE is the main algorithm to search for the optimal solution in hybrid PSO-DE. Route sets consisting of 4, 6, 7, 8, and 12 bus lines with a maximum of 8 nodes in each route are used. For each case, 10 independent runs are performed for 200 generations, each with a population size of 30. The computational results obtained by both hybrid algorithms are given in Table 3. The entries for Avg. represents the average result after the 10 runs. The transit route network configuration constructed by the proposed hybrid DE-PSO and hybrid PSO-DE is provided in Tables 4 and 5, respectively. In both Tables 4 and 5, column 3 gives the fleet required per route of the route set. The values in the bracket give the overall fleet size required for the given transit route network configuration. Their associated passenger costs are given in column 4.Table 3
Comparative results of hybrid DE-PSO and hybrid PSO-DE.
Bus line
Performance metric
Hybrid DE−PSO
Hybrid PSO−DE
t-test
p
Worst
Avg.
Best
Worst
Avg.
Best
4
d
0
91.64
95.44
95.94
93.51
95.35
94.60
4.41
0.001
d
1
8.36
4.56
4.06
6.49
4.65
5.40
2.12
0.003
d
un
0.00
0.00
0.00
0.00
0.00
0.00
0.00
1.000
C
o
99
96
92
99
97
96
−1.53
0.013
C
p
206,302
205,051
198,177
209,572
207,859
204,592
−1.37
0.018
T
inv
174,462
176,321
168,842
177,213
176,105
175,802
−3.80
<0.001
T
wt
23,892
23,251
25,125
27,092
26,421
24,254
−4.26
<0.001
T
tr
7,9485
5,479
4,210
8,267
5,333
4,536
0.16
0.041
6
d
0
92.08
95.05
97.68
90.04
92.75
94.54
2.31
0.004
d
1
7.92
4.95
2.32
9.96
7.25
5.46
−4.23
0.012
d
un
0.00
0.00
0.00
0.00
0.00
0.00
0.00
1.000
C
o
98
94
90
98
95
94
−2.06
0.021
C
p
221,344
191,562
190,068
231,452
194,568
191,720
−2.35
0.002
T
inv
184,514
160,034
160,835
188,019
156,106
161,012
−1,42
0.013
T
wt
28,268
26,105
25,103
31,085
28,148
25,100
−2.41
0.023
T
tr
8,562
5,423
4,130
12,348
10,314
5,608
−1.32
0.032
7
d
0
90.98
94.82
97.82
90.48
93.66
96.40
−1.24
0.011
d
1
9.02
5.18
2.18
9.52
6.34
3.60
−2.16
0.025
d
un
0.00
0.00
0.00
0.00
0.00
0.00
0.00
1.000
C
o
98
94
84
98
89
85
−2.04
0.031
C
p
215,845
191,875
189,697
226,214
194,874
192,003
−1.43
0.011
T
inv
177,874
158,033
157,800
186,195
158,801
158,557
−2.12
0.020
T
wt
30,145
28,634
27,847
31,087
29,345
27,985
−1.82
0.015
T
tr
7826
5,208
4,050
8,932
6,728
5,461
−2.13
0.021
8
d
0
91.27
94.61
96.59
91.27
93.92
96.47
−0.51
0.042
d
1
8.73
5.39
3.41
8.73
6.08
3.53
2.31
0.001
d
un
0.00
0.00
0.00
0.00
0.00
0.00
0.00
1.000
C
o
99
94
89
99
95
94
−3.40
0.001
C
p
201,162
192,068
184,841
206,925
205.368
193,557
−1.09
0.028
T
inv
161,326
160,725
158,503
170,825
168,584
162,162
−9.52
<0.001
T
wt
28,052
22,580
19,618
24,038
24,586
21,625
3.78
0.001
T
tr
11,784
8,763
6,720
12,062
12,198
9,770
−3.14
0.003
12
d
0
92.26
94.65
97.56
90.24
93.16
95.00
−3.04
0.023
d
1
7.74
5,35
2.44
9.76
6.84
5.00
−2.24
0.042
d
un
0.00
0.00
0.00
0.00
0.00
0.00
0.00
1.000
C
o
98
95
86
99
95
92
−2.13
0.014
C
p
216,080
192,782
184,532
241,658
193,843
191,148
−2.46
0.020
T
inv
185,223
164,870
158,685
208,639
164,069
162,903
−2.01
0.022
T
wt
25,415
23,842
22,632
26,121
24,418
23,164
−2.32
0.032
T
tr
5,442
4,070
3,215
6,898
5,356
5,081
−1.51
0.024Table 4
Best bus lines constructed by the proposed hybrid DE-PSO.
Bus line
Routes
Fleet size (Co)
Passenger cost (Cp)
4
0−1−4−3−5−7−9−12
26
198,177
0−1−2−5−7−14−6−9
29
8−14−7−9−13−12−10−11
14
4−1−2−5−3−11−10−9
23 (92)
6
0−1−3−11−10−12−13−9
15
190,068
8− 14− 5− 3− 4− 1− 0
13
13−12−9−10−11− 3− 4− 1
17
13− 9−7−5−3−4−1−2
12
0−1−2−5−7−14−6−9
15
8−14− 6− 9−10−11−3−5
18 (90)
7
13−9−12−10−11−3−1− 0
14
189,697
9− 6−14−5−2−1−0
9
8−14−6−9−10−11−3−5
18
8−14−5−2−1− 4−3
12
2−1−3−5−7−9−12
8
9−6−14−5−2−1−4−3
10
0−1−2−5−7−9−6
13 (84)
8
6−14−7−5−3−4−1−0
12
184,841
7−5−3−11
6
0−1−2−5−7−9−13−12
14
6−14−5−2−1− 4−3
7
13−9−12−10−11−3−5
22
12−9−7−5−3−4−1
6
8−14−7−5−3−1−0
5
8−14−6−9−10−11−3−5
17 (89)
12
6−14−7−5−3−4−1−0
7
184,532
0−1−4−3−11−10−12−13
10
12−13−9−10−11−3−5
7
10−11−3−4−1−2
5
0−1−2−5−7−14−6
5
0−1−4−3−11−10−12−9
8
0−1−4−3
2
12−13−9−10−11−3−1−4
9
12−10−11−3−4−1−0
8
14−5−7−9−13−12
6
2−5−14−7−9−10−11
7
8−14−6−9−13−12−10−11
12 (86)Table 5
Best bus lines constructed by the proposed hybrid PSO-DE.
Bus line
Routes
Fleet size (Co)
Passenger cost (Cp)
4
9 −7−5−2−1−4−3−11
27
204,592
10−9−7−5−3−4−1−0
26
8−14−7−9−13−12−10−11
28
0−1−2−5−7−9−6−14
15 (96)
6
0−1−2−5−7−9−13−12
17
191,720
8−14−6−9−13−12
15
7−5−3−11−10−9−13−12
13
2−1−4−3−5−7−9−13
19
0−1−2−5−7−14−6
12
9−13−12−10−11−3−1−0
18 (94)
7
0−1−3−5−7−9−10−11
13
192,003
10−9−7−5−3−4−1
10
0−1−4−3−5−2
8
8−14−6−9−13−12−10−11
16
0−1−2−5−14−6−9−13
11
13−9−10−11−3−5−14−8
15
0−1−2−5−7−14−8
12 (85)
8
2−5−7−14−8
7
193,557
13−9−12−10−11−3−1−0
14
5−7−9−13−12
9
6−9−7−5−2−1−4−3
10
0−1−2−5−7−14−6−9
12
8−14−5−7−9−13−12
11
13−12−9−6−14−7−5−3
18
7−5−14−6−9−10−11
13 (94)
12
14−6−9−13−12−10−11−3
11
191,148
1−2−5−7−9−13−12
8
12−13−9−10
4
12−10−9−6−14−8
6
12−10−9−6−14−7−5−3
10
13−12−9−7−5−3
5
8−14−7−5−3−11−10−12
9
8−14−5−3−11−10
6
10−9−6−14−5−2−1−0
8
12−13−9−10−11−3−4−1
10
9−12−10−11−3−4−1−0
8
10−9−7−5−3−4−1
7 (92)As shown in Table3, hybrid DE-PSO produced better results in terms of best d0, Co, Cp, Tinv, and Ttr for the five scenarios considered. However, the best values achieved for the parameter Twt by hybrid DE-PSO is similar to hybrid PSO-DE. In addition, hybrid DE-PSO achieves lower average Twt and Ttr as compared with hybrid PSO-DE. Furthermore, both algorithms produced solutions in which the demand is met with a maximum of only one transfer for the five scenarios considered. It can be observed that hybrid DE-PSO is more capable of finding better solutions from the 10 independent runs than hybrid PSO-DE. A statistical t-test at 5% significant level is also been carried out for both hybrid algorithms. From Table 3 (column 9 and column 10), it can be observed that there is a significant difference in the parameters (except dun) in all cases between both hybrid algorithms. Relatively, hybrid DE-PSO produced better results than hybrid PSO-DE in terms of the point estimates of the parameters. Consequently, we adopt the hybrid DE-PSO for comparison with other results reported in the literature.


### 5.2. Comparative Experiments of Hybrid DE-PSO

#### 5.2.1. Mandl’s Swiss Network

In this experiment, the proposed hybrid DE-PSO algorithm is performed on the Mandl’s Swiss network and compared with the studies of Mandl [42]; Baaj and Mahmassani [3]; Shih and Mahmassani [43]; Bagloe and Cedar [44]; Nikolić and Teodorović [20]; Zhao et al. [21]; and Buba and Lee [23]. These articles used the same passenger assignment method and the same transfer penalties to estimate passengers’ costs. The comparative results on Mandl’s Swiss network with route sets comprising 4, 6, 7, 8, and 12 bus lines are reported in Table 6.Table 6
Comparative results of hybrid DE-PSO for Mandl’s Swiss network.
Bus line
Performance metric
1
2
3
4
5
6
7
8
9
4
d
0
69.94
n/a
n/a
n/a
80.48
95.05
93.77
93.38
95.44
d
1
29.93
n/a
n/a
n/a
12.84
4.95
6.23
6.62
4.56
d
un
0.13
n/a
n/a
n/a
6.68
0.00
0.00
0.00
0.00
C
o
99
n/a
n/a
n/a
70
94
99
95
92
C
p
219,094
n/a
n/a
n/a
180,453
186,368
206,770
199,880
198,177
T
inv
177,400
n/a
n/a
n/a
149,904
161,371
n/a
170,632
169,842
T
wt
18,194
n/a
n/a
n/a
20,549
21,147
n/a
24,098
24,125
T
tr
23,500
n/a
n/a
n/a
10,000
3,850
n/a
5,150
4,210
6
d
0
n/a
78.61
82.59
n/a
87.73
94.34
98.52
96.92
97.68
d
1
n/a
21.39
17.41
n/a
12.27
5.66
1.48
3.08
2.32
d
un
n/a
0.00
0.00
n/a
0.00
0.00
0.00
0.00
0.00
C
o
n/a
89
84
n/a
75
99
89
92
90
C
p
n/a
205,656
203,936
n/a
199,908
185,224
201,270
191,035
190,068
T
inv
n/a
168,076
170,328
n/a
163,020
159,059
n/a
162,080
162,835
T
wt
n/a
20,930
20,058
n/a
27,338
21,766
n/a
24,705
23,103
T
tr
n/a
16,650
13,550
n/a
9,550
4,400
n/a
4,250
4,130
7
d
0
n/a
80.99
n/a
n/a
90.62
94.41
99.68
96.34
97.82
d
1
n/a
19.01
n/a
n/a
9.38
5.59
0.32
3.66
2.18
d
un
n/a
0.00
n/a
n/a
0.00
0.00
0.00
0.00
0.00
C
o
n/a
82
n/a
n/a
78
99
82
90
84
C
p
n/a
217,954
n/a
n/a
195,476
185,406
209,455
188,337
189,697
T
inv
n/a
180,350
n/a
n/a
158,100
157,899
n/a
158,650
157,800
T
wt
n/a
22,804
n/a
n/a
30,076
23,157
n/a
25,587
27,847
T
tr
n/a
14,800
n/a
n/a
7,300
4,350
n/a
4,100
4,050
8
d
0
n/a
79.96
87.73
n/a
91.91
96.40
98.39
97.17
97.56
d
1
n/a
20.04
12.27
n/a
8.09
3.60
1.61
2.83
2.44
d
un
n/a
0.00
0.00
n/a
0.00
0.00
0.00
0.00
0.00
C
o
n/a
78
68
n/a
78
99
77
94
89
C
p
n/a
210,632
204,028
n/a
197,516
185,590
206,910
188,519
184,841
T
inv
n/a
169,101
168,023
n/a
157,950
158,064
n/a
159,832
158,503
T
wt
n/a
25,931
26,455
n/a
33,266
24,726
n/a
25,487
23,718
T
tr
n/a
15,600
9,550
n/a
6,300
2,800
n/a
3,200
2,620
12
d
0
n/a
n/a
n/a
83.66
95.50
95.38
n/a
97.02
97.56
d
1
n/a
n/a
n/a
15.21
4.50
4.62
n/a
2.98
2.44
d
un
n/a
n/a
n/a
1.13
0.00
0.00
n/a
0.00
0.00
C
o
n/a
n/a
n/a
87
85
98
n/a
88
86
C
p
n/a
n/a
n/a
202,254
200,624
187,919
n/a
196,774
184,532
T
inv
n/a
n/a
n/a
167,198
156,769
160,452
n/a
167,754
158,685
T
wt
n/a
n/a
n/a
24,591
40,355
23,867
n/a
25,670
22,632
T
tr
n/a
n/a
n/a
10,465
3,500
3,600
n/a
3,350
3,215
Note: n/a = not available. 1. Mandl [42]; 2. Baaj and Mahmassani [3]; 3. Shih and Mahmassani [43] [uncoordinated]; 4. Reference [44]; 5. Nikolić and Teodorović [20] [Greedy]; 6. Nikolić and Teodorović [20] [BCO]; 7. Zhao et al. [21]; 8. Buba and Lee [23]; 9. Proposed DE-PSO.In Table6, the proposed hybrid DE-PSO (last column) outperformed the DE in terms of d0 for all cases considered. In addition, the DE-PSO algorithm achieves the best result in terms of d0 and d1 compared with previous studies in the case of route sets containing 4 and 12 bus lines. In the case of route sets with 8 and 12 bus lines, the hybrid algorithm outperformed the previous results in terms of Cp. The hybrid DE-PSO achieves the minimum transfer time of all passengers in four out of the five cases as compared with the previous studies. Furthermore, the proposed hybrid DE-PSO is able to produce significant improvement in Co, as reflected by the required fleet evidencing the high quality of solutions obtained. Zhao et al. [21] have the best value for d0 for cases of 6, 7, and 8 bus lines. However, they have some of the worse results for Cp in the literature.As mentioned previously, the UTNDP is a complex problem, given the two conflicting objectives that influence each other: higher frequencies would improve the passenger cost, but this will increase the operator cost. Consequently, Arbex and da Cunha [12] observed that it is not enough to report the best solution found in terms of percentage of direct trips (d0) and the one that minimizes the number of buses, as these two objectives are related. Hence, there is a set of solutions known as Pareto optimal solutions for the UTNDP, which represent the compromise solutions between the conflicting objectives [45]. The computational results of the Pareto front and the node sequence of the best routes found in the Pareto front by the proposed algorithm are given in Tables 7 and 8, respectively.Table 7
The Pareto front obtained by the hybrid DE-PSO.
Solution
Bus lines
Passenger cost (Cp)
Passenger cost above lower bound
Fleet size (Co)
d
0
d
1
d
un
Maximum route headway (min)
Average route headway (min)
Average in-vehicle travel time (min)
Average passenger cost (min)
Average waiting time (min)
1
8
184,841
29,051
89
96.59
3.41
0.00
11.34
6.300
10.18
11.87
1.26
2
10
190,003
34,213
82
97.17
2.83
0.00
12.30
8.488
10.24
12.20
1.31
3
6
190,732
34,942
80
95.12
4.88
0.00
8.00
5.915
10.48
12.25
1.35
4
7
192,581
36,791
79
95.18
4.82
0.00
10.99
7.136
10.62
12.37
1.39
5
9
193,115
37,325
78
98.20
1.20
0.00
10.50
6.812
10.79
11.40
1.21
6
6
193,456
37,666
76
94.99
5.01
0.00
7.71
6.003
10.80
12.43
1.43
7
7
194,898
39,108
75
97.75
2.25
0.00
12.00
7.493
10.84
12.52
1.44
8
7
195,359
39,569
73
95.05
4.95
0.00
12.32
8.830
10.88
12.55
1.45
9
6
196,365
40,575
71
93.38
6.62
0.00
8.00
6.177
10.97
12.61
1.47
10
5
198,027
42,237
68
92.94
7.06
0.00
8.00
5.724
11.02
12.72
1.48
11
5
200,940
45,150
67
94.99
5.01
0.00
8.00
6.160
11.05
12.91
1.49Table 8
Node sequence of routes found in pareto solutions.
Bus line
Routes
Fleet size (Co)
Passenger cost (Cp)
8
6−14−7−5−3−4−1−0
12
184,841
7−5−3−11
6
0−1−2−5−7−9−13−12
14
6−14−5−2−1−4
7
13−9−12−10−11−3−5
22
12−9−7−5−3−4−1
6
8−14−7−5−3−1−0
5
8−14−6−9−10−11−3−5
17 (89)
10
0−1−4−3−11−10
16
190,003
7−9−6−14−5−2−1−0
8
4−3−1−2−5−7−14−8
5
8−14−7−9−12−10−11−3
10
13−9−12−10−11−3
7
4−1−3−11−10−9−12
14
2−1−3−5−7−9−10
4
0−1−2−5−7−9−10−12
7
12−9−6
6
9−13−12−10
5 (82)
6
13−12−9−7−14−8
9
190,732
11−10−9−7−5−2−1−0
21
0−1−4−3−11−10−12−13
18
10−11−3−1−2−5−14−6
10
3−11−10−12−13−9−6
15
12−13−9−7−5−3−4
7 (80)
7
0−1−2−5−7−9−12−13
16
192,581
9−13−12−10−11−3−4
20
8−14−5−2−1−0
8
0−1−2−5−3−11−10−9
13
3−4−1−2−5−14−6−9
9
4−3−5−7−9−13
7
8−14−5−7−9−12−13
6 (79)
9
1−2−5−7−9−12−13
7
193,115
0−1−3−5−7−9−12−13
9
5−7−14−6−9−12−10−11
11
0−1−4−3−11−10−9−6
10
4−3−11−10−9−6−14−8
12
13−12−9−10−11−3−5−2
13
0−1−4−3−5
4
8−14−5−2−1−3
6
0−1−2−5−14−6
6 (78)
6
0−1−2−5−7−9−12
14
193,456
8−14−6−9−7−5−3−1
15
3−4−1−2−5−14−6−9
7
0−1−3−11−10−12−9
6
12−13−9−10−11−3−4−1
19
8−14−5−3−11−10−12−9
15 (76)
7
12−13−9−10−11−3−5−2
13
194,898
3−4−1−2−5
7
5−7−9−12−10−11−3−4
18
0−1−4−3−5−7−9−6
10
0−1−2−5−7−9−12−10
7
0−1−2−5−14−6−9−10
5
11−10−12−13−9−6−14−8
15 (75)
7
6−9−7−5−2−1−0
5
195,359
0−1−3−11−10−12−9−13
23
2−5−3−11
6
0−1−2−5−14−6−9−12
6
1−3−11−10−9−7−5
7
0−1−3−11−10−9−7−5
20
8−14−6−9−7−5−3−4
6 (73)
6
0−1−4−3−5−2
8
196,365
3−11−10−12−9−6−14−8
22
8−14−7−5−3−11−10−9
14
13−9−6−14−5−2−1−3
9
12−9−7−5−2−1−3
7
12−10−9−7−5−2−1−0
11 (71)
5
8−14−6−9−7−5−3−4
15
198,027
0−1−2−5−7−9−10−11
10
13−12−9−7−5−3−1−0
23
8−14−5−3−1−0
11
13−12−10−11−3−5−14−6
9 (68)
5
13−9−7−5−3−11
15
200,940
8−14−5−7−9−10−11
9
10−9−6−14−5−2−1−4
7
0−1−2−5−7−9−13−12
14
0−1−4−3−11−10−9−12
22 (67)In Table7, some important performance indicators, including average route headways, in-vehicle travel times, and the maximum route headways are determined. Headways are useful indications of how frequent public transit service is, and therefore the waiting time of the passengers. Note that for these indicators, we do not have existing results to compare with our results. The maximum and average route headway lie between (7.71, 12.32) and (5.724, 8.830) minutes, respectively. The proposed hybrid DE-PSO solution produced more than one route choice for most OD pairs, as implied by the low values for average waiting times, which are significantly less than average route headways.For the Mandl’s Swiss network, the lower bound on the in-vehicle travel time is 155,790 minutes [17]. The lower bound represents the theoretical minimum possible passenger time if passengers incurred no waiting time or transfer penalties and were able to take a vehicle that followed the shortest path from their origin to their destination. If operator cost is not an issue and there is no maximum frequency constraint, then it is possible to achieve a total generalized passenger cost that is arbitrarily close to this limit. Table 7 (column 4) provides the additional passenger time above the theoretical minimum for the hybrid DE-PSO. In this table, the hybrid DE-PSO produced solutions that are 18.65% to 28.98% closer to the theoretical minimum passenger time.The Pareto frontier for the various solutions achieved from Table8 with passenger cost on the vertical axis and the number of buses required on the horizontal axis is depicted in Figure 6. Efficient frontier solutions are highlighted in dark crosses, whereas past literature results are author-labeled. It can be observed that the passenger cost for the best compromising solutions is lower than the previously published results, evidencing the high quality of the solutions obtained by the proposed hybrid DE-PSO algorithm.Figure 6
Comparison of solutions from hybrid DE-PSO with solutions from the literature.


#### 5.2.2. Rivera City Network

To demonstrate the scalability of the proposed hybrid DE-PSO, we applied the proposed algorithm to solve a real-size public transportation network of Rivera City (see Figure7). This case study belongs to a medium-size city of 65,000 citizens in Northern Uruguay. It comprises 84 nodes, 143 arcs, and 378 OD pairs. Because we do not have the optimal number of transit routes for the network under study, therefore, we considered the minimum number of routes is 40 and the maximum number of routes is 60, whereas the minimum and the maximum numbers of nodes per route are 10 and 30 base on preliminary run. In addition, all of the parameters in Table 1 are utilized in this methodology, except the maximum allowable fleet size, which to the best of our knowledge is not available.Figure 7
Rivera city network.The hybrid approach produced solutions with maximum and minimum fleet size (operator cost) of 126 and 86 buses, respectively (see Table9). This implies a variation of 32% in the cost between the two extreme solutions; however, it leads to an increase in the passenger cost by 34%. In Figure 8, the inherent conflict between the network bus fleet size and passenger cost that makes it difficult to find a unique optimal solution is depicted. The different trade-offs between the competing objectives are established and it is left for the decision-maker to attain a biased solution either to the passenger or the operator. It is important to note that it is difficult (impossible) to minimize passenger and operator costs at the same time. Furthermore, the overall passenger travel demand is satisfied with at most one transfer. The maximum and average route headway lie between (2.05, 8.20) and (1.21, 6.31) minutes, respectively. The proposed hybrid DE-PSO solution produced more than one route choice for most OD pairs, as implied by the low values for average waiting times, which are significantly less than average routes headways.Table 9
The Pareto front obtained by the hybrid DE-PSO for the Rivera city network.
Solution
Bus lines
Passenger cost (Cp)
Fleet size (Co)
d
0
d
1
d
un
Maximum route headway (min)
Average route headway (min)
Average waiting time (min)
1
46
211.56
86
80.61
19.39
0.00
8.20
6.31
1.94
2
47
199.64
88
79.52
20.48
0.00
7.32
6.26
1.81
3
49
183.73
91
85.24
14.76
0.00
6.45
5.09
1.62
4
50
178.42
93
82.45
17.55
0.00
6.21
4.92
1.46
5
51
165.31
94
82.25
17.75
0.00
5.26
4.02
1.53
6
53
161.43
96
85.35
14.65
0.00
4.12
3.23
1.47
7
54
159.74
98
91.25
8.75
0.00
2.61
1.86
1.50
8
55
148.62
105
93.67
6.33
0.00
3.33
1.60
1.51
9
58
144.25
110
93.73
6.27
0.00
2.18
1.57
1.50
10
60
138.86
126
93.86
6.14
0.00
2.05
1.21
1.50Figure 8
Solutions from hybrid DE-PSO for the Rivera city network.


## 5.1. Comparison of Hybrid DE-PSO and Hybrid PSO-DE

Computational experiments on benchmark Mandl’s Swiss network are conducted to assess the effectiveness of the two proposed hybrid algorithms: hybrid DE-PSO and hybrid PSO-DE. The initial population of both hybrid algorithms are obtained by the route set generation heuristic by Mumford [38], embedded with iSRR mechanism. The iSRR mechanism is used to repair the resulting infeasible candidate route sets. For hybrid DE-PSO, the DE algorithm is initially run for a finite number of generations, I (e.g., 20) to initialize the swarm population for the PSO. The PSO is the main algorithm to search for the optimal solution in hybrid DE-PSO. On the other hand, for hybrid PSO-DE, the PSO algorithm is initially run for a finite number of generations, I (e.g., 20) to initialize the vector population for the DE. DE is the main algorithm to search for the optimal solution in hybrid PSO-DE. Route sets consisting of 4, 6, 7, 8, and 12 bus lines with a maximum of 8 nodes in each route are used. For each case, 10 independent runs are performed for 200 generations, each with a population size of 30. The computational results obtained by both hybrid algorithms are given in Table 3. The entries for Avg. represents the average result after the 10 runs. The transit route network configuration constructed by the proposed hybrid DE-PSO and hybrid PSO-DE is provided in Tables 4 and 5, respectively. In both Tables 4 and 5, column 3 gives the fleet required per route of the route set. The values in the bracket give the overall fleet size required for the given transit route network configuration. Their associated passenger costs are given in column 4.Table 3
Comparative results of hybrid DE-PSO and hybrid PSO-DE.
Bus line
Performance metric
Hybrid DE−PSO
Hybrid PSO−DE
t-test
p
Worst
Avg.
Best
Worst
Avg.
Best
4
d
0
91.64
95.44
95.94
93.51
95.35
94.60
4.41
0.001
d
1
8.36
4.56
4.06
6.49
4.65
5.40
2.12
0.003
d
un
0.00
0.00
0.00
0.00
0.00
0.00
0.00
1.000
C
o
99
96
92
99
97
96
−1.53
0.013
C
p
206,302
205,051
198,177
209,572
207,859
204,592
−1.37
0.018
T
inv
174,462
176,321
168,842
177,213
176,105
175,802
−3.80
<0.001
T
wt
23,892
23,251
25,125
27,092
26,421
24,254
−4.26
<0.001
T
tr
7,9485
5,479
4,210
8,267
5,333
4,536
0.16
0.041
6
d
0
92.08
95.05
97.68
90.04
92.75
94.54
2.31
0.004
d
1
7.92
4.95
2.32
9.96
7.25
5.46
−4.23
0.012
d
un
0.00
0.00
0.00
0.00
0.00
0.00
0.00
1.000
C
o
98
94
90
98
95
94
−2.06
0.021
C
p
221,344
191,562
190,068
231,452
194,568
191,720
−2.35
0.002
T
inv
184,514
160,034
160,835
188,019
156,106
161,012
−1,42
0.013
T
wt
28,268
26,105
25,103
31,085
28,148
25,100
−2.41
0.023
T
tr
8,562
5,423
4,130
12,348
10,314
5,608
−1.32
0.032
7
d
0
90.98
94.82
97.82
90.48
93.66
96.40
−1.24
0.011
d
1
9.02
5.18
2.18
9.52
6.34
3.60
−2.16
0.025
d
un
0.00
0.00
0.00
0.00
0.00
0.00
0.00
1.000
C
o
98
94
84
98
89
85
−2.04
0.031
C
p
215,845
191,875
189,697
226,214
194,874
192,003
−1.43
0.011
T
inv
177,874
158,033
157,800
186,195
158,801
158,557
−2.12
0.020
T
wt
30,145
28,634
27,847
31,087
29,345
27,985
−1.82
0.015
T
tr
7826
5,208
4,050
8,932
6,728
5,461
−2.13
0.021
8
d
0
91.27
94.61
96.59
91.27
93.92
96.47
−0.51
0.042
d
1
8.73
5.39
3.41
8.73
6.08
3.53
2.31
0.001
d
un
0.00
0.00
0.00
0.00
0.00
0.00
0.00
1.000
C
o
99
94
89
99
95
94
−3.40
0.001
C
p
201,162
192,068
184,841
206,925
205.368
193,557
−1.09
0.028
T
inv
161,326
160,725
158,503
170,825
168,584
162,162
−9.52
<0.001
T
wt
28,052
22,580
19,618
24,038
24,586
21,625
3.78
0.001
T
tr
11,784
8,763
6,720
12,062
12,198
9,770
−3.14
0.003
12
d
0
92.26
94.65
97.56
90.24
93.16
95.00
−3.04
0.023
d
1
7.74
5,35
2.44
9.76
6.84
5.00
−2.24
0.042
d
un
0.00
0.00
0.00
0.00
0.00
0.00
0.00
1.000
C
o
98
95
86
99
95
92
−2.13
0.014
C
p
216,080
192,782
184,532
241,658
193,843
191,148
−2.46
0.020
T
inv
185,223
164,870
158,685
208,639
164,069
162,903
−2.01
0.022
T
wt
25,415
23,842
22,632
26,121
24,418
23,164
−2.32
0.032
T
tr
5,442
4,070
3,215
6,898
5,356
5,081
−1.51
0.024Table 4
Best bus lines constructed by the proposed hybrid DE-PSO.
Bus line
Routes
Fleet size (Co)
Passenger cost (Cp)
4
0−1−4−3−5−7−9−12
26
198,177
0−1−2−5−7−14−6−9
29
8−14−7−9−13−12−10−11
14
4−1−2−5−3−11−10−9
23 (92)
6
0−1−3−11−10−12−13−9
15
190,068
8− 14− 5− 3− 4− 1− 0
13
13−12−9−10−11− 3− 4− 1
17
13− 9−7−5−3−4−1−2
12
0−1−2−5−7−14−6−9
15
8−14− 6− 9−10−11−3−5
18 (90)
7
13−9−12−10−11−3−1− 0
14
189,697
9− 6−14−5−2−1−0
9
8−14−6−9−10−11−3−5
18
8−14−5−2−1− 4−3
12
2−1−3−5−7−9−12
8
9−6−14−5−2−1−4−3
10
0−1−2−5−7−9−6
13 (84)
8
6−14−7−5−3−4−1−0
12
184,841
7−5−3−11
6
0−1−2−5−7−9−13−12
14
6−14−5−2−1− 4−3
7
13−9−12−10−11−3−5
22
12−9−7−5−3−4−1
6
8−14−7−5−3−1−0
5
8−14−6−9−10−11−3−5
17 (89)
12
6−14−7−5−3−4−1−0
7
184,532
0−1−4−3−11−10−12−13
10
12−13−9−10−11−3−5
7
10−11−3−4−1−2
5
0−1−2−5−7−14−6
5
0−1−4−3−11−10−12−9
8
0−1−4−3
2
12−13−9−10−11−3−1−4
9
12−10−11−3−4−1−0
8
14−5−7−9−13−12
6
2−5−14−7−9−10−11
7
8−14−6−9−13−12−10−11
12 (86)Table 5
Best bus lines constructed by the proposed hybrid PSO-DE.
Bus line
Routes
Fleet size (Co)
Passenger cost (Cp)
4
9 −7−5−2−1−4−3−11
27
204,592
10−9−7−5−3−4−1−0
26
8−14−7−9−13−12−10−11
28
0−1−2−5−7−9−6−14
15 (96)
6
0−1−2−5−7−9−13−12
17
191,720
8−14−6−9−13−12
15
7−5−3−11−10−9−13−12
13
2−1−4−3−5−7−9−13
19
0−1−2−5−7−14−6
12
9−13−12−10−11−3−1−0
18 (94)
7
0−1−3−5−7−9−10−11
13
192,003
10−9−7−5−3−4−1
10
0−1−4−3−5−2
8
8−14−6−9−13−12−10−11
16
0−1−2−5−14−6−9−13
11
13−9−10−11−3−5−14−8
15
0−1−2−5−7−14−8
12 (85)
8
2−5−7−14−8
7
193,557
13−9−12−10−11−3−1−0
14
5−7−9−13−12
9
6−9−7−5−2−1−4−3
10
0−1−2−5−7−14−6−9
12
8−14−5−7−9−13−12
11
13−12−9−6−14−7−5−3
18
7−5−14−6−9−10−11
13 (94)
12
14−6−9−13−12−10−11−3
11
191,148
1−2−5−7−9−13−12
8
12−13−9−10
4
12−10−9−6−14−8
6
12−10−9−6−14−7−5−3
10
13−12−9−7−5−3
5
8−14−7−5−3−11−10−12
9
8−14−5−3−11−10
6
10−9−6−14−5−2−1−0
8
12−13−9−10−11−3−4−1
10
9−12−10−11−3−4−1−0
8
10−9−7−5−3−4−1
7 (92)As shown in Table3, hybrid DE-PSO produced better results in terms of best d0, Co, Cp, Tinv, and Ttr for the five scenarios considered. However, the best values achieved for the parameter Twt by hybrid DE-PSO is similar to hybrid PSO-DE. In addition, hybrid DE-PSO achieves lower average Twt and Ttr as compared with hybrid PSO-DE. Furthermore, both algorithms produced solutions in which the demand is met with a maximum of only one transfer for the five scenarios considered. It can be observed that hybrid DE-PSO is more capable of finding better solutions from the 10 independent runs than hybrid PSO-DE. A statistical t-test at 5% significant level is also been carried out for both hybrid algorithms. From Table 3 (column 9 and column 10), it can be observed that there is a significant difference in the parameters (except dun) in all cases between both hybrid algorithms. Relatively, hybrid DE-PSO produced better results than hybrid PSO-DE in terms of the point estimates of the parameters. Consequently, we adopt the hybrid DE-PSO for comparison with other results reported in the literature.


## 5.2. Comparative Experiments of Hybrid DE-PSO

### 5.2.1. Mandl’s Swiss Network

In this experiment, the proposed hybrid DE-PSO algorithm is performed on the Mandl’s Swiss network and compared with the studies of Mandl [42]; Baaj and Mahmassani [3]; Shih and Mahmassani [43]; Bagloe and Cedar [44]; Nikolić and Teodorović [20]; Zhao et al. [21]; and Buba and Lee [23]. These articles used the same passenger assignment method and the same transfer penalties to estimate passengers’ costs. The comparative results on Mandl’s Swiss network with route sets comprising 4, 6, 7, 8, and 12 bus lines are reported in Table 6.Table 6
Comparative results of hybrid DE-PSO for Mandl’s Swiss network.
Bus line
Performance metric
1
2
3
4
5
6
7
8
9
4
d
0
69.94
n/a
n/a
n/a
80.48
95.05
93.77
93.38
95.44
d
1
29.93
n/a
n/a
n/a
12.84
4.95
6.23
6.62
4.56
d
un
0.13
n/a
n/a
n/a
6.68
0.00
0.00
0.00
0.00
C
o
99
n/a
n/a
n/a
70
94
99
95
92
C
p
219,094
n/a
n/a
n/a
180,453
186,368
206,770
199,880
198,177
T
inv
177,400
n/a
n/a
n/a
149,904
161,371
n/a
170,632
169,842
T
wt
18,194
n/a
n/a
n/a
20,549
21,147
n/a
24,098
24,125
T
tr
23,500
n/a
n/a
n/a
10,000
3,850
n/a
5,150
4,210
6
d
0
n/a
78.61
82.59
n/a
87.73
94.34
98.52
96.92
97.68
d
1
n/a
21.39
17.41
n/a
12.27
5.66
1.48
3.08
2.32
d
un
n/a
0.00
0.00
n/a
0.00
0.00
0.00
0.00
0.00
C
o
n/a
89
84
n/a
75
99
89
92
90
C
p
n/a
205,656
203,936
n/a
199,908
185,224
201,270
191,035
190,068
T
inv
n/a
168,076
170,328
n/a
163,020
159,059
n/a
162,080
162,835
T
wt
n/a
20,930
20,058
n/a
27,338
21,766
n/a
24,705
23,103
T
tr
n/a
16,650
13,550
n/a
9,550
4,400
n/a
4,250
4,130
7
d
0
n/a
80.99
n/a
n/a
90.62
94.41
99.68
96.34
97.82
d
1
n/a
19.01
n/a
n/a
9.38
5.59
0.32
3.66
2.18
d
un
n/a
0.00
n/a
n/a
0.00
0.00
0.00
0.00
0.00
C
o
n/a
82
n/a
n/a
78
99
82
90
84
C
p
n/a
217,954
n/a
n/a
195,476
185,406
209,455
188,337
189,697
T
inv
n/a
180,350
n/a
n/a
158,100
157,899
n/a
158,650
157,800
T
wt
n/a
22,804
n/a
n/a
30,076
23,157
n/a
25,587
27,847
T
tr
n/a
14,800
n/a
n/a
7,300
4,350
n/a
4,100
4,050
8
d
0
n/a
79.96
87.73
n/a
91.91
96.40
98.39
97.17
97.56
d
1
n/a
20.04
12.27
n/a
8.09
3.60
1.61
2.83
2.44
d
un
n/a
0.00
0.00
n/a
0.00
0.00
0.00
0.00
0.00
C
o
n/a
78
68
n/a
78
99
77
94
89
C
p
n/a
210,632
204,028
n/a
197,516
185,590
206,910
188,519
184,841
T
inv
n/a
169,101
168,023
n/a
157,950
158,064
n/a
159,832
158,503
T
wt
n/a
25,931
26,455
n/a
33,266
24,726
n/a
25,487
23,718
T
tr
n/a
15,600
9,550
n/a
6,300
2,800
n/a
3,200
2,620
12
d
0
n/a
n/a
n/a
83.66
95.50
95.38
n/a
97.02
97.56
d
1
n/a
n/a
n/a
15.21
4.50
4.62
n/a
2.98
2.44
d
un
n/a
n/a
n/a
1.13
0.00
0.00
n/a
0.00
0.00
C
o
n/a
n/a
n/a
87
85
98
n/a
88
86
C
p
n/a
n/a
n/a
202,254
200,624
187,919
n/a
196,774
184,532
T
inv
n/a
n/a
n/a
167,198
156,769
160,452
n/a
167,754
158,685
T
wt
n/a
n/a
n/a
24,591
40,355
23,867
n/a
25,670
22,632
T
tr
n/a
n/a
n/a
10,465
3,500
3,600
n/a
3,350
3,215
Note: n/a = not available. 1. Mandl [42]; 2. Baaj and Mahmassani [3]; 3. Shih and Mahmassani [43] [uncoordinated]; 4. Reference [44]; 5. Nikolić and Teodorović [20] [Greedy]; 6. Nikolić and Teodorović [20] [BCO]; 7. Zhao et al. [21]; 8. Buba and Lee [23]; 9. Proposed DE-PSO.In Table6, the proposed hybrid DE-PSO (last column) outperformed the DE in terms of d0 for all cases considered. In addition, the DE-PSO algorithm achieves the best result in terms of d0 and d1 compared with previous studies in the case of route sets containing 4 and 12 bus lines. In the case of route sets with 8 and 12 bus lines, the hybrid algorithm outperformed the previous results in terms of Cp. The hybrid DE-PSO achieves the minimum transfer time of all passengers in four out of the five cases as compared with the previous studies. Furthermore, the proposed hybrid DE-PSO is able to produce significant improvement in Co, as reflected by the required fleet evidencing the high quality of solutions obtained. Zhao et al. [21] have the best value for d0 for cases of 6, 7, and 8 bus lines. However, they have some of the worse results for Cp in the literature.As mentioned previously, the UTNDP is a complex problem, given the two conflicting objectives that influence each other: higher frequencies would improve the passenger cost, but this will increase the operator cost. Consequently, Arbex and da Cunha [12] observed that it is not enough to report the best solution found in terms of percentage of direct trips (d0) and the one that minimizes the number of buses, as these two objectives are related. Hence, there is a set of solutions known as Pareto optimal solutions for the UTNDP, which represent the compromise solutions between the conflicting objectives [45]. The computational results of the Pareto front and the node sequence of the best routes found in the Pareto front by the proposed algorithm are given in Tables 7 and 8, respectively.Table 7
The Pareto front obtained by the hybrid DE-PSO.
Solution
Bus lines
Passenger cost (Cp)
Passenger cost above lower bound
Fleet size (Co)
d
0
d
1
d
un
Maximum route headway (min)
Average route headway (min)
Average in-vehicle travel time (min)
Average passenger cost (min)
Average waiting time (min)
1
8
184,841
29,051
89
96.59
3.41
0.00
11.34
6.300
10.18
11.87
1.26
2
10
190,003
34,213
82
97.17
2.83
0.00
12.30
8.488
10.24
12.20
1.31
3
6
190,732
34,942
80
95.12
4.88
0.00
8.00
5.915
10.48
12.25
1.35
4
7
192,581
36,791
79
95.18
4.82
0.00
10.99
7.136
10.62
12.37
1.39
5
9
193,115
37,325
78
98.20
1.20
0.00
10.50
6.812
10.79
11.40
1.21
6
6
193,456
37,666
76
94.99
5.01
0.00
7.71
6.003
10.80
12.43
1.43
7
7
194,898
39,108
75
97.75
2.25
0.00
12.00
7.493
10.84
12.52
1.44
8
7
195,359
39,569
73
95.05
4.95
0.00
12.32
8.830
10.88
12.55
1.45
9
6
196,365
40,575
71
93.38
6.62
0.00
8.00
6.177
10.97
12.61
1.47
10
5
198,027
42,237
68
92.94
7.06
0.00
8.00
5.724
11.02
12.72
1.48
11
5
200,940
45,150
67
94.99
5.01
0.00
8.00
6.160
11.05
12.91
1.49Table 8
Node sequence of routes found in pareto solutions.
Bus line
Routes
Fleet size (Co)
Passenger cost (Cp)
8
6−14−7−5−3−4−1−0
12
184,841
7−5−3−11
6
0−1−2−5−7−9−13−12
14
6−14−5−2−1−4
7
13−9−12−10−11−3−5
22
12−9−7−5−3−4−1
6
8−14−7−5−3−1−0
5
8−14−6−9−10−11−3−5
17 (89)
10
0−1−4−3−11−10
16
190,003
7−9−6−14−5−2−1−0
8
4−3−1−2−5−7−14−8
5
8−14−7−9−12−10−11−3
10
13−9−12−10−11−3
7
4−1−3−11−10−9−12
14
2−1−3−5−7−9−10
4
0−1−2−5−7−9−10−12
7
12−9−6
6
9−13−12−10
5 (82)
6
13−12−9−7−14−8
9
190,732
11−10−9−7−5−2−1−0
21
0−1−4−3−11−10−12−13
18
10−11−3−1−2−5−14−6
10
3−11−10−12−13−9−6
15
12−13−9−7−5−3−4
7 (80)
7
0−1−2−5−7−9−12−13
16
192,581
9−13−12−10−11−3−4
20
8−14−5−2−1−0
8
0−1−2−5−3−11−10−9
13
3−4−1−2−5−14−6−9
9
4−3−5−7−9−13
7
8−14−5−7−9−12−13
6 (79)
9
1−2−5−7−9−12−13
7
193,115
0−1−3−5−7−9−12−13
9
5−7−14−6−9−12−10−11
11
0−1−4−3−11−10−9−6
10
4−3−11−10−9−6−14−8
12
13−12−9−10−11−3−5−2
13
0−1−4−3−5
4
8−14−5−2−1−3
6
0−1−2−5−14−6
6 (78)
6
0−1−2−5−7−9−12
14
193,456
8−14−6−9−7−5−3−1
15
3−4−1−2−5−14−6−9
7
0−1−3−11−10−12−9
6
12−13−9−10−11−3−4−1
19
8−14−5−3−11−10−12−9
15 (76)
7
12−13−9−10−11−3−5−2
13
194,898
3−4−1−2−5
7
5−7−9−12−10−11−3−4
18
0−1−4−3−5−7−9−6
10
0−1−2−5−7−9−12−10
7
0−1−2−5−14−6−9−10
5
11−10−12−13−9−6−14−8
15 (75)
7
6−9−7−5−2−1−0
5
195,359
0−1−3−11−10−12−9−13
23
2−5−3−11
6
0−1−2−5−14−6−9−12
6
1−3−11−10−9−7−5
7
0−1−3−11−10−9−7−5
20
8−14−6−9−7−5−3−4
6 (73)
6
0−1−4−3−5−2
8
196,365
3−11−10−12−9−6−14−8
22
8−14−7−5−3−11−10−9
14
13−9−6−14−5−2−1−3
9
12−9−7−5−2−1−3
7
12−10−9−7−5−2−1−0
11 (71)
5
8−14−6−9−7−5−3−4
15
198,027
0−1−2−5−7−9−10−11
10
13−12−9−7−5−3−1−0
23
8−14−5−3−1−0
11
13−12−10−11−3−5−14−6
9 (68)
5
13−9−7−5−3−11
15
200,940
8−14−5−7−9−10−11
9
10−9−6−14−5−2−1−4
7
0−1−2−5−7−9−13−12
14
0−1−4−3−11−10−9−12
22 (67)In Table7, some important performance indicators, including average route headways, in-vehicle travel times, and the maximum route headways are determined. Headways are useful indications of how frequent public transit service is, and therefore the waiting time of the passengers. Note that for these indicators, we do not have existing results to compare with our results. The maximum and average route headway lie between (7.71, 12.32) and (5.724, 8.830) minutes, respectively. The proposed hybrid DE-PSO solution produced more than one route choice for most OD pairs, as implied by the low values for average waiting times, which are significantly less than average route headways.For the Mandl’s Swiss network, the lower bound on the in-vehicle travel time is 155,790 minutes [17]. The lower bound represents the theoretical minimum possible passenger time if passengers incurred no waiting time or transfer penalties and were able to take a vehicle that followed the shortest path from their origin to their destination. If operator cost is not an issue and there is no maximum frequency constraint, then it is possible to achieve a total generalized passenger cost that is arbitrarily close to this limit. Table 7 (column 4) provides the additional passenger time above the theoretical minimum for the hybrid DE-PSO. In this table, the hybrid DE-PSO produced solutions that are 18.65% to 28.98% closer to the theoretical minimum passenger time.The Pareto frontier for the various solutions achieved from Table8 with passenger cost on the vertical axis and the number of buses required on the horizontal axis is depicted in Figure 6. Efficient frontier solutions are highlighted in dark crosses, whereas past literature results are author-labeled. It can be observed that the passenger cost for the best compromising solutions is lower than the previously published results, evidencing the high quality of the solutions obtained by the proposed hybrid DE-PSO algorithm.Figure 6
Comparison of solutions from hybrid DE-PSO with solutions from the literature.


### 5.2.2. Rivera City Network

To demonstrate the scalability of the proposed hybrid DE-PSO, we applied the proposed algorithm to solve a real-size public transportation network of Rivera City (see Figure7). This case study belongs to a medium-size city of 65,000 citizens in Northern Uruguay. It comprises 84 nodes, 143 arcs, and 378 OD pairs. Because we do not have the optimal number of transit routes for the network under study, therefore, we considered the minimum number of routes is 40 and the maximum number of routes is 60, whereas the minimum and the maximum numbers of nodes per route are 10 and 30 base on preliminary run. In addition, all of the parameters in Table 1 are utilized in this methodology, except the maximum allowable fleet size, which to the best of our knowledge is not available.Figure 7
Rivera city network.The hybrid approach produced solutions with maximum and minimum fleet size (operator cost) of 126 and 86 buses, respectively (see Table9). This implies a variation of 32% in the cost between the two extreme solutions; however, it leads to an increase in the passenger cost by 34%. In Figure 8, the inherent conflict between the network bus fleet size and passenger cost that makes it difficult to find a unique optimal solution is depicted. The different trade-offs between the competing objectives are established and it is left for the decision-maker to attain a biased solution either to the passenger or the operator. It is important to note that it is difficult (impossible) to minimize passenger and operator costs at the same time. Furthermore, the overall passenger travel demand is satisfied with at most one transfer. The maximum and average route headway lie between (2.05, 8.20) and (1.21, 6.31) minutes, respectively. The proposed hybrid DE-PSO solution produced more than one route choice for most OD pairs, as implied by the low values for average waiting times, which are significantly less than average routes headways.Table 9
The Pareto front obtained by the hybrid DE-PSO for the Rivera city network.
Solution
Bus lines
Passenger cost (Cp)
Fleet size (Co)
d
0
d
1
d
un
Maximum route headway (min)
Average route headway (min)
Average waiting time (min)
1
46
211.56
86
80.61
19.39
0.00
8.20
6.31
1.94
2
47
199.64
88
79.52
20.48
0.00
7.32
6.26
1.81
3
49
183.73
91
85.24
14.76
0.00
6.45
5.09
1.62
4
50
178.42
93
82.45
17.55
0.00
6.21
4.92
1.46
5
51
165.31
94
82.25
17.75
0.00
5.26
4.02
1.53
6
53
161.43
96
85.35
14.65
0.00
4.12
3.23
1.47
7
54
159.74
98
91.25
8.75
0.00
2.61
1.86
1.50
8
55
148.62
105
93.67
6.33
0.00
3.33
1.60
1.51
9
58
144.25
110
93.73
6.27
0.00
2.18
1.57
1.50
10
60
138.86
126
93.86
6.14
0.00
2.05
1.21
1.50Figure 8
Solutions from hybrid DE-PSO for the Rivera city network.


## 5.2.1. Mandl’s Swiss Network

In this experiment, the proposed hybrid DE-PSO algorithm is performed on the Mandl’s Swiss network and compared with the studies of Mandl [42]; Baaj and Mahmassani [3]; Shih and Mahmassani [43]; Bagloe and Cedar [44]; Nikolić and Teodorović [20]; Zhao et al. [21]; and Buba and Lee [23]. These articles used the same passenger assignment method and the same transfer penalties to estimate passengers’ costs. The comparative results on Mandl’s Swiss network with route sets comprising 4, 6, 7, 8, and 12 bus lines are reported in Table 6.Table 6
Comparative results of hybrid DE-PSO for Mandl’s Swiss network.
Bus line
Performance metric
1
2
3
4
5
6
7
8
9
4
d
0
69.94
n/a
n/a
n/a
80.48
95.05
93.77
93.38
95.44
d
1
29.93
n/a
n/a
n/a
12.84
4.95
6.23
6.62
4.56
d
un
0.13
n/a
n/a
n/a
6.68
0.00
0.00
0.00
0.00
C
o
99
n/a
n/a
n/a
70
94
99
95
92
C
p
219,094
n/a
n/a
n/a
180,453
186,368
206,770
199,880
198,177
T
inv
177,400
n/a
n/a
n/a
149,904
161,371
n/a
170,632
169,842
T
wt
18,194
n/a
n/a
n/a
20,549
21,147
n/a
24,098
24,125
T
tr
23,500
n/a
n/a
n/a
10,000
3,850
n/a
5,150
4,210
6
d
0
n/a
78.61
82.59
n/a
87.73
94.34
98.52
96.92
97.68
d
1
n/a
21.39
17.41
n/a
12.27
5.66
1.48
3.08
2.32
d
un
n/a
0.00
0.00
n/a
0.00
0.00
0.00
0.00
0.00
C
o
n/a
89
84
n/a
75
99
89
92
90
C
p
n/a
205,656
203,936
n/a
199,908
185,224
201,270
191,035
190,068
T
inv
n/a
168,076
170,328
n/a
163,020
159,059
n/a
162,080
162,835
T
wt
n/a
20,930
20,058
n/a
27,338
21,766
n/a
24,705
23,103
T
tr
n/a
16,650
13,550
n/a
9,550
4,400
n/a
4,250
4,130
7
d
0
n/a
80.99
n/a
n/a
90.62
94.41
99.68
96.34
97.82
d
1
n/a
19.01
n/a
n/a
9.38
5.59
0.32
3.66
2.18
d
un
n/a
0.00
n/a
n/a
0.00
0.00
0.00
0.00
0.00
C
o
n/a
82
n/a
n/a
78
99
82
90
84
C
p
n/a
217,954
n/a
n/a
195,476
185,406
209,455
188,337
189,697
T
inv
n/a
180,350
n/a
n/a
158,100
157,899
n/a
158,650
157,800
T
wt
n/a
22,804
n/a
n/a
30,076
23,157
n/a
25,587
27,847
T
tr
n/a
14,800
n/a
n/a
7,300
4,350
n/a
4,100
4,050
8
d
0
n/a
79.96
87.73
n/a
91.91
96.40
98.39
97.17
97.56
d
1
n/a
20.04
12.27
n/a
8.09
3.60
1.61
2.83
2.44
d
un
n/a
0.00
0.00
n/a
0.00
0.00
0.00
0.00
0.00
C
o
n/a
78
68
n/a
78
99
77
94
89
C
p
n/a
210,632
204,028
n/a
197,516
185,590
206,910
188,519
184,841
T
inv
n/a
169,101
168,023
n/a
157,950
158,064
n/a
159,832
158,503
T
wt
n/a
25,931
26,455
n/a
33,266
24,726
n/a
25,487
23,718
T
tr
n/a
15,600
9,550
n/a
6,300
2,800
n/a
3,200
2,620
12
d
0
n/a
n/a
n/a
83.66
95.50
95.38
n/a
97.02
97.56
d
1
n/a
n/a
n/a
15.21
4.50
4.62
n/a
2.98
2.44
d
un
n/a
n/a
n/a
1.13
0.00
0.00
n/a
0.00
0.00
C
o
n/a
n/a
n/a
87
85
98
n/a
88
86
C
p
n/a
n/a
n/a
202,254
200,624
187,919
n/a
196,774
184,532
T
inv
n/a
n/a
n/a
167,198
156,769
160,452
n/a
167,754
158,685
T
wt
n/a
n/a
n/a
24,591
40,355
23,867
n/a
25,670
22,632
T
tr
n/a
n/a
n/a
10,465
3,500
3,600
n/a
3,350
3,215
Note: n/a = not available. 1. Mandl [42]; 2. Baaj and Mahmassani [3]; 3. Shih and Mahmassani [43] [uncoordinated]; 4. Reference [44]; 5. Nikolić and Teodorović [20] [Greedy]; 6. Nikolić and Teodorović [20] [BCO]; 7. Zhao et al. [21]; 8. Buba and Lee [23]; 9. Proposed DE-PSO.In Table6, the proposed hybrid DE-PSO (last column) outperformed the DE in terms of d0 for all cases considered. In addition, the DE-PSO algorithm achieves the best result in terms of d0 and d1 compared with previous studies in the case of route sets containing 4 and 12 bus lines. In the case of route sets with 8 and 12 bus lines, the hybrid algorithm outperformed the previous results in terms of Cp. The hybrid DE-PSO achieves the minimum transfer time of all passengers in four out of the five cases as compared with the previous studies. Furthermore, the proposed hybrid DE-PSO is able to produce significant improvement in Co, as reflected by the required fleet evidencing the high quality of solutions obtained. Zhao et al. [21] have the best value for d0 for cases of 6, 7, and 8 bus lines. However, they have some of the worse results for Cp in the literature.As mentioned previously, the UTNDP is a complex problem, given the two conflicting objectives that influence each other: higher frequencies would improve the passenger cost, but this will increase the operator cost. Consequently, Arbex and da Cunha [12] observed that it is not enough to report the best solution found in terms of percentage of direct trips (d0) and the one that minimizes the number of buses, as these two objectives are related. Hence, there is a set of solutions known as Pareto optimal solutions for the UTNDP, which represent the compromise solutions between the conflicting objectives [45]. The computational results of the Pareto front and the node sequence of the best routes found in the Pareto front by the proposed algorithm are given in Tables 7 and 8, respectively.Table 7
The Pareto front obtained by the hybrid DE-PSO.
Solution
Bus lines
Passenger cost (Cp)
Passenger cost above lower bound
Fleet size (Co)
d
0
d
1
d
un
Maximum route headway (min)
Average route headway (min)
Average in-vehicle travel time (min)
Average passenger cost (min)
Average waiting time (min)
1
8
184,841
29,051
89
96.59
3.41
0.00
11.34
6.300
10.18
11.87
1.26
2
10
190,003
34,213
82
97.17
2.83
0.00
12.30
8.488
10.24
12.20
1.31
3
6
190,732
34,942
80
95.12
4.88
0.00
8.00
5.915
10.48
12.25
1.35
4
7
192,581
36,791
79
95.18
4.82
0.00
10.99
7.136
10.62
12.37
1.39
5
9
193,115
37,325
78
98.20
1.20
0.00
10.50
6.812
10.79
11.40
1.21
6
6
193,456
37,666
76
94.99
5.01
0.00
7.71
6.003
10.80
12.43
1.43
7
7
194,898
39,108
75
97.75
2.25
0.00
12.00
7.493
10.84
12.52
1.44
8
7
195,359
39,569
73
95.05
4.95
0.00
12.32
8.830
10.88
12.55
1.45
9
6
196,365
40,575
71
93.38
6.62
0.00
8.00
6.177
10.97
12.61
1.47
10
5
198,027
42,237
68
92.94
7.06
0.00
8.00
5.724
11.02
12.72
1.48
11
5
200,940
45,150
67
94.99
5.01
0.00
8.00
6.160
11.05
12.91
1.49Table 8
Node sequence of routes found in pareto solutions.
Bus line
Routes
Fleet size (Co)
Passenger cost (Cp)
8
6−14−7−5−3−4−1−0
12
184,841
7−5−3−11
6
0−1−2−5−7−9−13−12
14
6−14−5−2−1−4
7
13−9−12−10−11−3−5
22
12−9−7−5−3−4−1
6
8−14−7−5−3−1−0
5
8−14−6−9−10−11−3−5
17 (89)
10
0−1−4−3−11−10
16
190,003
7−9−6−14−5−2−1−0
8
4−3−1−2−5−7−14−8
5
8−14−7−9−12−10−11−3
10
13−9−12−10−11−3
7
4−1−3−11−10−9−12
14
2−1−3−5−7−9−10
4
0−1−2−5−7−9−10−12
7
12−9−6
6
9−13−12−10
5 (82)
6
13−12−9−7−14−8
9
190,732
11−10−9−7−5−2−1−0
21
0−1−4−3−11−10−12−13
18
10−11−3−1−2−5−14−6
10
3−11−10−12−13−9−6
15
12−13−9−7−5−3−4
7 (80)
7
0−1−2−5−7−9−12−13
16
192,581
9−13−12−10−11−3−4
20
8−14−5−2−1−0
8
0−1−2−5−3−11−10−9
13
3−4−1−2−5−14−6−9
9
4−3−5−7−9−13
7
8−14−5−7−9−12−13
6 (79)
9
1−2−5−7−9−12−13
7
193,115
0−1−3−5−7−9−12−13
9
5−7−14−6−9−12−10−11
11
0−1−4−3−11−10−9−6
10
4−3−11−10−9−6−14−8
12
13−12−9−10−11−3−5−2
13
0−1−4−3−5
4
8−14−5−2−1−3
6
0−1−2−5−14−6
6 (78)
6
0−1−2−5−7−9−12
14
193,456
8−14−6−9−7−5−3−1
15
3−4−1−2−5−14−6−9
7
0−1−3−11−10−12−9
6
12−13−9−10−11−3−4−1
19
8−14−5−3−11−10−12−9
15 (76)
7
12−13−9−10−11−3−5−2
13
194,898
3−4−1−2−5
7
5−7−9−12−10−11−3−4
18
0−1−4−3−5−7−9−6
10
0−1−2−5−7−9−12−10
7
0−1−2−5−14−6−9−10
5
11−10−12−13−9−6−14−8
15 (75)
7
6−9−7−5−2−1−0
5
195,359
0−1−3−11−10−12−9−13
23
2−5−3−11
6
0−1−2−5−14−6−9−12
6
1−3−11−10−9−7−5
7
0−1−3−11−10−9−7−5
20
8−14−6−9−7−5−3−4
6 (73)
6
0−1−4−3−5−2
8
196,365
3−11−10−12−9−6−14−8
22
8−14−7−5−3−11−10−9
14
13−9−6−14−5−2−1−3
9
12−9−7−5−2−1−3
7
12−10−9−7−5−2−1−0
11 (71)
5
8−14−6−9−7−5−3−4
15
198,027
0−1−2−5−7−9−10−11
10
13−12−9−7−5−3−1−0
23
8−14−5−3−1−0
11
13−12−10−11−3−5−14−6
9 (68)
5
13−9−7−5−3−11
15
200,940
8−14−5−7−9−10−11
9
10−9−6−14−5−2−1−4
7
0−1−2−5−7−9−13−12
14
0−1−4−3−11−10−9−12
22 (67)In Table7, some important performance indicators, including average route headways, in-vehicle travel times, and the maximum route headways are determined. Headways are useful indications of how frequent public transit service is, and therefore the waiting time of the passengers. Note that for these indicators, we do not have existing results to compare with our results. The maximum and average route headway lie between (7.71, 12.32) and (5.724, 8.830) minutes, respectively. The proposed hybrid DE-PSO solution produced more than one route choice for most OD pairs, as implied by the low values for average waiting times, which are significantly less than average route headways.For the Mandl’s Swiss network, the lower bound on the in-vehicle travel time is 155,790 minutes [17]. The lower bound represents the theoretical minimum possible passenger time if passengers incurred no waiting time or transfer penalties and were able to take a vehicle that followed the shortest path from their origin to their destination. If operator cost is not an issue and there is no maximum frequency constraint, then it is possible to achieve a total generalized passenger cost that is arbitrarily close to this limit. Table 7 (column 4) provides the additional passenger time above the theoretical minimum for the hybrid DE-PSO. In this table, the hybrid DE-PSO produced solutions that are 18.65% to 28.98% closer to the theoretical minimum passenger time.The Pareto frontier for the various solutions achieved from Table8 with passenger cost on the vertical axis and the number of buses required on the horizontal axis is depicted in Figure 6. Efficient frontier solutions are highlighted in dark crosses, whereas past literature results are author-labeled. It can be observed that the passenger cost for the best compromising solutions is lower than the previously published results, evidencing the high quality of the solutions obtained by the proposed hybrid DE-PSO algorithm.Figure 6
Comparison of solutions from hybrid DE-PSO with solutions from the literature.


## 5.2.2. Rivera City Network

To demonstrate the scalability of the proposed hybrid DE-PSO, we applied the proposed algorithm to solve a real-size public transportation network of Rivera City (see Figure7). This case study belongs to a medium-size city of 65,000 citizens in Northern Uruguay. It comprises 84 nodes, 143 arcs, and 378 OD pairs. Because we do not have the optimal number of transit routes for the network under study, therefore, we considered the minimum number of routes is 40 and the maximum number of routes is 60, whereas the minimum and the maximum numbers of nodes per route are 10 and 30 base on preliminary run. In addition, all of the parameters in Table 1 are utilized in this methodology, except the maximum allowable fleet size, which to the best of our knowledge is not available.Figure 7
Rivera city network.The hybrid approach produced solutions with maximum and minimum fleet size (operator cost) of 126 and 86 buses, respectively (see Table9). This implies a variation of 32% in the cost between the two extreme solutions; however, it leads to an increase in the passenger cost by 34%. In Figure 8, the inherent conflict between the network bus fleet size and passenger cost that makes it difficult to find a unique optimal solution is depicted. The different trade-offs between the competing objectives are established and it is left for the decision-maker to attain a biased solution either to the passenger or the operator. It is important to note that it is difficult (impossible) to minimize passenger and operator costs at the same time. Furthermore, the overall passenger travel demand is satisfied with at most one transfer. The maximum and average route headway lie between (2.05, 8.20) and (1.21, 6.31) minutes, respectively. The proposed hybrid DE-PSO solution produced more than one route choice for most OD pairs, as implied by the low values for average waiting times, which are significantly less than average routes headways.Table 9
The Pareto front obtained by the hybrid DE-PSO for the Rivera city network.
Solution
Bus lines
Passenger cost (Cp)
Fleet size (Co)
d
0
d
1
d
un
Maximum route headway (min)
Average route headway (min)
Average waiting time (min)
1
46
211.56
86
80.61
19.39
0.00
8.20
6.31
1.94
2
47
199.64
88
79.52
20.48
0.00
7.32
6.26
1.81
3
49
183.73
91
85.24
14.76
0.00
6.45
5.09
1.62
4
50
178.42
93
82.45
17.55
0.00
6.21
4.92
1.46
5
51
165.31
94
82.25
17.75
0.00
5.26
4.02
1.53
6
53
161.43
96
85.35
14.65
0.00
4.12
3.23
1.47
7
54
159.74
98
91.25
8.75
0.00
2.61
1.86
1.50
8
55
148.62
105
93.67
6.33
0.00
3.33
1.60
1.51
9
58
144.25
110
93.73
6.27
0.00
2.18
1.57
1.50
10
60
138.86
126
93.86
6.14
0.00
2.05
1.21
1.50Figure 8
Solutions from hybrid DE-PSO for the Rivera city network.


## 6. Conclusions and Future Research

In this article, the UTNDP is tackled through a hybrid DE-PSO algorithm taking into consideration the interest of both passenger and operator. The problem is modeled as a multiobjective optimization problem with the aim to simultaneously optimize the route configuration and the associated service frequencies that produce a minimum total passengers’ and operators’ costs while satisfying a given set of constraints. The proposed hybrid DE-PSO algorithm is designed to adapt the strength of both approaches to achieve better quality solutions. Experimental studies are conducted to evaluate the relative efficiency of hybrid DE-PSO and hybrid PSO-DE where both algorithms are capable of determining efficient solutions. The hybrid DE-PSO algorithms adopted for further comparative studies as it obtained better quality solutions than the hybrid PSO-DE. In addition, comparisons are made between the proposed hybrid DE-PSO algorithm with other approaches from the literature using the benchmark Mandl’s Swiss network. Furthermore, the proposed hybrid DE-PSO algorithm is applied to a public transport system of the Rivera City network. The computational results of the proposed hybrid DE-PSO algorithm improve over the results obtained from the previous studies. As a multiobjective optimization problem, we have shown that the proposed hybrid DE-PSO produces a diverse set of nondominated solutions. The results also dominated solutions from previous studies in the literature. The application of the proposed hybrid DE-PSO to larger and more realistic problem instances with heterogeneous buses will be the direction of future research.



---

*Source: 5963240-2019-12-31.xml*