An Iterated Greedy Algorithm with Variable Neighborhood Descent for the Planning of Specialized Diagnostic Services in a Segmented Healthcare System

Abstract: In this paper, a problem arising in the planning of specialized diagnostic services in a segmented public healthcare system is addressed. The problem consists of deciding which hospitals will provide the service and their capacity levels, the allocation of demand in each institution, and the reallocation of uncovered demand to other institutions or private providers, while minimizing the total equivalent annual cost of investment and operating cost required to satisfy all the demand. An associated mixed-integer linear programming model can be solved by conventional branch and bound for relatively small instances; however, for larger instances the problem becomes intractable. To eectively address larger instances, a hybrid metaheuristic framework combining iterated greedy and variable neighborhood descent components for this problem is proposed. Two greedy construction heuristics are developed, one starting with an infeasible solution and iteratively adding capacity and the other starting with a feasible, but expensive, solution and iteratively decrease capacity. The iterated greedy algorithm includes destruction and reconstruction procedures. Four dierent neighborhood structures are designed and tested within a VND procedure. In addition, the computation of local search components benet from an intelligent exploitation of problem structure since, when the rst-level location variables (hospital location and capacity) are xed, the remaining subproblem can be solved e diagnostic servciently as it is very close to a transshipment problem. All components and dierent strategies were empirically assessed both individually and within the IGA-VND framework. The resulting metaheuristic is able to obtain near optimal solutions, within 3% of optimality, when tested over a data base of 60- to 300-hospital instances.