OPTIMAL ROUTING WITH CAPACITY, RELIABILITY AND COST CONSTRAINTS

Abstract

This paper considers a graph G in a network in which each arc (i,j) is weighted with a vector (k_ij, p_ij, c_ij) where k_ij is the capacity of arc (i,j), p_i,j is its reliability and c_i,j is the cost associated with traversing the arc (i,j). The problem is to find the route from source to sink with maximum capacity, within a threshold reliability R and at a total cost of no more than C. This problem has a particular type of Pareto optimal solution and is distinct from the problem discussed by Sancho5 in which all Pareto optimal solutions are found. In theory, many Pareto optimal solutions can exist; hence the need for finding a method in which the particular optimal solution can be found. The application of transporting hazardous material is an example of this particular problem.

KEY WORDS:

• Capacity
• reliability
• cost
• dynamic programming
• networks.