A Case Study of Vehicle Route Optimization

• URL: http://arxiv.org/abs/2111.09087v1
• Date: Wed, 17 Nov 2021 13:10:55 GMT
• Title: A Case Study of Vehicle Route Optimization
• Authors: Veronika Lesch and Maximilian K\"onig and Samuel Kounev and Anthony Stein and Christian Krupitzer
• Abstract summary: In this work, we incorporate the main relevant real-world constraints and requirements. We propose a two-stage strategy and a Timeline algorithm for time windows and pause times. Our evaluation of eight different problem instances against four state-of-the-art algorithms shows that our approach handles all given constraints in a reasonable time.
• Score: 2.2101681534594237
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In the last decades, the classical Vehicle Routing Problem (VRP), i.e., assigning a set of orders to vehicles and planning their routes has been intensively researched. As only the assignment of order to vehicles and their routes is already an NP-complete problem, the application of these algorithms in practice often fails to take into account the constraints and restrictions that apply in real-world applications, the so called rich VRP (rVRP) and are limited to single aspects. In this work, we incorporate the main relevant real-world constraints and requirements. We propose a two-stage strategy and a Timeline algorithm for time windows and pause times, and apply a Genetic Algorithm (GA) and Ant Colony Optimization (ACO) individually to the problem to find optimal solutions. Our evaluation of eight different problem instances against four state-of-the-art algorithms shows that our approach handles all given constraints in a reasonable time.

Related papers

• Learn to Solve Vehicle Routing Problems ASAP: A Neural Optimization Approach for Time-Constrained Vehicle Routing Problems with Finite Vehicle Fleet [0.0]
  We propose an NCO approach to solve a time-constrained capacitated VRP with a finite vehicle fleet size. The method is able to find adequate and cost-efficient solutions, showing both flexibility and robust generalizations.
  arXiv  Detail & Related papers  (2024-11-07T15:16:36Z)
• A Neural Column Generation Approach to the Vehicle Routing Problem with Two-Dimensional Loading and Last-In-First-Out Constraints [3.9594431485015096]
  A vehicle routing problem with two-dimensional loading constraints (2L-CVRP) presents significant practical and algorithmic challenges. This article presents an exact algorithm that integrates advanced machine learning techniques, specifically a novel combination of attention and recurrence mechanisms. The proposed algorithm successfully resolves an open instance in the standard test-bed, demonstrating significant improvements brought about by the incorporation of machine learning models.
  arXiv  Detail & Related papers  (2024-06-18T09:58:29Z)
• Combinatorial Optimization with Policy Adaptation using Latent Space Search [44.12073954093942]
  We present a novel approach for designing performant algorithms to solve complex, typically NP-hard, problems. We show that our search strategy outperforms state-of-the-art approaches on 11 standard benchmarking tasks.
  arXiv  Detail & Related papers  (2023-11-13T12:24:54Z)
• Roulette-Wheel Selection-Based PSO Algorithm for Solving the Vehicle Routing Problem with Time Windows [58.891409372784516]
  This paper presents a novel form of the PSO methodology that uses the Roulette Wheel Method (RWPSO) Experiments using the Solomon VRPTW benchmark datasets on the RWPSO demonstrate that RWPSO is competitive with other state-of-the-art algorithms from the literature.
  arXiv  Detail & Related papers  (2023-06-04T09:18:02Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
  We exploit between first-order algorithms for constrained optimization and non-smooth systems to design a new class of accelerated first-order algorithms. An important property of these algorithms is that constraints are expressed in terms of velocities instead of sparse variables.
  arXiv  Detail & Related papers  (2023-02-01T08:50:48Z)
• CACTO: Continuous Actor-Critic with Trajectory Optimization -- Towards global optimality [5.0915256711576475]
  This paper presents a novel algorithm for the continuous control of dynamical systems that combines Trayy (TO) and Reinforcement Learning (RL) in a single trajectory.
  arXiv  Detail & Related papers  (2022-11-12T10:16:35Z)
• An Overview and Experimental Study of Learning-based Optimization Algorithms for Vehicle Routing Problem [49.04543375851723]
  Vehicle routing problem (VRP) is a typical discrete optimization problem. Many studies consider learning-based optimization algorithms to solve VRP. This paper reviews recent advances in this field and divides relevant approaches into end-to-end approaches and step-by-step approaches.
  arXiv  Detail & Related papers  (2021-07-15T02:13:03Z)
• Deep Policy Dynamic Programming for Vehicle Routing Problems [89.96386273895985]
  We propose Deep Policy Dynamic Programming (D PDP) to combine the strengths of learned neurals with those of dynamic programming algorithms. D PDP prioritizes and restricts the DP state space using a policy derived from a deep neural network, which is trained to predict edges from example solutions. We evaluate our framework on the travelling salesman problem (TSP) and the vehicle routing problem (VRP) and show that the neural policy improves the performance of (restricted) DP algorithms.
  arXiv  Detail & Related papers  (2021-02-23T15:33:57Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  This paper investigates the classical integer least-squares problem which estimates signals integer from linear models. The problem is NP-hard and often arises in diverse applications such as signal processing, bioinformatics, communications and machine learning. We propose a general hyper-accelerated tree search (HATS) algorithm by employing a deep neural network to estimate the optimal estimation for the underlying simplified memory-bounded A* algorithm.
  arXiv  Detail & Related papers  (2021-01-07T08:00:02Z)
• Run2Survive: A Decision-theoretic Approach to Algorithm Selection based on Survival Analysis [75.64261155172856]
  survival analysis (SA) naturally supports censored data and offers appropriate ways to use such data for learning distributional models of algorithm runtime. We leverage such models as a basis of a sophisticated decision-theoretic approach to algorithm selection, which we dub Run2Survive. In an extensive experimental study with the standard benchmark ASlib, our approach is shown to be highly competitive and in many cases even superior to state-of-the-art AS approaches.
  arXiv  Detail & Related papers  (2020-07-06T15:20:17Z)
• A New Arc-Routing Algorithm Applied to Winter Road Maintenance [0.0]
  This paper studies large scale instances of a fairly general arc-routing problem as well as incorporate practical constraints. We develop a new algorithm based on a bin-packing which is well-scalable and able to solve road networks on thousands of crossroads and road segments in few minutes.
  arXiv  Detail & Related papers  (2020-01-23T08:44:42Z)

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.