In this study, we present exact and heuristics algorithms for a traffic sensors location problem called the screen line problem. It is a problem of how to locate traffic sensors on a transportation network where all the origin/destination node pairs are fully separated. The problem experiences two main complexity dimensions that obstruct finding an efficient solution algorithm for large-scale networks: its mathematical formulation, which is proved in the literature to be NP-hard, and an inherent combinatorial complexity due to the need for a network complete path enumeration. In this study, the problem is reformulated as a set covering problem. Thereafter, the dual formulation is recalled showing that the shortest path-based column generation method would yield as many paths as necessary and hence circumvent the intractability of the full path enumeration task. This path generation technique enables applying both the proposed heuristics and exact methods to the problem. In addition, the gap value between the heuristics and the exact algorithms is set to be examined statistically. For evaluation, three networks of different sizes were used to track the scalability of proposed algorithms. The methodology showed high efficiency to deal with up to 10,000 demand node pairs in addition to the capability of producing practical solutions with respect to normal traffic flow conditions. The proposed heuristics algorithm stipulates a gap value of less than 25% with more than 99% confidence.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    Exact and Heuristics Algorithms for Screen Line Problem in Large Size Networks: Shortest Path-Based Column Generation Approach


    Contributors:

    Published in:

    Publication date :

    2022-12-01


    Size :

    1422507 byte




    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    English





    Heuristics for Fast One-to-Many Multicriteria Shortest Path Search

    Kurbanov, Temirlan / Cuchy, Marek / Vokrinek, Jiri | IEEE | 2022


    An exact algorithm for the mean–standard deviation shortest path problem

    Khani, Alireza / Boyles, Stephen D. | Elsevier | 2015


    Shortest Path Algorithms: An Evaluation using Real Road Networks

    Zhan, F. B. / Noon, C. E. | British Library Online Contents | 1998