A branch‐price‐and‐cut algorithm for the min‐max k ‐vehicle windy rural postman problem

Journal Article

  • Author(s): Enrique Benavent, Ángel Corberán, Guy Desaulniers, François Lessard, Isaac Plana, José M. Sanchis
  • Article first published online: 05 Oct 2013
  • DOI: 10.1002/net.21520
  • Read on Online Library
  • Subscribe to Journal


The min‐max k‐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

Related Topics

Related Publications

Related Content

Site Footer


This website is provided by John Wiley & Sons Limited, The Atrium, Southern Gate, Chichester, West Sussex PO19 8SQ (Company No: 00641132, VAT No: 376766987)

Published features on are checked for statistical accuracy by a panel from the European Network for Business and Industrial Statistics (ENBIS)   to whom Wiley and express their gratitude. This panel are: Ron Kenett, David Steinberg, Shirley Coleman, Irena Ograjenšek, Fabrizio Ruggeri, Rainer Göb, Philippe Castagliola, Xavier Tort-Martorell, Bart De Ketelaere, Antonio Pievatolo, Martina Vandebroek, Lance Mitchell, Gilbert Saporta, Helmut Waldl and Stelios Psarakis.