The Median Shortest Path Problem with Latency

The Median Shortest Path Problem (MSPP) is a network design problem, which consists of constructing a simple path, between a predetermined source-destination pair of nodes, such that each node that is not on this path must be assigned to the nearest node on the path. This problem minimizes two conflicting objectives: the cost of path construction and the cost of accessibility to the path. In this paper, latency is incorporated into the MSPP to consider the travel time from the location of each node to the destination node. A mixed integer linear programming formulation for the MSPP with latency (MSPPL) is presented and valid inequalities that improve the lower bound of the linear relaxation are proposed. A branch and cut algorithm is implemented in C++ with Cplex and instances from the literature are used to evaluate and validate the model