Can we optimize locations of hospitals by minimizing the number of patients at risk?

BACKGROUND: To reduce risk of death in acute ST-segment elevation myocardial infraction (STEMI), patients must reach a percutaneous coronary intervention (PCI) within 120 min from the start of symptoms. Current hospital locations represent choices made long since and may not provide the best possibilities for optimal care of STEMI patients. Open questions are: (1) how the hospital locations could be better optimized to reduce the number of patients residing over 90 min from PCI capable hospitals, and (2) how this would affect other factors like average travel time. METHODS: We formulated the research question as a facility optimization problem, which was solved by clustering method using road network and efficient travel time estimation based on overhead graph. The method was implemented as an interactive web tool and tested using nationwide health care register data collected during 2015-2018 in Finland. RESULTS: The results show that the number of patients at risk for not receiving optimal care could theoretically be reduced significantly from 5 to 1%. However, this would be achieved at the cost of increasing average travel time from 35 to 49 min. By minimizing average travel time, the clustering would result in better locations leading to a slight decrease in travel time (34 min) with only 3% patients at risk. CONCLUSIONS: The results showed that minimizing the number of patients at risk alone can significantly improve this single factor but, at the same time, increase the average burden of others. A more appropriate optimization should consider more factors. We also note that the hospitals serve also for other operators than STEMI patients. Although optimization of the entire health care system is a very complex optimization problems goal, it should be the aim of future research.

Solving the Large-Scale TSP Problem in 1 h: Santa Claus Challenge 2020.

The scalability of traveling salesperson problem (TSP) algorithms for handling large-scale problem instances has been an open problem for a long time. We arranged a so-called Santa Claus challenge and invited people to submit their algorithms to solve a TSP problem instance that is larger than 1 M nodes given only 1 h of computing time. In this article, we analyze the results and show which design choices are decisive in providing the best solution to the problem with the given constraints. There were three valid submissions, all based on local search, including k-opt up to k = 5. The most important design choice turned out to be the localization of the operator using a neighborhood graph. The divide-and-merge strategy suffers a 2% loss of quality. However, via parallelization, the result can be obtained within less than 2 min, which can make a key difference in real-life applications.

Planning Your Route: Where to Start?

Tour planning is an important part of location-based applications. A tour planner provides an optimized path through places of interests (targets) by minimizing the tour length or by applying some other constraints. It is usually formulated as a travelling salesman problem (TSP) or vehicle routing problem (VRP). In the present study, we focus on how to choose the best starting location in case of an open-loop TSP. We consider three different strategies for selecting the starting location and compare their effectiveness with regard to optimizing tour length. If all targets are visible, most humans tend to start on the convex hull or from the furthest point. However, there are also cases where not all targets are visible beforehand, and the only information given is the bounding box. An optimum tour then typically starts from the corner or the shorter side of the box. Humans also have a strong preference to start from a corner. A good strategy can result in the shortest tour, while a bad strategy can even add 20% to the total tour length.