Research Progress of Vehicle Routing Problem

JIANG Hua-wei; GUO Tao; YANG Zhen

doi:10.12263/DZXB.20201154

您当前的位置：

首页 >

文章列表页 >

Research Progress of Vehicle Routing Problem

SURVEYS AND REVIEWS | 更新时间：2025-12-08

- Research Progress of Vehicle Routing Problem
- ACTA ELECTRONICA SINICA Vol. 50, Issue 2, Pages: 480-492(2022)
- 作者机构：
  
  1.粮食信息处理与控制教育部重点实验室(河南工业大学)，河南郑州 450001
  2.河南工业大学信息科学与工程学院，河南郑州 450001
- 作者简介：
- 基金信息：
- DOI：10.12263/DZXB.20201154
  CLC： TP399;
- Received：19 October 2020，
  
  Revised：2021-01-30，
  
  Published：25 February 2022
- 稿件说明：
移动端阅览
蒋华伟,郭陶,杨震.车辆路径问题研究进展[J].电子学报,2022,50(02):480-492.

JIANG Hua-wei,GUO Tao,YANG Zhen.Research Progress of Vehicle Routing Problem[J].ACTA ELECTRONICA SINICA,2022,50(02):480-492.
蒋华伟,郭陶,杨震.车辆路径问题研究进展[J].电子学报,2022,50(02):480-492. DOI： 10.12263/DZXB.20201154.

JIANG Hua-wei,GUO Tao,YANG Zhen.Research Progress of Vehicle Routing Problem[J].ACTA ELECTRONICA SINICA,2022,50(02):480-492. DOI： 10.12263/DZXB.20201154.

摘要

车辆路径作为经典的组合优化问题一直是研究的热点与难点，无论是在应急管理工作还是物流配送中，对它的合理规划都至关重要.为了今后更好地开展相关工作，本文回顾了精确算法、启发式算法和机器学习算法在车辆路径优化问题中的研究进展，并基于Solomon标准数据集对六种经典算法的求解性能进行了比较分析；分别从局部最优和收敛速度间的平衡关系、个体评价函数、动态车辆路径问题以及机器学习算法在车辆路径问题中的应用等四个方面对其发展趋势进行了展望.

Abstract

As a classical combinatorial optimization problem

vehicle routing has always been a hot and difficult research topic. It is very important to make reasonable planning for it in both emergency management and logistics distribution. In order to better carry out related work in the future

this paper reviewed the research progress of exact algorithm

heuristic algorithm

and machine learning algorithm in vehicle routing optimization problem. Then the comparisons of the performance of six classical algorithms were conducted based on Solomon standard data set. The development trend was prospected from the aspects of balance relationship between the local optimum and the convergence speed

individual evaluation function

dynamic vehicle routing problem

and the application of machine learning algorithms in the vehicle routing problem.

关键词

Keywords

references

DANTZIG G B , RAMSER J H . The truck dispatching problem [J]. Management Science , 1959 , 6 ( 1 ): 80 - 91 .

DORLING K , HEINRICHS J , MESSIER G G , et al . Vehicle routing problems for drone delivery [J]. IEEE Transactions on Systems, Man, and Cybernetics: Systems , 2017 , 47 ( 1 ): 70 - 85 .

戚远航 , 蔡延光 , 蔡颢 , 等 . 带时间窗的车辆路径问题的离散蝙蝠算法 [J]. 电子学报 , 2018 , 46 ( 3 ): 672 - 679 .

QI Y H , CAI Y G , CAI H , et al . Discrete bat algorithm for vehicle routing problem with time window [J]. Acta Electronica Sinica , 2018 , 46 ( 3 ): 672 - 679 . （in Chinese）

LAU H C W , CHAN T M , TSUI W T , et al . Application of genetic algorithms to solve the multidepot vehicle routing problem [J]. IEEE Transactions on Automation Science & Engineering , 2010 , 7 ( 2 ): 383 - 392 .

易云飞 , 蔡永乐 , 董文永 , 等 . 求解带用户满意度的多目标实时车辆路径问题的改进伊藤算法 [J]. 电子学报 , 2015 , 43 ( 10 ): 2053 - 2061 .

YI Y F , CAI Y L , DONG W Y , et al . Improved ITO algorithm for multiobjective real-time vehicle routing problem with customers’ satisfaction [J]. Acta Electronica Sinica , 2015 , 43 ( 10 ): 2053 - 2061 . （in Chinese）

KIM G , ONG Y S , CHEONG T , et al . Solving the dynamic vehicle routing problem under traffic congestion [J]. IEEE Transactions on Intelligent Transportation Systems , 2016 , 17 ( 8 ): 2367 - 2380 .

王江晴 , 覃俊 , 李子茂 . 求解动态最优路径的混合优化算法 [J]. 通信学报 , 2008 , 29 ( 7 ): 135 - 140 .

WANG J Q , QIN J , LI Z M . Hybrid optimization algorithm for dynamic optimal path [J]. Journal on Communications , 2008 , 29 ( 7 ): 135 - 140 . （in Chinese）

涂伟 , 李清泉 , 方志祥 . 一种大规模车辆路径问题的启发式算法 [J]. 武汉大学学报(信息科学版) , 2013 , 38 ( 3 ): 307 - 310, 338 .

TU W , LI Q Q , FANG Z X . A heuristic algorithm for largescale vehicle routing problem [J]. Geomatics and Information Science of Wuhan University , 2013 , 38 ( 3 ): 307 - 310, 338 . （in Chinese）

黄戈文 , 蔡延光 , 戚远航 , 等 . 自适应遗传灰狼优化算法求解带容量约束的车辆路径问题 [J]. 电子学报 , 2019 , 47 ( 12 ): 2602 - 2610 .

HUANG G W , CAI Y G , QI Y H , et al . Adaptive genetic gray wolf optimizer algorithm for vehicle routing problem with capacity constraint [J]. Acta Electronica Sinica , 2019 , 47 ( 12 ): 2602 - 2610 . （in Chinese）

LAWLER E L , WOOD D E . Branch-and-bound methods: A survey [J]. Operations Research , 1966 , 14 ( 4 ): 699 - 719 .

PECIN D , CONTARDO C , DESAULNIERS G , et al . New enhancements for the exact solution of the vehicle routing problem with time windows [J]. Informs Journal on Computing , 2017 , 29 ( 3 ): 489 - 502 .

CESELLI A , RIGHINI G , TRESOLDI E . Vehicle routing problems with different service constraints: A branch‐and-cut-and-price algorithm [J]. Networks , 2014 , 64 ( 4 ): 282 - 291 .

SANTOS F A , MATEUS G R , DA CUNHA A S . A branch-and-cut-and-price algorithm for the two-echelon capacitated vehicle routing problem [J]. Transportation Science , 2013 , 49 ( 2 ): 355 - 368 .

DANTZIG G B , WOLFE P . Decomposition principle for linear programs [J]. Operations Research , 1960 , 8 ( 1 ): 101 - 111 .

CHABRIER A . Vehicle routing problem with elementary shortest path based column generation [J]. Computers & Operations Research , 2006 , 33 ( 10 ): 2972 - 2990 .

HERNANDEZ F , FEILLET D , GIROUDEAU R , et al . Branch-and-price algorithms for the solution of the multi-trip vehicle routing problem with time windows [J]. European Journal of Operational Research , 2016 , 249 ( 2 ): 551 - 559 .

PECIN D , PESSOA A , POGGI M , et al . Improved branch-cut-and-price for capacitated vehicle routing [C]// Integer Programming and Combinatorial Optimization . Bonn, Germany : Springer, Cham , 2014 : 393 - 403 .

FUKASAWA R , LONGO H , LYSGAARD J , et al . Robust branch-and-but-and-price for the capacitated vehicle routing problem [J]. Math-ematical Programming , 2006 , 106 ( 3 ): 491 - 511 .

BELLMAN R . Dynamic programming [J]. Science , 1966 , 153 ( 3731 ): 34 - 37 .

SOYSAL M , CIMEN M . A simulation based restricted dynamic programming approach for the green time dependent vehicle routing problem [J]. Computers & Operations Research , 2017 , 88 ( 12 ): 297 - 305 .

XIAO Y , KONAK A . A genetic algorithm with exact dynamic programming for the green vehicle routing & scheduling problem [J]. Journal of Cleaner Production , 2016 , 167 : 1450 - 1463 .

MARINELLI M , COLOVIC A , DELL’ORCO M . A novel dynamic programming approach for two-echelon capacitated vehicle routing problem in city logistics with environmental considerations [J]. Transportation Research Procedia , 2018 , 30 : 147 - 156 .

DORIGO M , MANIEZZO V , COLORNI A . Ant System: Optimization by a colony of cooperating agents [J]. IEEE Transactions on Systems, Man, and Cybernetics-Part B: Cybernetics , 1996 , 26 ( 1 ): 29 - 41 .

KUO R J , WIBOWO B S , ZULVIA F E . Application of a fuzzy ant colony system to solve the dynamic vehicle routing problem with uncertain service time [J]. Applied Mathematical Modelling , 2016 , 40 ( 23-24 ): 9990 - 10001 .

TANG Y L , CAI Y G , YANG Q J . Improved ant colony optimization for multi-depot heterogeneous vehicle routing problem with soft time windows [J]. Journal of Southeast University(English Edition) , 2015 , 31 ( 1 ): 94 - 99 .

ZHANG H , ZHANG Q , MA L , et al . A hybrid ant colony optimization algorithm for a multi-objective vehicle routing problem with flexible time windows [J]. Information Sciences , 2019 , 490 : 166 - 190 .

胡蓉 , 李洋 , 钱斌 , 等 . 结合聚类分解的增强蚁群算法求解复杂绿色车辆路径问题 [J/OL]. 自动化学报 , 2020 : 1 - 16 . https://doi.org/10.16383/j.aas.c190872 https://doi.org/10.16383/j.aas.c190872 .

HU R , LI Y , QIAN B , et al . Enhanced ant colony algorithm combined with clustering decomposition for complex green vehicle routing problem [J/OL]. Acta Automatica Sinica , 2020 : 1 - 16 . https://doi.org/10.16383/j.aas. c190872. https://doi.org/10.16383/j.aas.c190872. （in Chinese）

MAVROVOUNIOTIS M , YANG S . Ant algorithms with immigrants schemes for the dynamic vehicle routing problem [J]. Information Sciences , 2015 , 294 : 456 - 477 .

NARASIMHA K , KIVELEVITCH E , SHARMA B , et al . An ant colony optimization technique for solving min-max multi-depot vehicle routing problem [J]. Swarm and Evolutionary Computation , 2013 , 13 : 63 - 73 .

YAO B , CHEN C , SONG X , et al . Fresh seafood delivery routing problem using an improved ant colony optimization [J]. Annals of Operations Research , 2019 , 273 ( 1-2 ): 163 - 186 .

HOLLAND J H . Adaptation in Natural and Artificial Systems [M]. USA : University of Michigan Press , 1975 : 126 - 137 .

SRIPRIYA J , RAMALINGAM A , RAJESWARI K . A hybrid genetic algorithm for vehicle routing problem with time windows [C]// International Conference on Innovations in Information, Embedded and Communication Systems . Coimbatore, India : IEEE , 2015 : 1 - 4 .

BOUCHRA B , BTISSAM D , MOHAMMAD C . A hybrid genetic algorithm for the static and dynamic vehicle routing problem with soft time windows [C]// International Conference on Logistics Operations Management . Fez, Morocco : IEEE , 2016 : 1 - 9 .

WANG K , LAN S , ZHAO Y . A genetic-algorithm-based approach to the two-echelon capacitated vehicle routing problem with stochastic demands in logistics service [J]. Journal of the Operational Research Society , 2017 , 68 ( 11 ): 1409 - 1421 .

MA Y , LI Z , YAN F , et al . A hybrid priority-based genetic algorithm for simultaneous pickup and delivery problems in reverse logistics with time windows and multiple decision-makers [J]. Soft Computing , 2019 , 23 ( 15 ): 6697 - 6714 .

ERFAN T , ALI H , MEHDI S , et al . A hybrid genetic algorithm for multi-trip green capacitated arc routing problem in the scope of urban services [J]. Sustainability , 2018 , 10 ( 5 ): 1366 .

WANG S , LU Z , WEI L , et al . Fitness-scaling adaptive genetic algorithm with local search for solving the multiple depot vehicle routing problem [J]. Simulation: Transactions of the Society for Modeling and Simulation International , 2016 , 92 ( 7 ): 601 - 616 .

CATTARUZZA D , ABSI N , FEILLET D , et al . The multi-trip vehicle routing problem with time windows and release dates [J]. Transportation Science , 2015 , 50 ( 2 ): 676 - 693 .

PIERRE D M , ZAKARIA N . Stochastic partially optimized cyclic shift crossover for multi-objective genetic algorithms for the vehicle routing problem with time-windows [J]. Applied Soft Computing , 2016 , 52 : 863 - 876 .

ALIJLA B O , WONG L P , LIM C P , et al . An ensemble of intelligent water drop algorithms and its application to optimization problems [J]. Information Sciences , 2015 , 325 : 175 - 189 .

EZUGWU A E , OLUSANYA M O , ADEWUMI A O . A hybrid method based on intelligent water drop algorithm and simulated annealing for solving multi-depot vehicle routing problem [C]// Advances in Intelligent Systems and Computing . Cham, Germany : Springer , 2017 : 204 - 219 .

TEYMOURIAN E , KAYVANFAR V , KOMAKI G M , et al . Enhanced intelligent water drops and cuckoo search algorithms for solving the capacitated vehicle routing problem [J]. Information Sciences , 2016 , 334/335 : 354 - 378 .

KENNEDY J , EBERHART R . Particle swarm optimization [C]// International Conference on Neural Networks . Perth, WA, Australia : IEEE , 1995 : 1942 - 1948 .

MIRHASSANI S A , ABOLGHASEMI N . A particle swarm optimization algorithm for open vehicle routing problem [J]. Expert Systems with Applications , 2011 , 38 ( 9 ): 11547 - 11551 .

ALINAGHIAN M , GHAZANFARI M , NOROUZI N , et al . A novel model for the time dependent competitive vehicle routing problem: Modified random topology particle swarm optimization [J]. Networks and Spatial Economics , 2017 , 17 ( 4 ): 1 - 27 .

GALLEGO R A , ROMERO R . Tabu search algorithm for network synthesis [J]. IEEE Transactions on Power Systems , 2000 , 15 ( 2 ): 490 - 495 .

李国明 , 李军华 . 基于混合禁忌搜索算法的随机车辆路径问题研究 [J/OL]. 控制与决策 , 2020 : 1 - 10 . https: //doi.org/10.13195/j.kzyjc.2020.0107 https://doi.org/10.13195/j.kzyjc.2020.0107 .

LI G M , LI J H . Research on stochastic vehicle routing problem based on hybrid tabu search algorithm [J/OL]. Control and Decision , 2020 : 1 - 10 . https://doi.org/10. 13195/j.kzyjc.2020.0107. https://doi.org/10.13195/j.kzyjc.2020.0107. （in Chinese）

ZHANG D , CAI S , YE F , et al . A hybrid algorithm for a vehicle routing problem with realistic constraints [J]. Information Sciences , 2017 , 394/395 : 167 - 182 .

JAIN A K , MAO J , MOHIUDDIN K M . Artificial neural networks: A tutorial [J]. Computer , 1996 , 29 ( 3 ): 31 - 44 .

STEINHAUS M , SHIRAZI A N , SODHI M . Modified self organizing neural network algorithm for solving the vehicle routing problem [C]// International Conference on Computational Science & Engineering . Porto, Portugal : IEEE , 2015 : 246 - 252 .

YOSHIIKE N , TAKEFUJI Y . Vehicle routing problem using clustering algorithm by maximum neural networks [C]// International Conference on Intelligent Processing & Manufacturing of Materials . Honolulu, USA : IEEE , 1999 : 1109 - 1113 .

SHENG Y , MA H , XIA W . A pointer neural network for the vehicle routing problem with task priority and limited resources [J]. Information Technology and Control , 2020 , 49 ( 2 ): 237 - 248 .

YU J J Q , YU W , GU J . Online vehicle routing with neural combinatorial optimization and deep reinforcement learning [J]. IEEE Transactions on Intelligent Transportation Systems , 2019 , 20 ( 10 ): 3806 - 3817 .

WANG H B , GU M , YU Q , et al . Adaptive and large-scale service composition based on deep reinforcement learning [J]. Knowledge-Based Systems , 2019 , 180 ( 15 ): 75 - 90 .

高阳 , 陈世福 , 陆鑫 . 强化学习研究综述 [J]. 自动化学报 , 2004 , 30 ( 1 ): 86 - 100 .

GAO Y , CHEN S F , LU X . A review of reinforcement learning [J]. Acta Automatica Sinica , 2004 , 30 ( 1 ): 86 - 100 . （in Chinese）

PENG B , ZHANG Y , GAJPAL Y , et al . A memetic algorithm for the green vehicle routing problem [J]. Sustainability , 2019 , 11 ( 21 ): 6055 .

LOPES SILVA M A , DE SOUZA S R , FREITAS SOUZA M J , et al . A reinforcement learning-based multi-agent framework applied for solving routing and scheduling problems [J]. Expert Systems with Applications , 2019 , 131 ( 10 ): 148 - 171 .

SAMMA H , LIM C P , SALEH J M . A new reinforcement learning-based memetic particle swarm optimizer [J]. Applied Soft Computing , 2016 , 43 : 276 - 297 .

PENG B , WANG J H , ZHANG Z Z . A deep reinforcement learning algorithm using dynamic attention model for vehicle routing problems [C]// Artificial Intelligence Algorithms and Applications . Singapore : Springer , 2019 : 636 - 650 .

DESROCHERS M , DESROSIERS J , SOLOMON M . A new optimization algorithm for the vehicle routing problem with time windows [J]. Operations Research , 1992 , 40 ( 2 ): 342 - 354 .

IRNICH S , DESAULNIERS G . Shortest path problems with resource constraints [C]// Column Generation . Boston, USA : Springer , 2005 : 33 - 65 .

SECOMANDI N . Comparing neuro-dynamic programming algorithms for the vehicle routing problem with stochastic demands [J]. Computers & Operations Research , 2000 , 27 ( 11-12 ): 1201 - 1225 .

吴华锋 , 陈信强 , 毛奇凰 , 等 . 基于自然选择策略的蚁群算法求解TSP问题 [J]. 通信学报 , 2013 , 34 ( 4 ): 165 - 170 .

WU H F , CHEN X Q , MAO Q H , et al . Ant colony algorithm based on natural selection strategy for solving TSP problem [J]. Journal on Communications , 2013 , 34 ( 4 ): 165 - 170 . （in Chinese）

王燕 , 聂长海 , 钮鑫涛 , 等 . 覆盖表生成的禁忌搜索算法 [J]. 软件学报 , 2018 , 29 ( 12 ): 3665 - 3691 .

WANG Y , NIE C H , NIU X T , et al . Tabu search algorithm for covering table generation [J]. Journal of Software , 2018 , 29 ( 12 ): 3665 - 3691 . （in Chinese）

GHAZIRI H , OSMAN I H . Self-organizing feature maps for the vehicle routing problem with backhauls [J]. Journal of Scheduling , 2006 , 9 ( 2 ): 97 - 114 .

SUTTON R S , BARTO A G . Reinforcement Learning: An Introduction [M]. Cambridge, MA, USA : MIT Press , 1998 .

SOLOMON M M . VRPTW benchmark problems [EB/OL]. (2003) . http: //web.cba.neu.edu/msolomon/problems.htm http://web.cba.neu.edu/msolomon/problems.htm .

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

A Detection Method for Android Repackaged Malware Based on Sensitive Component Function Call Graph

Heuristic Clustering Algorithm Based on Sub-Game Perfect Equilibrium

Research on High-Efficiency Integrated Circuit DFT Technology Based on Machine Learning

DRHA-UIE: An Underwater Image Enhancement Method Based on Dual Residual Hybrid Attention Block

Cognitive Learning: A New Paradigm for Machine Learning in Electromagnetic Spectrum Environment

Related Author

DU Rui-ying

CHEN Jing

WU Cong

YAN Xi-yu

CHANG Lu-yao

NIU Xin-zheng

LUO Tao

QIAN Zao-guo

Related Institution

School of Computer and Information Engineering, Henan Normal University

School of Cyber Science and Engineering, Wuhan University

Key Laboratory of Aerospace Information Security and Trusted Computing, Ministry of Education, Wuhan University

Rizhao Institute of Information Technology, Wuhan University

Department of Electrical and Electronic Engineering, Faculty of Engineering, The University of Hong Kong

⁰