Analytics and machine learning in vehicle routing research

Abstract

The Vehicle Routing Problem (VRP) is one of the most intensively studied combinatorial optimisation problems for which numerous models and algorithms have been proposed. To tackle the complexities, uncertainties and dynamics involved in real-world VRP applications, Machine Learning (ML) methods have been used in combination with analytical approaches to enhance problem formulations and algorithmic performance across different problem solving scenarios. However, the relevant papers are scattered in several traditional research fields with very different, sometimes confusing, terminologies. This paper presents a first, comprehensive review of hybrid methods that combine analytical techniques with ML tools in addressing VRP problems. Specifically, we review the emerging research streams on ML-assisted VRP modelling and ML-assisted VRP optimisation. We conclude that ML can be beneficial in enhancing VRP modelling, and improving the performance of algorithms for both online and offline VRP optimisations. Finally, challenges and future opportunities of VRP research are discussed.

Keywords:

• Vehicle routing
• machine learning
• data driven methods
• uncertainties

Data availability statement

Data sharing is not applicable to this article as no new data were created or analysed in this study.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Notes

1 http://www.vrp-rep.org/, last accessed 4 July 2021.

2 https://developers.google.com/optimization/scheduling/job_shop

3 https://www.anylogic.com/features/artificial-intelligence/microsoft-bonsai/

Additional information

Funding

This work is supported by the National Natural Science Foundation of China [grant number 72071116] and the Ningbo Science and Technology Bureau [grant numbers 2019B10026, 2017D10034].

Notes on contributors

Ruibin Bai

Ruibin Bai is Professor at the University of Nottingham Ningbo China. He is a Senior Member of IEEE, currently serving as a Board Member for EJOR and an Associate Editor for Networks. He was awarded with Zhejiang Provincial ‘Outstanding Young Scientist’ Fund in 2016. His research areas include computational intelligence, reinforcement learning, combinatorial optimisation, transportation optimisation and digital twins.

Xinan Chen

Xinan Chen received the B.Eng. from the University of Electronic Science and Technology of China, the M.Re. degree from Liverpool University, and is currently a computer science Ph.D. candidate at the University of Nottingham Ningbo China. His research interests are mainly focused on hyper-heuristics, dynamic optimisation, evolutionary algorithms, reinforcement learning, and other related fields.

Zhi-Long Chen

Zhi-Long Chen received his Ph.D. degree in Operations Research from Princeton University in 1997. He is currently Orkand Corporation Professor of Management Science at the Robert H. Smith School of Business. His research interests cover supply chain scheduling, production and transportation operations, dynamic pricing, and optimisation. Dr Chen has conducted several NSF funded research projects on integrated production and distribution operations, coordination of dynamic pricing and scheduling, and transportation capacity planning. He is currently serving as an associate editor of Operations Research, POM, IIE Transactions, NRL, Networks, and Journal of Scheduling.

Tianxiang Cui

Tianxiang Cui obtained his Ph.D. from University of Nottingham UK in 2016 and currently he is an assistant professor in the School of Computer Science at the University of Nottingham Ningbo China (UNNC). Before joining UNNC, he was a senior AI engineer in Huawei and a senior algorithm researcher in PingAn. He was involved in some frontier industrial projects, including autonomous driving and quantitative trading. His main research interests include computational intelligence, particularly metaheuristic, evolutionary computation and neural networks; machine learning and reinforcement Learning.

Shuhui Gong

Shuhui Gong is an Assistant professor in Computer Science, China University of Geoscience (Beijing).

Wentao He

Wentao He received the B.Sc. degree from the University of Nottingham Ningbo China, in 2018, and the M.Sc. degree from Imperial College London, UK, in 2019. He is currently pursuing the Ph.D. degree in computer science in UNNC with the scholarship cooperated with Microsoft Research Asia (MSRA). His research interests include deep learning, computer vision and visual reasoning by applying tradition logical reasoning schemes into practical computer vision tasks.

Xiaoping Jiang

Xiaoping Jiang is an Assistant Professor in Operations Research at National University of Defense Technology (China). He was awarded a B.Sc. and a M.Sc. in Automatic Control & System Engineering from Harbin Institute of Technology (China) and received his Ph.D. in Computer Science & Operations Research from the University of Nottingham (UK). His research interests lie at the interface of operations research and computer science, including combinatorial optimisation, stochastic programming, (meta-)heuristics and applications of optimisation in logistics, scheduling, network design and mission planning.

Huan Jin

Huan Jin is an assistant professor in the School of Computer Science at the University of Nottingham Ningbo China (UNNC). She received her Ph.D. degree in Management Sciences from University of Iowa, USA in 2016. Before joining UNNC, she was an assistant professor at Ningbo China Institute for Supply Cain Innovation and a research affiliate at the MIT Centre for Transportation and Logistics. Her research interests focus on applying optimisation (LP/IP/MIP, Branch & Bound, Branch & Price, Nonlinear Programming) and machine learning techniques (Heuristics algorithms and Machine Learning algorithms) to solve large scaled real-world problem, including vehicle routing, transportation scheduling, network design, etc.

Jiahuan Jin

Jiahuan Jin received the B.S. degree in computer science from University of Nottingham, Ningbo, China. He is currently pursuing the Ph.D. degree with Artificial Intelligence and Optimisation Research Group, University of Nottingham, Ningbo, China. His current research interests include combinatorial optimisation and reinforcement learning.

Graham Kendall

Graham Kendall is an Emeritus Professor in the University of Nottingham, Professor Kendall is a Fellow of the British Computer Society (FBCS) and a Fellow of the Operational Research Society (FORS). His research interests include Operations Research, Scheduling, Logistics, Vehicle Routing, Meta- and Hyper-heuristics, Evolutionary Computation and Games.

Jiawei Li

Jiawei Li has a B.Sc. and Ph.D. in Engineering. He is assistant professor at the School of Computer Science of University of Nottingham Ningbo China. He has over 40 research publications of which 21 are in international journals. His research interests include evolutionary game theory, fuzzy logic, hyper-heuristics and their applications in real world decision-making problems.

Zheng Lu

Zheng Lu received his Ph.D. from the National University of Singapore in 2011. He is currently an Assistant Professor at the University of Nottingham Ningbo China. Prior to his current position, he was a Postdoc-toral Research Fellow at the University of Texas at Austin, and an Assistant Professor at the City University of Hong Kong. He has published over 30 research papers in conferences and journals including CVPR, ECCV, TPAMI, IJCV, PR, etc. His current research interests include the area of machine learning, computer vision, natural language processing and their applications in the field including e-heritage and healthcare.

Jianfeng Ren

Jianfeng Ren received M.Sc. and Ph.D. in 2009 and 2015, respectively, both from Nanyang Technological University (NTU). Before that, he graduated with B.Eng. from National University of Singapore in 2001. He is now an Assistant Professor in the School of Computer Science, University of Nottingham Ningbo China. Dr Ren has authored 19 journal papers and 11 conference papers, including papers Pattern Recognition, IEEE T-IP, IEEE T-MM and IEEE SPL. His research interests include image/video processing, statistical pattern recognition, machine learning and radar target recognition.

Paul Weng

Paul Weng currently a tenure-track associate professor at UM-SJTU Joint Institute. Previously, he was a faculty at SYSU-CMU Joint Institute of Engineering from 2015 to 2017. During 2015, he was a visiting faculty at Carnegie Mellon University (CMU). Before that, he was an associate professor in computer science at Sorbonne University (Pierre and Marie Curie University, UPMC), Paris. He received his Master in 2003 and his Ph.D. in 2006, both at UPMC. Before joining academia, he graduated from ENSAI (French National School in Statistics and Information Analysis) and worked as a financial quantitative analyst in London. His main research work lies in artificial intelligence and machine learning. Notably, it focuses on adaptive control (reinforcement learning, Markov decision process) and multiobjective optimisation (compromise programming, fair optimisation).

Ning Xue

Ning Xue received the M.Sc. degree in computer science from the University of Birmingham, in 2012, and the Ph.D. degree in computer science from the University of Nottingham, in 2017. He is currently a data scientist at Microlise. He works in the development and application of optimisation techniques, particularly meta-heuristics, for solving vehicle routing and scheduling problems.

Huayan Zhang

Huayan Zhang received Bachelor's Degree in University of Nottingham Ningbo China, M.Sc. Degree in Artifictial Intelligence from the University of Edinburgh. He is currently pursuing Ph.D. with Artificial Intelligence and Optimisation. His research interest is reinforcement learning and optimisation.