Model and algorithm for resolving regional bus scheduling problems with fuzzy travel times

Abstract

Regional bus scheduling is necessary to urban public transport that is complicated by the necessity of assigning trips that belong to several routes to buses located at different depots while reducing fleet size and operating costs. Considering the reality of emergencies that may interfere with the ability of vehicles to complete trips on time, it is reasonable to use fuzzy numbers to express uncertain delay times. Based on this idea, this paper proposes a chance-constrained programming model of regional bus scheduling that will reflect additional constraints such as the capacities of related depots and fueling needs. The objective of this paper is to maximize utilization of fleet vehicles. To overcome the defect of premature convergence in the particle swarm optimization algorithm (PSO), an improved PSO is proposed by using an organic fusion with group search optimization. Finally, an example demonstrates the correctness and effectiveness of the model and algorithm.

Keywords

Urban traffic regional bus scheduling problem fuzzy travel time particle swarm optimization group search optimization

1 Introduction

In contrast to traditional single-depot bus scheduling, the regional bus scheduling problem (RBSP) [5] aims to achieve a unified schedule by sharing vehicle resources across all routes. This is accomplished by inserting deadhead trips between depots to assign trips belonging to several routes to buses located at different depots. Due to the non-uniformity of departure frequency for all routes in a given period, RBSP can significantly reduce operating costs and improve the efficient utilization of vehicles. Bodin and Golden [1] have proven the RBSP is an NP-hard.

Most scholars study RBSP using the optimal scheduling theory, which is divided into network flow [3 , 19] and set partitioning [4 , 11–13]. Most research into RBSP relies on established travel durations. However, conditions of real traffic environments, such as fluctuations in passenger loads at different time etc., cause deviations between the plan and actual operation, which make practical applications of RBSP difficult to analyze. In general, delays to trip completion are very difficult to predict in advance. Problems in which delay time is assumed to be an uncertain variable are RBSP with uncertain travel times (RBSPUTT). Research into RBSPUTT is rare [6 , 11–13]. Huisman and Albert studied RBSPUTT [6, 7] by assuming that future travel time is fixed or predicted in advance. Wei, et al. [11] studied a more realistic RBSPUTT with a stochastic travel time. Wei, et al. [12] proposed a multi-vehicle-type RBSPUTT with a grey travel time, as well as a bi-level programming model for uncertain regional bus scheduling that revealed the overall relationship between a scheduling plan and its procurement scheme [13]. However, these models are typically difficult to solve in practice because of a lack of sufficient reliable historical data to determine the distribution function of the random variable or predict future growth trends.

This paper studies an RBSP with fuzzy travel times (RBSPFTT), which assumes that travel time is an uncertain variable. In combination with the rich experience and knowledge of scheduling staff, fuzzy numbers can represent this type of uncertain information when provided with capacity constraints and other practical factors. In this case, the triangular fuzzy number is used to express the actual travel time; it is then transformed to the corresponding chance-constrained programming model. A new hybrid algorithm based on the fuzzy simulation is proposed to solve the model. Finally, an actual example calculates a bus scheme to test the correctness and effectiveness of the model and algorithm.

2 Mathematical model

2.1 Mathematical model

Each trip requires a bus to depart from its depot on time.

When historical data and expertise are considered, it is possible to use triangular fuzzy numbers to represent certain time delays for each bus trip not completed on time.

To ensure that a bus does not require refueling during daily operations, it should be fully fueled before or after the work day.

2.2 Decision variables

$T_{d}^{k} = {x_{1}, x_{2}, \dots, x_{| T_{d}^{k} |}}$ denotes a sequence of trips accomplished in turn by each bus ∀k ∈ V_d, which begins and ends at same depot ∀d ∈ D.

2.3 Decision variables

T = {T₁, T₂, …, T_|T|} denotes a given set of trips belonging to several routes. Each trip ∀T_i ∈ T requires uninterrupted driving from the starting point sp_{T
_i} at starting time st_{T
_i} to the ending point dp_{T
_i} at ending time et_{T
_i}.

D denotes a given set of depots. For each depot∀d ∈ D, let V_d denote a given set of buses initially located at the depot, and let capacity_d denote the capacity of the depot.

Each vehicle k (∀ k ∈ V_d, ∀ d ∈ D) arrives at the trip $\forall x_{i} \in T_{d}^{k}$ starting point sp_{x
_i} at the time indicated by $t_{x_{i}}^{k} = {et}_{x_{i - 1}} + Δ T_{x_{i - 1}} + time ({dp}_{x_{i - 1}}, {sp}_{x_{i}})$ . If time (dp_{x
_i-1}, sp_{x
_i}) ≠0, this situation is called a Deadhead Trip (DH Trip). In this situation, time (dp_{x
_i-1}, sp_{x
_i}) denotes the time spent in traveling from the ending point of the trip $\forall x_{i - 1} \in T_{d}^{k}$ to the starting point of the trip $\forall x_{i} \in T_{d}^{k}$ . ΔT_{x
_i} denotes the fuzzy delay time that prevents a vehicle from accomplishing a trip x_i on time.

a₀ denotes the weight of number of the buses.

a₁ denotes the weight of waiting time.

a₂ denotes the weight of the deadhead time.

Pos {•} denotes the possibility of the case {•}.

|x| denotes the number of elements in the set x.

2.4 Objective function equation

$min \bar{f}$ (1)

2.5 Constraint equations

$st . V_{p} \cap V_{q} = \emptyset \forall p, q \in D$ (2) $\underset{\forall d \in D, \forall k \in V_{d}}{\cup} T_{d}^{k} = T$ (3) $T_{p}^{u} \cap T_{q}^{v} = \emptyset \forall u \in V_{p}, \forall v \in V_{q}$ (4) $| V_{d} | \leq {capacity}_{d} \forall d \in D$ (5)

$\begin{matrix} P os {{et}_{x_{i - 1}} + time ({dp}_{x_{i - 1}}, {sp}_{x_{i}}) + Δ T_{x_{i - 1}} \\ \leq {st}_{x_{i}}} \geq α \forall d \in D, \forall k \in V_{d}, \forall x_{i} \in T_{d}^{k} \end{matrix}$ (6)

$\begin{matrix} Pos {f = a_{0} \sum_{k \in D} | V_{k} | + \sum_{k \in D} \sum_{u \in V_{k}} \sum_{x_{i} \in T_{k}^{u}} [a_{1} . ({st}_{x_{i}} - t_{x_{i}}^{u}) \\ + a_{2} . time ({dp}_{x_{i - 1}}, {sp}_{x_{i}})] \geq \bar{f}} \geq β \end{matrix}$ (7)

The objective function in Equation (1) aims to minimize the number of buses, the total waiting time, and the deadhead time. Equations (2–7) represent the constraints, as follows: Equation (2) ensures that each bus belongs to only one depot; Equation (3) ensures that all trips are successfully completed by all vehicles; Equation (4) expresses that each trip is assigned to exactly one vehicle, and a vehicle cannot simultaneously run two trips; Equation (5) ensures that no more than a given number of backup vehicles are dispatched from each depot; Equation (6) ensures that the possibility of two trips normally accomplished in turn by the same bus in the random environment is at least α; Equation (7) ensures that the confidence level of $\bar{f}$ representing the maximum value of f is at least β.

3 Group particle swarm optimization algorithm for RBSPFTT solution

Particle Swarm Optimization (PSO) [17] is an evolutionary bionic algorithm that simulates flying birds, with advantages including smaller numbers of individuals and simple calculation. PSO performs well in multi-dimensional continuous space optimizations, and provides very rapid local convergence to a stable state. The group search optimization (GSO) [16], recently proposed by S. He and Q.H. Wu, is a novel algorithm based on the social behavior of hunting animals, such as lions and wolves. The GSO performs well in local searches, and can maintain the diversity of the solution to promote the evolution of the population. Each algorithm has advantages and disadvantages. Their homologous natures determine that they should easily integrate with one another; however, current studies involving both algorithms are rare [15].

This paper proposes a Group Particle Swarm Optimization (GPSO) based on a fuzzy simulation to solve RBSPFTT. According to the problem characteristics, the definite scheme solution process is described, and the following terms are defined: particle encoding scheme, constraints handling, and position and velocity correction equation.

3.1 Particle code scheme

In GPSO, each individual or potential solution in the swarm is called a particle. Every particle has its own position and velocity, where the position vector can be decoded as a solution to the problem, and the velocity vector is in the direction of particle movement.

The position vector X = (x₁, x₂, …, x_|T|) is used to represent a potential solution of RBSPFTT [2, 10], wherein the i-th element is a trip x_i, which differs from other trips in the range 1 - |T|. Furthermore, V = (v₁, v₂, …, v_|T|) denotes the velocity vector, where the element v_i is a real number ranging from -|T| - |T|. If ∀x_i-1, x_i ∈ X meets constraint Equation (6), the bus will immediately execute trip x_i after it has accomplished trip x_i-1; otherwise, the two trips would be executed by different buses. Hence, each individual can be decoded into a sequence of trips accomplished by different buses according to Equation (6).

As mentioned above, any individual X satisfies constraints Equations (2–5). Therefore, if the individual X complies with constraints Equations (5–7), it is a feasible solution.

3.2 Fitness function

The fitness value, determined by the fitness function, is the standard according to which the merit of each particle position is evaluated. Each particle can be decoded into a set of trips finished by different vehicles. In this paper, Equation (1) is used as the fitness function to assess the quality of any individual. Because all individuals meet constraints Equations (2–4), constraint Equation (5) can be regarded as a penalty function to generate a new fitness function. $min \bar{f} + A \sum_{\forall d \in D} Max (| V_{d} | - {capacity}_{d}, 0)$ (8) where A, which is set of a sufficiently large number, denotes the penalty factor. The fitness function, expressed by Equation (8), ensures that an infeasible solution confers great fitness value and will be eliminated in the iteration.

3.3 Fuzzy objective function and handling constraints

Constraints Equations (6) and (7) with fuzzy parameters also determine the objective function Equation (8). Because the computer does not deal directly with fuzzy parameters, the fuzzy simulation technology proposed by Wu, et al. [18] can be used to examine its objective function and constraint with respective confidence levels of α and β.

According to the definition of fuzzy number arithmetic for vector ΔT_{x
_i} of a fuzzy delay time in a given decision vector X the establishment of Equation (6) holds if and only if there exists a clear vector $Δ T_{x_{i}}^{0}$ in the vector ΔT_{x
_i} that satisfies ${et}_{x_{i - 1}} + time ({dp}_{x_{i - 1}}, {sp}_{x_{i}}) + Δ T_{x_{i}}^{0} \leq {st}_{x_{i}}$ and $μ (Δ T_{x_{i}}^{0}) \geq a$ , where μ (•) is the membership function of the fuzzy set. That is to say, if ${et}_{x_{i - 1}} + time ({dp}_{x_{i - 1}}, {sp}_{x_{i}}) + Δ T_{x_{i}}^{0} \leq {st}_{x_{i}}$ , which uniformly generates vector $Δ T_{x_{i}}^{0}$ from fuzzy vector ΔT_{x
_i} in order to satisfy $μ (Δ T_{x_{i}}^{0}) \geq a$ , then Equation (6) is established. After a given number N of iterations, if vector $Δ T_{x_{i}}^{0}$ does not satisfy ${et}_{x_{i - 1}} + time ({dp}_{x_{i - 1}}, {sp}_{x_{i}}) + Δ T_{x_{i}}^{0} \leq {st}_{x_{i}}$ , then the decision vector X is considered to be impossible.

As mentioned above, the specific procedure of fuzzy Equation (6) is as follows:

Step 1: Uniformly generate vector $Δ T_{x_{i}}^{0}$ from fuzzy vector ΔT_{x
_i} at a horizontal cross-sectional level α;

Step 2: If ${et}_{x_{i - 1}} + time ({dp}_{x_{i - 1}}, {sp}_{x_{i}}) + Δ T_{x_{i}}^{0} \leq {st}_{x_{i}}$ , then the output is “feasible”;

Step 3: Repeat step 1 and 2 N times;

Step 4: Output “infeasible”.

Similarly, the specific procedure of fuzzy Equation (7) is as follows:

Step 1: Set $\bar{f} = - \infty$ ;

Step 2: Uniformly generate vector $Δ T_{x_{i}}^{0}$ from fuzzy vector ΔT_{x
_i} at a horizontal cross-sectional level β;

Step 3: If $\bar{f} \leq f$ , then $\bar{f} = f$ ;

Step 4: Repeat step 2 and 3 N times to calculate $\bar{f}$ ;

Step 5: Output $\bar{f}$ .

3.4 Formula for modifying position and updating velocity

In PSO, each particle updates itself by tracking the personal extreme value $f_{i}^{*} (t)$ and global extreme value $f_{g}^{*} (t)$ in every iteration. When all particles gather to the same location (that of the current best particle), its velocity approaches zero due to inertia, personal awareness and social consciousness. Each particle will then refuse to search the solution space in other regions.

To address the inadequacies of PSO, a concept derived from GSO is embedded in the search procedure for GPSO; this concept involves a random movement by a small number of rogue particles, wherein each particle generates a random head angle and distance and then moves to this new position. The number of randomly wandering particles is related to the diversity of the population. According to the process described above, the particle updates its velocity and position formula as follows:

$\begin{matrix} V_{i} (t + 1) & = & w \cdot V_{i} (t) + c_{1} \cdot rand \cdot (X_{i}^{*} (t) - X_{i} (t)) \\ + c_{2} \cdot rand \cdot (X_{g}^{*} (t) - X_{i} (t)) \end{matrix}$ (9) $X_{i} (t + 1) = {\begin{matrix} X_{i} (t) + V_{i} (t + 1), othes \\ X_{i} (t) + l_{i} D_{i}^{t} (φ^{t + 1}), rand > σ \end{matrix}$ (10)

where w, c₁ and c₂ denote the inertia factor, weight, and global optimal value, respectively;l_i ∈ [0, l_max], φ^t+1 ∈ [0, θ_max] and $D_{i}^{t} (φ^{t + 1})$ denote a random distance, head angle and the vector of the angle, respectively; and rand denotes a random number in the range [0, 1].

Definition 1. $σ = \frac{1}{N (N - 1)} \sum_{i \neq j, i, j = 1}^{N} c_{ij}$ denotes the population’s diversity where $c_{ij} = {\begin{matrix} 1, f_{i} \neq f_{j} \\ 0, otherwise \end{matrix}$ .

3.5 Algorithm flow

The detailed procedure for GPSO solving RBSPFTT is described as follows.

Step 1: Set the parameters of the algorithm.

Step 2: Let t = 0 and initialize the first generation of particle swarm.

Step 2.1: For each particle, randomly generate its position and velocity vector X_i (0) and V_i (0), and calculate its fitness value f_i (0).

Step 2.2: If $X_{i}^{*} (0) = X_{i} (0)$ , then $f_{i}^{*} (0) = f_{i} (0)$ to determine the extreme value of each particle.

Step 2.3: Find the global optimal particle $f_{g}^{*} (0) = min {f_{1}^{*} (0), \dots \dots, f_{n}^{*} (0)}$ .

Step 3: Let t = t+1, and update the current status of the t-th generation swarm.

Step 3.1: For each particle, update its position vector X_i (t) and velocity vector V_i (t), according to Equations (9) and (10).

Step 3.2: Recalculate the fitness value f_i (t). If $f_{i} (t) < f_{i}^{*} (t)$ , let $f_{i}^{*} (t) = f_{i} (t)$ and $f_{i}^{*} (t) = f_{i} (t)$ . If $f_{i} (t) < f_{g}^{*} (t)$ , let $f_{g}^{*} (t) = f_{i} (t)$ and $f_{g}^{*} (t) = f_{i} (t)$ .

Step 4: If the termination condition is satisfied, output $f_{g}^{*} (t)$ ; otherwise return to step 3.

4 Analysis of computational examples

A regional bus network is composed of three depots (capacity_d = 15, d = 1, 2, 3) and five routes. Tables 1–4 depict details of the test instance as follows: Tables 1 and 2 demonstrate the basic information and the fixed schedule of these lines; Table 3 depicts the deadhead time information; and Table 4 depicts the fuzzy delay time between two trips. Using a unified model for bus scheduling, a bus company will assign a certain number of vehicles to the three depots to complete a total of 210 trips while minimizing operation costs.

In order to verify the validity of the model and algorithms, the empirical parameters of GPSO are set as follows: the maximum number of iterations is 200, and the number of particles is 50. Let w = 0.75, c₁ = c₂ = 1.5, l_max = 5, θ_max = 45o, a₀ = 500, a₁ = 1, and a₂ = 2.5. Matlab was used to program GPSO to solve the RBSPFTT, and the simulation as repeated 50 times at confidence levels α= 1.0 and β= 0.9 on the same computer in order to avoid accidental phenomena. Table 5 indicates the simulation results. There are a total of five solutions. The optimal solution of f is equal to 19,950, the mean is equal to 19,964, and the variance is equal to 28.6. The best solution can be identified at 62% probability, a suboptimal solution can be identified at 22% probability, and the worst solution can be identified at 4% probability. Thus, GPSO can find a satisfactory solution in most cases.

Table 6 demonstrates the best schedule for the regional buses, and Fig. 1 shows the number of vehicles in each parking yard. Each bus follows a predefined trip sequence and is allowed to return to the starting point of the initial trip. That is to say, if a given trip must be assigned to a vehicle, the vehicle must arrive at a fixed time in advance of its starting time. In order to cover all of the trips in a fixed bus time table, 23 buses are required to execute a total of 85 deadhead trips, wherein:

9, 9, and 5 vehicles, respectively, are initially located at depots A, B, and C.

Deadhead trips occur 23, 6, 10, 4, 21, and 21 times between two depots.

The total working time for all buses is equal to 12,445 min. Their waiting and deadhead times are equal to 4,100 min. and 1,740 min., respectively.

The influence of the two parameters α and β on bus scheduling was also analyzed to study the effect of the fuzzy travel time feature on f. As parameter α decreases and parameter β increases, the number of pairs of feasible trips completed by a vehicle decreases; this leads to a further reduction in the feasible solution space consisting of these pairs, and the sub-solution space containing better solutions is abandoned. Ultimately, the cost of the scheme increases with less uncertainty. However, the scheme is less disturbed by emergencies, and less cost change occurs in the process of a real-time adjustment scheme. The results shown in Fig. 2 are consistent with visual analysis.

In order to verify the validity of the improved algorithms, a case study was calculated 50 times each with GPSO, PSO, and GSO. Figure 3 comparatively analyzes the average simulation results, with the conclusions as follows:

GPSO, PSO, and GSO require 210, 95, and 390 iterations, respectively, to converge to their optimal solutions. The differences in optimal solutions among them are 2.1% , 2.5% , and 4.6% , respectively. This indicates that GPSO performs better than PSO and GSO in convergence.

PSO obtains the optimal solution faster than GSO, but it easily converges to local optima. Hence, GPSO, which combines the advantages of the other two algorithms, can perform thermal simulations effectively. By judging the degree of prematurity to maintain swarm diversity, GPSO can not only yield a suboptimal solution quickly, but also jump from local optimization solutions by controlling the search space of particles. This indicates that GPSO performs more robustly than PSO and GSO.

5 Conclusions

The primary contribution of this paper is to propose a chance-constrained programming model for regional bus scheduling with fuzzy travel times. Compared to existing studies on RBSPUTT with random or grey travel times, the proposed model can avoid the defect of requiring a large amount of traffic data to determine the distribution function of uncertain travel times, making it easier to optimally solve in practice. The test case analyzed the influence of the fuzzy feature of travel time on bus scheduling, and results indicate that the scheme with less fuzziness of travel time is less disturbed by emergencies and has less cost change in a real-time adjustment scheme.

This paper also contributes to the design of a new hybrid GPSO algorithm, which combines the advantages of both PSO and GSO by embedding the concept of a small portion of particles to take a random walk out of the group into GSO, as occurs in the search procedure for PSO. The simulation indicates that, compared to PSO and GSO in convergence and robustness of the algorithm, GPSO can not only converge to a suboptimal solution quickly, but also jump from a local optimization solution by controlling the search space of particles.

Footnotes

Acknowledgments

This research was supported by the Major State Basic Research Development Program (973 program)(No.2012CB725402),the National Natural Science Foundation of China (Nos. 61503201 and 51178109), China Postdoctoral Science Foundation (No. 2013M540408), University Science Research Project of Jiangsu Province (Nos. 13KJB580008 and 15KJB580011), the Nantong Science and Technology Program (No. BK2014059). This support is gratefully acknowledged. However, all facts, conclusions, and opinions expressed here are solely the responsibility of the authors. The authors thank the anonymous referee for her/his helpful comments.

References

Bertossi

Carraresi

1987

On some matching problems arising in vehicle scheduling models

Networks 17 271 281

Hosseinabadi

AAR

2014

GELS-GA: Hybrid metaheuristic algorithm for solving multiple traveling salesman problem

The 14th IEEE ISDA 76 81

Haghani

Banihashemi

2002

Heuristic approaches for solving large-scale bus transit vehicle scheduling problem with route time constraints

Transportation Research 36 309 333

Ribeiro

Soumis

1994

Column generation approach to the multiple-depot vehicle scheduling problem

Operations Research 42 41 52

Wang

Zang

Wang

2008

Research on situation and developing trend for optimization theory and method of public transit vehicle scheduling problem

Journal of Beijing Jiaotong University 32 3 42 47

Huisman

Freling

Wagelmans

APM

2004

A robust solution approach to the dynamic vehicle and crew scheduling problem

Transportation Science 38 447 458

Huisman

Freling

Wagelmans

APM

2006

A solution approach for dynamic vehicle and crew scheduling

European Journal of Operational Research 172 453 471

Wang

Shen

2007

Heuristic approaches for solving transit vehicle scheduling problem with route and fueling time constraints

Applied Mathematics and Computation 190 1237 1249

Mirchandani

Borenstein

2009

Lagrangian heuristic for the real-time vehicle rescheduling problem

Transportation Research Part E 23 419 433

10.

Zhang

2015

A hybrid distribution algorithm based on membrane computing for solving the multi-objective multiple traveling salesman problem

Fundamental Information 136 3 199 208

11.

Wei

Jin

Sun

2011

Model and algorithm for regional bus scheduling with stochastic travel time

Journal of Highway and Transportation Research and Development 28 10 151 156

12.

Wei

Jin

Sun

2012

Model and algorithm for regional bus scheduling with grey travel time

Journal of Transportation Systems Engineering and Information Technology 12 0 134 151

13.

Wei

Sun

Jin

2013

Bi-level programming model for uncertain regional bus scheduling problem

Journal of Transportation Systems Engineering and Information Technology 12 2 1 8

14.

Kliewer

Mellouli

Suhl

2006

Time space network based exact optimization model for multi-depot bus scheduling

Eurpoean Journal of Operational Research 175 1616 1627

15.

Kang

Wang

2001

An Introduction to Natural Computation Shanghai

Shanghai Science and Technology Press

16.

Saunders

2009

Group search optimizer: An optimization algorithm inspired by animal searching behavior

IEEE Transactions on Evolutionary Computation 33 5 973 1001

17.

Xie

Zhang

Yang

2003

Overview of particle swarm optimization

Control and Decision 18 2 129 135

18.

Liu

Wang

2006 Fuzzy Stochastic Optimization Theory China Agricultural University Press

Beijing

19.

Liu

Shen

2007

Regional bus operation bi-level programming model integrating timetabling and vehicle scheduling

Systems Engineering Theory & Practice 11 135 141