Due to varying traffic volumes and limited traffic infrastructure in urban areas, travel times are uncertain and differ during the day. In this environment, city logistics service providers have to fulfill deliveries in a cost-efficient and reliable manner. To ensure cost-efficient routing while satisfying promised delivery dates, information on the expected travel times between customers needs to be considered appropriately.

Typically, vehicle routing is conducted on an abstract level, relying on direct connections between customers, to determine a desirable sequence of customer visits. These direct connections are usually precomputed using shortest path algorithms. Most approaches merely consider a single (shortest) path, based on a single cost value (e.g., distance or average travel time). When concentrating on travel times, their variation (e.g., due to congestion) is therefore ignored. To incorporate information on travel time variation, it might be of value to consider alternative paths and more sophisticated travel time models such as Interval Travel Times. Exploiting the high connectivity of urban road networks and available travel time information allows for more efficient and reliable routing.

In this work, we investigate the incorporation of alternative paths into city logistics vehicle routing. For this purpose, different approaches for the computation of paths are considered with regard to deterministic and stochastic travel time models. Experiments are conducted within an exemplary city logistics setting. Combinations of different path computation and customer sequencing approaches are evaluated and discussed to investigate the additional value of incorporating more complex travel time models.