The Traveling Salesman Problem with Draft Limits

The Traveling Salesman Problem with Draft Limits

0.00 Avg rating0 Votes
Article ID: iaor20121277
Volume: 39
Issue: 9
Start Page Number: 2161
End Page Number: 2167
Publication Date: Sep 2012
Journal: Computers and Operations Research
Authors: , , ,
Keywords: combinatorial optimization, programming: travelling salesman
Abstract:

In maritime transportation, routing decisions are sometimes affected by draft limits in ports. The draft of a ship is the distance between the waterline and the bottom of the ship and is a function of the load onboard. Draft limits in ports can thus prevent ships to enter these ports fully loaded and may impose a constraint on the sequence of visits made by a ship. This paper introduces the Traveling Salesman Problem with Draft Limits (TSPDL), which is to determine an optimal sequence of port visits under draft limit constraints. We present two mathematical formulations for the TSPDL, and suggest valid inequalities and strengthened bounds. We also introduce a set of instances based on TSPLIB. A branch‐and‐cut algorithm is applied on both formulations for all these instances. Computational results show that introducing draft limits make the problem much harder to solve. They also indicate that the proposed valid inequalities and strengthened bounds significantly reduce both the number of branch‐and‐bound nodes and the solution times.

Reviews

Required fields are marked *. Your email address will not be published.