Estimation of Travel Cost between Geographic Coordinates Using Artificial Neural Network: Potential Application in Vehicle Routing Problems

Abstract

The vehicle routing problem (VRP) attempts to find optimal (minimum length) routes for a set of vehicles visiting a set of locations. Solving a VRP calls for a cost matrix between locations. The size of the matrix grows quadratically with an increasing number of locations, restricting large-sized VRPs from being solved in a reasonable amount of time. The time needed to obtain a cost matrix is expensive when routing engines are used, which solve shortest path problems in the back end. In fact, details on the shortest path are redundant; only distance or time values are necessary for VRPs. In this study, an artificial neural network (ANN) that receives two geo-coordinates as input and provides estimated cost (distance and time) as output is trained. The trained ANN model was able to estimate with a mean absolute percentage error of 7.68%, surpassing the quality of 13.2% with a simple regression model on Euclidean distance. The possibility of using a trained model in VRPs is examined with different implementation scenarios. The experimental results with VRPs confirm that using ANN estimation instead of Euclidean distance produces a better solution, which is verified to be statistically significant. The results also suggest that an ANN can be a better choice than routing engines when the trade-off between response time and solution quality is considered.

Keywords

• travel time prediction
• travel cost estimation
• artificial neural network
• vehicle routing problem