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 (CLSP) 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 based on information from shortest paths between customers, to determine the cost-minimal sequence of customer visits. This information is 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). 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 (ITT). In this work, we investigate the incorporation of alternative paths into city logistics vehicle routing. For this purpose, we compare our approach to classical shortest path approaches within a vehicle routing problem. Our approach considers a set of alternative paths and incorporates ITT. Experiments are conducted within an exemplary city logistics setting. Computational results show that the consideration of alternative paths allows to select better paths with regard to a trade-off between efficiency and reliability when travel times are varying. © 2017 The Authors. Published by Elsevier B.V.