Cardiff University | Prifysgol Caerdydd ORCA
Online Research @ Cardiff 
WelshClear Cookie - decide language by browser settings

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

Dijkstra, Lukas, Gagarin, Andrei ORCID:, Corcoran, Padraig ORCID: and Lewis, Rhyd ORCID: 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

[thumbnail of INOC_22.pdf]
PDF - Published Version
Available under License Creative Commons Attribution Non-commercial No Derivatives.

Download (751kB) | Preview


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
Publisher: OpenProceedings
ISBN: 9783893180967
Date of First Compliant Deposit: 30 January 2024
Last Modified: 16 Apr 2024 09:19

Actions (repository staff only)

Edit Item Edit Item


Downloads per month over past year

View more statistics