A* search algorithm for an optimal investment problem in vehicle-sharing systems

Le, Ba Luat, Martin, Layla, Demir, Emrah ORCID: https://orcid.org/0000-0002-4726-2556 and Vu, Duc Minh 2024. A* search algorithm for an optimal investment problem in vehicle-sharing systems. Presented at: Computational Data and Social Networks, Hanoi, Vietnam, 11-13 December 2023. Published in: Ha, M.H., Zhu, X. and Thai, M.T. eds. Conference proceedings: Computational Data and Social Networks, CSoNet 2023. Lecture Notes in Computer Science , vol.14479 Singapore: Springer, 162–173. 10.1007/978-981-97-0669-3_16

PDF - Accepted Post-Print Version Download (250kB)

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.

Item Type:	Conference or Workshop Item (Paper)
Date Type:	Publication
Status:	Published
Schools:	Business (Including Economics)
Publisher:	Springer
ISBN:	9789819706693
Date of First Compliant Deposit:	2 March 2024
Date of Acceptance:	1 February 2024
Last Modified:	05 Mar 2024 13:06
URI:	https://orca.cardiff.ac.uk/id/eprint/166770

Actions (repository staff only)

Edit Item