Scheme to Find k Disjoint Paths in Multi-Cost

This paper proposes a scheme to find k disjoint paths in multi-cost networks. This scheme, called the k-penalty scheme with initial arc cost matrix (KPI), penalizes the use of conflicting arcs found in previously set paths and increases the costs of these arcs in accordance with the initially given arc cost matrix. Simulations show that the KPI scheme is able to find k disjoint paths faster than the conventional scheme that uses the incrementally updated auxiliary arc cost matrix to increases the cost of conflicting arcs. Moreover, the KPI scheme yields k disjoint paths with lower total cost than the conventional scheme.