Machine Learning to Solve Vehicle Routing Problems: A Survey

IEEE Transactions on Intelligent Transportation Systems, Год журнала: 2024, Номер 25(6), С. 4754 - 4772

Опубликована: Янв. 2, 2024

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 and operations research communities in solving VRPs either through pure or by combining them with traditional handcrafted heuristics. We present taxonomy studies on paradigms, solution structures, underlying models, algorithms. Detailed results state-of-the-art are presented, demonstrating their competitiveness approaches. The survey highlights advantages learning-based models that aim exploit symmetry VRP solutions. outlines future directions incorporate solutions address challenges modern transportation systems.

Язык: Английский

---

Operational Research: methods and applications

Journal of the Operational Research Society, Год журнала: 2023, Номер 75(3), С. 423 - 617

Опубликована: Дек. 27, 2023

Throughout its history, Operational Research has evolved to include methods, models and algorithms that have been applied a wide range of contexts. This encyclopedic article consists two main sections: methods applications. The first summarises the up-to-date knowledge provides an overview state-of-the-art key developments in various subdomains field. second offers wide-ranging list areas where applied. is meant be read nonlinear fashion used as point reference by diverse pool readers: academics, researchers, students, practitioners. entries within applications sections are presented alphabetical order. authors dedicate this paper 2023 Turkey/Syria earthquake victims. We sincerely hope advances OR will play role towards minimising pain suffering caused future catastrophes.

Язык: Английский

---

PyVRP: A High-Performance VRP Solver Package

INFORMS journal on computing, Год журнала: 2024, Номер 36(4), С. 943 - 955

Опубликована: Янв. 29, 2024

We introduce PyVRP, a Python package that implements hybrid genetic search in state-of-the-art vehicle routing problem (VRP) solver. The is designed for the VRP with time windows (VRPTW), but can be easily extended to support other variants. PyVRP combines flexibility of performance C++, by implementing (only) critical parts algorithm while being fully customisable at level. polished implementation ranked 1st 2021 DIMACS VRPTW challenge and, after improvements, on static variant EURO meets NeurIPS 2022 competition. code follows good software engineering practices, and well-documented unit tested. freely available under liberal MIT license. Through numerical experiments we show achieves results capacitated VRP. hope enables researchers practitioners quickly build

Язык: Английский

---

Decarbonizing road freight transportation: recent advances and future trends

Journal of the Operational Research Society, Год журнала: 2025, Номер unknown, С. 1 - 21

Опубликована: Янв. 4, 2025

Язык: Английский

---

How Good is Neural Combinatorial Optimization? A Systematic Evaluation on the Traveling Salesman Problem

IEEE Computational Intelligence Magazine, Год журнала: 2023, Номер 18(3), С. 14 - 28

Опубликована: Июль 19, 2023

Traditional solvers for tackling combinatorial optimization (CO) problems are usually designed by human experts. Recently, there has been a surge of interest in utilizing deep learning, especially reinforcement to automatically learn effective CO. The resultant new paradigm is termed neural (NCO). However, the advantages and disadvantages NCO relative other approaches have not empirically or theoretically well studied. This work presents comprehensive comparative study alternative solvers. Specifically, taking traveling salesman problem as testbed problem, performance assessed five aspects, i.e., effectiveness, efficiency, stability, scalability, generalization ability. Our results show that learned approaches, general, still fall short traditional nearly all these aspects. A potential benefit would be their superior time energy efficiency small-size instances when sufficient training available. Hopefully, this help with better understanding strengths weaknesses provide evaluation protocol further benchmarking comparison approaches.

Язык: Английский

---

Waste collection routing: a survey on problems and methods

Central European Journal of Operations Research, Год журнала: 2023, Номер 32(2), С. 399 - 434

Опубликована: Ноя. 15, 2023

Abstract Waste collection is a vital service performed all over the world, which heavily relies on vehicle routing. Due to regulations and local conditions, problems their characteristics often differ greatly. This literature survey aims review current state of art overlap in waste routing literature. The most notable papers are categorized according underlying problem type, examined brought into relation based common characteristics. types comprise general, node arc problems, with being common, followed by location problems. Besides use intermediate facilities, naturally very literature, authors point out other interesting found practical such as uncertain demand, personnel planning aspects, alternative systems or types, related risk sustainability. Additionally, highlight prominent scopes objectives well recent developments this area. Overall, provides selective overview calls attention research gaps possible future directions.

Язык: Английский

---

Learn to optimize—a brief overview

National Science Review, Год журнала: 2024, Номер 11(8)

Опубликована: Апрель 2, 2024

Most optimization problems of practical significance are typically solved by highly configurable parameterized algorithms. To achieve the best performance on a problem instance, trial-and-error configuration process is required, which very costly and even prohibitive for that already computationally intensive, e.g. associated with machine learning tasks. In past decades, many studies have been conducted to accelerate tedious from set training instances. This article refers these as

Язык: Английский

---

Efficient Neural Neighborhood Search for Pickup and Delivery Problems

Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, Год журнала: 2022, Номер unknown, С. 4776 - 4784

Опубликована: Июль 1, 2022

We present an efficient Neural Neighborhood Search (N2S) approach for pickup and delivery problems (PDPs). In specific, we design a powerful Synthesis Attention that allows the vanilla self-attention to synthesize various types of features regarding route solution. also exploit two customized decoders automatically learn perform removal reinsertion pickup-delivery node pair tackle precedence constraint. Additionally, diversity enhancement scheme is leveraged further ameliorate performance. Our N2S generic, extensive experiments on canonical PDP variants show it can produce state-of-the-art results among existing neural methods. Moreover, even outstrips well-known LKH3 solver more constrained variant. implementation available online.

Язык: Английский

---

An expandable machine learning-optimization framework to sequential decision-making

European Journal of Operational Research, Год журнала: 2023, Номер 314(1), С. 280 - 296

Опубликована: Ноя. 1, 2023

Язык: Английский

---

Integrating Machine Learning Into Vehicle Routing Problem: Methods and Applications

IEEE Access, Год журнала: 2024, Номер 12, С. 93087 - 93115

Опубликована: Янв. 1, 2024

The vehicle routing problem (VRP) and its variants have been intensively studied by the operational research community. existing surveys majority of published articles tackle traditional solutions, including exact methods, heuristics, meta-heuristics. Recently, machine learning (ML)-based methods applied to a variety combinatorial optimization problems, specifically VRPs. strong trend using ML in VRPs gap literature motivated us review state-of-the-art. To provide clear understanding ML-VRP landscape, we categorize related studies based on their applications/constraints technical details. We mainly focus reinforcement (RL)-based approaches because importance literature, while also address non RL-based methods. cover both theoretical practical aspects clearly addressing trends, gap, limitations advantages ML-based discuss some potential future directions.

Язык: Английский

---