The bi-objective insular traveling salesman problem with maritime and ground transportation costs

This paper introduces and studies the bi-objective insular traveling salesman problem, where a set of rural islands must be served using a single barge following a single route. Each island presents a number of docks from which at least one dock must be selected for visiting. One distinctive feature is that the freight to be collected from each dock or node is not known in advance, since they depend on a set of selected docks at each island and on the strategy employed to allocate the island demands among the visited docks. In contrast to other similar problems found in the literature, particularly the generalized traveling salesman problem, two objective functions are aimed to be minimized: maritime and ground transportation costs. The ground transportation cost incurred at the islands is strongly related to the strategy for transporting the freight to the selected docks inside the islands, which is a distinct characteristic of the studied problem. The proposed mixed integer programming model is solved for a set of real instances from Chile using a weighted sum approach, denoting the bi-objective nature of the problem. This problem feature along with the optimal solution structure are revealed and analyzed, and the appropriateness of the proposed approach is highlighted for freight collection or distribution decision making in insular zones.