# Bus Dispatching Interval Optimization Based on Adaptive Bacteria Foraging Algorithm

Authors: Zhong-hua Wei; Xia Zhao; Ke-wen Wang; Yan Xiong
Journal: Mathematical Problems in Engineering
 (2012)

---

## Abstract

The improved bacterial foraging algorithm was applied in this paper to schedule the bus departing interval. Optimal interval can decrease the total operation cost and passengers’ mean waiting time. The principles of colony sensing, chemotactic action, and improved foraging strategy made this algorithm adaptive. Based on adaptive bacteria foraging algorithm (ABFA), a model on one bus line in Hohhot city in China was established and simulated. Two other algorithms, original bacteria foraging algorithm (BFA) and genetic algorithm (GA), were also used in this model to decide which one could greatly accelerate convergence speed, improve searching precision, and strengthen robustness. The final result showed that ABFA was most feasible in optimizing variables.


---

## Body

## 1. Introduction

Traffic demand becomes increasingly higher with the great development of social economy and urbanization. With the large amount of private cars and limited road facilities, severe traffic congestion occurs inevitably. Municipal governments and road transport authority have strongly recommended public transportation for its higher passenger capacity and smaller coverage area. So it is necessary to improve the quality of bus dispatching management, and a wholesome and intelligent bus scheduling scheme is needed.Bus interval scheduling is a complex optimization problem for its nonlinear and multiobjective characteristics. It requires traffic planners to take round consideration of multi-interests, such as bus operating enterprises and passengers. The relationship between the two is contradictory. Obviously, bus operating enterprises always try to dispatch buses as few as possible with the longest intervals and the highest profit, whereas passengers are the opposite. According to the two contradictory characteristics, an optimal bus dispatching interval model is urgent to be established to benefit both sides.As to the optimal algorithms, lots of intelligent algorithms have been adopted to solve transportation optimal problems [1]. Intelligent algorithms enlightened by bacterium have become fashionable recently. Back to the history of bacteria foraging algorithm (BFA), it was initially proposed in 2002 by Passino [2] and applied to dealing with several engineering problems [3–5] successfully. However, it was limited to solo modal function optimization for its poor convergence behavior. So effort to pursue more adaptive algorithms goes on. Muñoz et al. [6] proposed some methods to simplify the algorithm while maintaining its core elements. These included the simplification of the algorithm architecture, the elimination of the bacteria colony scale, a clear adaptation rule for the step size, the use of a uniform distribution the position initialization, and the removal of the cell-to-cell communication. In 2008, Dasgupta et al. [7] mathematically analyzed the chemotactic step of a one-dimensional BFA and proposed the adaptive step size for BFA. In the same year, Chen et al. [8] analyzed how the run length unit parameter controlled the exploration and exploitation process of BFA and then employed the adaptive search strategy to significantly improve the performance of the original algorithm.In this paper, the adaptive bacteria foraging algorithm was adopted to solve the complex bus interval dispatching problem. Many variables were taken into consideration such as dispatching interval, waiting time, load factor, economic efficiency, and trip service level. Among them, dispatching interval was chosen as the control variable. To compare which one was the best, genetic algorithm [9] (GA) and nonadaptive bacteria foraging algorithm (BFA) were employed in optimizing this model. The simulation results, focusing on minimizing two specific objective functions, depicted the advantages of the mentioned algorithm.The rest of the paper is organized as follows. Section2 gives brief views of basic and adaptive bacteria foraging algorithm. The theoretical optimal model for bus dispatching interval is built in Section 3. Based on this model, the simulations on ABFA, GA, and BFA are given in Section 4. Finally, Section 5 gives the conclusions.


## 2. Adaptive Bacteria Foraging Algorithm

### 2.1. Basic Bacteria Foraging Algorithm

To forage food, a bacterium needs to communicate with the group with its sensing abilities. By generating common knowledge, developing group identity and recognizing the identity of other colonies, bacterium engages in group decision-making [10]. A sort of collective intelligence subsequently occurs. And this wit consists of four steps: chemotaxis, swarming, reproduction, and elimination and dispersal [11–13].(1) Chemotaxis
Basically, chemotaxis is a foraging strategy that implements a type of local optimization where the bacteria try to climb up the nutrient concentration [7]. Swimming and tumbling are two aspects of this step. The bacterium’s flagella rotation determines its foraging direction in an anticipated route (swimming) or an unexpected one (tumbling). φ(j) stands for the unit random length in the direction of a tumble, that is,
(2.1)θi(j+1,k,l)=θi(j,k,l)+C(i)φ(j),
where θi(j,k,l) means the ith bacteria’s jth chemotactic behavior at the kth reproductive and lth elimination step. C(i) represents the step size adopted in the random route in a tumble. And C is labeled as run length unit.(2) Swarming
It is assumed that bacterium tends to inform others of its optimal food path, so group can locate food area more swiftly. Swarming gathers bacterium into high-density group and then forage food in a type of concentric circle, that is,(2.2)Jcc=∑i=1SJcci(θ,θi(j,k,l))=∑i=1S[-dattractexp(-wattract∑m=1P(θm-θmi)2)]+∑i=1S[hrepellentexp(-wrepellent∑m=1P(θm-θmi)2)],
where Jcci(θ,θi(j,k,l)) is the cost function value to be minimized;  S  is the bacterium scale;  P  is the number of parameters to be optimized. dattract, wattract, hrepellent, and wrepellent are different coefficients that are to be chosen carefully.(3) Reproduction
The least healthy bacterium vanishes, and the other healthiest bacterium splits into two and are released in the same position. This makes the population of bacteria constant.(4) Elimination and Dispersal
Possibly in the current surroundings, bacterium’s life span changes slightly either by nutrient supplements or other unexpected influence. Accidents can kill some bacteria colonies in one second. But this has the effect of assisting in chemotaxis.


### 2.2. Adaptive Bacterial Foraging Algorithm

BFA is adaptive by adjusting the run length step parameter dynamically during its execution process to balance the exploration or exploitation search [14]. Each bacterium has two different foraging states in ABFA model.(1)
Exploration: imprecisely explore the regions never gone before quickly in the search space in a large run length unit.(2)
Exploitation: exploit the potential regions slowly in its immediate vicinity in a small run length unit.The self-adaptive search is given in pseudocode in Table1 below.Table 1
Pseudocode for dynamic self-adaptive strategy [17, 18].
(1)FOR(each bacterium i) IN PARALLEL
(2)IF (Criterion-1) then
(3)Ci(t+1)=Ci(t)/α;   // exploitation
(4)εi(t+1)=εi/β;
(5)ELSE IF (Criterion-2) then
(6)Ci(t+1)=Cinitial;    // exploration
(7)εi(t+1)=εinitial;
(8)ELSE
(9)Ci(t+1)=Ci(t);
(10)εi(t+1)=εi;
(11)END IF
(12) END FOR IN PARALLEL
Where Criterion-2: exploration state; Criterion-1: exploitation state;t: the current iterations; α,β: default constants; Ci(t): current run-length unit of theith bacteria; εi(t): the desired precision in the current iteration of theith bacteria; Cinitial: the original run length unit; εinitial: the original precision.


### 2.3. Algorithm Flowchart of ABFA

The flowchart of ABFA is listed below.Step 1.
Initialize parameters like bacterium scaleS, custom constants n,  α, and  β, run length step Cinitial and precision εinitial, and position of bacterium colony.Step 2 (chemotaxis and swarming).
In this process, the signaling concentration (fitness value) released on every path will be calculated. Bacterium will choose paths that own the highest fitness value.Step 3 (reproduction).
Sort by the bacteria colony’s fitness values. The best half of the population undergoes reproduction. And the rest are eliminated to accelerate convergence speed.Step 4 (elimination and dispersal).
The wholesome adaptive bacteria colony migrate to other spaces randomly to expand the diversity of the colony.Step 5 (judgment).
If the current iteration is lower than the max iterations, then go to Step2; if not, the algorithm loop ends.The algorithm flowchart is given below in Figure1, where, S—the colony scale; t—the current iterations; Ns—the max iterations in the current nutrient gradient; Xi—the current location in searching space of the ith bacteria; flagi—the number of times that bacteria’s fitness value has no continuous improvement.Figure 1
Flowchart of ABFA [15].


## 2.1. Basic Bacteria Foraging Algorithm

To forage food, a bacterium needs to communicate with the group with its sensing abilities. By generating common knowledge, developing group identity and recognizing the identity of other colonies, bacterium engages in group decision-making [10]. A sort of collective intelligence subsequently occurs. And this wit consists of four steps: chemotaxis, swarming, reproduction, and elimination and dispersal [11–13].(1) Chemotaxis
Basically, chemotaxis is a foraging strategy that implements a type of local optimization where the bacteria try to climb up the nutrient concentration [7]. Swimming and tumbling are two aspects of this step. The bacterium’s flagella rotation determines its foraging direction in an anticipated route (swimming) or an unexpected one (tumbling). φ(j) stands for the unit random length in the direction of a tumble, that is,
(2.1)θi(j+1,k,l)=θi(j,k,l)+C(i)φ(j),
where θi(j,k,l) means the ith bacteria’s jth chemotactic behavior at the kth reproductive and lth elimination step. C(i) represents the step size adopted in the random route in a tumble. And C is labeled as run length unit.(2) Swarming
It is assumed that bacterium tends to inform others of its optimal food path, so group can locate food area more swiftly. Swarming gathers bacterium into high-density group and then forage food in a type of concentric circle, that is,(2.2)Jcc=∑i=1SJcci(θ,θi(j,k,l))=∑i=1S[-dattractexp(-wattract∑m=1P(θm-θmi)2)]+∑i=1S[hrepellentexp(-wrepellent∑m=1P(θm-θmi)2)],
where Jcci(θ,θi(j,k,l)) is the cost function value to be minimized;  S  is the bacterium scale;  P  is the number of parameters to be optimized. dattract, wattract, hrepellent, and wrepellent are different coefficients that are to be chosen carefully.(3) Reproduction
The least healthy bacterium vanishes, and the other healthiest bacterium splits into two and are released in the same position. This makes the population of bacteria constant.(4) Elimination and Dispersal
Possibly in the current surroundings, bacterium’s life span changes slightly either by nutrient supplements or other unexpected influence. Accidents can kill some bacteria colonies in one second. But this has the effect of assisting in chemotaxis.


## 2.2. Adaptive Bacterial Foraging Algorithm

BFA is adaptive by adjusting the run length step parameter dynamically during its execution process to balance the exploration or exploitation search [14]. Each bacterium has two different foraging states in ABFA model.(1)
Exploration: imprecisely explore the regions never gone before quickly in the search space in a large run length unit.(2)
Exploitation: exploit the potential regions slowly in its immediate vicinity in a small run length unit.The self-adaptive search is given in pseudocode in Table1 below.Table 1
Pseudocode for dynamic self-adaptive strategy [17, 18].
(1)FOR(each bacterium i) IN PARALLEL
(2)IF (Criterion-1) then
(3)Ci(t+1)=Ci(t)/α;   // exploitation
(4)εi(t+1)=εi/β;
(5)ELSE IF (Criterion-2) then
(6)Ci(t+1)=Cinitial;    // exploration
(7)εi(t+1)=εinitial;
(8)ELSE
(9)Ci(t+1)=Ci(t);
(10)εi(t+1)=εi;
(11)END IF
(12) END FOR IN PARALLEL
Where Criterion-2: exploration state; Criterion-1: exploitation state;t: the current iterations; α,β: default constants; Ci(t): current run-length unit of theith bacteria; εi(t): the desired precision in the current iteration of theith bacteria; Cinitial: the original run length unit; εinitial: the original precision.


## 2.3. Algorithm Flowchart of ABFA

The flowchart of ABFA is listed below.Step 1.
Initialize parameters like bacterium scaleS, custom constants n,  α, and  β, run length step Cinitial and precision εinitial, and position of bacterium colony.Step 2 (chemotaxis and swarming).
In this process, the signaling concentration (fitness value) released on every path will be calculated. Bacterium will choose paths that own the highest fitness value.Step 3 (reproduction).
Sort by the bacteria colony’s fitness values. The best half of the population undergoes reproduction. And the rest are eliminated to accelerate convergence speed.Step 4 (elimination and dispersal).
The wholesome adaptive bacteria colony migrate to other spaces randomly to expand the diversity of the colony.Step 5 (judgment).
If the current iteration is lower than the max iterations, then go to Step2; if not, the algorithm loop ends.The algorithm flowchart is given below in Figure1, where, S—the colony scale; t—the current iterations; Ns—the max iterations in the current nutrient gradient; Xi—the current location in searching space of the ith bacteria; flagi—the number of times that bacteria’s fitness value has no continuous improvement.Figure 1
Flowchart of ABFA [15].


## 3. Theoretical Optimal Model Building

Bus scheduling is a complex optimal problem influenced by varied external environment. According to the specific and available data on bus dispatching, the following hypothesis was made to establish a simulated model [15].(1)
The type of buses was identical. They were well operated and dispatched strictly according to bus schedule, with no accidents on the road.(2)
Passengers’ traffic flow volume at a bus line was independent of each other; their arrival distribution followed a uniform distribution.(3)
The dispatching interval of every two successive buses was identical in a given period.(4)
The trip cost unit for passengers and operation cost unit for bus operating enterprises were fixed.A certain bus line with its upstream travel direction was selected as the scheduling object. The whole operating time was divided into several one-hour intervals. And the theoretical optimization model was given below.(1) Control Variable
Bus dispatching interval was chosen as control variable.(2) Objective Function
Minimum bus operating cost and minimum passengers’ waiting cost were two optimal objectives. In formula (3.1), f1 represented the operation cost bus enterprises invested one day; in (3.2), f2 represented the trip cost passengers invested one day; in (3.3), f represented the final minimum function with weighting coefficients given:
(3.1)f1=∑k=1K(tk/Δtk)ts/((tmax+tmin)/2),(3.2)f2=∑k=1K∑j=1Jmj×ρkjΔtk2/∑k=1K∑j=1JUkj(tmax+tmin)/2,(3.3)f=min(η×f1+τ×f2),
where tk is time duration at kth interval; k=max/min means the upper or lower bound of bus interval; k=s means the whole operating time span one day; Δtk is the kth dispatching interval; mj is passenger volume at the jth site; ρkj,  ukj is the density of passenger flow or passenger volume arriving at the jth site in the kth interval; Ukj is the getting off at the jth site in the kth interval; η,  τ is weighting coefficient.(3) Standard Constraint Condition
Formula (3.4) represented the mean bus load factor to be more than 75%; formula (3.5) represented dispatching interval to be between the lower and upper bounds; (3.6) represented condition to ensure profitability for bus enterprises.Standard constraint condition(3.4)∑k=1k∑j=1JUkjQ×∑k=1K(tk/Δtk)≥75%,(3.5)tmin≤Δtk≤tmax,(3.6)∑k=1k∑j=1JUkj∑k=1K(tk/Δtk)≥2.5×L,
where Q is the rated passenger capacity of a bus; K is time set K={1,…,k,…K}, K is the total time intervals; J is site set J={1,…,j,…J}, J is the amount of bus sites of a line; L is the length of the total bus line.


## 4. Practical Simulation Based on Optimal Model

A bus line in its upstream travel direction in Hohhot city in China was selected as the scheduling object. Several relevant data had been investigated and listed as follows: the number of total sites wasJ=34 sites; the operation period was 6:00–20:00 and divided into K=14 hours; the lower and upper bounds of bus dispatching interval were tmin=2 min and tmax=15 min, with the rated passenger capacity Q=100 persons.


### 4.1. Passenger Traffic Flow and Basic Data on Bus Site Facilities

Data on passenger volume in each site of the upstream line were shown in Table2 and adjacent sites distance and average running time between them were displayed in Table 3.Table 2
Passenger volume in each site.
Time period
Passengersget in
Passengersget off
Time period
Passengersget in
Passengersget off
06:01–07:00
98
52
13:01–14:00
69
78
07:01–08:00
74
105
14:01–15:00
85
90
08:01–09:00
83
97
15:01–16:00
49
45
09:01–10:00
54
52
16:01–17:00
63
81
10:01–11:00
85
69
17:01–18:00
78
93
11:01–12:00
52
44
18:01–19:00
89
96
12:01–13:00
48
45
19:01–20:00
79
59Table 3
Adjacent site’s distance and average running time between sites.
Site no.
Adjacent site’s distance (m)
Running time (min)
Site no.
Adjacent site’s distance (m)
Running time (min)
1
0
0
18
397
1.87
2
406
2.375
19
562
3.6
3
308
1.28
20
491
2.85
4
562
3.7
21
374
1.73
5
461
2.75
22
259
1.25
6
364
1.54
23
376
1.65
7
347
1.37
24
549
3.2
8
570
3.3
25
523
3.0
9
440
2.5
26
1100
6.7
10
389
2.1
27
563
3.25
11
607
3.7
28
395
1.95
12
709
4
29
397
1.94
13
533
3.1
30
426
2.75
14
604
3.4
31
407
2.25
15
552
3.5
32
714
5.1
16
385
1.75
33
199
0.8
17
546
3.2
34
424
2.5


### 4.2. Simulation Results and Analysis

The bus dispatching interval optimal model was built and simulated on ABFA comparison with GA and BFA. First, basic settings were initialized: the population scale was 40. The maximum iterations was 1000.α=β=10. Cinitial=0.1. εinitial=100. The parameters of BFA and GA were similarly set. Three graphs showing convergence trend were given in Figure 2.Figure 2
The convergence trend based on 3 algorithms [16].It could be drawn from Figure2 that ABFA was the best one to accelerate convergence speed, improve searching precision, and strengthen robustness. So with the desired algorithm, latest bus interval was calculated in Table 4. Each bus departure interval was Δt1=4; Δt2=3; Δt3=4; Δt4=5; Δt5=5; Δt6=5; Δt7=5; Δt8=6; Δt9=6; Δt10=5; Δt11=4; Δt12=3; Δt13=4; Δt14=6.Table 4
Bus dispatching interval schedule based on ABFA.
Interval
Bus departure schedule
Departure times
1
6:00
:04
:08
:12
:16
:20
:24
:28
:32
15
:36
:40
:44
:48
:52
:56
2
7:00
:03
:06
:09
:12
:15
:18
:21
:24
20
:27
:30
:33
:36
:39
:42
:45
:48
:51
:54
:57
3
8:00
:04
:08
:12
:16
:20
:24
:28
:32
15
:36
:40
:44
:48
:52
:56
4
9:00
:05
:10
:15
:20
:25
:30
:35
:40
12
:45
:50
:55
5
10:00
:05
:10
:15
:20
:25
:30
:35
:40
12
:45
:50
:55
6
11:00
:05
:10
:15
:20
:25
:30
:35
:40
12
:45
:50
:55
7
12:00
:05
:10
:15
:20
:25
:30
:35
:40
12
:45
:50
:55
8
13:00
:06
:12
:18
:24
:30
:36
:42
:48
10
:54
9
14:00
:06
:12
:18
:24
:30
:36
:42
:48
10
:54
10
15:00
:05
:10
:15
:20
:25
:30
:35
:40
12
:45
:50
:55
11
16:00
:04
:08
:12
:16
:20
:24
:28
:32
15
:36
:40
:44
:48
:52
:56
12
17:00
:03
:06
:09
:12
:15
:18
:21
:24
20
:27
:30
:33
:36
:39
:42
:45
:48
:51
:54
:57
13
18:00
:04
:08
:12
:16
:20
:24
:28
:32
15
:36
:40
:44
:48
:52
:56
14
19:00
:06
:12
:18
:24
:30
:36
:42
:48
10
:54
Total bus departure times
190


## 4.1. Passenger Traffic Flow and Basic Data on Bus Site Facilities

Data on passenger volume in each site of the upstream line were shown in Table2 and adjacent sites distance and average running time between them were displayed in Table 3.Table 2
Passenger volume in each site.
Time period
Passengersget in
Passengersget off
Time period
Passengersget in
Passengersget off
06:01–07:00
98
52
13:01–14:00
69
78
07:01–08:00
74
105
14:01–15:00
85
90
08:01–09:00
83
97
15:01–16:00
49
45
09:01–10:00
54
52
16:01–17:00
63
81
10:01–11:00
85
69
17:01–18:00
78
93
11:01–12:00
52
44
18:01–19:00
89
96
12:01–13:00
48
45
19:01–20:00
79
59Table 3
Adjacent site’s distance and average running time between sites.
Site no.
Adjacent site’s distance (m)
Running time (min)
Site no.
Adjacent site’s distance (m)
Running time (min)
1
0
0
18
397
1.87
2
406
2.375
19
562
3.6
3
308
1.28
20
491
2.85
4
562
3.7
21
374
1.73
5
461
2.75
22
259
1.25
6
364
1.54
23
376
1.65
7
347
1.37
24
549
3.2
8
570
3.3
25
523
3.0
9
440
2.5
26
1100
6.7
10
389
2.1
27
563
3.25
11
607
3.7
28
395
1.95
12
709
4
29
397
1.94
13
533
3.1
30
426
2.75
14
604
3.4
31
407
2.25
15
552
3.5
32
714
5.1
16
385
1.75
33
199
0.8
17
546
3.2
34
424
2.5


## 4.2. Simulation Results and Analysis

The bus dispatching interval optimal model was built and simulated on ABFA comparison with GA and BFA. First, basic settings were initialized: the population scale was 40. The maximum iterations was 1000.α=β=10. Cinitial=0.1. εinitial=100. The parameters of BFA and GA were similarly set. Three graphs showing convergence trend were given in Figure 2.Figure 2
The convergence trend based on 3 algorithms [16].It could be drawn from Figure2 that ABFA was the best one to accelerate convergence speed, improve searching precision, and strengthen robustness. So with the desired algorithm, latest bus interval was calculated in Table 4. Each bus departure interval was Δt1=4; Δt2=3; Δt3=4; Δt4=5; Δt5=5; Δt6=5; Δt7=5; Δt8=6; Δt9=6; Δt10=5; Δt11=4; Δt12=3; Δt13=4; Δt14=6.Table 4
Bus dispatching interval schedule based on ABFA.
Interval
Bus departure schedule
Departure times
1
6:00
:04
:08
:12
:16
:20
:24
:28
:32
15
:36
:40
:44
:48
:52
:56
2
7:00
:03
:06
:09
:12
:15
:18
:21
:24
20
:27
:30
:33
:36
:39
:42
:45
:48
:51
:54
:57
3
8:00
:04
:08
:12
:16
:20
:24
:28
:32
15
:36
:40
:44
:48
:52
:56
4
9:00
:05
:10
:15
:20
:25
:30
:35
:40
12
:45
:50
:55
5
10:00
:05
:10
:15
:20
:25
:30
:35
:40
12
:45
:50
:55
6
11:00
:05
:10
:15
:20
:25
:30
:35
:40
12
:45
:50
:55
7
12:00
:05
:10
:15
:20
:25
:30
:35
:40
12
:45
:50
:55
8
13:00
:06
:12
:18
:24
:30
:36
:42
:48
10
:54
9
14:00
:06
:12
:18
:24
:30
:36
:42
:48
10
:54
10
15:00
:05
:10
:15
:20
:25
:30
:35
:40
12
:45
:50
:55
11
16:00
:04
:08
:12
:16
:20
:24
:28
:32
15
:36
:40
:44
:48
:52
:56
12
17:00
:03
:06
:09
:12
:15
:18
:21
:24
20
:27
:30
:33
:36
:39
:42
:45
:48
:51
:54
:57
13
18:00
:04
:08
:12
:16
:20
:24
:28
:32
15
:36
:40
:44
:48
:52
:56
14
19:00
:06
:12
:18
:24
:30
:36
:42
:48
10
:54
Total bus departure times
190


## 5. Conclusions

In this paper, an interval optimal model was applied into one bus line in Hohhot city in China. The bus interval dispatching issue was considered as a nonlinear and multiobjective optimization. The enterprise profits, load factor, and dispatching interval were particularly chosen as the primary parameters in this optimization. Two relevant objective functions were defined. The proposed optimal algorithm, ABFA, combined colony sensing, chemotactic action, and improved foraging strategy to solve the distributed bacterial optimization. For comparison purpose, two other algorithms, GA and BFA, were employed to decide which was the best one. Furthermore, extensive sight would be thrown years ahead to evaluate the practical merits of ABFA in traffic and transportation optimization problems.



---

*Source: 389086-2012-12-12.xml*