A Cost Function Approximation Based Large Neighborhood Search for Dynamic Medical Courier Services

ABSTRACT Medical on‐demand couriers play an important role in urban medical services. They transport medical supplies, tests, blood, or organs between different locations in the city within a short amount of time. Transportation orders are issued spontaneously and differ in their priority and time restrictions. Since all orders must be served, the goal is to minimize the priority‐dependent delay penalty of all orders. To this end, we propose an anticipatory re‐optimization approach by integrating a parametric Cost Function Approximation (CFA) into a Large Neighborhood Search (LNS). Whenever a new order is placed, the LNS iteratively optimizes the current route plans. The CFA addresses the tradeoff between minimizing delays for pending orders and the fleet's flexibility to react to future orders. To this end, it is used both to evaluate decision candidates (i.e., new route plans) and to assess insertion options within the LNS repair operator. We demonstrate the advantages of our approach in comprehensive computational experiments and provide insights into the method and problem.