A general neighborhood search for Traveling Salesman Problem with Draft Limits
Résumé
Traveling Salesman Problem with Draft Limits (TSPDL) is a new variant of the well-known Traveling Salesman Problem
(TSP), proposed recently in the context of maritime transportation. TSPDL consists of visiting and delivering goods for a set of ports using a ship located initially at a depot. Since each port has a delivery demand known in advance the ship starts tour with a load equal to the total demand, visits each port exactly once and comes back to the depot performing the lowest cost tour. However, to each port is assigned a draft limit, which represent the maximal allowed load on the ship upon entering some port. We propose two General Variable Neighborhood Search for solving Traveling Salesman Problem with Draft Limits. The proposed methods are tested on a set of benchmark instances from the literature and computational results shows that they are very efficient in solving this problem.