AN EFFICIENT ALGORITHM FOR THE PARETO-SOLUTION OF A MULTI-OBJECTIVE NETWORK WITH SHORTEST PATH PROBLEM AND COMFORTABLE COST
The simple shortest path problem is a well-known optimization problem, which is the problem of finding the shortest path connecting the two specific nodes of a directed or undirected graph. When considering not only the distances between the nodes but also other than the information, for example, toll, fuel cost or longitudinal level, the problem is formulated as a multi-objective shortest path problem that involves multiple conflicting objective functions. To solve the multi-objective single source shortest path problem is difficult because the multiple objectives have to be simultaneously optimized. Thus, few algorithms for this problem have been proposed yet. In this study, we consider two-objective shortest path problem, where the conception of comfortable driving are introduced, and propose 3 efficient algorithms for Pareto-solutions, based on “extended Dijkstras algorithm. One algorithm finds out all Pareto-solutions and the other two algorithms find out almost Pareto-solutions. From the results of the numerical experiments, we see proposed algorithm is efficient for the calculation of Pareto-solutions for the two-objective shortest path problem.
Multi-objective singlesource shortest path problem Eztended Dijkstras algorithm Navigation system
Tomoaki Akiba Hideki Nagatsuka Tomonori Egashira Sayuri Iwakami Hisashi Yamamoto
Information Management Engineering, Yamagata College of Industry and Technology, 2-2-1 Matsuei, Yama Faculty of System Design, Tokyo Metropolitan University, 6-6 Asahigaoka, Hino, Tokyo, Japan
国际会议
上海
英文
1-5
2009-08-02（万方平台首次上网日期，不代表论文的发表时间）