Exploring the discrete and continuous edge improvement problems: Models and algorithms

Abstract

In this paper, we investigate the edge improvement problem where the fixed edge traversal time assumption of the traditional network flow problems is relaxed. We consider two variants of the problem: one where improvement decisions are restricted to a discrete set (discrete edge improvement problem), and the other where they can take any value within a specified range (continuous edge improvement problem). We first analyze both problem variants on a tree-shaped network and discuss their computational complexities. For the general case, where the underlying network has no special structure, we provide mixed-integer programming (MIP) formulations for both versions of the problem. To the best of our knowledge, this study is the first to propose and compare different formulations for the discrete edge improvement problem and to present a formulation for the continuous edge improvement problem. Since the developed models do not perform well for medium and large problem instances, we introduce a Benders decomposition algorithm to solve the discrete edge improvement problem. Additionally, we employ it heuristically to find high-quality solution for the continuous edge improvement problem within reasonable times. We also devise an MIP formulation to find lower bounds for the continuous edge improvement problem, leveraging the McCormick envelopes and optimal solution properties. Our experiments demonstrate that the Benders decomposition algorithm outperforms the other formulations for the discrete edge improvement problem, while the heuristic method proposed for the continuous edge improvement problem provides quite well results even for large problem instances.