Estimating of time-dependent travel times vía Mixed Integer Programming

Abstract

Routing and distribution problems have been widely studied within the Operations Research (OR) community. When restricting to distribution problems in large cities, the congestion of the road network becomes a key aspect with a significant practical impact. These problems are known as Time-Dependent VRPs (TDVRPs), as they naturally capture the effect of congestion by assuming that the travel time between any two customers varies depending on the departure time. The TDVRP literature has widely accepted to model the time-dependent travel time model between two customers as continuous piecewise linear (PWL) function that satisfies the first-in first-out (FIFO) condition. In this paper, we investigate the problem of estimating these continuous PWL travel time functions from real data travel time data. We benchmark two recently proposed Mixed Integer Programming based models for estimating general PWL functions and a well-known heuristic proposed within the context of travel-time estimations. In addition, we also contribute with a new dataset of instances created using real-world data as input.