Solving vehicle routing problem through a tabu bee colony-based genetic algorithm

Lingyan Lv; Yuxin Liu; Chao Gao; Jianjun Chen; Zili Zhang

doi:10.1007/978-3-319-93815-8_19

Solving vehicle routing problem through a tabu bee colony-based genetic algorithm

Lingyan Lv, Yuxin Liu, Chao Gao, Jianjun Chen, Zili Zhang

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

1 Scopus citations

Abstract

Vehicle routing problem (VRP) is a classic combinatorial optimization problem and has many applications in industry. Solutions of VRP have significant impact on logistic cost. In most VRP models, the shortest distance is used as the objective function, which is not the case in many real-word applications. To this end, a VRP model with fixed and fuel cost is proposed. Genetic algorithm (GA) is a common approach for solving VRP. Due to the premature issue in GA, a tabu bee colony-based GA is employed to solve this model. The improved GA has three characteristics that differentiate from other similar algorithms: (1) The maximum preserved crossover is proposed, to protect the outstanding sub-path and avoid the phenomenon that two identical individuals cannot create new individuals; (2) The bee evolution mechanism is introduced. The optimal solution is selected as the queen-bee and a number of outstanding individuals are as the drones. The utilization of excellent individual characteristics is improved through the crossover of queen-bee and drones; (3) The tabu search is applied to optimize the queen-bee in each generation of bees and improve the quality of excellent individuals. Thus the population quality is improved. Extensive experiments were conducted. The experimental results show the rationality of the model and the validity of the proposed algorithm.

Original language	English
Title of host publication	Advances in Swarm Intelligence - 9th International Conference, ICSI 2018, Proceedings
Editors	Ying Tan, Yuhui Shi, Qirong Tang
Publisher	Springer Verlag
Pages	191-200
Number of pages	10
ISBN (Print)	9783319938141
DOIs	https://doi.org/10.1007/978-3-319-93815-8_19
State	Published - 2018
Externally published	Yes
Event	9th International Conference on Swarm Intelligence, ICSI 2018 - Shanghai, China Duration: 17 Jun 2018 → 22 Jun 2018

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	10941 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	9th International Conference on Swarm Intelligence, ICSI 2018
Country/Territory	China
City	Shanghai
Period	17/06/18 → 22/06/18

Keywords

Bee colony algorithm
Genetic algorithm
Tabu search
Vehicle routing problem

Access to Document

10.1007/978-3-319-93815-8_19

Cite this

Lv, L., Liu, Y., Gao, C., Chen, J., & Zhang, Z. (2018). Solving vehicle routing problem through a tabu bee colony-based genetic algorithm. In Y. Tan, Y. Shi, & Q. Tang (Eds.), Advances in Swarm Intelligence - 9th International Conference, ICSI 2018, Proceedings (pp. 191-200). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10941 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-93815-8_19

Lv, Lingyan ; Liu, Yuxin ; Gao, Chao et al. / Solving vehicle routing problem through a tabu bee colony-based genetic algorithm. Advances in Swarm Intelligence - 9th International Conference, ICSI 2018, Proceedings. editor / Ying Tan ; Yuhui Shi ; Qirong Tang. Springer Verlag, 2018. pp. 191-200 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{ee64bd45f9624daeb79169e625f1e946,

title = "Solving vehicle routing problem through a tabu bee colony-based genetic algorithm",

abstract = "Vehicle routing problem (VRP) is a classic combinatorial optimization problem and has many applications in industry. Solutions of VRP have significant impact on logistic cost. In most VRP models, the shortest distance is used as the objective function, which is not the case in many real-word applications. To this end, a VRP model with fixed and fuel cost is proposed. Genetic algorithm (GA) is a common approach for solving VRP. Due to the premature issue in GA, a tabu bee colony-based GA is employed to solve this model. The improved GA has three characteristics that differentiate from other similar algorithms: (1) The maximum preserved crossover is proposed, to protect the outstanding sub-path and avoid the phenomenon that two identical individuals cannot create new individuals; (2) The bee evolution mechanism is introduced. The optimal solution is selected as the queen-bee and a number of outstanding individuals are as the drones. The utilization of excellent individual characteristics is improved through the crossover of queen-bee and drones; (3) The tabu search is applied to optimize the queen-bee in each generation of bees and improve the quality of excellent individuals. Thus the population quality is improved. Extensive experiments were conducted. The experimental results show the rationality of the model and the validity of the proposed algorithm.",

keywords = "Bee colony algorithm, Genetic algorithm, Tabu search, Vehicle routing problem",

author = "Lingyan Lv and Yuxin Liu and Chao Gao and Jianjun Chen and Zili Zhang",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing AG, part of Springer Nature 2018.; 9th International Conference on Swarm Intelligence, ICSI 2018 ; Conference date: 17-06-2018 Through 22-06-2018",

year = "2018",

doi = "10.1007/978-3-319-93815-8_19",

language = "英语",

isbn = "9783319938141",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "191--200",

editor = "Ying Tan and Yuhui Shi and Qirong Tang",

booktitle = "Advances in Swarm Intelligence - 9th International Conference, ICSI 2018, Proceedings",

}

Lv, L, Liu, Y, Gao, C, Chen, J & Zhang, Z 2018, Solving vehicle routing problem through a tabu bee colony-based genetic algorithm. in Y Tan, Y Shi & Q Tang (eds), Advances in Swarm Intelligence - 9th International Conference, ICSI 2018, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10941 LNCS, Springer Verlag, pp. 191-200, 9th International Conference on Swarm Intelligence, ICSI 2018, Shanghai, China, 17/06/18. https://doi.org/10.1007/978-3-319-93815-8_19

Solving vehicle routing problem through a tabu bee colony-based genetic algorithm. / Lv, Lingyan; Liu, Yuxin; Gao, Chao et al.
Advances in Swarm Intelligence - 9th International Conference, ICSI 2018, Proceedings. ed. / Ying Tan; Yuhui Shi; Qirong Tang. Springer Verlag, 2018. p. 191-200 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10941 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Solving vehicle routing problem through a tabu bee colony-based genetic algorithm

AU - Lv, Lingyan

AU - Liu, Yuxin

AU - Gao, Chao

AU - Chen, Jianjun

AU - Zhang, Zili

N1 - Publisher Copyright: © Springer International Publishing AG, part of Springer Nature 2018.

PY - 2018

Y1 - 2018

N2 - Vehicle routing problem (VRP) is a classic combinatorial optimization problem and has many applications in industry. Solutions of VRP have significant impact on logistic cost. In most VRP models, the shortest distance is used as the objective function, which is not the case in many real-word applications. To this end, a VRP model with fixed and fuel cost is proposed. Genetic algorithm (GA) is a common approach for solving VRP. Due to the premature issue in GA, a tabu bee colony-based GA is employed to solve this model. The improved GA has three characteristics that differentiate from other similar algorithms: (1) The maximum preserved crossover is proposed, to protect the outstanding sub-path and avoid the phenomenon that two identical individuals cannot create new individuals; (2) The bee evolution mechanism is introduced. The optimal solution is selected as the queen-bee and a number of outstanding individuals are as the drones. The utilization of excellent individual characteristics is improved through the crossover of queen-bee and drones; (3) The tabu search is applied to optimize the queen-bee in each generation of bees and improve the quality of excellent individuals. Thus the population quality is improved. Extensive experiments were conducted. The experimental results show the rationality of the model and the validity of the proposed algorithm.

AB - Vehicle routing problem (VRP) is a classic combinatorial optimization problem and has many applications in industry. Solutions of VRP have significant impact on logistic cost. In most VRP models, the shortest distance is used as the objective function, which is not the case in many real-word applications. To this end, a VRP model with fixed and fuel cost is proposed. Genetic algorithm (GA) is a common approach for solving VRP. Due to the premature issue in GA, a tabu bee colony-based GA is employed to solve this model. The improved GA has three characteristics that differentiate from other similar algorithms: (1) The maximum preserved crossover is proposed, to protect the outstanding sub-path and avoid the phenomenon that two identical individuals cannot create new individuals; (2) The bee evolution mechanism is introduced. The optimal solution is selected as the queen-bee and a number of outstanding individuals are as the drones. The utilization of excellent individual characteristics is improved through the crossover of queen-bee and drones; (3) The tabu search is applied to optimize the queen-bee in each generation of bees and improve the quality of excellent individuals. Thus the population quality is improved. Extensive experiments were conducted. The experimental results show the rationality of the model and the validity of the proposed algorithm.

KW - Bee colony algorithm

KW - Genetic algorithm

KW - Tabu search

KW - Vehicle routing problem

UR - http://www.scopus.com/inward/record.url?scp=85049060941&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-93815-8_19

DO - 10.1007/978-3-319-93815-8_19

M3 - 会议稿件

AN - SCOPUS:85049060941

SN - 9783319938141

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 191

EP - 200

BT - Advances in Swarm Intelligence - 9th International Conference, ICSI 2018, Proceedings

A2 - Tan, Ying

A2 - Shi, Yuhui

A2 - Tang, Qirong

PB - Springer Verlag

T2 - 9th International Conference on Swarm Intelligence, ICSI 2018

Y2 - 17 June 2018 through 22 June 2018

ER -

Lv L, Liu Y, Gao C, Chen J, Zhang Z. Solving vehicle routing problem through a tabu bee colony-based genetic algorithm. In Tan Y, Shi Y, Tang Q, editors, Advances in Swarm Intelligence - 9th International Conference, ICSI 2018, Proceedings. Springer Verlag. 2018. p. 191-200. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-93815-8_19

Solving vehicle routing problem through a tabu bee colony-based genetic algorithm

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this