𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A branch-and-cut algorithm for the undirected prize collecting traveling salesman problem

✍ Scribed by Jean-François Bérubé; Michel Gendreau; Jean-Yves Potvin

Publisher
John Wiley and Sons
Year
2009
Tongue
English
Weight
130 KB
Volume
54
Category
Article
ISSN
0028-3045

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

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. © 2009 Wiley Periodicals, Inc. NETWORKS, 2009

📜 SIMILAR VOLUMES

A branch-and-cut algorithm for the undir
A branch-and-cut algorithm for the undirected selective traveling salesman problem
✍ Gendreau, Michel; Laporte, Gilbert; Semet, Fr�d�ric 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 120 KB 👁 2 views

The Selective Traveling Salesman Problem (STSP) is defined on a graph in which profits are associated with vertices and costs are associated with edges. Some vertices are compulsory. The aim is to construct a tour of maximal profit including all compulsory vertices and whose cost does not exceed a p

A branch-and-cut algorithm for the picku
A branch-and-cut algorithm for the pickup and delivery traveling salesman problem with multiple stacks
✍ Jean-François Côté; Claudia Archetti; Maria Grazia Speranza; Michel Gendreau; Je 📂 Article 📅 2012 🏛 John Wiley and Sons 🌐 English ⚖ 208 KB 👁 1 views

This article studies the pickup and delivery traveling salesman problem with multiple stacks. The vehicle contains a number of (horizontal) stacks of finite capacity for loading items from the rear of the vehicle. Each stack must satisfy the last-in-first-out constraint that states that any new item

A polynomial algorithm for a constrained
A polynomial algorithm for a constrained traveling salesman problem
✍ J.H. Rubinstein; D.A. Thomas; N.C. Wormald 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 125 KB

## Abstract We give a polynomial‐time algorithm for finding a solution to the Traveling Salesman Problem when the points given are constrained to lie on a fixed set of smooth curves of finite length. © 2001 John Wiley & Sons, Inc.