Solving the Inventory Slack Routing Problem for Emergency Medication Distribution

Abstract

A bioterrorist attack, or natural disaster, would prompt an immediate government response in order to efficiently address the possible health effects of the population. Such a scenario would create a logistics problem of delivering medication (or other supplies) to makeshift dispensing centers in a short period of time and in high quantities while operating. These makeshift centers, or Points of Dispensing, require schedules of delivery that are robust against uncertainty. This inventory slack routing problem is a novel vehicle routing problem. The objective function is to maximize the slack in the schedule. This thesis presents heuristic approaches that separate the problem into routing and scheduling. The routing problem is solved using a route first-cluster second method. The scheduling problem is solved using a heuristic and an improvement approach. This thesis also presents a search approach that uses heuristics to search various neighborhoods in the solution space. These heuristics are chosen randomly based on probabilities that adapt during the search according to their performance. The inventory slack routing problem is also formulated as a mixed-integer program and solved using a column generation procedure that utilizes simulated annealing to generate new vehicle schedules. This thesis presents the results of testing these three approaches on a set of 432 instances that were generated from real-world data to evaluate solution quality and computational effort. The search approach outperformed the heuristic approach with a reasonable amount of computational effort. The column generation approach did not generate desirable vehicle schedules and therefore was not productive in solving the problem.