The Research Of Vehicle Routing Problem In Emergency Management On Robust Optimization

This thesis mainly focuses on the research of Vehicle Routing Problem(VRP) in Emergency Management on robust optimization.Robust optimization has been remarkable by many researchers as a new method for dealing with uncertain optimization problems. After having an analysis on uncertain optimization problems, the thesis introduces the research results of Soyster ,Ben-Tal and Bertsimas, and mainly has a detail discription on robust linear programming and robust discrete optimization. This thesis also introduces how to model the uncertain optimization problems and gets the robust optimization model, indicating the policy of prior-analysis. That is taking into the parameter uncertainy account in the optimizaiton model, making sure of constaint satisfaction on the realization of all the parameters those make values in the given uncertain set, and not ordering the parameter to obey some probability distributing. After that, the thesis mainly introduces the core problem, which is how to transform the robust optimization model into the robust counterpart. The purpose is to tranform the prior uncertain optimization problem into a tractable optimization problem, which can be solved by optimization software.With the high-speed development of social economy, a series of large-scale abrupt affairs take place more often than past, such as various large-scale natural disaster and terror activity etc. Hence, it is particularly important to these abrupt affairs how to be efficiently carry on emergency management .When the abrupt affairs takes place, how deliver relief supplies quickly and in time to save more properties and life .This is becoming an important problem. On the basis of analyzing themethods those mentioned above, this thesis mainly discusses the difficulty of the vehicle routing problem in emergency managent, which is the uncertainty of demand and travel times. This thesis analyzes vehicle routing problem in emergency managent from the point of programming, incoporating with the Sosyter research formulation on robust optimization.Demand and travel times is as the uncertainty parameter. The minimizing unmet demand and the total period of time during which one is delayed is as the objective. The robust optimization model of the vehicle routing problem in emergency managent is a robust 0-1 discrete optimization.After the deduction on robust 0-1 discrete optimization, the robust counterpart is equal to a mixed integer programming finally.The mixed integer programming is solved in the branch and bound and genetic algrithom for this thesis. Results show the good performance on different demand and travel times for the proposed algrithom in contrast to the other ones, and also verify the feasiblity of the robust optimizaton model on the vehicle routing problem in emergency managent.