带时间窗的多车场车辆路径优化的粒子群算法

计算机工程与应用 ›› 2012, Vol. 48 ›› Issue (27): 27-30.

带时间窗的多车场车辆路径优化的粒子群算法

王铁君1，邬开俊2

1.西北民族大学数学与计算机科学学院，兰州 730030
2.兰州交通大学电子与信息工程学院，兰州 730070

出版日期:2012-09-21 发布日期:2012-09-24

Study on multi-depot vehicle routing problem with time windows based on Particle Swarm Optimization

WANG Tiejun1, WU Kaijun2

1.School of Mathematics and Computer Science, Northwest University for Nationalities, Lanzhou 730030, China
2.School of Electronic and Information Engineering, Lanzhou Jiaotong Unversity, Lanzhou 730070, China

Online:2012-09-21 Published:2012-09-24

摘要/Abstract

摘要： 带时间窗的多车场车辆路径问题在基本车辆路径问题的基础上增加了“多车场”与“时间窗”两个约束条件，是一个典型的NP难解问题。将粒子群算法应用于带时间窗的多车场车辆路径优化问题，构造了一种适用于求解车辆路径问题的粒子编码方法，建立了相应的数学模型，在此基础上设计了相应的算法。算例通过和遗传算法、蚁群算法进行比较，证明了其搜索速度和寻优能力的优越性。

关键词: 时间窗, 多车场, 车辆路径优化, 粒子群算法

Abstract: Multi-depot vehicle routing problem with time windows is a variation of the vehicle routing problem constrained by multi-depot and time windows, which is a typical NP-hard problem. Particle swarm optimization with a particle coding method is designed to solve the problem. The mathematic mode is established and the solution algorithm is developed. The simulation results of example indicate that the algorithm has faster search speed and stronger optimization ability than the GA and ACO.

Key words: time windows, multi-depot, vehicle routing problem, Particle Swarm Optimization（PSO）

王铁君1，邬开俊2. 带时间窗的多车场车辆路径优化的粒子群算法[J]. 计算机工程与应用, 2012, 48(27): 27-30.

WANG Tiejun1, WU Kaijun2. Study on multi-depot vehicle routing problem with time windows based on Particle Swarm Optimization[J]. Computer Engineering and Applications, 2012, 48(27): 27-30.

[1]	史春天，曾艳阳，侯守明. 群体智能算法在图像分割中的应用综述[J]. 计算机工程与应用, 2021, 57(8): 36-47.
[2]	李静星，杨有龙. 针对高维数据的马尔科夫毯特征选择[J]. 计算机工程与应用, 2021, 57(6): 58-66.
[3]	朱佳莹，高茂庭. 融合粒子群与改进蚁群算法的AUV路径规划算法[J]. 计算机工程与应用, 2021, 57(6): 267-273.
[4]	姚洪刚，沐年国. EMD-LSTM模型对金融时间序列的预测[J]. 计算机工程与应用, 2021, 57(5): 239-244.
[5]	王嘉月，史立. 考虑电池损耗的电动冷藏车路径及充电策略[J]. 计算机工程与应用, 2021, 57(24): 283-289.
[6]	李倩，蒋丽，梁昌勇. 基于模糊时间窗的多目标冷链配送优化[J]. 计算机工程与应用, 2021, 57(23): 255-262.
[7]	王琛，茅健. 基于时间窗模型的双向机器人路径规划方法[J]. 计算机工程与应用, 2021, 57(23): 287-294.
[8]	林炜星，王宇嘉，陈万芬，梁海娜. 基于多因子粒子群的高维数据特征选择算法[J]. 计算机工程与应用, 2021, 57(22): 199-207.
[9]	马龙，王春嬉，张正义，董睿. 多目标多时间窗车辆路径问题的鸽群-水滴算法[J]. 计算机工程与应用, 2021, 57(2): 237-250.
[10]	丁一，张成成. 集装箱码头送箱外集卡预约优化研究[J]. 计算机工程与应用, 2021, 57(19): 267-273.
[11]	张凯，靳鹏，崔勇. 带时间窗的多车型需求可拆分揽收配送问题[J]. 计算机工程与应用, 2021, 57(14): 281-288.
[12]	于国龙，赵勇，吴恋，崔忠伟. QPSO算法的改进及其在DBN参数优化中应用[J]. 计算机工程与应用, 2021, 57(10): 154-162.
[13]	梁承姬，黄帅. 考虑时间窗的集装箱港口场桥全局调度优化[J]. 计算机工程与应用, 2020, 56(8): 226-232.
[14]	陆航，师智斌，刘忠宝. 融合用户兴趣和评分差异的协同过滤推荐算法[J]. 计算机工程与应用, 2020, 56(7): 24-29.
[15]	周蓉，李俊，王浩. 基于灰狼优化的反向学习粒子群算法[J]. 计算机工程与应用, 2020, 56(7): 48-56.