The enriched median routing problem and its usefulness in practice. (June 2022) - Huizing, Dylan; van der Mei, Rob; Schäfer, Guido; Bhulai, Sandjai
Highlights: We extend the Median Routing Problem with fifteen additional features from practice. We leverage the flexibility of linear programs in our original matheuristic. We model real world behaviour using almost the same algorithm. In a relevant case study, response times can be reduced while performing more jobs. Our methodology is generalized to many practical emergency logistics settings. Abstract: Emergency response fleets often have to simultaneously perform two types of tasks: (1) urgent tasks requiring immediate action, and (2) non-urgent preventive maintenance tasks that can be scheduled upfront. In Huizing et al. (2020), Huizing et al. proposed the Median Routing Problem (MRP) to optimally schedule agents to a given set of non-urgent tasks, such that the response time for urgent tasks remains minimal. They proposed both an exact MILP-solution and a fast, scalable and accurate heuristic. However, when implementing the MRP-solution in a real-life pilot with a Dutch railway provider, we found that the model needed to be extended by including additional practical objectives and constraints. Therefore, in this paper, we extend the MRP to the so-called Enriched Median Routing Problem (E-MRP), making the model much better aligned with considerations from practice. Accordingly, we extend the MRP-based solutions to the E-MRP. This allows us to compare the performance of our proposed E-MRP solutions to performance obtained in the current operational practice of our partnering railway infrastructure company. We conclude that the E-MRP solution leads to a strong reduction in emergency response times compared to current practice by smartly scheduling the same volumes of non-urgent tasks.