Vehicle Routing Problem with Steep Roads

Most routing decisions assume that the world is flat meaning that routing costs are modelled as a weighted sum of total distance and time spend by delivery vehicles. However, this assumption does not apply for urban logistics operations in cities with significant altitude differences. We fill a space in the VRP literature and model routing decisions including the impact of road grades in a fuel consumption cost model. A cost-efficient routing model over these geographies requires to distinguish different vehicle cargo levels and road grades in arc costs. To do so, we formulate the Vehicle Routing Problem in regions with steep roads (VRP-SR) as an integer linear program and implement a heuristic solution for this problem. In simulated experiments based on the geography of a real city, we estimate the potentialcost benefits obtained by our solution compared to a benchmark assuming a flat geography. Our results suggest that we may reduce costs up to 13% for the city of Valparaiso, Chile. In addition, we obtain valuable managerial insights from our routing plans. We built routes that initially cluster customers with small altitudes differences to avoid abrupt altitude changes between consecutive customer visits with a loaded vehicle; our solutions may produce higher altitude changes between consecutive customers after the vehicle drops of a considerable amount of weight. We also notice situations in which it is cost-efficient to split a route into multiple routes; this may occur even if a single route can visit all customers to drop weight in between routes and climb hills with a lighter vehicle.