A branch & cut algorithm for the windy general routing problem and special cases

被引：46

作者：

Corberan, Angel

Plana, Isaac

Sanchis, Jose M.

机构：

[1] Univ Valencia, DEIO, E-46100 Valencia, Spain

[2] Univ Politecn Valencia, DMA, Valencia 46022, Spain

来源：

NETWORKS | 2007年 / 49卷 / 04期

关键词：

branch & cut; arc routing; windy general routing problem; windy rural postman problem;

D O I：

10.1002/net.20176

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

In this paper, we present an exact algorithm for the Windy General Routing Problem. This problem generalizes many important Arc Routing Problems and also has some interesting real-life applications. The Branch & Cut method presented here is based on a cutting-plane algorithm that identifies violated inequalities of several classes of facet-inducing inequalities for the corresponding polyhedron. The whole procedure has been tested over different sets of instances and is capable of solving to optimality large-size instances of several routing problems defined on undirected, mixed, and windy graphs. (c) 2007 Wiley Periodicals, Inc.

引用

页码：245 / 257

页数：13