Solving watt-hour meter distribution vehicle routing problem based on hybrid simulated annealing algorithm

doi:10.13196/j.cims.2017.11.024

›› 2017, Vol. 23 ›› Issue (第11): 2553-2560.DOI: 10.13196/j.cims.2017.11.024

Online:2017-11-30 Published:2017-11-30
Supported by:
Project supported by the National Natural Science Foundation,China(No.51175262),the Key Research and Developement Program of Jiangsu Province,China(No.BE2016004-3),and the Jiangsu Provincial University Qing Lan Project,China.

基于混合模拟退火算法求解电表配送车辆路径问题

钱晓明¹,孙颖¹,刘建²

1.南京航空航天大学机电学院
2.江苏省电力公司电力科学研究院

基金资助:
国家自然科学基金资助项目(51175262);江苏省重点研发计划资助项目(BE2016004-3);江苏省高校青蓝工程资助项目。

Abstract

Abstract: To make the vehicle routing selection optimum in phase watt-hour meter distribution,a hybrid simulated annealing algorithm was proposed.Combined with the demand of single-phase watt-hour meter distribution,by considering the fixed cost,variable distribution costs and distribution range of vehicles,the Heterogeneous Fixed Fleet Vehicle Routing Problem (HFFVRP) optimization model was established to improve the load rate and reduce the travel times.The initial feasible solutions of the model was generated based on multi-vehicle routing algorithm,and the hybrid simulated annealing algorithm was improved with tabu list in tabu search by introducing probability-based multi-operators neighborhood search.The practicability of the model and the effectiveness of the algorithm were verified by the example of measurement center distribution service.

Key words: vehicle routing problem, simulated annealing algorithm, tabu search, heterogeneous, watt-hour meter distribution

摘要： 为了使电能表集中配送业务中的车辆路径选择最优化,提出一种混合模拟退火算法。针对单相电能表集中检定后的配送需求,综合考虑各车型的固定成本、可变配送成本和配送里程,以总成本最小为目标,建立了具有固定车辆数的多车型车辆路径优化模型。基于多车型路径划分算法生成初始可行解,通过引入基于概率的多算子邻域搜索,采用禁忌搜索中的禁忌表对模拟退火算法进行改进,给出求解算法。以计量中心配送业务为实例,验证了模型的实用性和算法的有效性。

关键词: 车辆路径问题, 模拟退火算法, 禁忌搜索, 多车型, 电表配送

CLC Number:

TP39

钱晓明,孙颖,刘建. 基于混合模拟退火算法求解电表配送车辆路径问题[J]. 计算机集成制造系统, 2017, 23(第11): 2553-2560.

[1]	. Improved simulated annealing algorithm for capacitated vehicle routing problem [J]. , 2021, 27(8): 2260-2269.
[2]	. Algorithms for vehicle routing problem with stochastic demand with soft time window [J]. , 2021, 27(8): 2270-2281.
[3]	. Adaptive strategy of cooperative changeover based on simulation evaluation method [J]. , 2021, 27(7): 1918-1928.
[4]	. 2L-CVRP vehicle routing problem with LIFO loading constraint [J]. , 2021, 27(7): 2134-2143.
[5]	. Multi-row facility layout considering material loading/unloading points and handling passages [J]. , 2021, 27(5): 1269-1280.
[6]	. Tracking and registration method based on image matching for augmented reality aided assembly system [J]. , 2021, 27(5): 1281-1291.
[7]	. Pollution routing problem based on time window assignment [J]. , 2021, 27(4): 1178-1187.
[8]	. Fresh food vehicle routing problem with split deliveries and customer classification [J]. , 2021, 27(4): 1238-1248.
[9]	. Multi-type resource scheduling technology based on distributed photovoltaic operation and maintenance [J]. , 2021, 27(3): 787-799.
[10]	. Negative word-of-mouth diffusion study for Chinese domestic automotive enterprises based on SIR-HCA model [J]. , 2021, 27(12): 3669-3681.
[11]	. Improved Jaya algorithm and tabu search for flexile job shop scheduling problem [J]. , 2021, 27(11): 3172-3184.
[12]	. Robust collaborative optimization method under mixed uncertainty [J]. , 2021, 27(11): 3282-3290.
[13]	. Bi-directional annular corridor allocation problem design using hybrid whale optimization algorithm [J]. , 2021, 27(10): 2908-2920.
[14]	. Solving open vehicle routing problem with time windows based on variable neighborhood search algorithm [J]. , 2021, 27(10): 3014-3025.
[15]	. Optimization of low-carbon cold chain vehicle path considering customer satisfaction [J]. , 2020, 26(第4): 1108-1117.