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


    Multivehicle Spacing Along Smooth Curvilinear Paths

    Weitz, Lesley / Hurtado, John | AIAA | 2010


    Vehicle Miles Traveled in Multivehicle Households

    Pathomsiri, Somchai / Haghani, Ali / Schonfeld, Paul M. | Transportation Research Record | 2005