A matheuristics approach to solve a liner network design problem

The process of ship itinerary planning for tourist cruises must take into account several specific constraints related to fuel consumption, port costs, and point of interests to be inserted in each tour. The present work models the tour planning problem as a variant of vehicle routing problem considering several particular features: fixed number of tours, not mandatory visits all nodes, multiple time windows, possibility to choose among different travel speed values. The resulting mathematical formulation lead to a complex model for which commercial solver fails to solve large instances in a reasonable time. Some features of models such as not mandatory visit of all nodes let the model to be exploited in order to develop a specific heuristic solution approach.