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 |
August 5-7, 2013 - Honolulu, Hawaii, U.S.A. |