Clustering-based iterative heuristic framework for a non-emergency patients transportation problem

Non-emergency patient transportation (NEPT) services are particularly important nowadays due to the aging population and contagious disease outbreaks (e.g., Covid-19 and SARS). In this work, we study a NEPT problem with a case study of patient transportation services in Hong Kong. The purpose of this work is to study the discomfort and inconvenience measures (e.g., waiting time and extra ride time) associated with the transportation of non-emergency patients while optimizing the operational costs and utilization of NEPT ambulances.

A mixed-integer linear programming (MILP) formulation is developed to model the NEPT problem. This MILP model contributes to the existing literature by not only including the patient inconvenience measures in the objective function but also illustrating a better trade-off among different performance measures through its specially customized formulation and real-life characteristics. CPLEX is used to find the optimal solutions for the test instances. To overcome the computational complexity of the problem, a clustering-based iterative heuristic framework is designed to solve problems of practical sizes. The proposed framework distinctively exploits the problem-specific structure of the considered NEPT problem in a novel way to enhance and improve the clustering mechanism by repeatedly updating cluster centers.

The computational experiments on 19 realistic problem instances show the effective execution of the solution method and demonstrate the applicability of our approach. Our heuristic framework observes an optimality gap of less than 5% for all those instances where CPLEX delivered the result. The weighted objective function of the proposed model supports the analysis of different performance measures by setting different preferences for these measures. An extensive sensitivity analysis performed to observe the behavior of the MILP model shows that when operating costs are given a weightage of 0.05 in the objective function, the penalty value for user inconvenience measures is the lowest; when the weightage value for operating costs varies between 0.8 and 1.0, the penalty value for the same measures is the highest.

This research can assist decision-makers in improving service quality by balancing operational costs and patient discomfort during transportation.