Joint Optimization of Electric Vehicle Routes and Charging Locations Learning Charge Constraints Using QUBO Solver

• URL: http://arxiv.org/abs/2506.04687v1
• Date: Thu, 05 Jun 2025 07:08:19 GMT
• Title: Joint Optimization of Electric Vehicle Routes and Charging Locations Learning Charge Constraints Using QUBO Solver
• Authors: Akihisa Okada, Keisuke Otaki, Hiroaki Yoshida,
• Abstract summary: 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.
• Score: 5.616693462159185
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Optimal routing problems of electric vehicles (EVs) have attracted much attention in recent years, and installation of charging stations is an important issue for EVs. Hence, we focus on the joint optimization of the location of charging stations and the routing of EVs. When routing problems are formulated in the form of quadratic unconstrained binary optimization (QUBO), specialized solvers such as quantum annealer are expected to provide optimal solutions with high speed and accuracy. However, battery capacity constraints make it hard to formulate into QUBO form without a large number of auxiliary qubits. Then, we propose a sequential optimization method utilizing the Bayesian inference and QUBO solvers, in which method the battery capacity constraints are automatically learned. This method enables us to optimize the number and location of charging stations and the routing of EVs with a small number of searches. Applying this method to a routing problem of 20 locations, we confirmed that the learning process works well and efficient searches find good solutions. This result enhances the possibility that the QUBO solver could be applied to the constraints contained problems which is difficult to formulate into QUBO form without a large number of ancilla qubits.

Related papers

• Preventing Local Pitfalls in Vector Quantization via Optimal Transport [77.15924044466976]
  We introduce OptVQ, a novel vector quantization method that employs the Sinkhorn algorithm to optimize the optimal transport problem.<n>Our experiments on image reconstruction tasks demonstrate that OptVQ achieves 100% codebook utilization and surpasses current state-of-the-art VQNs in reconstruction quality.
  arXiv  Detail & Related papers  (2024-12-19T18:58:14Z)
• A Quantum Optimization Algorithm for Optimal Electric Vehicle Charging Station Placement for Intercity Trips [4.749824105387292]
  Electric vehicles (EVs) play a significant role in enhancing the sustainability of transportation systems.<n>Finding optimal charging station locations in large transportation networks presents a well-known NP-hard optimization problem.<n>This paper introduces a quantum search-based optimization algorithm designed to enhance the efficiency of solving this NP-hard problem.
  arXiv  Detail & Related papers  (2024-10-21T17:37:38Z)
• A Feasibility-Preserved Quantum Approximate Solver for the Capacitated Vehicle Routing Problem [3.0567007573383678]
  The Capacitated Vehicle Routing Problem (CVRP) is an NP-optimization problem (NPO) that arises in various fields including transportation and logistics. We present a new binary encoding for the CVRP, with an objective function of minimizing the shortest path that bypasses the vehicle capacity constraint of the CVRP. We discuss the effectiveness of the proposed encoding under the framework of the variant of the Quantum Alternating Operator Ansatz.
  arXiv  Detail & Related papers  (2023-08-17T05:14:43Z)
• Qubit efficient quantum algorithms for the vehicle routing problem on NISQ processors [48.68474702382697]
  Vehicle routing problem with time windows (VRPTW) is a common optimization problem faced within the logistics industry. In this work, we explore the use of a previously-introduced qubit encoding scheme to reduce the number of binary variables.
  arXiv  Detail & Related papers  (2023-06-14T13:44:35Z)
• Multi-Tour Set Traveling Salesman Problem in Planning Power Transmission Line Inspection [8.202492922523591]
  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.
  arXiv  Detail & Related papers  (2023-02-02T15:59:46Z)
• Data-Driven Chance Constrained AC-OPF using Hybrid Sparse Gaussian Processes [57.70237375696411]
  The paper proposes a fast data-driven setup that uses the sparse and hybrid Gaussian processes (GP) framework to model the power flow equations with input uncertainty. We advocate the efficiency of the proposed approach by a numerical study over multiple IEEE test cases showing up to two times faster and more accurate solutions.
  arXiv  Detail & Related papers  (2022-08-30T09:27:59Z)
• Optimal Solutions for Joint Beamforming and Antenna Selection: From Branch and Bound to Machine Learning [47.10315221141495]
  This work revisits the joint beamforming (BF) and antenna selection (AS) problem, as well as its robust beamforming (RBF) version under imperfect channel state information (CSI) The main contribution of this work is threefold. First, an effective it branch and bound (B&B) framework for solving the problems of interest is proposed. Second, to expedite the potentially costly B&B algorithm, a machine learning (ML)-based scheme is proposed to help skip intermediate states of the B&B search tree.
  arXiv  Detail & Related papers  (2022-06-11T17:43:02Z)
• Quantum Annealing for Vehicle Routing Problem with weighted Segment [0.0]
  The study presents a QUBO formulation to solve traffic congestion problems on certain roads. The resulting route selection by optimizing the distribution of the flow of alternative road vehicles based on the weighting of road segments. The simulations on the D-Wave quantum annealer show optimal results on the route deployment of several vehicles.
  arXiv  Detail & Related papers  (2022-03-25T06:38:18Z)
• Towards an Optimal Hybrid Algorithm for EV Charging Stations Placement using Quantum Annealing and Genetic Algorithms [0.0]
  This paper aims to find a good for solving the Electric Vehicle Charger Placement (EVCP) problem. The authors introduce a novel combining Quantum Annealing and Genetic Algorithms to solve the problem.
  arXiv  Detail & Related papers  (2021-11-02T14:36:51Z)
• Ranking Cost: Building An Efficient and Scalable Circuit Routing Planner with Evolution-Based Optimization [49.207538634692916]
  We propose a new algorithm for circuit routing, named Ranking Cost, to form an efficient and trainable router. In our method, we introduce a new set of variables called cost maps, which can help the A* router to find out proper paths. Our algorithm is trained in an end-to-end manner and does not use any artificial data or human demonstration.
  arXiv  Detail & Related papers  (2021-10-08T07:22:45Z)
• Do Neural Optimal Transport Solvers Work? A Continuous Wasserstein-2 Benchmark [133.46066694893318]
  We evaluate the performance of neural network-based solvers for optimal transport. We find that existing solvers do not recover optimal transport maps even though they perform well in downstream tasks.
  arXiv  Detail & Related papers  (2021-06-03T15:59:28Z)
• 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)
• 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.