Digraphs and k-domination models for facility location problems in road networks: Greedy heuristics

Dijkstra, Lukas, Gagarin, Andrei ORCID: https://orcid.org/0000-0001-9749-9706, Corcoran, Padraig ORCID: https://orcid.org/0000-0001-9731-3385 and Lewis, Rhyd ORCID: https://orcid.org/0000-0003-1046-811X 2024. Digraphs and k-domination models for facility location problems in road networks: Greedy heuristics. Presented at: International Network Optimization Conference 2024, Dublin, Ireland, 11-13 March 2024. Proceedings of the 11th International Network Optimization Conference (INOC). OpenProceedings, pp. 22-27. 10.48786/inoc.2024.05

Preview

PDF - Published Version Available under License Creative Commons Attribution Non-commercial No Derivatives. Download (751kB) | Preview

Abstract

We consider modelling the placement of refuelling facilities for alternative fuel vehicles in road networks by using directed graphs and k-dominating sets. The concept of a reachability digraph corresponding to a road network is introduced, and three greedy heuristics are proposed and experimentally tested to search for k-dominating sets in two types of digraphs, including the reachability digraphs of road networks. These simple and efficient heuristics show that refined greedy strategies usually provide better results for large as well as small digraphs, and their results are reasonably close to exact solutions for small digraphs. Combining the greedy strategies with some randomized heuristic ideas helps to improve the results even further in the case of digraphs associated with the road networks.

Item Type:	Conference or Workshop Item (Paper)
Date Type:	Publication
Status:	Published
Schools:	Computer Science & Informatics Mathematics
Publisher:	OpenProceedings
ISBN:	9783893180967
Date of First Compliant Deposit:	30 January 2024
Last Modified:	16 Apr 2024 09:19
URI:	https://orca.cardiff.ac.uk/id/eprint/165912

Actions (repository staff only)

Edit Item