A memetic algorithm for the patient transportation problem

This paper addresses a real-life public patient transportation problem derived from the Hong Kong Hospital Authority (HKHA), which provides ambulance transportation services for disabled and elderly patients from one location to another. We model the problem as a multi-trip dial-a-ride problem (MTDARP), which requires designing several routes for each ambulance. A route is a sequence of locations, starting and terminating at the depot (hospital), according to which the ambulance picks up clients at the origins and delivers them to the destinations. A route is feasible only if it satisfies a series of side constraints, such as the pair and precedence constraints, capacity limit, ride time, route duration limit and time windows. Owing to the route duration limit, in particular, every ambulance is scheduled to operate several routes during the working period. To prevent the spread of disease, the interior of the ambulances needs to be disinfected at the depot between two consecutive trips. The primary aim of the problem investigated herein is to service more requests with the given resources, and to minimize the total travel cost for the same number of requests. In this paper, we provide a mathematical formulation for the problem and develop a memetic algorithm with a customized recombination operator. Moreover, the segment-based evaluation method is adapted to examine the moves quickly. The performance of the proposed algorithm is assessed using the real-world data from 2009 and compared with results obtained by solving the mathematical model. In addition, the proposed algorithm is adapted to solve the classic DARP instances, and found to perform well on medium-scale instances.