Abstract
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, fluid flow systems and neural decision systems. The primary aim of these network models is to optimize the performance with respect to pre defined 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 applications, dealing with above networks, require the computation of best or shortest paths from one node to another, called Shortest Path Problem (SPP). In this paper, three new algorithms for Multiple Objective Shortest Path Problem (MOSPP) and an algorithm to detect negative 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. We prove here, the maximum number of Pareto optimal paths of any MOSPP in a completely connected network, in the worst case, 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.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Bellman, R.E., (1958), “On a Routing Problem”, Quarterly Journal of Applied Mathematics, Vol. 16, pp. 87–90.
Corley, H.W. and Moon, I.D, (1985), “Technical Note: Shortest Path in Networks with Vector Weights”, Journal of Optimization Theory and Applications, 46, 79–86.
Deo, N. and Pang, C., (1984), “Shortest Path Algorithms: Taxonomy and Annotations”, Networks, 14, 275–323.
Dijkstra, E.W., (1959), “A note on two problems in connection with graphs”, Numerische Mathematik, Vol. 1, pp. 269–271.
Dreyfus, S.E., (1969), “An appraisal of some shortest path algorithms”, Operations Research, 17, 395–412.
Ford, L.R., (1956), “Network Flow Theory”, The Rand Corporation, pp. 923.
Hansen, P., (1980), “Bi-criterion Path Problems”, In Lecture Notes in Economics and Mathematical System 177 (Edited by M. Beckmann and H.P. Kunzi), 109–127, Springer, Berlin.
Hwang, C. and Masud, A.S.M., (1979), “Multiple Objective Decision Making — Methods and Applications”, (Springer, Berlin).
Martins, E.Q.V. and Santos, J.L.E., (1999), “The labelling algorithm for the multi objective shortest path problem”, CISUC, 1–24.
Sastry, V.N. and Ismail Mohideen, S., (1999), “A Modified Algorithm to Compute Pareto Optimal Vectors”, Journal of Optimization Theory and Applications, Vol. 103, No. 1, 241–244.
Yen, J.Y., (1970), “An algorithm for finding shortest routes from all source nodes to a given destination in general networks”, Quarterly Journal of Applied Mathematics, 27, 526–530.
Zhan, F.B. and Noon, C.E., (1998), “Shortest Path Algorithm: An Evaluation using Real Road Networks”, Transportation Science, Vol. 32, No. 1, pp. 65–73.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Sastry, V.N., Janakiraman, T.N. & Mohideen, S.I. New Algorithms For Multi Objective Shortest Path Problem. OPSEARCH 40, 278–298 (2003). https://doi.org/10.1007/BF03398701
Published:
Issue Date:
DOI: https://doi.org/10.1007/BF03398701