An effective greedy method for the Meals-On-Wheels service districting problem

- An integrated mixed-integer programming model for Meals-On-Wheels service districting (MOWSD) problem is proposed.
- An effective greedy heuristic method for solving the MOWSD problem is proposed.
- Proposed MOWSD model and greedy heuristic method are compared and illustrated by a real instance.
- Effects of key parameters of the developed model on performance are analyzed.

This paper focuses on a specific districting problem related to home health care (HHC) services, that is, the Meals-On-Wheels service districting (MOWSD) problem which is formulated as an integrated mixed-integer programming (MIP) model. The MOWSD problem aims at finding the minimum number of districts to cover all basic units while satisfying the constraints, including capacity and time window limitation, accessibility, compactness, and the indivisibility of locations. Inspired from the thought of the planner who has to solve the MOWSD problem in practice, an effective greedy heuristic method is proposed to quickly construct good districts. The results indicate that the greedy heuristic method can achieve as many good solutions as the Gurobi Optimizer, which is applied to solve the MIP, but with an extremely shorter computation time. We firstly conduct the sensitivity analysis on the key parameters of the MOWSD problem, which reveals that the performance is significantly affected by the available time period for the service delivery, the capacity of a meal cart, and the maximum travel duration between any two basic units in a district. We further compare the resulting districts determined using these two methods with the existing districts identified using manual planning. This comparison claims that the proposed greedy heuristic method is capable of not only improving the design of districts but also achieving better compactness than Gurobi Optimizer.