Journal Home > Volume 2 , Issue 3
Complex System Modeling and Simulation 2022, 2(3): 238-252 https://doi.org/10.23919/CSMS.2022.0012
Open Access | Issue | Published: 30 September 2022

A Discrete Artificial Bee Colony Algorithm for Stochastic Vehicle Scheduling

Show Author's Information Yuanyuan Li1,  Yindong Shen1( ),  Jingpeng Li2
Key Laboratory of Image Processing and Intelligent Control, School of Artificial Intelligence and Automation, Huazhong University of Science and Technology, Wuhan 430074, China
Division of Computer Science and Mathematics, University of Stirling, Stirling, FK9 4LA, UK
Keywords:
public transportation, stochastic vehicle scheduling, discrete artificial bee colony, search scheme
Cite this article:
Li Y, Shen Y, Li J. A Discrete Artificial Bee Colony Algorithm for Stochastic Vehicle Scheduling. Complex System Modeling and Simulation, 2022, 2(3): 238-252. https://doi.org/10.23919/CSMS.2022.0012
Download citation
EndNote(RIS)
BibTeX

600

Views

31

Downloads

Citations

4

Crossref

N/A

WoS

4

Scopus

N/A

CSCD

Abstract Full text About this article

Vehicle scheduling plays a profound role in public transportation. Especially, stochastic vehicle scheduling may lead to more robust schedules. To solve the stochastic vehicle scheduling problem (SVSP), a discrete artificial bee colony algorithm (DABC) is proposed. Due to the discreteness of SVSP, in DABC, a new encoding and decoding scheme with small dimensions is designed, whilst an initialization rule and three neighborhood search schemes (i.e., discrete scheme, heuristic scheme, and learnable scheme) are devised individually. A series of experiments demonstrate that the proposed DABC with any neighborhood search scheme is able to produce better schedules than the benchmark results and DABC with the heuristic scheme performs the best among the three proposed search schemes.


menu
Abstract
Full text
Outline
About this article

A Discrete Artificial Bee Colony Algorithm for Stochastic Vehicle Scheduling

Show Author's information Yuanyuan Li1, Yindong Shen1( ), Jingpeng Li2
Key Laboratory of Image Processing and Intelligent Control, School of Artificial Intelligence and Automation, Huazhong University of Science and Technology, Wuhan 430074, China
Division of Computer Science and Mathematics, University of Stirling, Stirling, FK9 4LA, UK

Abstract

Vehicle scheduling plays a profound role in public transportation. Especially, stochastic vehicle scheduling may lead to more robust schedules. To solve the stochastic vehicle scheduling problem (SVSP), a discrete artificial bee colony algorithm (DABC) is proposed. Due to the discreteness of SVSP, in DABC, a new encoding and decoding scheme with small dimensions is designed, whilst an initialization rule and three neighborhood search schemes (i.e., discrete scheme, heuristic scheme, and learnable scheme) are devised individually. A series of experiments demonstrate that the proposed DABC with any neighborhood search scheme is able to produce better schedules than the benchmark results and DABC with the heuristic scheme performs the best among the three proposed search schemes.

Keywords: public transportation, stochastic vehicle scheduling, discrete artificial bee colony, search scheme

References(36)

1
A. Wren, A review of computer scheduling of buses and crews, in Proc. PTRC Seminar, London, UK, 1968, pp. 42–47.
2
M. Hickman, P. Mirchandani, and S. Voss, eds., Computer-Aided Systems in Public Transport. Berlin, Germany: Springer, 2008.
DOI
3
A. Ceder, Public Transit Planning And Operation: Theory, Modelling, and Practice. Burlington, MA, USA: Butterworth-Heinemann, 2007.
DOI
4

Y. Shen, J. Xu, and J. Li, A probabilistic model for vehicle scheduling based on stochastic trip times, Transportation Research Part B, vol. 85, pp. 19–31, 2016.
DOI Google Scholar
5

P. G. Furth and T. H. J. Muller, Service reliability and optimal running time schedules, Transportation Research Record, vol. 2034, no. 1, pp. 55–61, 2007.
DOI Google Scholar
6
Kittelson and Associates, Inc., Transit capacity and quality of service manual, Technical report, Transportation Research Board, Washington, DC, USA, 2003.
7

M. Salicrú, C. Fleurent, and J. M. Armengol, Timetable-based operation in urban transport: Run-time optimisation and improvements in the operating process, Transportation Research Part A:Policy &Practice, vol. 45, no. 8, pp. 721–740, 2011.
DOI Google Scholar
8
P. G. Furth, B. Hemily, T. H. J. Muller, and J. G. Strathman, Using archived AVL-APC data to improve transit performance and management, Technical report, Transportation Research Board of the National Academies, Washington, DC, USA, 2006.
9
T. H. J. Muller and P. G. Furth, Integrating bus service planning with analysis, operational control and performance monitoring, presented at ITS America 10th Annual Meeting and Exposition: Revolutionary Thinking, Real Results, Washington, DC, USA, 2000.
10

J. Zhao, M. Dessouky, and S. Bukkapatnam, Optimal slack time for schedule-based transit operations, Transportation Science, vol. 40, no. 4, pp. 529–539, 2006.
DOI Google Scholar
11

J. Xu and Y. Shen, Setting scheduled trip time based on AVL data, Journal of Transportation Systems Engineering and Information Technology, vol. 12, no. 5, pp. 39–45, 2012.
DOI Google Scholar
12
D. Huisman, R. Freling, and A. P. M. Wagelmans, A robust solution approach to the dynamic vehicle scheduling problem, Transportation Science, vol. 38, no. 4, pp. 447–458, 2004.
DOI
13

M. S. Visentini, D. Borenstein, J. Q. Li, and P. B. Mirchandani, Review of real-time vehicle schedule recovery methods in transportation services, Journal of Scheduling, vol. 17, no. 6, pp. 541–567, 2014.
DOI Google Scholar
14

E. M. L. Simões, L. D. S. Batista, and M. J. F. A. Souza, A matheuristic algorithm for the multiple-depot vehicle and crew scheduling problem, IEEE Access, vol. 9, pp. 155897–155923, 2021.
DOI Google Scholar
15

A. Oukil, H. B. Amor, J. Desrosiers, and H. E. Gueddari, Stabilized column generation for highly degenerate multiple-depot vehicle scheduling problems, Computers &Operations Research, vol. 34, no. 3, pp. 817–834, 2007.
DOI Google Scholar
16

J. Q. Yuan, Hybrid tabu search algorithm for solving dynamic vehicle scheduling, Computer Applications and Software, vol. 29, no. 4, pp. 148–150,155, 2012.
Google Scholar
17

G. Zhou, D. Xie, X. Zhao, and C. Lu, Collaborative optimization of vehicle and charging scheduling for a bus fleet mixed with electric and traditional buses, IEEE Access, vol. 8, pp. 8056–8072, 2020.
DOI Google Scholar
18
J. Teng, T. Chen and W. D. Fan, Integrated approach to vehicle scheduling and bus timetabling for an electric bus line, Journal of Transportation Engineering, vol. 146, no. 2, p. 04019073, 2020.
DOI
19

C. Wang, H. Shi, and X. Zuo, A multi-objective genetic algorithm based approach for dynamical bus vehicles scheduling under traffic congestion, Swarm and Evolutionary Computation, vol. 54, p. 100667, 2020.
DOI Google Scholar
20

B. Akay and D. Karaboga, Artificial bee colony algorithm for large-scale problems and engineering design optimization, Journal of Intelligent Manufacturing, vol. 23, no. 4, pp. 1001–1014, 2012.
DOI Google Scholar
21

H. Wang, W. J. Wang, X. Y. Zhou, J. Zhao, Y. Wang, S. Y. Xiao, and M. Y. Xu, Artificial bee colony algorithm based on knowledge fusion, Complex &Intelligent System, vol. 7, no. 3, pp. 1139–1152, 2021.
DOI Google Scholar
22
D. Karaboga and S. Aslan, A discrete artificial bee colony algorithm for detecting transcription factor binding sites in DNA sequences, Genetics & Molecular Research: GMR, vol. 15, no. 2, pp. 1–11, 2016.
DOI
23
B. Xue, Y. Zhang, X. Zhang, and X. Sun, An improved artificial bee colony algorithm based on faster convergence, in Proc. 2021 IEEE International Conference on Artificial Intelligence and Computer Applications, Dalian, China, 2021, pp. 776–779.
24
J. Zhang, Z. Zhang, and X. Lin, An improved artificial bee colony with self-adaptive strategies and application, in Proc. 2021 International Conference on Computer Network, Electronic and Automation, Xi’an, China, 2021, pp. 101–104.
DOI
25

Y. Duan, Y. Xiang, and G. Chen, A discrete artificial bee colony algorithm for traveling salesman problem, Operations Research and Management Science, vol. 25, no. 5, pp. 141–146, 2016.
Google Scholar
26

M. F. Tasgetiren, Q. K. Pan, P. N. Suganthan, and A. Chen, A discrete artificial bee colony algorithm for the total flowtime minimization in permutation flow shops, Information Sciences, vol. 181, no. 16, pp. 3459–3475, 2011.
DOI Google Scholar
27

A. Yurtkuran and E. Emel, A discrete artificial bee colony algorithm for single machine scheduling problems, International Journal of Production Research, vol. 54, no. 22, pp. 6860–6878, 2016.
DOI Google Scholar
28

Q. Pan, M. F. Tasgetiren, P. N. Suganthan, and T. J. Chua, A discrete artificial bee colony algorithm for the lot-streaming flow shop scheduling problem, Information Sciences, vol. 181, no. 12, pp. 2455–2468, 2011.
DOI Google Scholar
29
D. Xue, S. Y. Cheing, and P. Gu, Configuration design considering the impact of design changes on downstream processes based upon the axiomatic design approach, Journal of Engineering Design, vol. 17, no. 6, pp. 487–508, 2006.
DOI
30

J. Zhang, CAE optimization analysis of injection process parameters for automobile CD bracket, (in Chinese), Engineering Plastics Application, vol. 44, no. 7, pp. 73–78, 2016.
Google Scholar
31

T. Sathish and S. Karthick, Wear behaviour analysis on aluminium alloy 7050 with reinforced SiC through taguchi approach, Journal of Materials Research and Technology, vol. 9, no. 3, pp. 3481–3487, 2020.
DOI Google Scholar
32
D. Huisman, R. Rreling, and A. P. M. Wagelmans, A robust solution approach to the dynamic vehicle scheduling problem, Transportation Science, vol. 38, no. 4, pp. 447–458, 2004.
DOI
33
R. P. Dilworth, A decomposition theorem for partially ordered sets, Annals of Mathematics, vol. 251, no. 1, pp. 161–166, 1950.
DOI
34

D. Bai, Z. Zhang, and Q. Zhang, Flexible open shop scheduling problem to minimize makespan, Computers &Operations Research, vol. 67, pp. 207–215, 2016.
DOI Google Scholar
35

X. Han, Y. Han, Q. Chen, J. Li, H. Sang, Y. Liu, Q. Pan, and Y. Nojima, Distributed flow shop scheduling with sequence-dependent setup times using an improved iterated greedy algorithm, Complex System Modeling and Simulation, vol. 1, no. 3, pp. 198–217, 2021.
DOI Google Scholar
36
F. Zhao, S. Di, J. Cao, J. Tang, and Jonrinaldi, A novel cooperative multi-stage hyper-heuristic for combination optimization problems, Complex System Modeling and Simulation, vol. 1, no. 2, pp. 91–108, 2021.
DOI
Publication history
Copyright
Acknowledgements
Rights and permissions

Publication history

Received: 18 April 2022
Revised: 01 July 2022
Accepted: 05 July 2022
Published: 30 September 2022
Issue date: September 2022

Copyright

© The author(s) 2022

Acknowledgements

Acknowledgment

This research was supported by the National Natural Science Foundation of China (No. 71571076). The authors would like to thank the editor and anonymous reviewers for their valuable comments and helpful suggestions.

Rights and permissions

The articles published in this open access journal are distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/).

Return