THE SHORTEST-PATH PROBLEM WITH 2 OBJECTIVE FUNCTIONS

被引:60
作者
HENIG, MI
机构
[1] Tel-Aviv Univ, Tel-Aviv, Isr, Tel-Aviv Univ, Tel-Aviv, Isr
关键词
DECISION THEORY AND ANALYSIS - MATHEMATICAL PROGRAMMING; DYNAMIC;
D O I
10.1016/0377-2217(86)90092-5
中图分类号
C93 [管理学];
学科分类号
12 ; 1201 ; 1202 ; 120202 ;
摘要
The author presents methods to find the shortest path in a network where each path is associated with two objectives. He describes how to obtain the nondominated paths and the extreme nondominated paths, and compares the expected complexity of the methods. An improvement in efficiency can be obtained when quasiconcave or quasiconvex utility functions are assumed. In the first case, the author describes how to find the optimalextreme nondominated path and bounds for the optimal path value. Then the optimal path can be located by calculating the k-th shortest path. In the second case he suggests a branch and bound method to solve the problem.
引用
收藏
页码:281 / 291
页数:11
相关论文
共 20 条
[1]  
Bazaraa MS, 1979, NONLINEAR PROGRAMMIN
[2]  
Bellman R., 1957, DYNAMIC PROGRAMMING
[3]   DYNAMIC PROGRAMMING IN MULTIPLICATIVE LATTICES [J].
BROWN, TA ;
STRAUCH, RE .
JOURNAL OF MATHEMATICAL ANALYSIS AND APPLICATIONS, 1965, 12 (02) :364-&
[4]  
CLIMACO JCN, 1982, EUR J OPER RES, V11, P399, DOI 10.1016/0377-2217(82)90205-3
[5]   NOTE ON MULTIPLE OBJECTIVE DYNAMIC-PROGRAMMING [J].
DAELLENBACH, HG ;
DEKLUYVER, CA .
JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 1980, 31 (07) :591-594
[6]  
Debreu G., 1959, THEORY VALUE AXIOMAT
[7]  
DENARDO E, 1980, DYNAMIC PROGRAMMING
[8]  
Fishburn P.C., 1970, UTILITY THEORY DECIS
[9]   A DUAL ALGORITHM FOR THE CONSTRAINED SHORTEST-PATH PROBLEM [J].
HANDLER, GY ;
ZANG, I .
NETWORKS, 1980, 10 (04) :293-310
[10]  
Hansen Pierre, 1980, MULTIPLE CRITERIA DE, P109