高级检索

    赵灿华, 侍洪波. 基于自适应变邻域搜索的大规模电动车辆路径优化[J]. 华东理工大学学报(自然科学版), 2020, 46(5): 694-701. DOI: 10.14135/j.cnki.1006-3080.20190730001
    引用本文: 赵灿华, 侍洪波. 基于自适应变邻域搜索的大规模电动车辆路径优化[J]. 华东理工大学学报(自然科学版), 2020, 46(5): 694-701. DOI: 10.14135/j.cnki.1006-3080.20190730001
    ZHAO Canhua, SHI Hongbo. Large-Scale Electric Vehicle Route Optimization Based on Adaptive Variable Neighborhood Search[J]. Journal of East China University of Science and Technology, 2020, 46(5): 694-701. DOI: 10.14135/j.cnki.1006-3080.20190730001
    Citation: ZHAO Canhua, SHI Hongbo. Large-Scale Electric Vehicle Route Optimization Based on Adaptive Variable Neighborhood Search[J]. Journal of East China University of Science and Technology, 2020, 46(5): 694-701. DOI: 10.14135/j.cnki.1006-3080.20190730001

    基于自适应变邻域搜索的大规模电动车辆路径优化

    Large-Scale Electric Vehicle Route Optimization Based on Adaptive Variable Neighborhood Search

    • 摘要: 针对变邻域搜索后期出现的在某些邻域内长时间无法找到更优的可行解的情况,提出了一种基于邻域选择概率自适应的变邻域搜索算法。该算法能够自适应调整在某个邻域进行搜索的概率,进而提高优化效率。对城市配送中的大规模电动车辆路径问题进行了建模分析,根据客户的地理位置、时间窗等信息设计了高效的初始解生成算法。使用片段交换、2-opt、Relocation等邻域算子进行自适应变邻域搜索。最后使用不同规模的实际数据对算法进行仿真验证,相比于传统的变邻域搜索算法,本文算法能更有效地跳出局部最优解,降低物流成本。

       

      Abstract: The variable neighborhood search algorithm may have difficulty in searching a better feasible solution in some neighborhoods for a long time in later stage. Aiming at the shortcoming, this paper proposes an adaptive variable neighborhood search algorithm based on neighborhood selection probability. The proposed algorithm can adjust the selection probability in some neighborhoods adaptively according to the optimization circumstance of this neighborhood such that the optimization efficiency can be improved. This paper designs two select probability update methods and analyzes their characteristics. By setting the minimum selection probability, the selection probability may be avoided to reduce to zero and the diversity of the neighborhood can be ensured. Due to battery capacity limitations and charging requirements, the optimization problem of the electric vehicle route is more complicated than the traditional vehicle route problem. By modeling and analyzing the large-scale electric vehicle routing problem under the actual urban distribution logistics, this paper propose an efficient initial solution generation algorithm according to the geographic location and the time window of the service customer. Some neighborhood operators using segmentation-exchange, 2-opt, and relocation are designed to achieve the adaptive variable neighborhood search. Finally, the simulation experiments with different scales data are made. It is shown from the results that the variation curves of the two select probability update methods have the same tendency, which verifies the rationality of minimum selection probability vector setting. Compared with the traditional variable neighborhood search algorithm, the proposed adaptive variable neighborhood search algorithm can effectively jump out of the local optimal solution and reduce the logistical cost under urban distribution.

       

    /

    返回文章
    返回