A MapReduce-based approach for shortest path problem in large-scale networks

The cloud computing allows to use virtually infinite resources, and seems to be a new promising opportunity to solve scientific computing problems. The MapReduce parallel programming model is a new framework favoring the design of algorithms for cloud computing. Such framework favors processing of problems across huge datasets using a large number of heterogeneous computers over the web. In this paper, we are interested in evaluating how the MapReduce framework can create an innovative way for solving operational research problems. We proposed a MapReduce-based approach for the shortest path problem in large-scale real-road networks. Such a problem is the cornerstone of any real-world routing problem including the dial-a-ride problem (DARP), the pickup and delivery problem (PDP) and its dynamic variants. Most of efficient methods dedicated to these routing problems have to use the shortest path algorithms to construct the distance matrix between each pair of nodes and it could be a time-consuming task on a large-scale network due to its size. We focus on the design of an efficient MapReduce-based approach since a classical shortest path algorithm is not suitable to accomplish efficiently such task. Our objective is not to guarantee the optimality but to provide high quality solutions in acceptable computational time. The proposed approach consists in partitioning the original graph into a set of subgraphs, then solving the shortest path on each subgraph in a parallel way to obtain a solution for the original graph. An iterative improvement procedure is introduced to improve the solution. It is benchmarked on a graph modeling French road networks extracted from OpenStreetMap. The results of the experiment show that such approach achieves significant gain of computational time.