The balanced p-median problem with unitary demand

We consider a bi-objective variant of the -median problem where facilities must be located to serve a set of customers with unitary demand. The considered objectives are: minimizing the average traveled distance between customers and facilities, and balancing the number of allocated customers per facility. We denote the latter by customer allocation inequity and measure it as the mean absolute deviation of the number of customers assigned to each median. We formulate this new problem as a bi-objective mixed-integer linear program ,and use a weighted sum method to generate a representative set of Pareto optimal solutions. Considering the single-objective subproblem solved by the weighted sum method, we develop a primal–dual algorithm that handles large-scale instances by combining a Lagrangian relaxation heuristic within a variable neighborhood search metaheuristic. This algorithm relies on the solution of a tailored minimum cost flow problem for the case where the locations of the facilities are known. We evaluate the proposed formulation and algorithm on test instances from the literature. After demonstrating the effectiveness of the developed algorithm, we test it on a series of large instances derived from an industrial application of districting for last-mile delivery. We analyze the trade-off between the assignment cost and customer allocation inequity, and evaluate the quality of the solutions by comparing them with those attained through alternative inequity measures.