A Multi-objective Iterated Local Search Approach to Solve the Insular Traveling Salesman Problem

In this work, we solve the bi-objective insular traveling salesman problem, which arises when a barge collects the waste generated by a set of islands. It considers selection and routing decisions coming from the selection of docks to be visited and the sequence of visits performed by the barge. Moreover, the cost of the tour performed by the barge and the waste ground transportation costs are minimized in a multi-objective approach. In this work, we propose a local search multi-objective approach to find approximations of the Pareto sets of efficient solutions. It uses an iterated local search method to find solutions in several areas of the front based on a weighted sum approach. We evaluated the performance of our proposal on a set of real-world problem instances from twenty-one islands in the south of Chile. Our results demonstrated the ability of the proposed approach to find high-quality approximations of the Pareto sets for all the problem instances evaluated in reduced times compared to an exact approach.