A Branch-and-Cut Algorithm for the Undirected Prize Collecting Traveling Salesman Problem

被引：22

作者：

Berube, Jean-Francois

Gendreau, Michel ^{[1
]}

Potvin, Jean-Yves

机构：

[1] Univ Montreal, Ctr Interuniv Rech Reseaux Entreprise Logist & Tr, Montreal, PQ H3C 3J7, Canada

来源：

NETWORKS | 2009年 / 54卷 / 01期

基金：

加拿大自然科学与工程研究理事会;

关键词：

prize collecting traveling salesman problem; branch-and-cut; valid inequalities; FACETS;

D O I：

10.1002/net.20307

中图分类号：

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

学科分类号：

0812 ;

摘要：

Given an undirected graph with edge costs and vertex prizes, the aim of the Prize Collecting Traveling Salesman Problem (PCTSP) is to find a simple cycle minimizing the total edge cost while collecting at least a minimum amount of prizes. In this article, we present a branch-and-cut algorithm to solve the PCTSP. We have adapted and implemented some classical polyhedral results for the PCTSP and derived inequalities from cuts designed for the Orienteering Problem. Computational results on instances with more than 500 vertices are reported. (C) 2009 Wiley Periodicals, Inc. NETWORKS, Vol. 54(1), 56-67 2009

引用

页码：56 / 67

页数：12

共 33 条

[1] Branching rules revisited [J].