The multi-path traveling salesman problem with stochastic travel costs. Building realistic instances for city logistics applications

One of the main issues related to routing problems applied in an urban context with uncertainty related to the transportation costs is how to define realistic instances. In fact, the instances present in the literature are often too much artificial to really reflect the peculiarities of urban transportation, and the freight transportation in particular. In this paper, we overcome this issue, providing a standard methodology to extend routing instances from the literature incorporating real data provided by sensors networks. In order to test the methodology, we consider a recently introduced routing problem specifically designed for City Logistics and Smart City applications, the multi-path Traveling Salesman Problem with stochastic travel costs. Given a set of nodes, where each pair of nodes is connected by several paths and each path shows a stochastic travel cost with unknown distribution, the multi-path Traveling Salesman Problem with stochastic travel costs (mpTSPs) aims at finding an expected minimum Hamiltonian tour connecting all nodes. The mpTSPs arises in City Logistics when one has to design tours to provide services such as garbage collection, periodic delivery of goods in urban grocery distribution, and periodic checks of shared resources as in bike sharing services. In these situations, the decision maker must provide tours that will be used within a time horizon, which spans from one to several weeks. In this case, the different paths connecting pairs of nodes in the city are affected by the uncertainty due to the different time-dependent travel time distributions of the paths. Moreover, in many cases even an approximated knowledge of the travel time distribution is made difficult by the large size of the data involved and the high variance of the travel times. New instances representing a medium-sized city derived from the speed sensor network of the city of Turin are introduced and the corresponding results discussed, showing benefits and limits of the methods presently available in the literature.