Two Optimization Models for Small-Scale Routing of Military Units in a RoadNetwork

摘要

This thesis describes two integer programming models that are developed tosupport movement planners in optimally routing military units through a road network with minimal delays. The formulations are based on a multicommodity time-expanded network flow problem. The first model (called model close column) is designed for use when all vehicles of a military unit are required to move together over one route. The second model (called model separate column) allows a military unit to be split into groups of vehicles which may use different routes and start at irregular times. Variants of the models allow all units to move at just one speed, or allow units to move at one of two speeds, fast or slow. Both models are designed with the German Army in mind, but could be used with minor modifications by other Armies. The models are implemented via the General Algebraic Modeling System (GAMS). A hypothetical peacetime scenario based upon completion of a German brigade live exercise is used to test both models. In the test data, five military units are specified such that their movements inside an area of 24 by 12 km would conflict without careful planning. Depending on the model and whether movements are planned with different speeds, these five units are routed with solution times from 14 sec to 131 sec on a 486/33 MHz personal computer with the ZOOM solver. The advantage of movements at different speeds is clearly demonstrated. Evaluation of all results shows that they are accurate and that planners can be effectively supported by the models. Multicommodity, Time-Expanded, Dynamic, Transportation, Network, Optimal routing.