Stochastic Capacitated Arc Routing Problem

• URL: http://arxiv.org/abs/2211.12728v1
• Date: Wed, 23 Nov 2022 06:39:17 GMT
• Title: Stochastic Capacitated Arc Routing Problem
• Authors: Fleury G\'erard, Lacomme Philippe, Christian Prins
• Abstract summary: This paper deals with the Capacitated Arc Routing Problem (SCARP), obtained by randomizing quantities on the arcs in the CARP. For real-life problems, it is important to create solutions insensitive to variations of the quantities to collect because of the randomness of these quantities. The results prove it is possible to obtain robust solutions without any significant enlargement of the solution cost.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper deals with the Stochastic Capacitated Arc Routing Problem (SCARP), obtained by randomizing quantities on the arcs in the CARP. Optimization problems for the SCARP are characterized by decisions that are made without knowing their full consequences. For real-life problems, it is important to create solutions insensitive to variations of the quantities to collect because of the randomness of these quantities. Efficient robust solutions are required to avoid unprofitable costly moves of vehicles to the depot node. Different criteria are proposed to model the SCARP and advanced concepts of a genetic algorithm optimizing both cost and robustness are provided. The method is benchmarked on the well-known instances proposed by DeArmon, Eglese and Belenguer. The results prove it is possible to obtain robust solutions without any significant enlargement of the solution cost. This allows treating more realistic problems including industrial goals and constraints linked to variations in the quantities to be collected.

Related papers

• Path Matters: Industrial Data Meet Quantum Optimization [2.7883868459582737]
  Real-world optimization problems must undergo a series of transformations before becoming solvable on current quantum hardware. We benchmark a representative subset of these transformation paths using a real-world industrial production planning problem with industry data. Our results show that QA on D-Wave hardware consistently produces near-optimal solutions, whereas LR-QAOA on IBM quantum devices struggles to reach comparable performance.
  arXiv  Detail & Related papers  (2025-04-23T10:45:38Z)
• From approximation error to optimality gap -- Explaining the performance impact of opportunity cost approximation in integrated demand management and vehicle routing [0.0]
  We propose an explainability technique that quantifies and visualizes the magnitude of approximation errors, their immediate impact, and their relevance in specific regions of the state space. Applying the technique to a generic i-DMVRP in a full-factorial computational study, we show that the technique contributes to better explaining algorithmic performance and provides guidance for the algorithm selection and development process.
  arXiv  Detail & Related papers  (2024-12-18T13:46:46Z)
• New Additive OCBA Procedures for Robust Ranking and Selection [0.9558392439655016]
  We develop new fixed-budget robust R&S procedures to minimize the probability of incorrect selection under a limited sampling budget. We then conduct a comprehensive numerical study to verify the superiority of our robust OCBA procedure over existing ones.
  arXiv  Detail & Related papers  (2024-12-08T18:42:07Z)
• Reinforcement Learning for Variational Quantum Circuits Design [10.136215038345012]
  Variational Quantum Algorithms have emerged as promising tools for solving optimization problems on quantum computers. In this study, we leverage the powerful and flexible Reinforcement Learning paradigm to train an agent capable of autonomously generating quantum circuits. Our results indicate that the $R_yz$-connected circuit achieves high approximation ratios for Maximum Cut problems.
  arXiv  Detail & Related papers  (2024-09-09T10:07:12Z)
• Randomized heuristic repair for large-scale multidimensional knapsack problem [0.5439020425819]
  The multidimensional knapsack problem (MKP) is an NP-hard optimization problem whose solution is determining a subset of maximum total profit items. This paper proposes an efficiency repair that increases the variability of the repaired solutions without deteriorating quality.
  arXiv  Detail & Related papers  (2024-05-24T14:01:05Z)
• Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
  We present sred, a truly adaptive algorithm that can reject arms in it any round based on the observed empirical gaps between the rewards of various arms. In particular, we present sred, a truly adaptive algorithm that can reject arms in it any round based on the observed empirical gaps between the rewards of various arms.
  arXiv  Detail & Related papers  (2023-12-19T13:17:43Z)
• Model-Based Epistemic Variance of Values for Risk-Aware Policy Optimization [59.758009422067]
  We consider the problem of quantifying uncertainty over expected cumulative rewards in model-based reinforcement learning. We propose a new uncertainty Bellman equation (UBE) whose solution converges to the true posterior variance over values. We introduce a general-purpose policy optimization algorithm, Q-Uncertainty Soft Actor-Critic (QU-SAC) that can be applied for either risk-seeking or risk-averse policy optimization.
  arXiv  Detail & Related papers  (2023-12-07T15:55:58Z)
• Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methods [52.0617030129699]
  We introduce a novel theoretical framework for analyzing the effectiveness of DeepMatching Networks and Reinforcement Learning methods. Our main contribution holds for a broad class of problems including Max-and Min-Cut, Max-$k$-Bipartite-Bi, Maximum-Weight-Bipartite-Bi, and Traveling Salesman Problem. As a byproduct of our analysis we introduce a novel regularization process over vanilla descent and provide theoretical and experimental evidence that it helps address vanishing-gradient issues and escape bad stationary points.
  arXiv  Detail & Related papers  (2023-10-08T23:39:38Z)
• Provably Efficient Model-Free Algorithms for Non-stationary CMDPs [10.930095238723327]
  We study model-free reinforcement learning algorithms in episodic non-stationary constrained Markov Decision Processes. In the non-stationary environment, reward, utility functions, and transition kernels can vary arbitrarily over time as long as the cumulative variations do not exceed certain variation budgets. We propose the first model-free, simulator-free RL algorithms with sublinear regret and zero constraint violation for non-stationary CMDPs.
  arXiv  Detail & Related papers  (2023-03-10T06:33:38Z)
• Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiency [90.40062452292091]
  We present the first computationally efficient algorithm for linear bandits with heteroscedastic noise. Our algorithm is adaptive to the unknown variance of noise and achieves an $tildeO(d sqrtsum_k = 1K sigma_k2 + d)$ regret. We also propose a variance-adaptive algorithm for linear mixture Markov decision processes (MDPs) in reinforcement learning.
  arXiv  Detail & Related papers  (2023-02-21T00:17:24Z)
• Reinforcement Learning and Tree Search Methods for the Unit Commitment Problem [0.0]
  Unit commitment problem determines operating schedules of generation units to meet demand. Approaches which more rigorously account for uncertainty could yield large reductions in operating costs. We develop guided tree search, a novel methodology combining model-free RL and model-based planning.
  arXiv  Detail & Related papers  (2022-12-12T16:03:31Z)
• A Lyapunov-Based Methodology for Constrained Optimization with Bandit Feedback [22.17503016665027]
  We consider problems where each action returns a random reward, cost, and penalty from an unknown joint distribution. We propose a novel low-complexity algorithm, named $tt LyOn$, and prove that it achieves $O(sqrtBlog B)$ regret and $O(log B/B)$ constraint-violation. The low computational cost bounds of $tt LyOn$ suggest that Lyapunov-based algorithm design methodology can be effective in solving constrained bandit optimization problems.
  arXiv  Detail & Related papers  (2021-06-09T16:12:07Z)
• Modeling the Second Player in Distributionally Robust Optimization [90.25995710696425]
  We argue for the use of neural generative models to characterize the worst-case distribution. This approach poses a number of implementation and optimization challenges. We find that the proposed approach yields models that are more robust than comparable baselines.
  arXiv  Detail & Related papers  (2021-03-18T14:26:26Z)
• 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)

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.