Premium
New facets and an enhanced branch‐and‐cut for the min–max K ‐vehicles windy rural postman problem
Author(s) -
Benavent Enrique,
Corberán Angel,
Plana Isaac,
Sanchis José M.
Publication year - 2011
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20469
Subject(s) - set (abstract data type) , branch and cut , mathematical optimization , facet (psychology) , mathematics , metaheuristic , computer science , vehicle routing problem , combinatorics , integer programming , algorithm , routing (electronic design automation) , psychology , social psychology , computer network , personality , big five personality traits , programming language
The min–max windy rural postman problem is a multiple vehicle version of the windy rural postman problem, WRPP, which consists of minimizing the length of the longest route to find a set of balanced routes for the vehicles. In a previous paper, an ILP formulation and a partial polyhedral study were presented, and a preliminary branch‐and‐cut algorithm that produced some promising computational results was implemented. In this article, we present further results for this problem. We describe several new facet‐inducing inequalities obtained from the WRPP, as well as some inequalities that have to be satisfied by any optimal solution. We present an enhanced branch‐and‐cut algorithm that takes advantage of both these new inequalities and high quality min–max K ‐WRPP feasible solutions obtained by a metaheuristic. Computational results on a large set of instances are also reported. © 2011 Wiley Periodicals, Inc. NETWORKS, Vol. 58(4), 255–272 2011