On λ-Cent-Dians and Generalized-Center for Network Design: Formulations and Algorithms

Abstract

In this paper, we study the $\lambda$-centdian problem in the domain of Network Design. The focus is on designing a sub-network within a given underlying network while adhering to a budget constraint. This sub-network is intended to efficiently serve a collection of origin/destination demand pairs. We extend the work presented in \cite{bucarey2024on}, providing an algorithmic perspective on the generalized $\lambda$-centdian problem. In particular, we provide a mathematical formulation for $\lambda \ge 0$ and discuss the bilevel structure of this problem for $\lambda >1$. Furthermore, we describe a procedure to obtain a complete parametrization of the Pareto-optimality set based on solving two mixed integer linear formulations by introducing the concept of maximum $\lambda$-cent-dian. We evaluate the quality of the different solution concepts using some inequality measures. Finally, for $\lambda \in [0,1]$, we study the implementation of a Benders decomposition method to solve it at scale.