Pareto optimal solutions providing optimal routes between every two different nodes in the cost-time trade-off routing network without the objectives being prioritized

Research paper by Satya Prakash, Anuj Gupta, Richa Garg, Bhuvnesh Tanwar, Deepika Kaushik, Sourabh Aggarwal

Indexed on: 12 May '16Published on: 10 May '16Published in: OPSEARCH

Discover, organise and share research that matters to you

Join Sparrho today to stay on top of science

Discover, organise and share research that matters to you

Abstract

A cost-time trade-off routing network problem is considered. In the network, each arc is associated with an ordered pair whose first component is the cost and the second component is the time of direct travel between two adjacent nodes. The cost-time trade-off routing network problem has two objectives without being prioritized. The objectives are to minimize the total cost and total time of travel between every two different nodes in the network. It is required to find all the Pareto optimal routes between every two different nodes in the network. An algorithm is developed for finding the set of Pareto optimal solutions providing all the optimal routes between every two different nodes in the network. The new algorithm extends Floyd’s algorithm, presently applicable only for solving the single-objective routing network problem, to solve the cost-time trade-off routing network problem, incorporating the concept of lexicographically lesser between two ordered pairs. The problem is solved in two phases. In the first phase, the cost-time trade-off routing network problem is represented by a square matrix whose rows and columns are equal to the number of nodes and whose entries are ordered pairs associated with the arcs in the network. In the second phase, the set of Pareto optimal solutions of the cost-time trade-off routing network problem is obtained through solving a sequence of prioritized bicriterion problems. The new algorithm is explained and is illustrated through solving a numerical example. Utility of the work is also indicated.