×

zbMATH — the first resource for mathematics

Empirical study of the greedy heuristic as applied to the link selection problem. (English) Zbl 1317.90082
Summary: 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.
MSC:
90B20 Traffic problems in operations research
90C10 Integer programming
90C59 Approximation methods and heuristics in mathematical programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] V. Chvátal, A greedy heuristic for the set-covering problem, Math. Oper. Res.,4, 3, (1979) 233-235. ⇒107 · Zbl 0443.90066
[2] D. S. Hochbaum (Ed.), Approximation Algorithms for NP-hard Problems, PWS Publishing Company, Boston, Mass., 1997. ⇒107, 108, 113
[3] D. B. Johnson, Approximation algorithms for combinatorial problems, J. Comp. System Sci., 9, 3 (1974) 256-278. ⇒107, 112 · Zbl 0296.65036
[4] L. Lovász, On the ratio of optimal integral, and fractional covers Discrete Math.,13, 4 (1975) 383-390. ⇒112
[5] L. Marton, P. Pusztai, On modelling and computing traffic assignment, Proc. EURO XVII. European Conf. Operational Research, Budapest, Hungary, 2000, pp. 114. ⇒107
[6] P. Pusztai, An application of the greedy heuristic of set cover to traffic checks, CEJOR Cent. Eur. J. Oper. Res., 16, 4 (2008) 407-414 ⇒107, 108, 115, 119 · Zbl 1162.90384
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.