Multi-Tour Set Traveling Salesman Problem in Planning Power Transmission Line Inspection

• URL: http://arxiv.org/abs/2302.01179v1
• Date: Thu, 2 Feb 2023 15:59:46 GMT
• Title: Multi-Tour Set Traveling Salesman Problem in Planning Power Transmission Line Inspection
• Authors: Franti\v{s}ek Nekov\'a\v{r}, Jan Faigl, Martin Saska
• Abstract summary: The problem is formulated for an inspection vehicle with a limited travel budget. The optimal solution of the problem is solved by the proposed Linear Programming (ILP) formulation. The algorithms are demonstrated in a real-world scenario to inspect power line segments at the electrical substation.
• Score: 8.202492922523591
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This letter concerns optimal power transmission line inspection formulated as a proposed generalization of the traveling salesman problem for a multi-route one-depot scenario. The problem is formulated for an inspection vehicle with a limited travel budget. Therefore, the solution can be composed of multiple runs to provide full coverage of the given power lines. Besides, the solution indicates how many vehicles can perform the inspection in a single run. The optimal solution of the problem is solved by the proposed Integer Linear Programming (ILP) formulation, which is, however, very computationally demanding. Therefore, the computational requirements are addressed by the combinatorial metaheuristic. The employed greedy randomized adaptive search procedure is significantly less demanding while providing competitive solutions and scales better with the problem size than the ILP-based approach. The proposed formulation and algorithms are demonstrated in a real-world scenario to inspect power line segments at the electrical substation.

Related papers

• Joint Optimization of Electric Vehicle Routes and Charging Locations Learning Charge Constraints Using QUBO Solver [5.616693462159185]
  We focus on the joint optimization of the location of charging stations and the routing of electric vehicles (EVs)<n>We propose a sequential optimization method utilizing the Bayesian inference and QUBO solvers, in which method the battery capacity constraints are automatically learned.<n>Applying this method to a routing problem of 20 locations, we confirmed that the learning process works well and efficient searches find good solutions.
  arXiv  Detail & Related papers  (2025-06-05T07:08:19Z)
• Trilevel Memetic Algorithm for the Electric Vehicle Routing Problem [0.0]
  This paper introduces a Trilevel Memetic Algorithm (TMA) that hierarchically optimize customer sequences, route assignments, and charging station insertions.<n> Benchmark tests on WCCI 2020 instances show competitive performance, matching best-known results for small-scale cases.
  arXiv  Detail & Related papers  (2025-06-01T16:08:43Z)
• A Multiagent Path Search Algorithm for Large-Scale Coalition Structure Generation [61.08720171136229]
  Coalition structure generation is a fundamental computational problem in multiagent systems. We develop SALDAE, a multiagent path finding algorithm for CSG that operates on a graph of coalition structures.
  arXiv  Detail & Related papers  (2025-02-14T15:21:27Z)
• Learning Multiple Initial Solutions to Optimization Problems [52.9380464408756]
  Sequentially solving similar optimization problems under strict runtime constraints is essential for many applications. We propose learning to predict emphmultiple diverse initial solutions given parameters that define the problem instance. We find significant and consistent improvement with our method across all evaluation settings and demonstrate that it efficiently scales with the number of initial solutions required.
  arXiv  Detail & Related papers  (2024-11-04T15:17:19Z)
• Competitive Facility Location under Random Utilities and Routing Constraints [4.9873153106566575]
  We study a facility location problem within a competitive market context, where customer demand is predicted by a random utility choice model. We introduce routing constraints that necessitate the selection of locations in a manner that guarantees the existence of a tour visiting all chosen locations.
  arXiv  Detail & Related papers  (2024-03-07T06:56:24Z)
• Exact algorithms and heuristics for capacitated covering salesman problems [0.0]
  This paper introduces the Capacitated Covering Salesman Problem (CCSP) The objective is to service customers through a fleet of vehicles in a depot, minimizing the total distance traversed by the vehicles. optimization methodologies are proposed for the CCSP based on ILP (Integer Linear Programming) and BRKGA (Biased Random-Key Genetic Routing) metaheuristic.
  arXiv  Detail & Related papers  (2024-03-03T07:50:29Z)
• Solving the Team Orienteering Problem with Transformers [46.93254771681026]
  Route planning for a fleet of vehicles is an important task in applications such as package delivery, surveillance, or transportation. This paper presents a multi-agent route planning system capable of solving the Team Orienteering Problem in a very fast and accurate manner.
  arXiv  Detail & Related papers  (2023-11-30T16:10:35Z)
• 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)
• 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)
• An SMT Based Compositional Model to Solve a Conflict-Free Electric Vehicle Routing Problem [2.64699517152535]
  The Electric Conflict-Free Vehicle Routing Problem (CF-EVRP) involves constraints such as limited operating range of the vehicles, time windows on the delivery to the customers, and limited capacity on the number of vehicles the road segments can accommodate. We develop a compositional model that breaks down the problem into smaller and simpler sub-problems and provides sub-optimal, feasible solutions.
  arXiv  Detail & Related papers  (2021-06-10T20:37:46Z)
• 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)
• Competitive Mirror Descent [67.31015611281225]
  Constrained competitive optimization involves multiple agents trying to minimize conflicting objectives, subject to constraints. We propose competitive mirror descent (CMD): a general method for solving such problems based on first order information. As a special case we obtain a novel competitive multiplicative weights algorithm for problems on the positive cone.
  arXiv  Detail & Related papers  (2020-06-17T22:11:35Z)
• A Quantum Annealing Approach for Dynamic Multi-Depot Capacitated Vehicle Routing Problem [5.057312718525522]
  This paper presents a quantum computing algorithm that works on the principle of Adiabatic Quantum Computation (AQC) It has shown significant computational advantages in solving optimization problems such as vehicle routing problems (VRP) when compared to classical algorithms. This is an NP-hard optimization problem with real-world applications in the fields of transportation, logistics, and supply chain management.
  arXiv  Detail & Related papers  (2020-05-26T01:47:39Z)

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.