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

计算机工程与科学

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

宋强

(1.肇庆学院计算机科学与软件学院，广东肇庆 526061;2.武汉理工大学信息工程学院，湖北武汉 430070)

收稿日期:2018-08-13 修回日期:2019-02-26 出版日期:2019-10-25 发布日期:2019-10-25
基金资助:
国家自然科学基金(60773212);肇庆市科技创新类项目（201904030404）;肇庆学院校基金(201948)

Application of an optimized beam-PSO

algorithm in multi-trip vehicle routing problem

SONG Qiang

(1.School of Computer Science and Software,Zhaoqing University,Zhaoqing 526061;

2.School of Information Engineering,Wuhan University of Technology,Wuhan 430070,China)

Received:2018-08-13 Revised:2019-02-26 Online:2019-10-25 Published:2019-10-25

摘要/Abstract

摘要：

针对城市物流配送系统，研究了一类带时间窗和释放时间约束的多行程车辆路径问题。首先，对该运输调度问题进行了描述，构建了以总配送时长最小化为目标的数学模型。其次，为了快速获得问题的满意解，提出了Beam-PSO优化算法。在算法设计中，结合该问题的性质，构建了基于随机键的编解码方法，以克服标准粒子群算法无法直接适用于求解离散问题的不足。同时，设计了基于Beam search优化技术的局部搜索流程，用于强化算法的优化性能。最后，进行了仿真实验，实验结果表明了Beam-PSO优化算法的可行性和有效性。

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

Abstract:

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.

Key words: multi-trip vehicle routing problem, release date, beam-PSO algorithm, decoding, local search

宋强. Beam-PSO优化算法在多行程车辆路径问题的应用[J]. 计算机工程与科学.

SONG Qiang.

Application of an optimized beam-PSO

algorithm in multi-trip vehicle routing problem

[J]. Computer Engineering & Science.

[1]	张文豪, 瞿绍军. 基于双解码器结构的多尺度注意力特征融合网络的视网膜血管分割#br#[J]. 计算机工程与科学, 2023, 45(12): 2175-2185.
[2]	胡春安, 熊昱然. 多策略改进的混沌哈里斯鹰优化算法[J]. 计算机工程与科学, 2023, 45(09): 1648-1660.
[3]	杨炳媛, 袁杰, 郭园园. 一种自适应鲸鱼快速优化算法[J]. 计算机工程与科学, 2023, 45(01): 145-153.
[4]	黄泽民, 吴晓鸰, 吴迎岗, 凌捷. 结合BERT和BiSRU-AT的中文文本情感分类[J]. 计算机工程与科学, 2021, 43(09): 1668-1674.
[5]	夏珺1，钱磊2，严伟3，柴志雷1. 基于FPGA的HEVC后处理CNN硬件加速器研究[J]. 计算机工程与科学, 2018, 40(12): 2126-2132.
[6]	顾清华，马龙，卢才武. 一种用于时空体元编解码存储的低计算量优化方法[J]. 计算机工程与科学, 2018, 40(12): 2146-2155.
[7]	黄亚飞1,2,梁昔明1,樊绍胜2. 基于局部字典搜索和多原子匹配追踪的图像逼近算法[J]. 计算机工程与科学, 2018, 40(01): 72-78.
[8]	林要华1，王维2. 基于逐维策略的布谷鸟搜索增强算法[J]. 计算机工程与科学, 2017, 39(01): 165-172.
[9]	刘汉强,郑朋. 局部搜索自适应核模糊聚类方法[J]. 计算机工程与科学, 2016, 38(08): 1735-1740.
[10]	臧培荃，孙晨骜，顾晓峰，吴滨，周长喜. 具有自适应趋向性和引导因子的人工蜂群算法[J]. J4, 2015, 37(09): 1692-1697.
[11]	张建明，唐勇，周书仁，吴宏林. 深度广度联合解码的基因表达式程序设计[J]. J4, 2014, 36(10): 1966-1971.
[12]	包云，姜华，郑丽萍. 基于和声搜索的阻塞流水车间调度问题的算法优化[J]. J4, 2013, 35(7): 108-112.
[13]	刘一丹1,王子牛2 ,陈洁1 , 李少博1. 基于DEXEL和离散点阵法的数控加工仿真研究[J]. J4, 2011, 33(1): 171-175.
[14]	林沛，王德胜，朱光喜，雷萌. 交织复用空时码在协作中继网络中的应用[J]. J4, 2010, 32(11): 153-155.
[15]	向佐勇[1,2] 刘正才[2]. 一种改进的混合遗传算法研究[J]. J4, 2008, 30(9): 53-57.