Collaborative ant colony algorithm for online regional bus scheduling

Abstract

An online regional bus scheduling model is proposed which focuses on the dynamic regulation of scheduling according to changes in the external environment, dynamic occurrences and periodic encounters of traffic incidents that interfere with the timely completion of vehicle trips. This paper employs fuzzy and random numbers to reflect uncertain delays as a result of meeting yard capacity constraints and other practical factors. A collaborative ant colony algorithm is employed to address the premature convergence defects of a traditional ant colony algorithm and to define the construct rules, pheromones, heuristic information and selection strategies of solutions. Finally, the validity of the proposed model and algorithm is verified by a numerical example.

Keywords

Online regional bus scheduling regional problems fuzzy and random travel time collaborative ant colony algorithm

1 Introduction

Regional bus scheduling problems (RBSP) [9]primarily involve the assignment of trips to several bus routes through numerous depots in order to minimize cost by inserting deadhead trips between depots to share vehicle resources. As compared to traditional single-line bus scheduling, RBSP achieve a unified scheduling that significantly improves vehicle utilization according to non-uniform departure frequencies for different routes in a given period. Bertossi and Carraresi [1] have proven that RBSP are NP-hard problems.

Currently, scholars worldwide are primarily investigating RBSP with static travel times [2 , 25]. However, traffic jams or other uncertain events may cause delay times for vehicles which interfere with trip completion and which can lead to deviations between the plan and actual operation. Hence, there is an urgent need to explore uncertainty RBSP in order to create a scheme that is adaptable to changes in traffic environment. Generally, trip completion delays are very difficult to predict in advance. Problems in which delay time is assumed as an uncertain variable are regarded as RBSP with uncertain travel times (RBSPUTT). Most scholars investigate RBSPUTT with the assumption that statistical distribution of travel time is obtainable by analyzing historical operational data. The primary related research can be divided into two categories, as follows.

RBSPUTT in relatively stable traffic environments has been widely investigated, though the resultant scheme is rarely disrupted by uncertain events, and is highly reliable in uncertain environments. Huisman and Albert [7, 8] first investigated RBSPUTT in order to predict a fixed future travel time. Based on their work, Ming Wei [14, 15] studied a more reasonable RBSPUTT with random travel times. Ming Wei [16] also proposed another multi-vehicle RBSPUTT with grey travel time and additionally [17] proposed a chance-constrained programming model of regional bus scheduling with fuzzy travel times. However, such studies do not incorporate dynamic adjustments in their scheme failuremechanisms.

RBSPUTT in unstable traffic environments has been investigated in order to analyze how real-time adjustment infeasible schemes fail in the event of certain occurrences interfering with timely vehicle trip completion. Such a dynamic RBSP, which is related to online scheduling, is referred to as an online RBSP (ORBSP). At present, online scheduling is relatively mature in its relationship to job shop scheduling and vehicle route problems [3 , 23]. Scholars generally use three dynamic strategies to reschedule upon scheme failure, including robust, prediction, and complete response scheduling. However, ORBSP has not been widely studied.

Since historical data may not always be available to determine the distribution function of the travel time in real traffic situations, the use of fuzzy random numbers to represent such uncertain variables is more realistic. This paper constructs a fuzzy random expectation model for ORBSPSTT based on analysis of an online VRP [24], in consideration of dynamically-generated uncertainties and real world encounters which may interfere with vehicle trip completion. The primary objective of the present study is to minimize operating costs to meet certain constraints such as vehicle completion of two trips, fueling and depot capacity, etc. Solutions are obtained by the use of a collaborative ant colony algorithm, based on the fuzzy stochastic simulation technique, which provides feasible solution construction method, pheromone trails, heuristic information, and transition rules to eliminate contradictions between accelerating convergences and to avoid stagnation. Furthermore, a numerical example is provided to verify the validity of the proposed model and algorithm.

2 Mathematical model

Definition 1. [22] Setting ξ as the fuzzy random variable based on Ω and defining f as a real-valued continuous function upon $R$ considers the fuzzy random event f (ξ) ≤0, the credibility of which may be defined as Cr {f (ξ) ≤0}.

Definition 2. [22] Setting ξ as the fuzzy random variable, based on Ω and defining f as real-valued continuous function upon $R$ , if fuzzy random event f (ξ) ≤0 is considered, average chance of the event may be defined as $Ch {f (ξ) \leq 0} = \int_{0}^{1} P {ω \in Ω | Cr {f (ξ) \leq 0} \geq p} dp$ , in which the function P (•) is the probability of the event •.

Definition 3. [22] By setting ξ as the fuzzy random variable based on probability space (Ω, ∑, P (·)), the expected value of ξ may be defined as $E [ξ] = \int_{0}^{\infty} Ch {ξ \geq r} dr - \int_{- \infty}^{0} Ch {ξ \leq r} dr$

2.1 Assumption

If one trip can be covered immediately before another trip by the same bus, its delay time for the vehicle completing a trip, caused by uncertainties dynamically generated and encountered in traffic environment, is fuzzy random variable.

There are enough vehicles in each depot. A vehicle must begin each trip on time in its starting point.

Each bus begins its first task with a full tank of fuel whose consumption is not linked to driver behavior and traffic congestion, only related to mileage:

2.2 Decision variable

${RT}_{d}^{k} = {x_{1}, x_{2}, \dots, x_{| {RT}_{d}^{k} |}}$ and $T_{d}^{k} = {x_{1}, x_{2}, \dots, x_{| T_{d}^{k} |}}$ denotes a ordered sequence of trips that have been complete and will be served by each vehicle ∀k ∈ V_d, beginning and ending at depot∀d ∈ D.

2.3 Parameters

D stands for a set of depots. For each depot ∀d ∈ D, V_d and capacity_d respectively stand for all vehicles departing from the depot and itscapacity.

T = CT ∪ UT = {T₁, T₂, ⋯ , T_|T|} stands for a set of trips corresponding to the fixed timetable of different lines, where CT and UT stand for all trips that have been performed or have not been performed by vehicles when a traffic incident occurs to interfere with a vehicle to complete a sequence of trips one by one on time. To compete each trip ∀T_i ∈ T, a vehicle must depart from the depot sp_{T
_i} at time st_{T
_i} and arrive at the depot dp_{T
_i} at the terminationtime et_{T
_i}.

If dis (dp_{x
_i-1}, sp_{x
_i}) >0, the process that a vehicle travels to sp_{x
_i} of $\forall x_{i} \in T_{d}^{k}$ from dp_{x
_i-1} of $\forall x_{i - 1} \in T_{d}^{k}$ with no load is called Deadhead Trip (DH Trip).

y_{x
_i} stands for whether the vehicle ∀k ∈ V_d may be fueled up at sp_{x
_i} of $\forall x_{i} \in T_{d}^{k}$ in time ST. DD is the maximum travel distance of the vehicle without fuel make-up.

z_{x
_i} stands for whether the vehicle could be delayed a fuzzy random time ΔT_{x
_i} by uncertain events to complete the trip $\forall x_{i} \in T_{d}^{k}$ . p_{x
_i} is the probability of occurrence of the event.

c₁ is vehicle cost, including depreciation, warranty, insurance and management fees, etc.; c₂ is fuel cost.

|x| stands for the number of the elements of the set x.

2.4 Objective function

$\begin{matrix} min E [f (x, ξ)] = c_{1} \sum_{\forall d \in D} | V_{d} | \\ + c_{2} [\sum_{\forall d \in D} \sum_{\forall k \in V_{d}} \sum_{\forall x_{i} \in {RT}_{d}^{k} \cup T_{d}^{k}} dis ({dp}_{x_{i - 1}}, {sp}_{x_{i}}) \\ + \sum_{\forall T_{i} \in T} dis ({sp}_{T_{i}}, {dp}_{T_{i}})] \end{matrix}$ (1)

2.5 Constraint condition

$\begin{matrix} st . \\ E [g (x, ξ)] = {\begin{matrix} V_{p} \cap V_{q} = Ø, \forall p, q \in D (2) \\ [\underset{\forall d \in D, \forall k \in V_{d}}{\cup} {RT}_{d}^{k}] \cup [\underset{\forall d \in D, \forall k \in V_{d}}{\cup} T_{d}^{k}] = CT \cup UT = T (3) \\ T_{p}^{u} \cap T_{q}^{v} = Ø, \forall u \in V_{p}, \forall v \in V_{q} (4) \\ | V_{d} | \leq {capacity}_{d}, \forall d \in D (5) \\ \sum_{u \leq i \leq v} [dis ({sp}_{x_{i}}, {dp}_{x_{i}}) + dis ({dp}_{x_{i}}, {sp}_{x_{i + 1}})] > DD, \\ \exists x_{u}, x_{v} \in {RT}_{d}^{k} \cup T_{d}^{k}, y_{x_{u}} = y_{x_{v}} = 1 (6) \\ t_{x_{i}}^{k} = {et}_{x_{i - 1}} + time ({dp}_{x_{i - 1}}, {sp}_{x_{i}}) + z_{x_{i - 1}} \cdot p_{x_{i - 1}} \cdot Δ T_{x_{i - 1}} \leq {st}_{x_{i}}, \forall x_{i} \in T_{d}^{k} (7) \end{matrix} \end{matrix}$

Formula (1) represents the objective function of the problem, which aims to discover the optimal rebuilt scheduling scheme that includes the vehicle, deadhead kilometers and fixed mileage expenses. Formula (2) assumes that a vehicle only belongs to one depot. Formula (3) indicates that all trips will be completed by vehicles. Formula (4) expresses that each trip is assigned to exactly one vehicle and that a single vehicle cannot run two trips simultaneously. Formula (5) ensures that a maximum given number of backup vehicles are dispatched from a single depot. Formula (6) guarantees that a vehicle has adequate fuel to cover a series of trips between two adjacent gas points (i.e., depots). Formula (7) predicts whether two separate trips could be accomplished by a single vehicle.

3 Collaborative ant colony algorithm applied to ORBSPFSTT

Ant colony optimization (ACO) [6 , 19], proposed by Dorigo and Stützle in 1991, is a swarm intelligence algorithm that functions by simulating the foraging behavior of an ant colony. However, little research has taken into account the collaborative foraging behavior of ants. Hence, this paper proposes a collaborative ant colony algorithm to solve ORBSPSTT, in which each ant communicates with its fellows by marking the vertices it passes. If another ant responds to the original ant by following the route marked by the original ant, the two ants will collaborate to build a tour.

In order to address the problem characteristics, a hybrid intelligent algorithm based on the fuzzy stochastic simulation technique is designed to solve the fuzzy random expectation model of ORBSPSTT, which defines the solution building rule, pheromones, heuristic information and selection strategy in the graph G_C = (C, L) (C = {i| ∀ T_i ∈ UT} , L = {(i, j) | ∀ T_i, T_j ∈ UT}).

3.1 Solution building

According to the proposed algorithm, several ants collaborate in order to build a feasible scheduling scheme as follows:

Step 1. For $\forall T_{i}^{'} \in G_{C}$ , set $cur (T_{i}^{'}) = Ø, pre (T_{i}^{'}) = Ø$ and $nex (T_{i}^{'}) = Ø$ . Each ant ∀k ∈ M is randomly placed at different vertices $\exists T_{i}^{'} \in G_{C}$ , let $cur (T_{i}^{'}) \neq Ø$ and $T_{k} = {T_{i}^{'}}$ .

Step 2. Set M′ = M.

Step 3. For a randomly selected ant ∀k ∈ M′, determine the set $preTrips (T_{1}^{'})$ of previous trips completed by the corresponding vehicle before its first trip $T_{1}^{'} \in T_{k}$ is completed, and determine the set $nexTrips (T_{| T_{k} |}^{'})$ of next trips completed by the vehicle after it completes its last trip $T_{| T_{k} |}^{'} \in T_{k}$ . Select a trip $T_{h}^{'}$ in $preTrips (T_{1}^{'})$ and $nexTrips (T_{| T_{k} |}^{'})$ at a certain probability. If $T_{h}^{'} \neq Ø$ ,∃z ∈ M′ (z ≠ k) and $T_{h}^{'} \in T_{z}$ , set M = M - {z}, M′ = M and T_k = T_k ∪ T_z; otherwise set $T_{k} = T_{k} \cup {T_{h}^{'}}$ . Set $nex (T_{h}^{'}) \neq Ø$ ( $nex (T_{| T_{k} |}^{'}) \neq Ø$ ), $pre (T_{1}^{'}) \neq Ø (pre (T_{h}^{'}) \neq Ø$ ), $cur (T_{h}^{'}) \neq Ø$ and M′ = M′ - {k}, and turn to Step 4.

For each ant ∃k ∈ M′, the generation of $preTrips (T_{1}^{'})$ is similar to that of $nexTrips (T_{| T_{k} |}^{'})$ . The former is taken as an example to describe the procedure as follows:

For $\forall T_{i}^{'} \in G_{C}$ , if $cur (T_{i}^{'}) = Ø$ and ${et}_{T_{i}^{'}} + time ({dp}_{T_{i}^{'}}, {sp}_{T_{1}^{'}}) \leq {st}_{T_{1}^{'}}$ , then $preTrips (T_{i}^{'}) = preTrips (T_{i}^{'}) \cup {T_{i}^{'}}$ .

For each ant ∀i ∈ M (i ≠ k), find first trip $T_{i 1}^{'} \in T_{i}$ and last trip $T_{i | T_{k} |}^{'} \in T_{i}$ currently performed by the corresponding vehicle. Under the constraint of (3-5)–(3-7), if ${et}_{T_{i 1}^{'}} + time ({dp}_{T_{i 1}^{'}}, {sp}_{T_{1}^{'}}) \leq {st}_{T_{1}^{'}}$ , then $preTrips (T_{i}^{'}) = preTrips (T_{i}^{'}) \cup {T_{i 1}^{'}}$ ; if ${et}_{T_{i | T_{k} |}^{'}} + time ({dp}_{T_{i | T_{k} |}^{'}}, {sp}_{T_{1}^{'}}) \leq {st}_{T_{1}^{'}}$ , then $preTrips (T_{i}^{'}) = preTrips (T_{i}^{'}) \cup {T_{i | T_{k} |}^{'}}$ .

Step 4. If M′≠ Ø, turn to Step 3, otherwise, turn to Step 5.

Step 5. For $\exists T_{i}^{'} \in G_{C}$ , if $cur (T_{i}^{'}) \neq Ø, M = M \cup {New ant}$ , turn to Step 2; otherwise, turn to Step 6.

Step 6. Output the result and terminate the algorithm.

Obviously, the solution built in the above way is feasible.

3.2 Pheromone τ_ij and heuristic information η_ij

$η_{ij} = \frac{1}{[({st}_{i} - t_{i}^{j}) + γ \cdot time ({dp}_{ψ (j)}, {sp}_{i}) \cdot exp (ξ (i, j)) + 0.01]}$ represents the compensation for selecting vehicle j to complete trip i, apt to selecting less waiting and deadhead time. γ is a constant, mainly used to prevent the denominator from 0. ξ (u, v) means: $ξ (u, v) = {\begin{matrix} w ({sp}_{u}, {st}_{u}), w ({sp}_{u}, {st}_{u}) \geq 0 \\ \land w ({dp}_{ψ (v)}, {et}_{ψ (v)}) \geq 0 \\ w ({dp}_{ψ (v)}, {et}_{ψ (v)}), w ({sp}_{u}, {st}_{u}) \\ \geq 0 \land w ({dp}_{ψ (v)}, {et}_{ψ (v)}) < 0 \\ 0, w ({sp}_{u}, {st}_{u}) < 0 \end{matrix}$ (8)

Definition 4. For a certain timetable, the difference between the number of the vehicles dispatched and the number of the vehicles arrived at the depot ∀d ∈ D by the time t is the deficit function of the yard, recorded w (d, t).

3.3 Selection strategy

In the process of artificial ant k building a solution to solving the problem, the vehicle j is selected to complete the trip i according to the pseudo-random proportional rule in Formula (9), where α and β are respectively the relative influence of the pheromone and heuristic information. $j = {\begin{matrix} \underset{j \in allowed}{arg max {τ_{ψ (j) i} [η_{ij}]^{β}}}, \begin{matrix} if & q \leq q_{0} \end{matrix}; \\ p_{ij}^{k} = \frac{τ_{ψ (j) i}^{α} (t) η_{ij}^{β}}{\sum_{l \in allowed} τ_{ψ (l) i}^{α} (t) η_{il}^{β}}, others . \end{matrix}$ (9)

3.4 Pheromone update rule

Pheromone decides the possibility of the artificial ant to along the selected path. The amount of pheromones is related to the pheromone trail deposited by ants and its volatility mechanism. The pheromone update rule may be divided into the local update described by Formula (10) and the global update described by Formula (11); the former is employed for each trail edge passed by the ant, while the latter is applied to the best global ant. $τ_{ij} \leftarrow (1 - ξ) τ_{ij} + ξ Q / f^{nn}$ (10) $τ_{ij} \leftarrow (1 - ρ) τ_{ij} + ρ Q / f^{bs}, \forall (i, j) \in T^{bs}$ (11) where ρ ∈ (0, 1) is the volatility coefficient, ξ ∈ (0, 1) and Q are parameters, f^bs is the length of the tour built by the best ant at a point in time.

3.5 Processing of the objective function and constraints with fuzzy random variables

As described above, fuzzy random variables appear in both the objective function and the constraints. According to fuzzy stochastic expected programming [4 , 21] first proposed by Liu, a simulation technique can be used to respectively calculate the fuzzy stochastic expected values. The objective function E [f (x, ξ)] is used as an example to describe the proposed procedure. Assume that the randomness of fuzzy random variable ξ of E [f (x, ξ)] is dependent on γ, according to the probability distribution Pr of γ. Select N samples ω_i (i = 1, 2, …, N) from the sample space Ω, and calculate $E [f (x, ξ)] = (1 / N) \sum_{i = 1}^{N} E [f (x, ξ (ω_{i}))]$ . E [f (x, ξ (ω_i))] can be obtained by fuzzy simulation, detailed asfollows.

Step 1. For the given arbitrary small positive number ɛ, a series of θ₁, θ₂, ⋯ , θ_M may be evenly obtained by the random number generation technique from the possible space of ξ, if Pos (θ_k) ≥ ɛ(k = 1, 2, …, M), set a = f (x, ξ (θ₁)) ∧ (x, ξ (θ₂)) ∧ ⋯ ∧ f (x, ξ (θ_M)) and b = f (x, ξ (θ₁)) ∨ f (x, ξ (θ₂)) ∨ ⋯ ∨ f (x, ξ (θ_M)).

Step 2. Generate a series of random variables r₁, r, ⋯ , r_M from U (a, b). Let $g = \sum_{k = 1}^{M} η_{k} Cr (f (x, ξ (ω_{i})) \leq r_{k})$ so that E [f (x, ξ (ω_i))] = a ∨ 0 + b ∧ 0 + (b/M - a/M), where $η_{k} = {\begin{matrix} - 1, r_{k} \geq 0 \\ 1, r_{k} \leq 0 \end{matrix}$ .

3.6 Algorithm flow chart

4 Computational example

There are five unified lines in the region operated by a bus company. The lines and their fixed timetables are detailed in Tables 1 and 2. The deadhead information is provided in Table 3. The probability of a vehicle completing a trip and its fuzzy stochastic delay time are described in Table 4. Other parametersinclude c₁ = 506.3 yuan/vehicle, c₂ = 2.52 yuan/km, DD = 280km, ST= 25 min and capacity_i = 15.

This paper used Matlab to employ ACO programming to solve the proposed problem, and relevant parameters were set by default as follows: maximum iterations = 500, the number of artificial ants = 40, Q= 200, q₀= 0.9, α= 1, β= 2, ρ=ξ= 0.1. The Monte Carlo method was employed to simulate dynamic stochastic information for six emergencies that were randomly encountered. For instance, when the current scheme is invalid, based on the “greedy strategy” all trips that have not been completed shall be regarded as having new starting points to reconstruct a best scheme. According to calculation, the following is obtained:

The optimal solution of the initial scheme free from emergencies is 17241.6.

When z₄₃= 1, trip 43 shall be regarded as having a new starting point, and the minimum operating cost of the new trip is expected to be 17266.8.

When z₆= 1 and z₁₆₈= 1, such emergencies will not affect the current scheme.

When z₁₆₉= 1, such emergencies may cause a certain vehicle to fail to complete the separate trips 169 and 21, resulting in the failure of the scheme. In this case, the minimum operating cost is expected to be 17342.4.

When z₁₀₂= 1, such emergencies may interfere with a certain vehicle which will fail to complete trips 102 and 140 in turn, and the minimum operating cost of the regenerated scheme is expected to be 17405.4.

When z₆₈= 1, such emergencies will not influence the current scheme and all vehicles shall operate accordingly.

The vehicle arrangements results are presented in Table 5. There are 24 vehicles assigned to complete 238 trips by refueling 24 times (six times at depot A, eight times at depot B and ten times at depot C) and by executing 93 deadhead trips (27, 25, 4, 20, 5 and 12 times between depots AB, AC, BA, BC, CA, and CB, respectively). All vehicles exhibited a total waiting time of 4330 minutes, 2240 minutes of deadhead time and 13830 minutes of total working time.

Additionally, standard and improved ACO may be run in the same instance a total of ten times under conditions that are free from the influence of emergencies. The ptimization curve of their average values is shown in Fig. 3. The performance difference between the two algorithms is 0.13%. Standard ACO will stop searching for a better solution after 182 iterations while the improved algorithm finds the best solution after 337 iterations. However, the solution found by the improved algorithm at the 203rd iteration is better than that determined by standard ACO, indicating that the proposed algorithm is more able to leave the local optimum in the later period of the iterative process. This is because the improved algorithm simulates the collaborative foraging behavior of ants to construct feasible solutions, in which random interactions between ants results in less dependence on pheromones to construct solutions, thus expanding the search space and increasing the diversity of the population.

5 Conclusions

By considering dynamically-generated emergencies that may be periodically encountered in a traffic environment, this paper proposes a fuzzy random expectation model of ORBSPFSTT and designs a collaborative ant colony algorithm to solve the model. When the current scheme becomes invalid, based on the “greedy strategy” all trips that have not been completed shall be regarded as having new starting points in order to reconstruct an optimal scheme. This study is of great importance to the daily management of bus companies. However, it also exhibits the following disadvantages.

A fixed timetable is the foundation of the model. However, dynamically-generated emergencies may result in imbalances in transport capacity and volume, leading to the failure of the timetable. Hence, a flexible timetable-based ORBSP would be a more accurate reflection of reality.

The proposed model does not investigate the reliability in ORBSP. When the current scheme becomes invalid, the newly-generated scheme is still unable to adapt to environmental changes. Hence, it is of great importance to generate a bus scheduling scheme of low cost and high reliability.

Conflict of interest

This article content has no conflict of interest.

Footnotes

Acknowledgments

This paper is funded by the National Natural Science Foundation of China (61503201); Natural Science Foundation of the Jiangsu Province in China (BK20161280); the Humanities and Social Sciences Foundation of the Ministry of Education in China (16YJCZH086); Natural Science Foundation of the Jiangsu High Education (15KJB580011); Nantong Science and Technology Innovation Program (GY12015025); Project of excellent graduate innovation in Hebei province (2016348).

References

Bertossi

A.A.

and Carraresi

, On some matching problems arising in vehicle scheduling models, Networks17 (1987), 271–281.

Haghani

and Banihashemi

, Heuristic approaches for solving large-scale bus transit vehicle scheduling problem with route time constraints, Transportation Research36 (2002), 309–333.

Riise

, Mannino

and Burke

E.K.

, Modelling and solving generalised operational surgery scheduling problems, Computers & Operations Research66 (2016), 1–11.

Liu

and Liu

Y.K.

, Expected value of fuzzy variable and fuzzy expected value models, IEEE Trans on Fuzzy Systems4 (2002), 445–450.

Ribeiro

C.C.

and Soumis

, A column generation approach to the multiple-depot vehicle scheduling problem, Operations Research42 (1994), 41–52.

Costa

and Hertz

, Ants can colour graphs, Journal of the Operational Research Society3 (1997), 295–305.

Huisman

, Freling

and Wagelmans

A.P.M.

, A solution approach for dynamic vehicle and crew scheduling, European Journal of Operational Research172 (2006), 453–471.

Huisman

, Freling

and Wagelmans

A.P.M.

, A robust solution approach to the dynamic vehicle and crew scheduling problem, Transporation Science38 (2004), 447–458.

Wang

D.Y.

, Zang

X.Y.

and Wang

H.X.

, Research on situation and developing trend for optimization theory and method of public transit vehicle scheduling problem, Journal of Beijing Jiaotong University13 (2008), 42–47.

10.

Rosenthal

E.C.

and Eisenstein

E.M.

, A rescheduling and cost allocation mechanism for delayed arrivals, Computers & Operations Research66 (2016), 20–28.

11.

Wang

H.X.

and Shen

J.S.

, Heuristic approaches for solving transit vehicle scheduling problem with route and fueling time constraints, Applied Mathematics and Computation190 (2007), 1237–1249.

12.

J.Q.

, Mirchandani

P.B.

and Borenstein

, A Lagrangian heuristic for the real-time vehicle rescheduling problem, Transportation Research Part E45 (2009), 419–433.

13.

Dorigo

and Stutzle

, Ant Colony Optimization, The MIT Press, 2004, pp. 2–264.

14.

Wei

, Sun

and Jin

W.Z.

, Bi-level programming model for uncertain regional bus scheduling problem, Journal of Transportation Systems Engineering and Information Technology2 (2013), 1–8.

15.

Wei

, Jin

W.Z.

and Sun

, Model and algorithm for regional bus scheduling with stochastic travel time, Journal of Highway and Transportation Research and Development10 (2011), 151–156.

16.

Wei

, Jin

W.Z.

and Sun

, Model and algorithm for regional bus scheduling with grey travel time, Journal of Transportation Systems Engineering and Information Technology12 (2012), 134–151.

17.

Wei

, Chen

X.W.

, Sun

and Zhou

Y.Y.

, Model and algorithm for resolving regional bus scheduling problems with fuzzy travel times, Journal of Intelligent & Fuzzy Systems29 (2015), 2689–2696.

18.

Kliewer

, Mellouli

and Suhl

, A time space network based exact optimization model for multi-depot bus scheduling, Eurpoean Journal of Operational Research175 (2006), 1616–1627.

19.

Chaharsooghi

S.K.

, An effective ant colony optimization algorithm for multiple objective resource allocation problem, Applied Mathematics Computation1 (2008), 167–177.

20.

Y.F.

, Xi

G.P.

, Yang

Y.X.

and Gong

, Model for global supply chain tactical plan based on fuzzy and random expectation planning, System Engineering Theory and Practice8 (2005), 1–9.

21.

Liu

Y.K.

and Liu

, Fuzzy random variables: A scalar expected value operator, Fuzzy Optimization and Decision Making2 (2003), 143–160.

22.

Liu

Y.K.

and Wang

S.M.

, Fuzzy and Random Optimization Theory, China Agricultural University Press, Beijing, (2006), pp. 45–271.

23.

Yin

, Cheng

T.C.E.

and Wang

D.J.

, Rescheduling on identical parallel machines with machine disruptions to minimize total completion time, European Journal of Operational Research252 (2016), 737–749.

24.

Zhang

, Huang

and Pu

X.Z.

, Model and algorithm for regional vehicle routing problem with random travel time, Journal of Industrial Engineering and Engineering Management3 (2006), 82–84.

25.

Liu

Z.G.

and Shen

J.S.

, Regional bus operation bi-level programming model integrating timetabling and vehicle scheduling, Systems Engineering Theory & Practice11 (2007), 135–141.

Collaborative ant colony algorithm for online regional bus scheduling

Abstract

Keywords

1 Introduction

2 Mathematical model

2.1 Assumption

2.2 Decision variable

2.3 Parameters

2.4 Objective function

3 Collaborative ant colony algorithm applied to ORBSPFSTT

3.1 Solution building

3.2 Pheromone τ ij and heuristic information η ij

3.6 Algorithm flow chart

4 Computational example

5 Conclusions

Conflict of interest

Footnotes

Acknowledgments

References

3.2 Pheromone τ_ij and heuristic information η_ij