Machine Learning to Solve Vehicle Routing Problems: A Survey

This paper provides a systematic overview of machine learning methods applied to solve NP-hard Vehicle Routing Problems (VRPs). Recently, there has been great interest from both the machine learning and operations research communities in solving VRPs either through pure learning methods or by combining them with traditional handcrafted heuristics. We present a taxonomy of studies on learning paradigms, solution structures, underlying models, and algorithms. Detailed results of state-of-the-art methods are presented, demonstrating their competitiveness with traditional approaches. The survey highlights the advantages of the machine learning-based models that aim to exploit the symmetry of VRP solutions. The paper outlines future research directions to incorporate learning-based solutions to address the challenges of modern transportation systems.

I. Introduction

Cost-effective logistics systems define the competitiveness of companies, and the relation of logistics expenditure to GDP indicates the effectiveness of business operations in a country. For instance, in 2018, USA businesses spent 10.4% of their revenue on transportation costs alone, while the overall logistics expenditure constituted 8% of GDP [1]. Along with increased fuel prices, transportation costs are mainly influenced by last-mile delivery, defined as transporting goods from a warehouse to a customer’s location. With the increased demand for online sales, the last-mile delivery system’s effectiveness has become essential as it comprises 50% of the total transportation costs [2]. Also, the carbon dioxide footprint is another emerging concern in logistics systems. To overcome the above-outlined challenges, efficiently solving vehicle routing problems has been of great interest to both practitioners and researchers.