A multiobjective evolutionary algorithm incorporating neighborhood detection for the vehicle routing problem with soft time windows - Hao Jiang; Zhiwei Zhang; Chao Wang; Xiaoshu Xiang (Complex & Intelligent Systems)
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.