Towards an efficient collection and transport of COVID-19 diagnostic specimens using genetic-based algorithms

The speed by which the COVID-19 pandemic spread throughout the world makes the emergency services unprepared to answer all the patients' requests. The Tunisian ministry of health established a protocol planning the sample collection from the patients at their location. A triage score is first assigned to each patient according to the symptoms he is showing, and his health conditions. Then, given the limited number of the available ambulances in each area, the location of the patients and the capacity of the nearby hospitals for receiving the testing samples, an ambulance scheduling and routing plan needs to be established so that specimens can be transferred to hospitals in short time. In this paper, we propose to model this problem as a Multi-Origin-Destination Team Orienteering Problem (MODTOP). The objective is to find the optimal one day tour plan for the available ambulances that maximizes the collected scores of visited patients while respecting duration and capacity constraints. To solve this NP-hard problem, two highly effective approaches are proposed which are Hybrid Genetic Algorithm (HGA) and Memetic Algorithm (MA). The HGA combines (i) a k-means construction method for initial population generation and (ii) a one point crossover operator for solution recombination. The MA is an improvement of HGA that integrates an effective local search based on three different neighborhood structures. Computational experiments, supported by a statistical analysis on benchmark data sets, illustrate the efficiency of the proposed approaches. HGA and MA reached the best known solutions in 54.7% and 73.5% of instances, respectively. Likewise, MA reached a relative error of 0.0675% and performed better than four existing approaches. Real-case instances derived from the city of Tunis were also solved and compared with the results of an exact solver Cplex to validate the effectiveness of our algorithm.