摘要
针对变邻域搜索后期出现的在某些邻域内长时间无法找到更优的可行解的情况,提出了一种基于邻域选择概率自适应的变邻域搜索算法。该算法能够自适应调整在某个邻域进行搜索的概率,进而提高优化效率。对城市配送中的大规模电动车辆路径问题进行了建模分析,根据客户的地理位置、时间窗等信息设计了高效的初始解生成算法。使用片段交换、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.
作者
赵灿华
侍洪波
ZHAO Canhua;SHI Hongbo(Key Laboratory of Advanced Control and Optimization for Chemical Processes,Ministry of Education,East China University of Science and Technology,Shanghai 200237,China)
出处
《华东理工大学学报（自然科学版）》
CAS
CSCD
北大核心
2020年第5期694-701,共8页
Journal of East China University of Science and Technology
基金
国家自然科学基金(61703161,61673173)
中央高校基本科研基金(222201714031,222201717006)
上海市自然科学基金(19ZR1473200)。
关键词
城市配送
电动车辆路径问题
自适应变邻域搜索
物流成本
urban distribution logistics
electric vehicle route problem
adaptive variable neighborhood search
logistics cost
