Paper Info
Title
A branch-and-cut algorithm for the capacitated profitable tour problem.
Abstract
This paper considers the Capacitated Profitable Tour Problem (CPTP) which is a special case of the Elementary Shortest Path Problem with Resource Constraints (ESPPRC). The CPTP belongs to the group of problems known as traveling salesman problems with profits. In CPTP each customer is associated with a profit and a demand and the objective is to find a capacitated tour (rooted in a depot node) that minimizes the total travel distance minus the profit of the visited customers. The CPTP can be recognized as the sub-problem in many column generation applications, where it is traditionally solved through dynamic programming. In this paper we present an alternative framework based on a formulation for the undirected CPTP and solved through branch-and-cut. Valid inequalities are presented among which we introduce a new family of inequalities for the CPTP denoted rounded multistar inequalities and we prove their validity. Computational experiments are performed on a set of instances known from the literature and a set of newly generated instances. The results indicate that the presented algorithm is highly competitive with the dynamic programming algorithms. In particular, we are able to solve instances with 800 nodes to optimality where the dynamic programming algorithms cannot solve instances with more than 200 nodes. Moreover dynamic programming and branch-and-cut complement each other well, giving us hope for solving more general problems through hybrid approaches. The paper is intended to serve as a platform for further development of branch-and-cut algorithms for CPTP hence also acting as a survey/tutorial.
Year
DOI
Venue
2014
10.1016/j.disopt.2014.08.001
Discrete Optimization
Keywords
Field
DocType
Branch-and-cut algorithm,Valid inequalities,Profitable tour problem,Capacitated shortest path problem,Traveling salesman problem
Dynamic programming,Column generation,Mathematical optimization,Shortest path problem,Branch and cut,Algorithm,Travelling salesman problem,Mathematics,Special case
Journal
Volume
Issue
ISSN
14
C
1572-5286
Citations 
PageRank 
References 
10
0.63
22
Authors
4
Name
Order
Citations
PageRank
Mads Jepsen11415.06
Bjørn Petersen21254.81
Simon Spoorendonk32079.17
David Pisinger42454148.80