Pickup and Delivery Service with Manpower Planning in Hong Kong Public Hospitals

This paper deals with a real-life healthcare problem derived from the Non-Emergency Ambulance Transfer Service for Hong Kong public hospitals which provides transportation services for disabled or elderly patients between their residences and clinics. The problem is modeled as a multitrip pickup and delivery problem with time windows and manpower planning (MTPDPTW-MP) that not only needs to design and schedule ambulance routes satisfying a series of constraints but also requires staff scheduling. Because of the strict limits on route duration, each ambulance traverses several routes per day, which, starting and terminating at the depot, complete a series of pickup and delivery operations to serve the clients. A feasible route demands a driver and several assistants to serve the clients and needs to satisfy some constraints, such as capacity, pickup before delivery, time windows, etc. The objective is hierarchical in that it primarily serves as many clients as possible, then minimizes the operational cost, and finally strikes a balance for the staff workload. Theoretically, MTPDPTW-MP, which is a combination of two well known NP-hard problems (i.e., the pickup and delivery problem with time windows and the staff scheduling problem), is difficult to solve. In this study, we propose an iterated local search metaheuristic that uses a variable neighborhood descent procedure in the local search phase. We use a modified regret insertion method to construct solutions; a heuristic backtracking algorithm is designed to schedule staff. To speed up the process, we adapt the segment-based evaluation for moves and reduce the neighborhoods explored based on the characteristics of the problem. The effectiveness of the proposed algorithm was tested in real-world instances. Results showed that it can serve more requests than the manually designed plans. In addition, the performance of the proposed algorithm was evaluated on a simplified problem: the multitrip vehicle routing problem with time windows.