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 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 >= 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 is an element of[0,1], we study the implementation of a Benders decomposition method to solve it at scale.