Optimal paths in bi-attribute networks with fractional cost functions |
| |
Authors: | HM Soroush |
| |
Institution: | aDepartment of Statistics and Operations Research, College of Science, Kuwait University, P.O. Box 5969, Safat 13060, Kuwait |
| |
Abstract: | An important routing problem is to determine an optimal path through a multi-attribute network which minimizes a cost function of path attributes. In this paper, we study an optimal path problem in a bi-attribute network where the cost function for path evaluation is fractional. The problem can be equivalently formulated as the “bi-attribute rational path problem” which is known to be NP-complete. We develop an exact approach to find an optimal simple path through the network when arc attributes are non-negative. The approach uses some path preference structures and elimination techniques to discard, from further consideration, those (partial) paths that cannot be parts of an optimal path. Our extensive computational results demonstrate that the proposed method can find optimal paths for large networks in very attractive times. |
| |
Keywords: | Routing Optimal path Networks Fractional/rational functions |
本文献已被 ScienceDirect 等数据库收录! |
|