New polynomial time algorithms to compute a set of Pareto optimal paths for multi-objective shortest path problems

Abstract

Multi-objective shortest path problem (MOSPP) is an active area of research because of its application in a large number of systems such as transportation systems, communication systems, power transmission systems, pipeline distribution systems of water, gas, blood and drainage, neural decision systems, production planning and project planning. In these networks it becomes necessary to find the best path from one node to a specified or all other nodes. The computational complexity of the existing algorithms in the literature to compute all Pareto minimum paths from a specified source node to all other nodes in an MOSPP is of exponential order in the worst case. Instead of generating all the values of the Pareto minimum paths in exponential time, we propose an algorithm to find a set of values of the Pareto minimum paths in polynomial time, which is very significant in many contexts. If an MOSPP of a network is having negative cycle, all the existing algorithm only indicate the existence of the negative cycle, that too after exponential number of operations. However, applying the proposed algorithm, we can find a set of Pareto minimum paths of any MOSPP of a network even if it contains negative cycles. The proposed algorithm is illustrated with examples.

Keywords:

• Networks
• Multiple objectives
• Pareto minimum paths
• k-Shortest paths

Acknowledgements

The authors are grateful to the referee for this present version of the research paper.