On $$\lambda $$ λ -cent-dians and generalized-center for network design: formulations and algorithms

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 Bucarey et al. (On $$\lambda $$ λ -cent-dians and generalized-center for network design: definitions and properties, 2024), providing an algorithmic perspective on the generalized $$\lambda $$ λ -centdian problem. In particular, we provide a mathematical formulation for $$\lambda \ge 0$$ λ ≥ 0 and discuss the bilevel structure of this problem for $$\lambda >1$$ λ > 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]$$ λ ∈ [ 0 , 1 ] , we study the implementation of a Benders decomposition method to solve it at scale.