A* search algorithm for an optimal investment problem in vehicle-sharing
systems
- URL: http://arxiv.org/abs/2311.08834v1
- Date: Wed, 15 Nov 2023 10:22:34 GMT
- Title: A* search algorithm for an optimal investment problem in vehicle-sharing
systems
- Authors: Ba Luat Le, Layla Martin, Emrah Demir, and Duc Minh Vu
- Abstract summary: We study an optimal investment problem that arises in the context of the vehicle-sharing system.
We propose an A* search algorithm to address this particular variant of the Traveling Salesman Problem.
- Score: 0.8999666725996978
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study an optimal investment problem that arises in the context of the
vehicle-sharing system. Given a set of locations to build stations, we need to
determine i) the sequence of stations to be built and the number of vehicles to
acquire in order to obtain the target state where all stations are built, and
ii) the number of vehicles to acquire and their allocation in order to maximize
the total profit returned by operating the system when some or all stations are
open. The profitability associated with operating open stations, measured over
a specific time period, is represented as a linear optimization problem applied
to a collection of open stations. With operating capital, the owner of the
system can open new stations. This property introduces a set-dependent aspect
to the duration required for opening a new station, and the optimal investment
problem can be viewed as a variant of the Traveling Salesman Problem (TSP) with
set-dependent cost. We propose an A* search algorithm to address this
particular variant of the TSP. Computational experiments highlight the benefits
of the proposed algorithm in comparison to the widely recognized Dijkstra
algorithm and propose future research to explore new possibilities and
applications for both exact and approximate A* algorithms.
Related papers
- Using metaheuristics for the location of bicycle stations [4.2847927405489195]
We model the problem as the p-median problem, that is a major existing localization problem in optimization.
The p-median problem seeks to place a set of facilities (bicycle stations) in a way that minimizes the distance between a set of clients (citizens) and their closest facility (bike station)
arXiv Detail & Related papers (2024-02-06T12:19:46Z) - Multi-Agent Learning of Efficient Fulfilment and Routing Strategies in
E-Commerce [11.421159751635667]
paper presents an integrated algorithmic framework for minimising product delivery costs in e-commerce.
One of the major challenges in e-commerce is the large volume of-temporally diverse orders from multiple customers.
We propose an approach that combines graph neural networks and reinforcement learning to train the node selection and vehicle agents.
arXiv Detail & Related papers (2023-11-20T10:32:28Z) - Energy-Guided Continuous Entropic Barycenter Estimation for General Costs [95.33926437521046]
We propose a novel algorithm for approximating the continuous Entropic OT (EOT) barycenter for arbitrary OT cost functions.
Our approach is built upon the dual reformulation of the EOT problem based on weak OT.
arXiv Detail & Related papers (2023-10-02T11:24:36Z) - Fast Optimal Locally Private Mean Estimation via Random Projections [58.603579803010796]
We study the problem of locally private mean estimation of high-dimensional vectors in the Euclidean ball.
We propose a new algorithmic framework, ProjUnit, for private mean estimation.
Our framework is deceptively simple: each randomizer projects its input to a random low-dimensional subspace, normalizes the result, and then runs an optimal algorithm.
arXiv Detail & Related papers (2023-06-07T14:07:35Z) - Optimal Horizon-Free Reward-Free Exploration for Linear Mixture MDPs [60.40452803295326]
We propose a new reward-free algorithm for learning linear Markov decision processes (MDPs)
At the core of our algorithm is uncertainty-weighted value-targeted regression with exploration-driven pseudo-reward.
We show that our algorithm only needs to explore $tilde O( d2varepsilon-2)$ episodes to find an $varepsilon$-optimal policy.
arXiv Detail & Related papers (2023-03-17T17:53:28Z) - Multi-Start Team Orienteering Problem for UAS Mission Re-Planning with
Data-Efficient Deep Reinforcement Learning [9.877261093287304]
We study a mission re-planning problem where vehicles are initially located away from the depot and have different amounts of fuel.
We develop a policy network with self-attention on each partial tour and encoder-decoder attention between the partial tour and the remaining nodes.
We propose a modified REINFORCE algorithm where the greedy rollout baseline is replaced by a local mini-batch baseline based on multiple, possibly non-duplicate sample rollouts.
arXiv Detail & Related papers (2023-03-02T15:15:56Z) - A Metaheuristic Algorithm for Large Maximum Weight Independent Set
Problems [58.348679046591265]
Given a node-weighted graph, find a set of independent (mutually nonadjacent) nodes whose node-weight sum is maximum.
Some of the graphs airsing in this application are large, having hundreds of thousands of nodes and hundreds of millions of edges.
We develop a new local search algorithm, which is a metaheuristic in the greedy randomized adaptive search framework.
arXiv Detail & Related papers (2022-03-28T21:34:16Z) - Learning (Re-)Starting Solutions for Vehicle Routing Problems [14.509927512118544]
A key challenge in solving a optimization problem is how to guide the agent (i.e., solver) to efficiently explore the enormous search space.
In this paper, we show it is possible to use machine learning to speedup the exploration.
arXiv Detail & Related papers (2020-08-08T02:53:09Z) - Congestion-aware Evacuation Routing using Augmented Reality Devices [96.68280427555808]
We present a congestion-aware routing solution for indoor evacuation, which produces real-time individual-customized evacuation routes among multiple destinations.
A population density map, obtained on-the-fly by aggregating locations of evacuees from user-end Augmented Reality (AR) devices, is used to model the congestion distribution inside a building.
arXiv Detail & Related papers (2020-04-25T22:54:35Z) - 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.