A Novel Multistrategy-Based Differential Evolution Algorithm and Its Application
To address the poor searchability, population diversity, and slow convergence speed of the differential evolution (DE) algorithm in solving capacitated vehicle routing problems (CVRP), a new multistrategy-based differential evolution algorithm with the saving mileage algorithm, sequential encoding,...
| Main Authors: | , , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2022-10-01
|
| Series: | Electronics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2079-9292/11/21/3476 |
| _version_ | 1797468493941047296 |
|---|---|
| author | Jinyin Wang Shifan Shang Huanyu Jing Jiahui Zhu Yingjie Song Yuangang Li Wu Deng |
| author_facet | Jinyin Wang Shifan Shang Huanyu Jing Jiahui Zhu Yingjie Song Yuangang Li Wu Deng |
| author_sort | Jinyin Wang |
| collection | DOAJ |
| description | To address the poor searchability, population diversity, and slow convergence speed of the differential evolution (DE) algorithm in solving capacitated vehicle routing problems (CVRP), a new multistrategy-based differential evolution algorithm with the saving mileage algorithm, sequential encoding, and gravitational search algorithm, namely SEGDE, is proposed to solve CVRP in this paper. Firstly, an optimization model of CVRP with the shortest total vehicle routing is established. Then, the saving mileage algorithm is employed to initialize the population of the DE to improve the initial solution quality and the search efficiency. The sequential encoding approach is used to adjust the differential mutation strategy to legalize the current solution and ensure its effectiveness. Finally, the gravitational search algorithm is applied to calculate the gravitational relationship between points to effectively adjust the evolutionary search direction and further improve the search efficiency. Four CVRPs are selected to verify the effectiveness of the proposed SEGDE algorithm. The experimental results show that the proposed SEGDE algorithm can effectively solve the CVRPs and obtain the ideal vehicle routing. It adopts better search speed, global optimization ability, routing length, and stability. |
| first_indexed | 2024-03-09T19:08:15Z |
| format | Article |
| id | doaj.art-4b9958b8772042f9a922e131c1b7247c |
| institution | Directory Open Access Journal |
| issn | 2079-9292 |
| language | English |
| last_indexed | 2024-03-09T19:08:15Z |
| publishDate | 2022-10-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Electronics |
| spelling | doaj.art-4b9958b8772042f9a922e131c1b7247c2023-11-24T04:24:34ZengMDPI AGElectronics2079-92922022-10-011121347610.3390/electronics11213476A Novel Multistrategy-Based Differential Evolution Algorithm and Its ApplicationJinyin Wang0Shifan Shang1Huanyu Jing2Jiahui Zhu3Yingjie Song4Yuangang Li5Wu Deng6UNI-FI Credit Solutions Co., Ltd., Beijing 100083, ChinaSchool of Electronic Information and Automation, Civil Aviation University of China, Tianjin 300300, ChinaSchool of Electronic Information and Automation, Civil Aviation University of China, Tianjin 300300, ChinaSchool of Electronic Information and Automation, Civil Aviation University of China, Tianjin 300300, ChinaCollege of Computer Science and Technology, Shandong Technology and Business University, Yantai 264005, ChinaFaculty of Business Information, Shanghai Business School, Shanghai 200235, ChinaSchool of Electronic Information and Automation, Civil Aviation University of China, Tianjin 300300, ChinaTo address the poor searchability, population diversity, and slow convergence speed of the differential evolution (DE) algorithm in solving capacitated vehicle routing problems (CVRP), a new multistrategy-based differential evolution algorithm with the saving mileage algorithm, sequential encoding, and gravitational search algorithm, namely SEGDE, is proposed to solve CVRP in this paper. Firstly, an optimization model of CVRP with the shortest total vehicle routing is established. Then, the saving mileage algorithm is employed to initialize the population of the DE to improve the initial solution quality and the search efficiency. The sequential encoding approach is used to adjust the differential mutation strategy to legalize the current solution and ensure its effectiveness. Finally, the gravitational search algorithm is applied to calculate the gravitational relationship between points to effectively adjust the evolutionary search direction and further improve the search efficiency. Four CVRPs are selected to verify the effectiveness of the proposed SEGDE algorithm. The experimental results show that the proposed SEGDE algorithm can effectively solve the CVRPs and obtain the ideal vehicle routing. It adopts better search speed, global optimization ability, routing length, and stability.https://www.mdpi.com/2079-9292/11/21/3476differential evolutioncapacitated vehicle routing planningsaving mileagegravity search |
| spellingShingle | Jinyin Wang Shifan Shang Huanyu Jing Jiahui Zhu Yingjie Song Yuangang Li Wu Deng A Novel Multistrategy-Based Differential Evolution Algorithm and Its Application Electronics differential evolution capacitated vehicle routing planning saving mileage gravity search |
| title | A Novel Multistrategy-Based Differential Evolution Algorithm and Its Application |
| title_full | A Novel Multistrategy-Based Differential Evolution Algorithm and Its Application |
| title_fullStr | A Novel Multistrategy-Based Differential Evolution Algorithm and Its Application |
| title_full_unstemmed | A Novel Multistrategy-Based Differential Evolution Algorithm and Its Application |
| title_short | A Novel Multistrategy-Based Differential Evolution Algorithm and Its Application |
| title_sort | novel multistrategy based differential evolution algorithm and its application |
| topic | differential evolution capacitated vehicle routing planning saving mileage gravity search |
| url | https://www.mdpi.com/2079-9292/11/21/3476 |
| work_keys_str_mv | AT jinyinwang anovelmultistrategybaseddifferentialevolutionalgorithmanditsapplication AT shifanshang anovelmultistrategybaseddifferentialevolutionalgorithmanditsapplication AT huanyujing anovelmultistrategybaseddifferentialevolutionalgorithmanditsapplication AT jiahuizhu anovelmultistrategybaseddifferentialevolutionalgorithmanditsapplication AT yingjiesong anovelmultistrategybaseddifferentialevolutionalgorithmanditsapplication AT yuangangli anovelmultistrategybaseddifferentialevolutionalgorithmanditsapplication AT wudeng anovelmultistrategybaseddifferentialevolutionalgorithmanditsapplication AT jinyinwang novelmultistrategybaseddifferentialevolutionalgorithmanditsapplication AT shifanshang novelmultistrategybaseddifferentialevolutionalgorithmanditsapplication AT huanyujing novelmultistrategybaseddifferentialevolutionalgorithmanditsapplication AT jiahuizhu novelmultistrategybaseddifferentialevolutionalgorithmanditsapplication AT yingjiesong novelmultistrategybaseddifferentialevolutionalgorithmanditsapplication AT yuangangli novelmultistrategybaseddifferentialevolutionalgorithmanditsapplication AT wudeng novelmultistrategybaseddifferentialevolutionalgorithmanditsapplication |