不确定车辆数的多约束车辆路径问题

doi:10.3778/j.issn.1002-8331.2310-0186

摘要/Abstract

摘要： 在经典车辆路径问题（vehicle routing problem，VRP）的基础上增加了客户要求访问的时间窗约束，以车辆行驶路径最短和使用车辆数最小为目标，建立了不确定车辆数的多约束车辆路径问题（multi-constraint vehicle routing problem with variable fleets，MVRP-VF）的数学模型。引入遗传算法的交叉操作以及大规模邻域搜索算法中的破坏算子和修复算子，重新定义了基本灰狼优化算法（grey wolf optimizer，GWO）的操作算子，优化了GWO的寻优机制，从而设计出用于求解MVRP-VF问题的混合灰狼优化算法（hybrid grey wolf optimizer，HGWO）。通过仿真实验与其他参考文献中的算法求解结果进行比较，验证了HGWO求解该类问题的有效性与可行性。

关键词: 交通工程, 车辆路径问题, 混合灰狼优化算法, 不确定车辆数, 时间窗

Abstract: On the basis of the classical vehicle routing problem (VRP), this paper adds the time window constraints customer-required, and establishes a mathematical model of the multi-constraint vehicle routing problem with variable fleets (MVRP-VF) with the objective of shortest vehicle routing and the minimum number of vehicles used. By introducing the crossover operation of the genetic algorithm (GA) and the destroy operator and repair operator of the large neighborhood search (LNS), this paper redefines the operator and optimizes the optimization-seeking mechanism of the basic grey wolf optimizer (GWO). A hybrid grey wolf optimizer (HGWO) algorithm is designed for solving the MVRP-VF model. The effectiveness and feasibility of the HGWO for solving the MVRP-VF are verified by comparing the results of simulation experiments with the algorithms in other references.

Key words: traffic engineering, vehicle routing problem, hybrid grey wolf optimizer, variable fleet, time window

马祥丽, 马良, 张惠珍. 不确定车辆数的多约束车辆路径问题[J]. 计算机工程与应用, 2025, 61(6): 369-376.

MA Xiangli, MA Liang, ZHANG Huizhen. Multi-Constraint Vehicle Routing Problem with Variable Fleets[J]. Computer Engineering and Applications, 2025, 61(6): 369-376.

参考文献

[1] DANTZIG G B, RAMSER J H. The truck dispatching problem[J]. Management Science, 1959, 6(1): 80-91.
[2] SOLOMON M M. Algorithms for the vehicle routing and scheduling problems with time window constraints[J]. Operations Research, 1987, 35(2): 254-265.
[3] POTVIN J Y, DUBE D, ROBILLARD C. A hybrid approach to vehicle routing using neural networks and genetic algorithms[J]. Applied Intelligence: the International Journal of Artificial Intelligence, Neural Networks, and Complex Problem-Solving Technologies, 1996, 6(3): 241-252.
[4] BERGER J, SALOIS M, BEGIN R. A hybrid genetic algorithm for the vehicle routing poblem with time windows[J]. Lecture Notes in Computer Science, 1998, 1418(1): 114-127.
[5] BAKER B M, AYECHEW M A. A genetic algorithm for the vehicle routing problem[J]. Computers and Operations Research, 2003, 30(5): 787-800.
[6] BERGER J, BARKAOUI M. A parallel hybrid genetic algorithm for the vehicle routing problem with time windows[J]. Computers and Operations Research, 2004, 31(12): 2037-2053.
[7] LIU R, TAO Y Y, XIE X L. An adaptive large neighborhood search heuristic for the vehicle routing problem with time windows and synchronized visits[J]. Computers and Operations Research, 2019, 101: 250-262.
[8] GUTIERREZ A, DIEULLE L, LABADIE N, et al. A multi-population algorithm to solve the VRP with stochastic service and travel times[J]. Computers & Industrial Engineering, 2018, 125: 144-156.
[9] 刘云, 张惠珍. 多目标带时间窗的车辆路径问题的单亲遗传混合蚁群算法[J]. 公路交通科技, 2016, 33(6): 95-100.
LIU Y, ZHANG H Z. A partheno-genetic hybrid ant colony algorithm for solving multi-objective vehicle routing problem with time window[J]. Journal of Highway and Transportation Research Development, 2016, 33(6): 95-100.
[10] 范厚明, 吴嘉鑫, 耿静, 等. 模糊需求与时间窗的车辆路径问题及混合遗传算法求解[J]. 系统管理学报, 2020, 29(1): 107-118.
FAN H M, WU J X, GENG J, et al. Hybrid genetic algorithm for solving fuzzy demand and time windows vehicle routing problem[J]. Journal of Systems & Management, 2020, 29(1): 107-118.
[11] 雷金羡, 孙宇, 朱洪杰. 改进蚁群算法在带时间窗车辆路径规划问题中的应用[J]. 计算机集成制造系统, 2022, 28(11): 3535-3544.
LEI J X, SUN Y, ZHU H J. Improved ant colony optimization algorithm for vehicle routing problems with time window[J]. Computer Integrated Manufacturing Systems, 2022, 28(11): 3535-3544.
[12] 何美玲, 魏志秀, 武晓晖, 等. 基于改进蚁群算法求解带软时间窗的车辆路径问题[J]. 计算机集成制造系统, 2023, 29(3): 1029-1039.
HE M L, WEI Z X, WU X H, et al. Improved ant colony optimization algorithm for solving vehicle routing problem with soft time windows[J]. Computer Integrated Manufacturing Systems, 2023, 29(3): 1029-1039.
[13] 文展, 唐康健, 李文藻. 一种改进粒子群优化算法在车辆路径问题的应用研究[J]. 重庆邮电大学学报 (自然科学版), 2020, 32(5): 891-897.
WEN Z, TANG K J, LI W Z. Research on application of vehicle routing problem using an enhanced particle swarm optimization[J]. Journal of Chongqing University of Posts and Telecommunications (Natural Science Edition), 2020, 32(5): 891-897.
[14] 叶勇, 张惠珍. 求解带时间窗车辆路径问题的狼群算法[J]. 公路交通科技, 2017, 34(10): 100-107.
YE Y, ZHANG H Z. Wolf pack algorithm for solving vehicle routing problem with time windows[J]. Journal of Highway and Transportation Research and Development, 2017, 34(10): 100-107.
[15] 张晓楠, 范厚明. 求解带时间窗车辆路径问题的混合Memetic算法[J]. 运筹与管理, 2021, 30(7): 128-135.
ZHANG X N, FAN H M. Hybrid memetic algorithm for vehicle routing problem with time windows[J]. Operations Research and Management Science, 2021, 30(7): 128-135.
[16] 殷亚, 张惠珍. 求解带硬时间窗的多目标车辆路径问题的多种混合蝙蝠算法[J]. 计算机应用研究, 2017, 34(12): 3632-3636.
YIN Y, ZHANG H Z. Multi-hybrid bat algorithm for solving multi-objectives vehicle routing problem with hard time-window[J]. Application Research of Computers, 2017, 34(12): 3632-3636.
[17] 张瑾, 洪莉, 戴二壮. 求解带容量和时间窗约束车辆路径问题的改进蝙蝠算法[J]. 计算机工程与科学, 2021, 43(8): 1479-1487.
ZHANG J, HONG L, DAI E Z. An improved bat algorithm for the vehicle routing problem with time windows and capacity constraints[J]. Computer Engineering & Science, 2021, 43(8): 1479-1487.
[18] 张建同, 丁烨. 变邻域模拟退火算法求解速度时变的VRPTW问题[J]. 运筹与管理, 2019, 28(11): 77-84.
ZHANG J T, DING Y. Simulated annealing with variable neighborhood for time-dependent vehicle routing problem with time window[J]. Operations Research and Management Science, 2019, 28(11): 77-84.
[19] 魏小迪, 郑洪清. 求解带时间窗车辆路径问题的改进离散花朵授粉算法[J]. 数学的实践与认识, 2020, 50(2): 193-200.
WEI X D, ZHENG H Q. Improved discrete flower pollination algorithm for vehicle routing problem with time window[J]. Mathematics in Practice and Theory, 2020, 50(2): 193-200.
[20] MIRJALILI S, MIRJALILI S M, LEWIS A. Grey wolf optimizer[J]. Advances in Engineering Software, 2014, 69(3): 46-61.
[21] SHAW P. A new local search algorithm providing high quality solutions to vehicle routing problems[R]. Glasgow, Scotland: University of Strathclyde, 1997.
[22] ROPKE S, PISINGER D. An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows[J]. Transportation Science, 2006, 40(4): 455-472.
[23] 胡俊桥. 蚁群混合算法求解带时间窗车辆路径问题[D]. 西安: 西安科技大学, 2017.
HU J Q. Hybrid ant colony algorithm for logistics distribution problem with time windows[D]. Xi’an: Xi’an University of Science and Technology, 2017.

编辑推荐 0

Metrics

阅读次数

全文

HTML			PDF

最新录用	在线预览	正式出版	最新录用	在线预览	正式出版
0	0	0	0	0	42

来源	本网站	其他网站

次数	40	2
比例	95%	5%

摘要

最新录用	在线预览	正式出版

0	0	36

	来源	本网站

	次数	36
	比例	100%