Path problems in networks with vector-valued edge weights

✍ Scribed by Tayi, Giri K.; Rosenkrantz, Daniel J.; Ravi, S. S.

• Publisher: John Wiley and Sons
• Year: 1999
• Tongue: English
• Weight: 214 KB
• Volume: 34
• Category: Article
• ISSN: 0028-3045
• DOI: 10.1002/(sici)1097-0037(199908)34:1<19::aid-net3>3.0.co;2-6

✦ Synopsis

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.