Routing Arena: A Benchmark Suite for Neural Routing Solvers
- URL: http://arxiv.org/abs/2310.04140v1
- Date: Fri, 6 Oct 2023 10:24:33 GMT
- Title: Routing Arena: A Benchmark Suite for Neural Routing Solvers
- Authors: Daniela Thyssens, Tim Dernedde, Jonas K. Falkner, Lars Schmidt-Thieme
- Abstract summary: We propose a benchmark suite for Routing Problems that provides a seamless integration of consistent evaluation and the provision of baselines and benchmarks prevalent in the Machine Learning- and Operations Research field.
A comprehensive first experimental evaluation demonstrates that the most recent Operations Research solvers generate state-of-the-art results in terms of solution quality and runtime efficiency when it comes to the vehicle routing problem.
- Score: 8.158770689562672
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Neural Combinatorial Optimization has been researched actively in the last
eight years. Even though many of the proposed Machine Learning based approaches
are compared on the same datasets, the evaluation protocol exhibits essential
flaws and the selection of baselines often neglects State-of-the-Art Operations
Research approaches. To improve on both of these shortcomings, we propose the
Routing Arena, a benchmark suite for Routing Problems that provides a seamless
integration of consistent evaluation and the provision of baselines and
benchmarks prevalent in the Machine Learning- and Operations Research field.
The proposed evaluation protocol considers the two most important evaluation
cases for different applications: First, the solution quality for an a priori
fixed time budget and secondly the anytime performance of the respective
methods. By setting the solution trajectory in perspective to a Best Known
Solution and a Base Solver's solutions trajectory, we furthermore propose the
Weighted Relative Average Performance (WRAP), a novel evaluation metric that
quantifies the often claimed runtime efficiency of Neural Routing Solvers. A
comprehensive first experimental evaluation demonstrates that the most recent
Operations Research solvers generate state-of-the-art results in terms of
solution quality and runtime efficiency when it comes to the vehicle routing
problem. Nevertheless, some findings highlight the advantages of neural
approaches and motivate a shift in how neural solvers should be conceptualized.
Related papers
- Are we making progress in unlearning? Findings from the first NeurIPS unlearning competition [70.60872754129832]
First NeurIPS competition on unlearning sought to stimulate the development of novel algorithms.
Nearly 1,200 teams from across the world participated.
We analyze top solutions and delve into discussions on benchmarking unlearning.
arXiv Detail & Related papers (2024-06-13T12:58:00Z) - Neural Active Learning Beyond Bandits [69.99592173038903]
We study both stream-based and pool-based active learning with neural network approximations.
We propose two algorithms based on the newly designed exploitation and exploration neural networks for stream-based and pool-based active learning.
arXiv Detail & Related papers (2024-04-18T21:52:14Z) - An Efficient Learning-based Solver Comparable to Metaheuristics for the
Capacitated Arc Routing Problem [67.92544792239086]
We introduce an NN-based solver to significantly narrow the gap with advanced metaheuristics.
First, we propose direction-aware facilitating attention model (DaAM) to incorporate directionality into the embedding process.
Second, we design a supervised reinforcement learning scheme that involves supervised pre-training to establish a robust initial policy.
arXiv Detail & Related papers (2024-03-11T02:17:42Z) - Rethinking and Benchmarking Predict-then-Optimize Paradigm for
Combinatorial Optimization Problems [62.25108152764568]
Many web applications rely on solving optimization problems, such as energy cost-aware scheduling, budget allocation on web advertising, and graph matching on social networks.
We consider the performance of prediction and decision-making in a unified system.
We provide a comprehensive categorization of current approaches and integrate existing experimental scenarios.
arXiv Detail & Related papers (2023-11-13T13:19:34Z) - Online Control of Adaptive Large Neighborhood Search using Deep Reinforcement Learning [4.374837991804085]
We introduce a Deep Reinforcement Learning based approach called DR-ALNS that selects operators, adjusts parameters, and controls the acceptance criterion throughout the search.
We evaluate the proposed method on a problem with orienteering weights and time windows, as presented in an IJCAI competition.
The results show that our approach outperforms vanilla ALNS, ALNS tuned with Bayesian optimization, and two state-of-the-art DRL approaches.
arXiv Detail & Related papers (2022-11-01T21:33:46Z) - Bi-objective Ranking and Selection Using Stochastic Kriging [0.0]
We consider bi-objective ranking and selection problems in which the two objective outcomes have been observed with uncertainty.
We propose a novel Bayesian bi-objective ranking and selection method that sequentially allocates extra samples to competitive solutions.
Experimental results show that the proposed method outperforms the standard allocation method, as well as a well-known state-of-the-art algorithm.
arXiv Detail & Related papers (2022-09-05T23:51:07Z) - Solving the vehicle routing problem with deep reinforcement learning [0.0]
This paper focuses on the application of RL for the Vehicle Routing Problem (VRP), a famous problem that belongs to the class of NP-Hard problems.
In a second phase, the neural architecture behind the Actor and Critic has been established, choosing to adopt a neural architecture based on the Convolutional neural networks.
Experiments performed on a wide range of instances show that the algorithm has good generalization capabilities and can reach good solutions in a short time.
arXiv Detail & Related papers (2022-07-30T12:34:26Z) - Sample-Efficient, Exploration-Based Policy Optimisation for Routing
Problems [2.6782615615913348]
This paper presents a new reinforcement learning approach that is based on entropy.
In addition, we design an off-policy-based reinforcement learning technique that maximises the expected return.
We show that our model can generalise to various route problems.
arXiv Detail & Related papers (2022-05-31T09:51:48Z) - Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
We present an end-to-end method to learn the proximal operator across non-family problems.
We show that for weakly-ized objectives and under mild conditions, the method converges globally.
arXiv Detail & Related papers (2022-01-28T05:53:28Z) - RoMA: Robust Model Adaptation for Offline Model-based Optimization [115.02677045518692]
We consider the problem of searching an input maximizing a black-box objective function given a static dataset of input-output queries.
A popular approach to solving this problem is maintaining a proxy model that approximates the true objective function.
Here, the main challenge is how to avoid adversarially optimized inputs during the search.
arXiv Detail & Related papers (2021-10-27T05:37:12Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.