Optimization Online


Exact algorithms for the Traveling Salesman Problem with Draft Limits

Maria Battarra(m.battarra***at***soton.ac.uk)
Artur Alves Pessoa(artur***at***producao.uff.br)
Anand Subramanian(anand***at***ct.ufpb.br)
Eduardo Uchoa(uchoa***at***producao.uff.br)

Abstract: This paper deals with the Traveling Salesman Problem (TSP) with Draft Limits (TSPDL), which is a variant of the well-known TSP in the context of maritime transportation. In this recently proposed problem, draft limits are imposed due to restrictions on the port infrastructures. Exact algorithms based on three mathematical formulations are proposed and their performance compared through extensive computational experiments. Optimal solutions are reported for open instances of benchmark problems available in the literature.

Keywords: draft limits, traveling salesman, cutting planes, column generation, extended formulation

Category 1: Integer Programming

Category 2: Combinatorial Optimization (Branch and Cut Algorithms )

Citation: Unpublished: University of Southampton, 2013

Download: [PDF]

Entry Submitted: 02/25/2013
Entry Accepted: 02/25/2013
Entry Last Modified: 02/25/2013

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society