Beam-PSO优化算法在多行程车辆路径问题的应用  

Application of an optimized beam-PSO algorithm in multi-trip vehicle routing problem

作　　者：宋强 SONG Qiang(School of Computer Science and Software,Zhaoqing University,Zhaoqing 526061;School of Information Engineering,Wuhan University of Technology,Wuhan 430070,China)

机构地区：[1]肇庆学院计算机科学与软件学院 [2]武汉理工大学信息工程学院

出　　处：《计算机工程与科学》2019年第10期1882-1891,共10页Computer Engineering & Science

基　　金：国家自然科学基金(60773212);肇庆市科技创新类项目(201904030404);肇庆学院校基金(201948)

摘　　要：针对城市物流配送系统,研究了一类带时间窗和释放时间约束的多行程车辆路径问题。首先,对该运输调度问题进行了描述,构建了以总配送时长最小化为目标的数学模型。其次,为了快速获得问题的满意解,提出了Beam-PSO优化算法。在算法设计中,结合该问题的性质,构建了基于随机键的编解码方法,以克服标准粒子群算法无法直接适用于求解离散问题的不足。同时,设计了基于Beam search优化技术的局部搜索流程,用于强化算法的优化性能。最后,进行了仿真实验,实验结果表明了Beam-PSO优化算法的可行性和有效性。We investigate the multi-trip vehicle routing problem with time windows and release dates(MTVRP-TW-RD)in the context of city logistics distribution system.Firstly,this transportation scheduling problem is formally described and a mathematical model is designed to minimize the total delivery time.Then,we propose a beam-PSO algorithm to quickly obtain satisfactory solutions.According to the characteristics of the MTVRP-TW-RD,we propose a new coding and decoding method based on random keys to overcome the shortcoming of the basic particle swarm optimization(PSO)which is that it cannot be directly applied to discrete problems.In addition,a local search process based on the beam search optimization technique is designed to enhance the performance of the beam-PSO.Simulations are carried out,and experimental results demonstrate the feasibility and validity of the proposed algorithm.

关 键 词：多行程车辆路径问题 释放时间 Beam-PSO算法 解码 局部搜索 

分 类 号：TP391.9[自动化与计算机技术—计算机应用技术]