A branch‐price‐and‐cut algorithm for the min‐max k‐vehicle windy rural postman problem. Issue 1 (5th October 2013)

• Record Type: Journal Article
• Authors: Benavent, Enrique; Corberán, Ángel; Desaulniers, Guy; Lessard, François; Plana, Isaac; Sanchis, José M.
• Is Part Of: Networks. Volume 63:Issue 1(2014:Jan.)
• Page Start: 34
• Page End: 45
• Publication Date: 2013-10-05
• Subjects: Network analysis (Planning) -- Periodicals; 658.4032
• DOI: 10.1002/net.21520
• Languages: English
• ISSNs: 0028-3045

Abstract

<abstract abstract-type="main"> <title>Abstract</title> <p>The min‐max <italic>k</italic>‐vehicles windy rural postman problem consists of minimizing the maximal distance traveled by a vehicle to find a set of balanced routes that jointly service all the required edges in a windy graph. This is a very difficult problem, for which a branch‐and‐cut algorithm has already been proposed, providing good results when the number of vehicles is small. In this article, we present a branch‐price‐and‐cut method capable of obtaining optimal solutions for this problem when the number of vehicles is larger for the same set of required edges. Extensive computational results on instances from the literature are presented. © 2013 Wiley Periodicals, Inc. NETWORKS, Vol. 63(1), 34–45 2014</p> </abstract>