Path problems in networks with vector-valued edge weights

Path problems in networks with vector-valued edge weights

0.00 Avg rating0 Votes
Article ID: iaor20022494
Country: United States
Volume: 34
Issue: 1
Start Page Number: 19
End Page Number: 35
Publication Date: Aug 1999
Journal: Networks
Authors: , ,
Abstract:

We consider path problems in networks where each edge is associated with a vector of weights. One application where such path problems arise is in transporting hazardous materials. In that context, the network is embedded in a cluster of communities (or zones), and it is important to consider the impact of an accident along an edge on the surrounding zones. This impact is modeled as a cost vector for each edge, where each component represents the impact of an accident on a zone. Under this model, we formulate two kinds of path problems, namely, routing and feasibility problems. These formulations utilize various definitions of equity with respect to cost impact on the zones. We present complexity results and pseudopolynomial algorithms for general versions as well as efficient algorithms for special cases. We also carry out a comparative analysis of different routing problems.

Reviews

Required fields are marked *. Your email address will not be published.