An embedded optimization-simulation approach to dynamic pickup and delivery problems.

摘要

For years analysts involved with military transportation have used simulations to analyze, plan, and schedule transportation requirements. The problems these analysts face are essentially very large, complex, and dynamic Pickup and Delivery Problems with Time Windows. Techniques found in the literature on this type of problem can be mostly described as pure optimization techniques using explicit mathematical models. For various reasons, analysts in the military have been resistant to change to these types of techniques. In this thesis we present a novel, evolutionary approach to introducing optimization into military transportation analysis by embedding optimization techniques into simulations.; We begin by presenting a linear programming heuristic for the Load-Matching Problem we call a Rolling Event Horizon method. We present results to a static problem consisting of 10 vehicles and 150 customers. We then show how constraint programming and the optimization software ILOG OPL Studio can be used to optimize scheduling problems.; We present an application of our developments in a solution of the Airlift Network Problem from the Air Mobility Command headquartered at Scott Air Force Base, IL. The objective is to simulate the delivery of a list of cargo with a given fleet of aircraft, including stochastics, while minimizing the amount of late cargo. We embed strategies in the simulation to use models in ILOG to assign aircraft to cargo using a rolling event horizon method, choose routes, and create optimal schedules. These optimization techniques replace the simple decision-making strategies commonly used in simulations. We present results from using different decision-making strategies and demonstrate how stochastics are taken into account when scheduling.; We also present a solution to an industrial scheduling problem. In this problem, we simulate the production of five chemicals in two production rooms and use OPL Studio to create a production schedule at the beginning of each simulated month. Stochastics are included in the simulation and we demonstrate how these are taken into account when creating the schedule.