The Steiner Bi-objective Shortest Path Problem

Abstract In this paper, we introduce the Steiner Bi-objective Shortest Path Problem. This problem is defined on a directed graph G = ( V , A ) , with a subset T ⊂ V of terminals. Arcs are labeled with travel time and cost. The goal is to find a complete set of efficient paths between every pair of nodes in T . The motivation behind this problem stems from data preprocessing for vehicle routing problems. We propose a solution method based on a labeling approach with a multi-objective A* search strategy guiding the search towards the terminals. Computational results based on instances generated from real road networks show the efficiency of the proposed algorithm compared to state-of-art approaches.