Solving a home-care districting problem in an urban setting

This article describes a districting study undertaken for the Côte-des-Neiges community health clinic in Montreal. A territory must be partitioned into six districts by suitably grouping territorial basic units. Five districting criteria must be respected: indivisibility of basic units, respect for borough boundaries, connectivity, visiting personnel mobility, and workload equilibrium. The last two criteria are combined into a single objective function and the problem was solved by means of a tabu search technique that iteratively moves a basic unit to an adjacent district or swaps two basic units between adjacent districts. The problem was solved and the clinic management confirmed its satisfaction after a 2 year implementation period.