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.

Keywords

• A* algorithm
• Multiple destinations
• Vehicle routing with road-network information