Askeri birliklerin intikalinde ulaştırma ihtiyaçlarının optimizasyonu

ABSTRACTOPTIMIZATION OF TRANSPORTATION REQUIREMENTSIN THE DEPLOYMENT OF MILITARY UNITSİbrahim AkgünPh.D. in Industrial EngineeringSupervisor: Prof. Barbaros Ç. TanselDecember 2005We study the deployment planning problem (DPP) that may roughly bedefined as the problem of the planning of the physical movement of militaryunits, stationed at geographically dispersed locations, from their home bases totheir designated destinations while obeying constraints on scheduling androuting issues as well as on the availability and use of various types oftransportation assets that operate on a multimodal transportation network. TheDPP is a large-scale real-world problem for which no analytical models areexistent. In this study, we define the problem in detail and analyze it withrespect to the academic literature. We propose three mixed integerprogramming models with the objectives of cost, lateness (the difference betweenthe arrival time of a unit and its earliest allowable arrival time at its destination),and tardiness (the difference between the arrival time of a unit and its latestarrival time at its destination) minimization to solve the problem. The cost-minimization model minimizes total transportation cost of a deployment and isof use for investment decisions in transportation resources during peacetime andfor deployment planning in cases where the operation is not imminent and thereis enough time to do deliberate planning that takes costs into account. Thelateness and tardiness minimization models are of min-max type and are of usewhen quick deployment is of utmost concern. The lateness minimization modelis for cases when the given fleet of transportation assets is sufficient to deployunits within their allowable time windows and the tardiness minimization modelis for cases when the given fleet is not sufficient. We propose a solutionmethodology for solving all three models. The solution methodology involvesan effective use of relaxation and restriction that significantly speeds up aCPLEX-based branch-and-bound. The solution times for intermediate sizedproblems are around one hour at maximum for cost and lateness minimizationmodels and around two hours for the tardiness minimization model. Producinga suboptimal feasible solution based on trial and error methods for a problem ofthe same size takes about a week in the current practice in the Turkish ArmedForces. We also propose a heuristic that is essentially based on solving themodels incrementally rather than at one step. Computational results show thatthe heuristic can be used to find good feasible solutions for the models. Weconclude the study with comments on how to use the models in the real-world.Keywords: large-scale optimization; military; transportation; mixed integerprogramming; min-max; deployment; mobility; restriction andrelaxation; branch and bound.