Back Optimizing Sample Collection Routes with Iterated Local Search

Optimizing Sample Collection Routes with Iterated Local Search

In this work, we propose a solution to improve the logistics of sample collection at clinical laboratories or other health organizations. The Sample Collection Problem (SCP) aims to find the routes to collect (blood, swab, etc.) samples from different locations and to deliver them to a clinical laboratory for analysis. The objective is to obtain efficient collection routes in terms of time and cost. We applied a state-of-the-art metaheuristic based on an “Iterated Local Search” (ILS) algorithm to solve the Sample Collection Problem. We implemented the ILS algorithm and integrated it in an Excel file to facilitate the application of the algorithm by anyone. The users can see the output solutions in a map associated with each route using Bing Maps.

If you are interested in applying these solution contact any of the researchers above.

02.06.2020

Imatge inicial

 

Optimizing Sample Collection Routes with Iterated Local Search

Pedro Martins

Coimbra Business School - Polytechnic Institute of Coimbra/CMAFcIO - University of Lisbon [email protected]

António Trigo

Coimbra Business School - Polytechnic Institute of Coimbra/Centro ALGORITMI, University of Minho [email protected]

Helena Ramalhinho

Universitat Pompeu Fabra, [email protected]

 

 

Background

One of the main challenges in healthcare systems today is to deliver high-quality services with limited resources. Therefore, optimization problems in healthcare have attracted the attention of many researchers, in particular from the area of Operations Research (OR). In the last years, OR has been applied to many healthcare logistics problems leading to significant improvements in the efficiency of the use of the health resources.

The solution described intends to improve the logistics of sample collection at clinical laboratories or other health organizations. Usually, the samples are collected daily from different collection points, such as extraction points, or health centers, and transported in thermal containers to a core laboratory for testing in the pre-analytical phase. These routes to collect samples for analysis must be designed in a time-efficient manner while satisfying constraints.

 

The Sample Collection Problem

The Sample Collection Problem (SCP) aims to find the routes to collect (blood, swab, etc.) samples from different locations and to deliver them to a clinical laboratory for analysis. This problem is a particular version of the Open Vehicle Problem (OVRP), which is well known in the OR area. The problem consists in defining the best routes that start at a collection point and finish at the laboratory (final destination). Due to restrictions on the vehicles’ capacity and total travel time by routes (for example 2 hours per route) there can exists more than one route.  The objective is to minimize the total traveling time (or logistics cost) while satisfying the following constraints: (i) a time windows between the first collection and delivery to the laboratory, and (ii) vehicle capacity.

 

Algorithmic Approach

We applied a state-of-the-art metaheuristic based on an “Iterated Local Search” (ILS) algorithm to solve the Sample Collection Problem. The ILS is one of the most applied and efficient algorithmic approach to solve large scale and complex optimization problems. Well known business companies are using this technique to optimize their last mile and routing logistics problems. We implemented the ILS algorithm and integrated it in an Excel file to facilitate the application of the algorithm by anyone.

 

How to use the Excel File OVRP-ILS

The user must facilitate all collection points’ addresses (or geographical coordinates) and the address of the laboratory (final destination). The researchers will generate the travel times among these locations, and afterwards prepare the excel file.

Each time a user wants to generate the routes, he or she must enter: capacity of the vehicles (for example in thermal containers); time limit of each route (in minutes); Activate if the collection point must be visited; The number of containers to be collected; The collection time of the driver at each collection point.

After the algorithm can be run to obtain collection routes that specify the collection sequence for each vehicle. The solution will appear in the Results Sheet indicating: driving time, time at clients; and the details routes, indicating the order of visiting the collection points

Finally, the users can see the map associated with each route in the maps button and it will be visualized in Bing Maps.

 

Previous works of the authors related with this topic:

Grasas A., Ramalhinho H., Pessoa L.S., Resende M.G.C., Caballé I. and Barba N. (2014) On the Improvement of Blood Sample Collection at Clinical Laboratories, BMC Health Services Research, 14:12 DOI:10.1186/1472-6963-14-12. Open access article.

Bastos B., Heleno T., Trigo A. and Martins P. (2019) Web Based Application for Home Care Visits’ Optimization of Health Professionals’ Teams of Health Centers, working paper.

Multimedia

Categories:

SDG - Sustainable Development Goals:

Els ODS a la UPF

Contact