Optimization Model for Base-Level Delivery Routes and Crew Scheduling

In the US Air Force, a Logistic Readiness Squadron (LRS) provides material management, distribution, and oversight of contingency operations. Dispatchers in the LRS must quickly prepare schedules that meet the needs of their customers while dealing with real-world constraints such as time windows, delivery priorities, and intermittent recurring missions. Currently, LRS vehicle operation elements are faced with a shortage of manpower and lack an efficient scheduling algorithm and tool. The purpose of this research is to enhance the dispatchers' capability to handle flexible situations and produce "good" schedules within current manpower restrictions. In this research, a new scheduling model and algorithm are provided as an approach to crew scheduling for a base-level delivery system with a single depot. A Microsoft Excel application, the Daily Squadron Scheduler (DSS), was built to implement the algorithm. DSS combines generated duties with the concept of a set covering problem. It utilizes a Linear Programming pricing algorithm and Excel Solver as the primary engine to solve the problem. Reduced costs and shadow prices from subproblems are used to generate a set of feasible duties from which an optimal solution to the LP relaxation can be found. From these candidate duties the best IP solution is then found. The culmination of this effort was the development of both a scheduling tool and an analysis tool to guide the LRS dispatcher toward efficient current and future schedules.