This article proposes a mathematical model and a branch-and-price algorithm for the multivehicle covering tour problem. This problem consists in finding a set of routes on a weighted graph such that a set of nodes that cannot be visited is covered. A node is covered if it lies within a predefined distance of a visited node. The subproblem encountered during the column generation is a variant of the profitable tour problem. It is reduced to a ring star problem and a branch-and-cut algorithm is developed. Computational results are reported on randomly generated instances.


    Access

    Access via TIB

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    A branch-and-price algorithm for the multivehicle covering tour problem


    Contributors:

    Published in:

    Networks ; 64 , 3 ; 160-168


    Publication date :

    2014


    Size :

    9 Seiten




    Type of media :

    Article (Journal)


    Type of material :

    Print


    Language :

    English





    The Profitable Arc Tour Problem: Solution with a Branch-and-Price Algorithm

    Feillet, D. / Dejax, P. / Gendreau, M. | British Library Online Contents | 2005


    Semiautonomous multivehicle safety

    Verma, R. / Vecchio, D.D. | Tema Archive | 2011


    Intelligent navigation and multivehicle coordination

    McKay, Mark D. / Anderson, Matthew O. / Kinoshita, Robert A. et al. | SPIE | 1999


    Multivehicle Spacing Along Smooth Curvilinear Paths

    Weitz, Lesley / Hurtado, John | AIAA | 2010