<abstract xmlns="http://www.w3.org/1999/xhtml"><p>Behind the link selection problem there is a practical problem that aims to check efficiently the vehicles on a road network. The checking process is to be realized with license plate reading cameras for checking the valid vignette of vehicles using that part of the network. However this problem should be defined generally and the methods of obtaining a solution can be applied to a wider range of problems independent of the original problem. This paper defines the link selection problem with directed graph, it shows the NP-hard complexity and it gives a heuristic and binary integer programming models to solve the problem. These two kinds of approaches allow us to examine and qualify the heuristic. The computational results of the methods are compared with different sizes of problems.</p></abstract>

Behind the link selection problem there is a practical problem that aims to check efficiently the vehicles on a road network. The checking process is to be realized with license plate reading cameras for checking the valid vignette of vehicles using that part of the network. However this problem should be defined generally and the methods of obtaining a solution can be applied to a wider range of problems independent of the original problem. This paper defines the link selection problem with directed graph, it shows the NP-hard complexity and it gives a heuristic and binary integer programming models to solve the problem. These two kinds of approaches allow us to examine and qualify the heuristic. The computational results of the methods are compared with different sizes of problems.

Empirical study of the greedy heuristic as applied to the link selection problem

Acta Universitatis Sapientiae, Informatica

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

{"article-title":"Empirical study of the greedy heuristic as applied to the link selection problem"}

Behind the link selection problem there is a practical problem that aims to check efficiently the vehicles on a road network. The checking process is to be...

Empirical study of the greedy heuristic as applied to the link selection problem

Publié en ligne: 08 juin 2015

Pages: 107 - 120

Reçu: 09 janv. 2015

DOI: https://doi.org/10.1515/ausi-2015-0014

© Pál Pusztai et al.

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.