文献类型：期刊文献

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

英文题名：Large-Scale Electric Vehicle Route Optimization Based on Adaptive Variable Neighborhood Search

作者：赵灿华[1];侍洪波[1]

机构：[1]华东理工大学化工过程先进控制和优化技术教育部重点实验室,上海200237

年份：2020

卷号：46

期号：5

起止页码：694

中文期刊名：华东理工大学学报（自然科学版）

外文期刊名：Journal of East China University of Science and Technology

收录：CSTPCD;;Scopus;北大核心:【北大核心2017】；CSCD:【CSCD_E2019_2020】；

基金：国家自然科学基金(61703161,61673173);中央高校基本科研基金(222201714031,222201717006);上海市自然科学基金(19ZR1473200)。

语种：中文

中文关键词：城市配送;电动车辆路径问题;自适应变邻域搜索;物流成本

外文关键词：urban distribution logistics;electric vehicle route problem;adaptive variable neighborhood search;logistics cost

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