Spatial-temporal-demand clustering for solving large-scale vehicle
routing problems with time windows
- URL: http://arxiv.org/abs/2402.00041v1
- Date: Sat, 20 Jan 2024 06:06:01 GMT
- Title: Spatial-temporal-demand clustering for solving large-scale vehicle
routing problems with time windows
- Authors: Christoph Kerscher and Stefan Minner
- Abstract summary: We propose a decompose-route-improve (DRI) framework that groups customers using clustering.
Its similarity metric incorporates customers' spatial, temporal, and demand data.
We apply pruned local search (LS) between solved subproblems to improve the overall solution.
- Score: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Several metaheuristics use decomposition and pruning strategies to solve
large-scale instances of the vehicle routing problem (VRP). Those complexity
reduction techniques often rely on simple, problem-specific rules. However, the
growth in available data and advances in computer hardware enable data-based
approaches that use machine learning (ML) to improve scalability of solution
algorithms. We propose a decompose-route-improve (DRI) framework that groups
customers using clustering. Its similarity metric incorporates customers'
spatial, temporal, and demand data and is formulated to reflect the problem's
objective function and constraints. The resulting sub-routing problems can
independently be solved using any suitable algorithm. We apply pruned local
search (LS) between solved subproblems to improve the overall solution. Pruning
is based on customers' similarity information obtained in the decomposition
phase. In a computational study, we parameterize and compare existing
clustering algorithms and benchmark the DRI against the Hybrid Genetic Search
(HGS) of Vidal et al. (2013). Results show that our data-based approach
outperforms classic cluster-first, route-second approaches solely based on
customers' spatial information. The newly introduced similarity metric forms
separate sub-VRPs and improves the selection of LS moves in the improvement
phase. Thus, the DRI scales existing metaheuristics to achieve high-quality
solutions faster for large-scale VRPs by efficiently reducing complexity.
Further, the DRI can be easily adapted to various solution methods and VRP
characteristics, such as distribution of customer locations and demands, depot
location, and different time window scenarios, making it a generalizable
approach to solving routing problems.
Related papers
- Towards a connection between the capacitated vehicle routing problem and the constrained centroid-based clustering [1.3927943269211591]
Efficiently solving a vehicle routing problem in a practical runtime is a critical challenge for delivery management companies.
This paper explores both a theoretical and experimental connection between the Capacitated Vehicle Problem (CVRP) and the Constrainedid-Based Clustering (CCBC)
The proposed framework consists of three stages. At the first step, a constrained centroid-based clustering algorithm generates feasible clusters of customers.
arXiv Detail & Related papers (2024-03-20T22:24:36Z) - Symmetry-preserving graph attention network to solve routing problems at
multiple resolutions [1.9304772860080408]
We introduce the first-ever completely equivariant model and training to solve problems.
It is essential to capture the multiscale structure of the input graph.
We propose a Multiresolution scheme in combination with Equi Graph Attention network (mEGAT) architecture.
arXiv Detail & Related papers (2023-10-24T06:22:20Z) - Genetic Algorithms with Neural Cost Predictor for Solving Hierarchical Vehicle Routing Problems [20.684353068460375]
When vehicle routing decisions are intertwined with higher-level decisions, the resulting optimization problems pose significant challenges for computation.
We propose a novel deep-learning-based approach called Genetic Algorithm with Neural Cost Predictor (GANCP) to tackle the challenge.
In particular, our proposed neural network learns the objective values of the HGS-CVRP open-source package that solves capacitated vehicle routing problems.
arXiv Detail & Related papers (2023-10-22T02:46:37Z) - Enhancing Column Generation by Reinforcement Learning-Based
Hyper-Heuristic for Vehicle Routing and Scheduling Problems [9.203492057735074]
Column generation (CG) is a vital method to solve large-scale problems by dynamically generating variables.
We propose a reinforcement learning-based hyper-heuristic framework, dubbed RLHH, to enhance the performance of CG.
arXiv Detail & Related papers (2023-10-15T00:05:50Z) - MARLIN: Soft Actor-Critic based Reinforcement Learning for Congestion
Control in Real Networks [63.24965775030673]
We propose a novel Reinforcement Learning (RL) approach to design generic Congestion Control (CC) algorithms.
Our solution, MARLIN, uses the Soft Actor-Critic algorithm to maximize both entropy and return.
We trained MARLIN on a real network with varying background traffic patterns to overcome the sim-to-real mismatch.
arXiv Detail & Related papers (2023-02-02T18:27:20Z) - Coded Stochastic ADMM for Decentralized Consensus Optimization with Edge
Computing [113.52575069030192]
Big data, including applications with high security requirements, are often collected and stored on multiple heterogeneous devices, such as mobile devices, drones and vehicles.
Due to the limitations of communication costs and security requirements, it is of paramount importance to extract information in a decentralized manner instead of aggregating data to a fusion center.
We consider the problem of learning model parameters in a multi-agent system with data locally processed via distributed edge nodes.
A class of mini-batch alternating direction method of multipliers (ADMM) algorithms is explored to develop the distributed learning model.
arXiv Detail & Related papers (2020-10-02T10:41:59Z) - Combining Deep Learning and Optimization for Security-Constrained
Optimal Power Flow [94.24763814458686]
Security-constrained optimal power flow (SCOPF) is fundamental in power systems.
Modeling of APR within the SCOPF problem results in complex large-scale mixed-integer programs.
This paper proposes a novel approach that combines deep learning and robust optimization techniques.
arXiv Detail & Related papers (2020-07-14T12:38:21Z) - FedPD: A Federated Learning Framework with Optimal Rates and Adaptivity
to Non-IID Data [59.50904660420082]
Federated Learning (FL) has become a popular paradigm for learning from distributed data.
To effectively utilize data at different devices without moving them to the cloud, algorithms such as the Federated Averaging (FedAvg) have adopted a "computation then aggregation" (CTA) model.
arXiv Detail & Related papers (2020-05-22T23:07:42Z) - Dynamic Federated Learning [57.14673504239551]
Federated learning has emerged as an umbrella term for centralized coordination strategies in multi-agent environments.
We consider a federated learning model where at every iteration, a random subset of available agents perform local updates based on their data.
Under a non-stationary random walk model on the true minimizer for the aggregate optimization problem, we establish that the performance of the architecture is determined by three factors, namely, the data variability at each agent, the model variability across all agents, and a tracking term that is inversely proportional to the learning rate of the algorithm.
arXiv Detail & Related papers (2020-02-20T15:00:54Z) - Reinforcement Learning Based Vehicle-cell Association Algorithm for
Highly Mobile Millimeter Wave Communication [53.47785498477648]
This paper investigates the problem of vehicle-cell association in millimeter wave (mmWave) communication networks.
We first formulate the user state (VU) problem as a discrete non-vehicle association optimization problem.
The proposed solution achieves up to 15% gains in terms sum of user complexity and 20% reduction in VUE compared to several baseline designs.
arXiv Detail & Related papers (2020-01-22T08:51:05Z)
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.