Fuzzy Maximum Capacity Path Problem and Its Application to Optimal Routing Control

The maximum capacity path problem (MCPP) is a classical combinatorial optimizationproblem that seeks to find a path with the maximum capacity in a network. Inthis paper, we consider a fuzzy extension of the MCPP, where the capacities are givenas arbitrary fuzzy numbers. Unlike previous approaches that rely on ranking functionsor specific orderings, we formulate the fuzzy MCPP as a bi-objective path-findingproblem, where one objective is to maximize the nominal capacity and the other is tooptimize the reliability value of the path. We propose an efficient algorithm that canfind a Pareto optimal path for any aggregation function between the two objectives.We also analyze the special case where the network is acyclic and show that the algorithmcan be specialized to run in strongly polynomial time. Furthermore, we presentan application of the fuzzy MCPP to the field of optimal control, where we use a discretizationalgorithm to transform a continuous routing problem into a discrete one andsolve it using the proposed algorithm as a subroutine. To implement this applicationin practice, we run the algorithm on an old real-world project in Iran called Iranrud.Moreover, we report some computational results on grid networks with different sizesthat illustrate the performance of the proposed algorithm.

Fuzzy Maximum Capacity Path Problem and Its Application to Optimal Routing Control Keywords:

Routing , Maximum capacity path , Fuzzy capacity , Optimal control , Iranrud project