## 4 Computational Experiments
### Instances  
Although Time-Dependent Vehicle Routing problems have received increased attention from the scientific community in recent years, there is still a lack of realistic instances. To overcome this aspect, we have generated a new set of instances based on the real travel time functions of two major European cities: Paris and London.  
During the last decade, the popularity of mobile technology and location services allowed the creation of high quality large real-time and historical floating vehicle datasets. These data are continuously collected by millions of users that anonymously send their GPS positions to services like Google Traffic or TomTom Live. Only these IT big players have the availability of time-dependent data. As a result, there is no complete dataset freely available to the entire research community.  
We extracted (approximate) travel time functions as follows. Given a road map from OpenStreetMap (in XML or PBF format) we first extracted the topology of graph \(G\) in terms of: vertices and their geographical coordinates (latitude and longitude), arcs with attributes like length, maximum speed \(u_{ij}\) (derived from tags or default street type speed), geometry (pillar and tower nodes). The API provided from the GraphHopper project has been used to accomplish tasks as OSM importation, road graph generation and routing between customers. We extended this time-invariant graph representation by assigning a traffic profile only to time-dependent arcs. In particular, traffic data were obtained through a two step procedure. Firstly, given the geographic coordinates of two points at a specific zoom level, we defined a bounding box around the reference Earth area. Therefore, at the start of every time slot \(h\) we captured a snapshot of the current map viewport augmented with the real-time traffic layer. Next, for each arc \((i,j)\) belonging in the bounding box we subdivided its geometry in uniform length segments. We denoted the set of all segments endpoints for arc \((i,j)\) by \(S_{ij}\). For each point \(s\in S_{ij}\) we projected the geographic coordinates over a pixel \(s^{\prime}\) of the image plane (Figure 1). We used the Haversine formula to measure Earth distances. For each period \(h\) the pixel \(s^{\prime}\) can assume a different color in the corresponding \(h\)-th snapshot. The color is classified using the CIEDE2000 color distance [40] from some reference color with a preassigned traffic jam factor as showed in Table 1.  
\begin{table}
\begin{tabular}{c c c c c} \hline \hline
**Ref. Color** & **Color Name** & **Jam\({}_{1}\)** & **Jam\({}_{2}\)** & **Description** \\ \hline
**\#84 CA50** & green & 1.0 & 1.0 & high speed \\ \hline
**\#F07D02** & orange & 0.7 & 0.3 & medium speed \\ \hline
**\#16.00** & red & 0.5 & 0.2 & low speed \\ \hline
**\#16.01** & brown & 0.3 & 0.1 & very low speed \\ \hline
**\#EBE8 DE** & gray & – & – & background \\ \hline
**\#FFFF** & white & 1.0 & 1.0 & freeflow \\ \hline \hline \end{tabular}
\end{table}
Table 1: Color map used to extract travel times.  
If \(s^{\prime}\) did not belong to a street, we started a neighborhood exploration procedure in order to identify the nearest valid color. This task is executed to repair small alignment errors between the osm map and the traffic layer image. After classification, the traffic jam factor of arc \((i,j)\) was computed as the mean of the jam factors associated to each geographical point \(s\in S_{ij}\). An arc was deemed to be time-dependent if it had at least one traffic jam factor strictly lower than \(1\) in the time horizon.