基于改进差分变邻域算法的多行程车辆路径问题的研究

doi:10.3969/j.issn.1674-0696.2020.02.06

重庆交通大学学报（自然科学版） ›› 2020, Vol. 39 ›› Issue (02): 35-42.DOI: 10.3969/j.issn.1674-0696.2020.02.06

基于改进差分变邻域算法的多行程车辆路径问题的研究

宋强1,2

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

收稿日期:2018-06-01 修回日期:2018-11-11 出版日期:2020-02-20 发布日期:2020-02-20
作者简介:宋强(1971—)，男，河南安阳人，副教授，博士，主要从事计算机控制及算法优化研究方面的工作。E-mail：gdpcit@163.com。
基金资助:
肇庆市科研创新项目(201904030404)；肇庆学院校科研项目(201948)

Multi-trip Vehicle Routing Problem Based on the Improved Difference Variable Neighborhood Search Algorithm

SONG Qiang1,2

(1. School of Computer Science and Software & Big Data, Zhaoqing University, Zhaoqing 526061, Guangdong, China; 2. School of Information Engineering, Wuhan University of Technology, Wuhan 430070, Hubei, China)

Received:2018-06-01 Revised:2018-11-11 Online:2020-02-20 Published:2020-02-20

摘要/Abstract

摘要： 针对多行程车辆路径问题，先后通过标准差分进化-编码与解码-适应度计算-变邻域局部搜索过程找到最优方案，构建了一种改进差分变邻域搜索算法。该算法采用了基于轮盘赌的编码与解码方法，克服了标准差分进化算法无法适用于离散问题的缺点；同时，利用变邻域优化技术进一步强化标准差分进化算法的深度开发能力与优化性能。最后采用MATLAB中的随机函数进行仿真结果对比，验证了该算法在求解多行程车辆路径问题方面的优越性。

关键词: 交通运输工程, 多行程, 编码, 解码, 优化

Abstract: Aiming at multi-trip vehicle routing problem, the optimal solution was successively found out by standard differential evolution-encoding and decoding-fitness calculation-variable neighborhood local search procedure, and an improved difference variable neighborhood search algorithm was established. The proposed algorithm adopted the encoding and decoding method based on roulette, and overcame the shortcomings of the standard differential evolution algorithm which couldnt be applied to the discrete problem. At the same time, the depth development ability and optimization performance of the standard differential evolution algorithm were further strengthened by using the variable neighborhood optimization technique. Finally, the simulation results were compared by the random function in MATLAB, which proved the superiority of the proposed algorithm in solving the multi-trip vehicle routing problem.

Key words: traffic and transportation engineering, multi-trip, coding, decoding, optimization

中图分类号:

U491

宋强1,2. 基于改进差分变邻域算法的多行程车辆路径问题的研究[J]. 重庆交通大学学报（自然科学版）, 2020, 39(02): 35-42.

SONG Qiang1,2. Multi-trip Vehicle Routing Problem Based on the Improved Difference Variable Neighborhood Search Algorithm[J]. Journal of Chongqing Jiaotong University(Natural Science), 2020, 39(02): 35-42.

参考文献

［1］李佳.多行程模式下机场接送服务车次分配与调度问题的精确算法研究［D］. 沈阳：东北大学, 2013.
LI Jia. Study on the Precise Algorithm of the Allocation and Scheduling of Airport Pickup Service in Multi-Stroke Mode ［D］. Shenyang:Northeast University, 2013.
［2］张媛媛,曾晓燕.多行程带时间窗的车辆调度问题研究［J］.数学的实践与认识, 2015,45(7):1-7.
ZHANG Yuanyuan, ZENG Xiaoyan. Research on multi-stroke vehicle scheduling with time Windows［J］. Practice and Understanding of Mathematics, 2015,45(7):1-7.
［3］许争争,唐加福.基于协作的三阶段启发式算法求解多行程车辆行程问题［J］. 南开大学学报(自然科学版), 2015,48(5):51-59.
XU Zhengzheng, TANG Jiafu. Solving the multi-stroke vehicle travel problem based on the cooperative three-stage heuristic algorithm［J］. Journal of Nankai
University (Nature Science Edition), 2015,48 (5):51-59.
［4］梁文博. 多车程带时间窗车辆路径问题的模型和算法［D］. 大连: 大连理工大学, 2011.
LIANG Wenbo. Model and Algorithm of Vehicle Path Problem with Time Window for Multi-Vehicle Driving ［D］. Dalian :Dalian University of Technology, 2011.
［5］ FLEISCHMANN B. The vehicle routing problem with multiple use of vehicles［R］∥Working paper, Fachbereich Wirtschaftswissenschaft-en. Universita of Hamburg,
1990.
［6］ TAILLARD E, LAPORTE G, GENDREAU M. Vehicle routing problem with multiple use of vehicles［J］. Journal of the Operational Research Society, 1996, 47(8):
1065-1070.
［7］ BRANDAO J, MERCER A. The Multi-trip vehicle routing problem ［J］. Journal of the Operational Research Society, 1998, 49(8): 799-805.
［8］ PETCH R J, SALHI S. A multi-phase constructive heuristic for the vehicle routing problems with multiple trips ［J］.Discrete Applied Mathematics, 2003, 133
(1): 69-92.
［9］ OLIVERA A, VIERA O. Adaptive memory programming for the vehicle routing problem with multiple trips ［J］. Computers & Operations Research, 2007, 34(1):28-
47.
［10］ SALHI S, PETCH R J. A GA based heuristic for the vehicle routing problem with multiple trips ［J］. Journal of Mathematical Modeling and Algorithms, 2007,
6(4): 591-613.
［11］ JARBOUI B, DERBEL H, HANAFI S N，et al. Variable neighbor-hood search for location routing ［J］. Computers & Operations Research, 2013, 40(1): 47-57.
［12］ STOM R, PRICE K. Differential evolution-a simple and efficient heuristic for global optimization over continuous spaces ［J］. Journal of Global
Optimization, 1997, 11(4):341-359.
［13］ STOM R, PRICE K, LAMPINEN J. The Motivation for Differen-tial Evolution ［M］//Berlin Heidelbery:Springer Press, 2005:1-36.
［14］刘志君, 高亚奎, 章卫国,等. 变邻域分解多目标自适应差分进化算法［J］. 控制理论与应用, 2014, 31(11):1492-1501.
LIU Zhijun, GAO Yakui, ZHANG Weiguo, et al. Variable-neighborhood decomposition multi-objective adaptive differential evolution algorithm ［J］. Control Theory and
Application, 2014, 31(11):1492-1501.
［15］梁峰. 基于BPSO和变邻域差分进化算法的配电网重构［D］. 吉林：东北电力大学, 2011.
LIANG Feng. Distribution Network Reconstruction Based on BPSO and Variable-Neighborhood Differential Evolution Algorithm ［D］. Jilin:Northeast Electric Power
University, 2011.
［16］赵洋, 贺毅朝, 李晰. 具有自加速与变邻域搜索的差分演化算法［J］. 计算机应用, 2012, 32(10):2911-2915.
ZHAO Yang, HE Yichao, LI Xi. Differential evolution algorithm with self-accelerating and variable neighborhood search ［J］. Computer Application, 2012, 32
(10):2911-2915.
［17］崔喆. 基于群智能优化算法的流水车间调度问题若干研究［D］.上海：华东理工大学, 2014.
CUI Zhe. A Number of Studies on Scheduling Problem of Flow Workshop Based on Swarm Intelligence Optimization Algorithm ［D］. Shanghai:East China University of
Technology, 2014.
［18］张铃, 张拔. 遗传算法机理的研究［J］. 软件学报, 2000, 11(7): 945-952.
ZHANG Ling, ZHANG Ba. Research on the mechanism of genetic algorithm ［J］. Software Journal, 2000, 11(7): 945-952.
［19］张银雪, 田学民, 曹玉苹. 改进搜索策略的人工蜂群算法［J］. 计算机应用, 2012, 32(12):3326-3330.
ZHANG Yinxue, TIAN Xuemin, CAO Yuping. Artificial swarm optimization algorithm for improved search strategy ［J］. Computer Application, 2012, 32(12):3326-3330.
［20］李宁, 邹彤, 孙德宝. 车辆路径问题的粒子群算法研究［J］. 系统工程学报, 2004, 19(6):596-600.
LI Ning, ZOU Tong, SUN Debao. Particle swarm optimization algorithms for vehicle path problems ［J］. Journal of Systems Engineering, 2004, 19(6):596-600.

[1]	李晶1,2，钟鹏1，吕靖1,2. 基于系统动力学的陆港与城市经济互动研究[J]. 重庆交通大学学报（自然科学版）, 2021, 40(07): 1-7.
[2]	李军1，朱云升2. 三角模糊层次分析的综合评价在黄河库区船舶安全评估中的应用[J]. 重庆交通大学学报（自然科学版）, 2021, 40(07): 16-22.
[3]	邓萍1,2，宋莲1，黄承锋1,2. 三峡坝区过闸船舶拥堵成本测算及对坝区货物总价值影响研究[J]. 重庆交通大学学报（自然科学版）, 2021, 40(07): 23-30.
[4]	程谦1 ，朱晓宁2 ，卢万胜3. 中长运距城际旅客出行方式选择行为模型——以高铁、民航为例[J]. 重庆交通大学学报（自然科学版）, 2021, 40(07): 39-45.
[5]	连齐才1，李涵1，石小林1，闫章存2. 基于面板数据Mixed logit模型的自动驾驶选择行为分析[J]. 重庆交通大学学报（自然科学版）, 2021, 40(07): 46-52.
[6]	戚春华，王笑男，朱守林，李航天. 基于驾驶员视觉兴趣区域的交通工程设施信息量阈值研究[J]. 重庆交通大学学报（自然科学版）, 2021, 40(07): 53-60.
[7]	李升朝，吴越，白雪萌，王玥，张海. 基于TOPSIS与灰色关联的危货车辆违规报警研究[J]. 重庆交通大学学报（自然科学版）, 2021, 40(07): 61-66.
[8]	杨庆芳1,2,3，王立强2，郑黎黎1,2,3，孟凡运2. 一种环形交叉口交通排放及燃油消耗模型研究[J]. 重庆交通大学学报（自然科学版）, 2021, 40(07): 67-73.
[9]	张东东，宗子淳，冯金芝. 基于NSGA-Ⅱ算法的两挡AMT换挡规律多目标优化[J]. 重庆交通大学学报（自然科学版）, 2021, 40(07): 128-135.
[10]	白翰，张康宇，王修光，燕翔，冯启龙. 合放交通流条件下城市交叉口通行能力研究[J]. 重庆交通大学学报（自然科学版）, 2021, 40(06): 12-20.
[11]	张重阳,黄淑萍. 路网抗震可靠性及震后运输调度路径选择研究[J]. 重庆交通大学学报（自然科学版）, 2021, 40(06): 43-51.
[12]	郭文文1，计明军2，祝慧灵3，周文杰2. 集装箱码头场桥调度优化模型研究[J]. 重庆交通大学学报（自然科学版）, 2021, 40(06): 66-72.
[13]	李广儒，张新，朱庆辉. 基于Adaboost的改进Elman神经网络港口吞吐量预测方法[J]. 重庆交通大学学报（自然科学版）, 2021, 40(05): 1-5.
[14]	孙元广1，茧敏2，金华2，陈绍宽2. 城市轨道交通列车故障救援延误计算与仿真[J]. 重庆交通大学学报（自然科学版）, 2021, 40(05): 6-12.
[15]	王宏刚1,2，白朋1，邹庆茹2，赵玲1. 地铁车辆段股道运用优化模型[J]. 重庆交通大学学报（自然科学版）, 2021, 40(05): 13-18.

基于改进差分变邻域算法的多行程车辆路径问题的研究

Multi-trip Vehicle Routing Problem Based on the Improved Difference Variable Neighborhood Search Algorithm

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics