Inverse Maximum Capacity Path Problems Under Sum-Type and Max-Type Distances and Their Practical Application to Transportation Networks

Abstract

The maximum capacity path problem is to find a path connecting two given nodes in a network such that the minimum arc capacity on this path is maximized. The inverse maximum capacity path problem (IMCP) is to modify the capacities of the arcs as little as possible so that a given path becomes maximum capacity path in the modified network. Two cases of IMCP are considered: the capacity of the given path is preserved or not. IMCP is studied and solved both, under any sum-type (e.g., weighted $l_{k}$ norms and sum-type Hamming distance) and max-type distance (e.g., weighted $l_{\infty }$ norm or bottleneck Hamming distance). The obtained algorithms for IMCP are applied to solve a real road transportation network optimization problem.

Keywords

• Maximum capacity path
• inverse optimization
• minimum cut
• Hamming distance