Time Dependent Travel Speed Vehicle Routing and Scheduling on a Real Road Network: The Case of Torino

AbstractVehicle routing and scheduling play a crucial role in the distribution chain. Although this research area has been broadly studied in the literature, there is still a lack of models closely representing real life problems. Most of the models proposed address constant travel times between nodes, without taking into account rush hours traffic congestion. In real applications in urban contexts the increasing of travel times due to congestion effects cannot be neglected. Models dealing with time dependent travel times work with simplified step functions, discretizing the time horizon in small time intervals. Even if this approach is broadly used, assuming travel times varying with discrete jumps is a strong approximation of real world conditions which evolve continuously. Another strong approximation adopted in the literature is that travel time (or speed) is computed on direct links, while in the real world vehicles travels on a road network, in which Euclidean distances do not hold anymore. In this paper, a vehicle routing problem (VRP) on a real road network with time dependent travel speed expressed by a polynomial function is addressed. Despite the difficulty to work with these kind of function, in this way congestion evolution behavior may be more precisely represented. In real situations, it is common to face different congestion peaks during the day, each one of which generally has different characteristics. Morning peaks are very sharp, i.e. congestion level rapidly increase reaching its maximum value which last for a short time after what congestion rapidly decrease, while evening peaks are generally much more spread across a longer time period and congestion variations are much more smoothed. Step functions, commonly used in practice, cannot represent at all realistic situations and peaks; linear functions may acceptable represents sharp peaks but not wider once. Polynomials, indeed, are able to better describe each type of peak. An application on Torino road network is presented. Speed evolution laws on main arcs are computed basing on real data obtained from an analysis carried out on averaged travel speed measured by an electronic system with 5minutes intervals over two weeks. Small streets for which this data are not available are supposed to have a constant travel speed. Computational results show that taking advantage on the available information on different rush hour peaks intensity and spread on different arcs, it is possible to obtain better vehicle routing and scheduling plan