Designing Single Origin-destination Itineraries for Several Classes of Cycle-tourists

This study concerns the optimal design of cycle tourist itineraries considering several classes of users. It builds upon a recent work which first introduced the problem of designing the most attractive itinerary for cycle tourists connecting a given origin to a given destination, subject to a budget and a time constraint. Starting from a network made of existing cycle-trails, gravel paths, and unsurfaced field roads, local administrators face the problem of selecting a budget-compliant set of edges to be reconditioned and turned into paved bike trails. Indeed, investing in enhancing cycle tourism infrastructures proved to be effective in fostering sustainable development but decision support tools are needed to support decision makers in optimizing scarce public resources spending. The key issue in this problem is the objective function, namely the route attractiveness. Each node and each edge of the network yields a reward each time it is traversed, related to the pleasure of cycling along it. Additional pleasure usually decreases when traversing the same edge or node one more time but it may still be positive. Therefore, the optimal route may contain cycles, which is a special feature of this problem. In previous studies attractiveness was computed on the basis of each point of interest located on the edges and at the nodes of the route, and the route maximizing total attractiveness was searched for. The focus was on the generalist cycle tourist, without thematic preferences. This study takes a more realistic view and proposes a model where different classes of cycle tourist are considered individually, each one with its own preferences, like the cultural oriented tourist, the gastronomic fan, or the one fond of wild life and nature. This new perspective yields a new network design problem in the field of vehicle routing problems with profits, generalizing the Orienteering Problem, that we call the multi-commodity orienteering problem with network design (MOP-ND): it consists of designing a set of itineraries, one for each user class, sharing the same origin and the same destination and potentially any edge of the network, so that each itinerary satisfies a maximum duration constraint and the cost of the whole infrastructure is budget compliant. The objective is to maximize the sum on all user classes of the attractiveness of the itinerary selected for that class. In this paper we provide a mathematical model for MOP-ND, test it on realistic data, and compare with the generalist model.