On algorithms for the tricriteria shortest path problem with two bottleneck objective functions

摘要

This paper addresses a tricriteria path problem involving two bottleneck objective functions and a cost. It presents an enhanced method that computes shortest paths in subnetworks, obtained by restricting the set of arcs according to the bottleneck values in order to find the minimal complete set of Pareto-optimal solutions, and taking into account the objective values of the determined shortest paths to reduce the number of considered subnetworks, and thus the number of solved shortest path problems. A labeling procedure for the problem is also developed. The algorithms are compared with the previous literature. Moreover a variant of the first method is presented. Its aim is to choose the solutions with the best bottleneck value when the cost is the same. Results for random instances reveal that the enhanced method is the fastest, and that, in average, it runs in less than 20 s for networks with 30000 nodes, an average degree of 20 and 1000 distinct bottleneck values. Its variant that avoids ties improved the former version up to 15% for costs in [1,10].