Efficient solutions to the home healthcare delivery problem

By Dr. Yasel Costa

With ageing populations, and more patients living with mobility-limiting conditions, the need for delivery of healthcare, including pharmaceuticals and medical equipment, to patients’ homes, is growing rapidly. The good news is that technologies such as aerial drones are making home delivery much more feasible in both congested urban and remote rural areas, and in many trials have reduced service times (and incidentally CO₂ emissions) significantly. The bad news is that planning routes for both drones and ground-based vehicles –in order to provide an efficient and cost-effective service in a context where time is of the essence and requirements can change rapidly– is far from straightforward.

There have been many studies addressing aspects of the problem but, in the view of Behrouz Mohammadi-Kordkheili and Rashed Sahraeian ((Shahed University, Tehran) and this author, such work has been of limited practical utility. We have re-examined the issues, proposing a new supply chain model and a novel computational approach to its resolution.

We see the supply chain as having two (at least) echelons – supply from manufacturers and vendors to local Home Healthcare Centres in (relative) bulk, and from thence the fulfilment of individual patient requirements via ground vehicle or aerial drone delivery rounds. The two echelons are of course intimately linked.

Superficially, this looks very like a retail supply chain with goods flowing from manufacturers or central distribution centres to ‘urban’ or ‘micro’ fulfilment centres for transhipment via a ‘last mile’ delivery mode. The similarities only go so far, however – if a retail e-commerce delivery is late or fails, no-one dies. That is not a given in a healthcare situation.

There is therefore an imperative to create delivery routes that minimise travel time and assure on-time delivery making best use of the resources and finances available. At the same time, since the mix of patients and their requirements is constantly changing, it must be possible to create or revise delivery plans in minutes, not days. Many of the published approaches, particularly those that use ‘classical’ computational techniques, require Central Processing Unit (CPU) durations that are quite unacceptable in the healthcare scenario – if indeed they can find a near-optimal solution at all for a more than trivial number of delivery destinations.

A further shortcoming of many existing studies has been a failure to fully capture some of the constraints which apply, particularly to drone operation. Constraints which we have incorporated and combined in our model include:

• The risk of collision with power lines and the like (bearing in mind that drones are often restricted to low level operation). Potential electromagnetic interference is also a consideration. Avoidance technologies may not function well in bad weather. An assessment of risk, based on the mapped density of power lines, is therefore applied.
• The effects of wind speed – in many jurisdictions there is a bar on drone operation in relatively high winds, and even if they can operate, wind affects the speed of the drone and therefore travel time. (For ground vehicles, traffic congestion has an analogous effect)
• Limitations on fuel or battery capacity (always remembering of course that the vehicle or drone has to be able to return to a refuelling/recharging point)
• Limitations on the carrying capacity of the vehicle or, particularly, drone (especially in built-up areas, the permissible all-up weight of a drone is often restricted).

The model also has to include parameters such as the number of drones/vehicles available and indeed the number of HHCs that could supply the patient. The solution looked for is the lowest achievable value of the ‘objective function’, across the two echelons. This seeks to minimise the cost components associated with fuel/energy consumption, and inventory holding costs. Importantly it also includes a ‘penalty cost’ representing any delays in deliveries to patients.

A realistic model run would see a HHC serving perhaps a dozen patients (nodes) in a given timeframe via a number of delivery rounds each using a drone or ground vehicle as appropriate and taking the most efficient pathway that will reduce service time.

This is of course a complex version of the Travelling Salesman problem, and as usual, for more than a trivial number of nodes it is categorised as NP-hard, which amongst other things means that the amount of computational time required to find a near-optimal solution tends to increase dramatically as the number of nodes increases.

We therefore devised an ‘improved Benders decomposition’ (IMBD) (actually, two – one was better than the other). This approach involves a master problem (MP), which in this case captures the routing, flight/driving conditions, and capacity restriction constraints, while a genetic algorithm runs a subproblem (SP) including constraints related to inventory, service completion times, and delays, feeding into the MP. The process is iterated until the algorithm converges: that is, the difference between a lower bound from the MP and an upper bound from the SP is smaller than a specified value.

Like other solution approaches the Benders method classically can require a large number of iterations to get to the optimal solution. We were able to apply various techniques to improve solution efficiency, for instance by eliminating subtours that may be computationally valid but aren’t part of a feasible real-world solution. (Many of these are very obvious, but we do have to remember to include them!). There are other shortcuts, such as predetermining which HHC of several is going to be used, or allowing for the opening of new HHCs, and identifying nodes that will probably have a fixed position in any solution – an example is to place the patient order with the longest deadline as the final delivery node.

Nonetheless it may be that the algorithm cannot avoid some violation of the constraint conditions (in other words its best effort is still infeasible) in which case we have devised a repair mechanism to be used on the best of the infeasible solutions to bring it into a state of compliance.

Does the approach work? We created a set of 50 test instances based on real-world conditions, of different sizes and using randomly generated parameter values, and evaluated six approaches, including our IMBD pair, in terms of cost function and execution time. We found that our IMBD II demonstrated the best performance in terms of execution time and solution quality. Although one other approach showed a better cost function result, two approaches couldn’t resolve medium and large instances at all within reasonable CPU time.

For further validation, we conducted a case study in and around the city of Sari in Iran, involving three pharmaceutical vendors supplying an HHC. Eight city and three countryside patients with a variety of medicines and medical equipment requirements were to be served with one drone and two vehicles available. Having set up and resolved this situation, we performed four sensitivity analyses:

• Changing deadline data inputs
• Changing wind/traffic and collision risk parameter values
• Supplier unavailability due to public holidays
• Changing fuel/energy/energy saving (new model of drone) parameters.

Our model and solution performed very much as hoped and expected across all these tests.

In summary, we believe our approach assists managers in determining the quantities of supplies to be delivered into the HHC and improves the deliver process to patients using drones or vehicles considering factors such as cost functions, deadlines and patient locations – all with a lower CPU time (and therefore faster responsiveness) and high solution quality.

The approach may also be useful in simulation to allow managers to work out the size and composition of drone and ground vehicle fleets that they need, and optimal locations for HHCs.

The full paper can be read at https://www.sciencedirect.com/science/article/abs/pii/S0305054825003351

For more information contact [email protected]