An Approach for the Fast Calculation Method of Pareto Solutions of a Two-Objective Network  
Author Tomoaki Akiba

 

Co-Author(s) Natsumi Takahashi; Shuhei Nomura; Hisashi Yamamoto

 

Abstract The multi-objective network model can be applied to common problems with many conditions. The shortest path problem is an optimization problem for finding the shortest path connecting two specific nodes of a directed or undirected graph. When considering not only the distances between the nodes but also other information, for example, toll, fuel cost, or gradient, the problem is formulated as a multi-objective shortest path problem that involves multiple conflicting objective functions. In this study, we consider shortest path problem for a network with two objective functions. However, solving the optimization problem of two-objective network need to obtain for Pareto-solutions because it is rare case that two objectives become optimized simultaneously. Thus, few algorithms for this problem have been proposed. In this study, we use a two-objective shortest path problem to find the shortest path between two terminal nodes on a network, and we propose efficient algorithms for obtaining the Pareto solutions based on the extended Dijkstra's algorithm, using weighted objective function. The results of the numerical experiments suggest that the proposed algorithms reduce the computing time and the memory size for obtaining the Pareto solutions.

 

Keywords Two-objective network, Shortest path problem, Pareto solutions, Extended Dijkstra's algorithm
   
    Article #:  19193
 
Proceedings of the 19th ISSAT International Conference on Reliability and Quality in Design
August 5-7, 2013 - Honolulu, Hawaii, U.S.A.