A data-thrifty approach to routing optimization

A data-thrifty approach to routing optimization

Abstract: Solving a routing optimisation problem often requires to know the travel times between each pair of points of the problem. Usually, when solving a routing optimisation problem, the travel time is assumed to be constant.
However, in real life problems, it can vary a lot due to traffic jams, especially near big cities. Some map data providers can provide accurate travel time estimations, but the data are expensive and querying such a data provider is time consuming. In this paper, we present a method to solve the Pickup and Delivery Problem with Time Windows (PDPTW) that reduces the number of calls to paid data providers while preserving the quality of the solution.

Keywords: Local Search, PDPTW, data, routing optimization, OscaR.cbls