A large neighborhood search based matheuristic for the tourist cruises itinerary planning

The planning of itineraries for tourist cruises is a complex process where several features, such as vessel selection, port services, and requirements for point of interest to be inserted in each tour, must be addressed. The present work models the tour planning problem as a variant of vehicle routing problem considering specific constraints such as: fixed number of tours, not mandatory visits of 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 solvers fail to solve large instances in a reasonable time. To overcome this issue we propose a Large Neighborhood Search based matheuristic, in which an over-constrained version of the mathematical model is used to exhaustively and efficiently explore large neighborhoods. Test results performed on a real case instances demonstrate effectiveness of the proposed approach.