The collect-and-process vehicle routing problem with completion time minimization: An application in home healthcare
针对居家医疗中血液样本收集与实验室处理流程，提出一种车辆路径与调度方案，最小化样本平均完成时间，并开发了多邻域局部搜索元启发式算法。
Home healthcare (or simply homecare) refers to providing medical services to individuals in their homes rather than in a hospital or in outpatient clinics. This system is convenient for the public authorities, which reduces the operational costs of medical facilities, is beneficial for the environment because it prevents patients from going to a hospital, and is comfortable for patients who can receive medical assistance without leaving their houses. In this work, we deal with clinical exams such as blood sampling, which requires collecting a sample from the patient and delivering it to a laboratory where it must be processed and analyzed. Currently, healthcare professionals collect all the samples and then deliver them to the labs at the end of the day. This results in an inefficiency in the processing system, in which labs are overloaded in the late afternoon and are not working during the first part of the day. To better balance lab workload and provide timely results to the patients, we introduce the Collect-and-Process Vehicle Routing Problem with Completion Time minimization, in which each lab has a maximum processing capacity for each time slot, and samples exceeding this capacity are postponed to the next slot. The goal is to provide a routing and scheduling plan that minimizes a sample’s average completion time. We provide a formulation of the problem and a fast procedure to compute tight lower bounds. To efficiently and effectively handle large-sized instances, we develop a multi-neighborhood local search matheuristic. Results show the high-quality performance of the proposed method. Insights indicate that it is more convenient to visit labs at the end of the time slot than to visit them at the beginning and exploit the residual time to collect further samples. Another insight is that solutions containing well-balanced routes in terms of route duration are preferable with respect to unbalanced ones.