017079 Sastry V N;Janakiraman T N;Mohideen S I (Inst of Development and Res in Banking Technol (IDRBT), , Road No.1, Castle Hills, Masab Tank, Hyderabad-500 057) : New Algorithms for multi objective shortest path problem. Opsearch 2003, 40(4), 278-98.
In recent years there has been an increase in research activity on multi-objective network optimization problems. Network optimization models can be obtained from a large number of application domains such as transportation systems, communication systems, pipeline distribution systems, pipeline distribution systems, fluid flow systems and neural decision systems. The primary aim of these network models is to optimize the performance with respect to predefined objectives. Multiple objectives such as optimization of cost, time, distance delay, risk, reliability, quality of service and environment impact etc. may arise in such problems. Many real life application, dealing with above networks, require the computation of best or shortst paths from one node to another, called Shortest path Problem (SPP). Three new algorithms for Multiple Objective Shortest Path Problem (MOSPP) and algorithm to detect negatice cycle in a network are proposed. MOSPP in a cyclic and acyclic network having weights either positive or negative or both can be solved using the proposed algorithms. Maximum number of Pareto optimal paths of a MOSPP in a network, is very much useful in finding the maximum number of iterations and the complexity of a particular algorithm. It has been proved that the maximum number of Pareto optimal paths of any MOSPP in a completely connected network, in the worst case isn is 1+(n-2)+(n-2)(n-3)+....+(n-2)!+(n-2)! and it lies between 2[n-2)!] and 3[(n-2)!]. The computational complexities of the proposed algorithms have been analyzed. all proposed algorithms are illustrated with examples of cyclic and acyclic network.
12 ref
