A multiobjective evolutionary algorithm incorporating neighborhood detection for the vehicle routing problem with soft time windows
Abstract The Vehicle Routing Problems with Soft Time Windows (VRPSTWs) presents a common challenge in practical scenarios, which has spurred the development of various algorithmic solutions. Among these solutions, hybrid approaches that integrate evolutionary algorithms and neighborhood search techn...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Springer
2025-08-01
|
| Series: | Complex & Intelligent Systems |
| Subjects: | |
| Online Access: | https://doi.org/10.1007/s40747-025-02044-y |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849225773832994816 |
|---|---|
| author | Hao Jiang Zhiwei Zhang Chao Wang Xiaoshu Xiang |
| author_facet | Hao Jiang Zhiwei Zhang Chao Wang Xiaoshu Xiang |
| author_sort | Hao Jiang |
| collection | DOAJ |
| description | Abstract The Vehicle Routing Problems with Soft Time Windows (VRPSTWs) presents a common challenge in practical scenarios, which has spurred the development of various algorithmic solutions. Among these solutions, hybrid approaches that integrate evolutionary algorithms and neighborhood search techniques have shown great promise. However, existing research mainly focuses on improving solution quality within large and diverse neighborhoods, often resulting in increased computational complexity and the risk of getting trapped in local optima. To overcome these limitations, we first designed a neighborhood detection method that selectively identifies relevant neighbors for a given solution, thereby streamlining the search space. Subsequently, we proposed a Multi-Objective Evolutionary Algorithm with Neighborhood Detection (MOEAND), which utilizes this customized neighborhood to efficiently solve VRPSTWs. By reducing the neighborhood size before conducting the search, MOEAND ensures focused exploration within a compact space, thereby improving performance. Extensive experiments on a benchmark dataset have validated the effectiveness of MOEAND. The experimental results show that, compared to six state-of-the-art algorithms specifically designed for VRPSTWs, MOEAND achieves superior performance, highlighting its potential as an efficient and effective algorithm for solving VRPSTWs. |
| format | Article |
| id | doaj-art-7e01f463c6d242a180bdb551471e47e4 |
| institution | Kabale University |
| issn | 2199-4536 2198-6053 |
| language | English |
| publishDate | 2025-08-01 |
| publisher | Springer |
| record_format | Article |
| series | Complex & Intelligent Systems |
| spelling | doaj-art-7e01f463c6d242a180bdb551471e47e42025-08-24T12:02:15ZengSpringerComplex & Intelligent Systems2199-45362198-60532025-08-01111012510.1007/s40747-025-02044-yA multiobjective evolutionary algorithm incorporating neighborhood detection for the vehicle routing problem with soft time windowsHao Jiang0Zhiwei Zhang1Chao Wang2Xiaoshu Xiang3Key Laboratory of Intelligent Computing and Signal Processing of Ministry of Education, School of Computer Science and Technology, Anhui UniversityKey Laboratory of Intelligent Computing and Signal Processing of Ministry of Education, School of Artificial Intelligence, Anhui UniversityKey Laboratory of Intelligent Computing and Signal Processing of Ministry of Education, School of Artificial Intelligence, Anhui UniversityKey Laboratory of Intelligent Computing and Signal Processing of Ministry of Education, Institutes of Physical Science and Information Technology, Anhui UniversityAbstract The Vehicle Routing Problems with Soft Time Windows (VRPSTWs) presents a common challenge in practical scenarios, which has spurred the development of various algorithmic solutions. Among these solutions, hybrid approaches that integrate evolutionary algorithms and neighborhood search techniques have shown great promise. However, existing research mainly focuses on improving solution quality within large and diverse neighborhoods, often resulting in increased computational complexity and the risk of getting trapped in local optima. To overcome these limitations, we first designed a neighborhood detection method that selectively identifies relevant neighbors for a given solution, thereby streamlining the search space. Subsequently, we proposed a Multi-Objective Evolutionary Algorithm with Neighborhood Detection (MOEAND), which utilizes this customized neighborhood to efficiently solve VRPSTWs. By reducing the neighborhood size before conducting the search, MOEAND ensures focused exploration within a compact space, thereby improving performance. Extensive experiments on a benchmark dataset have validated the effectiveness of MOEAND. The experimental results show that, compared to six state-of-the-art algorithms specifically designed for VRPSTWs, MOEAND achieves superior performance, highlighting its potential as an efficient and effective algorithm for solving VRPSTWs.https://doi.org/10.1007/s40747-025-02044-yVehicle routing problem with soft time windowsEvolutionary algorithmNeighborhood detectionMultiobjective optimization |
| spellingShingle | Hao Jiang Zhiwei Zhang Chao Wang Xiaoshu Xiang A multiobjective evolutionary algorithm incorporating neighborhood detection for the vehicle routing problem with soft time windows Complex & Intelligent Systems Vehicle routing problem with soft time windows Evolutionary algorithm Neighborhood detection Multiobjective optimization |
| title | A multiobjective evolutionary algorithm incorporating neighborhood detection for the vehicle routing problem with soft time windows |
| title_full | A multiobjective evolutionary algorithm incorporating neighborhood detection for the vehicle routing problem with soft time windows |
| title_fullStr | A multiobjective evolutionary algorithm incorporating neighborhood detection for the vehicle routing problem with soft time windows |
| title_full_unstemmed | A multiobjective evolutionary algorithm incorporating neighborhood detection for the vehicle routing problem with soft time windows |
| title_short | A multiobjective evolutionary algorithm incorporating neighborhood detection for the vehicle routing problem with soft time windows |
| title_sort | multiobjective evolutionary algorithm incorporating neighborhood detection for the vehicle routing problem with soft time windows |
| topic | Vehicle routing problem with soft time windows Evolutionary algorithm Neighborhood detection Multiobjective optimization |
| url | https://doi.org/10.1007/s40747-025-02044-y |
| work_keys_str_mv | AT haojiang amultiobjectiveevolutionaryalgorithmincorporatingneighborhooddetectionforthevehicleroutingproblemwithsofttimewindows AT zhiweizhang amultiobjectiveevolutionaryalgorithmincorporatingneighborhooddetectionforthevehicleroutingproblemwithsofttimewindows AT chaowang amultiobjectiveevolutionaryalgorithmincorporatingneighborhooddetectionforthevehicleroutingproblemwithsofttimewindows AT xiaoshuxiang amultiobjectiveevolutionaryalgorithmincorporatingneighborhooddetectionforthevehicleroutingproblemwithsofttimewindows AT haojiang multiobjectiveevolutionaryalgorithmincorporatingneighborhooddetectionforthevehicleroutingproblemwithsofttimewindows AT zhiweizhang multiobjectiveevolutionaryalgorithmincorporatingneighborhooddetectionforthevehicleroutingproblemwithsofttimewindows AT chaowang multiobjectiveevolutionaryalgorithmincorporatingneighborhooddetectionforthevehicleroutingproblemwithsofttimewindows AT xiaoshuxiang multiobjectiveevolutionaryalgorithmincorporatingneighborhooddetectionforthevehicleroutingproblemwithsofttimewindows |