Metaheuristic Algorithms for Transportation Problems in HealthCare

One of the most challenging problems in healthcare systems nowadays is the one of satisfying all the demand while delivering a high-quality service with very limited resources. That is why optimization problems in healthcare have been the subject of many research studies. During recent years transportation problems in particular have gathered a lot of attention. Healthcare transportation problems can be divided in two main groups, patient transportation and the transportation of goods, such as biological samples. Patient transportation is an important issue in healthcare systems, both for emergency and non-emergency transportation. Non-emergency transportations contain for example, the transfer of patients between hospitals, the transportation between patients’ homes and medical structures and the transportation to nursing homes and rehabilitation centers. The complexity of the above mentioned problems, the many user related constraints and the limited resources make these types of problems very challenging. That is why OR and in particular optimization algorithms have become a useful tool to solve these problems. Pickup and delivery problems (PDP) are a variant of vehicle routing problems (VRP), where a number of loads have to be transported from pickup locations to delivery locations with the aim of finding a routing for a fleet of available vehicles that minimizes the overall routing cost. Each available vehicle has a given capacity and is located in a depot, where it has to return at the end of the service. Each request is characterized by the size of the load and by the location where it has to be picked up (pickup location) and the location where it has to be dropped off (delivery location). Dial-a-ride problem (DARP) is a generalization of the Pickup and Delivery Problem with Time Windows (PDPTW). In DARP, people are transported instead of goods and consequently issues on the quality of the provided service and timing must be carefully taken into account (through additional constraints or by extra terms in the objective function). In this thesis different metaheuristic algorithms are proposed to solve transportation problems in healthcare. Two real-life transportation problems are presented one focusing on the on-demand patient transportation and the other focused on the collection and transportation of biological samples. The thesis tackles the unforeseen constraints that arise when adapting pickup and delivery (PDP) problems to real scenarios. These unforeseen constraints include the user’s preferences, complex cost functions, user’s quality service for the patient transportation problem and the possibility of transfers for the biological sample transportation problem. The first addressed problem is a multi-depot dial-a-ride problem arising from a real-world healthcare application, concerning the non-emergency transportation of patients in the Italian region of Tuscany. Different versions of Variable Neighborhood Search (VNS) algorithms have been created able to tackle all the characteristics of the problem. The computational results obtained by testing the VNS algorithms on literature instances and on random instances taken from a real-life healthcare problem show the effectiveness of the proposed approaches. Finally, the last problem deals with a multi-depot pickup and delivery problem with transfers that arises from a real-world healthcare application, the blood and biological sample transportation in the Metropolitan Area of Bologna, an Italian city. The proposed Adaptive Large Neighborhood Search algorithm is able to tackle all the characteristics of the problem. Computational results on real-life instances show the effectiveness of the proposed approach, in quality of the solution as well as in the distribution of the vehicles to the hospital, compared to the current real situation of the HUB, the main hospital of Bologna.