Minimum-Cost Strong Network Orientation Problems: Classification, Complexity, and Algorithms

摘要

In the minimum-cost strong network orientation problem (MCSO), we are given an undirected graph G=(V,E) with nonnegative edge lengths e(e) and a transportation schedule T={(s_1,t_1,w_1), ..., (s_k,t_k,w_k)}, where W_i units of weight have to be transported from the soruce vertex S_i to the target vertex t_i for i=1,...,k. Let G~σ be a strongly connected orientation of G and Let L~σ_i be the length of the shortest (directed) path from s_i to t_i in G~σ. The goal in the MCSO is to find a strongly connected orientation G~σ such that the overall cost of the orientation given by ∑~k_i=1 w_iL~ σ_i (sum case) or max_i=1...,k w_iL~σ_i (bottleneck case) is minimized. The strong network orient work orientation problems is motivated by the practical problem of designing the optimal unidirectional flow path of automated guided vehicles. In this paper, we investigate the MCSO from teh algorithmic and complexity points of view and propose a classification scheme. In the first part of the paper, we identify several efficiently solvable cases of the MCSO with sum and bottleneck objective functions which arise if additional restrictions are imposed on the structure of the graph G, the edge lengths e(e), and/or the transportation schedule T. In the second part, we identify special cases of the MCSO which are NP-hard.