On spatio-temporal granularity of optimal delivery tours

International audienceUrban delivery optimization is mainly based on the classical Travel-ing Salesman Problem (TSP). Time-Dependent TSP (TD-TSP) is an extension of the TSP wherein the cost of an edge depends on the departure time from its source node. It is particularly relevant in real urban traffic environments, as the actual travel speeds vary according to the time of the day. By decomposing the time horizon into equal-sized time steps, and associating a travel time to each time-step of each edge, we first examine the relationship between the length of the time-step and the spatio-temporal features of the data-set, which describe the amount of information degradation in the data-set along both dimensions. We also study the effect of this spatio-temporal granularity on the quality of the TSP and the TD-TSP solutions. Our benchmark data-set is produced from a realistic traffic flow micro-simulation of the city of Lyon. Four time-step lengths, ranging from six to sixty minutes, and several numbers of deliveries, ranging from ten to thirty, are considered for two exact solvers, namely dynamic programming and an integer linear programming solver