A branch‐and‐price algorithm for the multivehicle covering tour problem. Issue 3 (15th September 2014)

• Record Type: Journal Article
• Authors: Jozefowiez, Nicolas
• Is Part Of: Networks. Volume 64:Issue 3(2014:Oct.)
• Page Start: 160
• Page End: 168
• Publication Date: 2014-09-15
• Subjects: Network analysis (Planning) -- Periodicals; 658.4032
• DOI: 10.1002/net.21564
• Languages: English
• ISSNs: 0028-3045

Abstract

<abstract abstract-type="main"> <title> <x xml:space="preserve">Abstract</x> </title> <p>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. © 2014 Wiley Periodicals, Inc. NETWORKS, Vol. 64(3), 160–168 2014</p> </abstract>