Conference Agenda

A well-structured patient transportation service in hospitals is not only crucial for meeting patients’ appointments in time but could also help a hospital to reduce overtime as well as idle time in costly areas. In this work, the “patient transportation problem” is modelled as a Multiple Travelling Salesperson Problem with Time Windows. By assigning a node to every transportation request, time windows referring to the associated medical appointment can be incorporated, whereas the salespersons represent the staff of the hospital’s inner clinical transportation service. In order to improve the staff’s well-being, the objective is to balance the workload of these employees. Due to complexity reasons, two different column generation approaches in combination with a greedy heuristic are used to create upper and lower bounds, which are compared in a computational study. The column generation algorithms differ in the subproblem and its solution process: In the first approach, the subproblem is an Elementary Shortest Path Problem with Time Windows, which is solved using a standard solver. In the second approach, the relaxed version of the subproblem, the Shortest Path Problem with Time Windows (SPPTW), is solved using a labelling algorithm, but the tours are made elementary afterwards. Real world data of about one year is provided by the University Hospital Augsburg. First results for randomly picked real-world transportation requests show a clearly superior runtime of the column generation algorithm that solves the SPPTW as a subproblem and a good performance of the greedy heuristic.

Due to the ever-growing demand for home healthcare (HHC) services, optimizing the routing and scheduling decisions in HHC is crucial to efficiently utilize the limited resources and deliver high-quality care to patients. One of the biggest challenges in HHC is the shortage of healthcare personnel, especially during periods when traditional healthcare institutions are overloaded (i.e., COVID-19) and more people try to avoid going to hospitals and prefer to get treatment at home. In this study, we investigate the effect of different limits on health care personnel availability on small instances adapted from the literature with various scenarios by solving these instances optimally. The trade-off between decreasing the number of personnel and the corresponding increase in the traveled distance is explored. Moreover, we generate larger instances and analyze the coverage percentage of patients with varying available staffing capacities.

Emergency medical service (EMS) has to respond quickly and efficiently to all emergencies within a considered area. However, especially in areas with heterogeneous demand distribution like urban, mixed and rural areas, the level of coverage can vary widely. To reduce inequalities in coverage, many approaches take into account fairness as model objective by explicitly addressing the coverage of the worst-covered area. Thereby, the coverage levels of the second, third etc. worst-covered areas are not directly addressed.

Therefore, we propose to maximize the average expected coverage of the set p of worst covered areas. Our fairness objective explicitly considers the second, third etc. worst-covered area and aims to improve not only the coverage level of the worst-covered area, but the average coverage level of the set p of worst-covered areas. We combine our novel fairness objective with expected coverage to a bi-objective optimization model using the epsilon constraint method. In that way, we aim at maintaining an acceptable level of overall coverage. Our model’s applicability is analyzed at hand of a real-world case study for the city of Duisburg (Germany). We examine different levels of overall coverage to analyze the influence on the individual coverage levels of the different areas. First results show that the proposed fairness model can improve the average coverage of the set p of worst-covered areas without giving up too much efficiency.