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

*(English)*Zbl 1317.90082Summary: 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

\textit{P. Pusztai} and \textit{T. Hajba}, Acta Univ. Sapientiae, Inform. 7, No. 1, 107--120 (2015; Zbl 1317.90082)

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.