الگوريتم شاخه و كران براي مسئله‌ برون‌بري- مكان‌يابيِ (ايستا و پوياي استوار) در لجستيكِ اضطراري

Branch and Bound Algorithms for Static and Robust Dynamic Evacuation-Location Problem in Emergency Logistics

فرآيند تخليه از كليدي‌ترين فعاليت‌هاي همزمان با بحران هنگام رخداد فجايع است. در پژوهش‌هاي مديريت بحران، فرض بر وجود مكان‌هاي اسكان اضطراريِ از پيش‌ تعيين‌شده‌اي است كه تخليه افراد از نواحي بحران‌زده به سوي آن‌ها انجام مي‌شود. ما در اين مقاله در پيِ يافتن يك پايگاه اسكان از ميان مجموعة پايگاه هاي پيش‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌بيني‌شده هستيم كه جريان تخليه افراد از ناحية بحران را بيشينه مي‌كند و بنابراين امكان تصميم‌‌گيري دربارة مكان‌هاي امن را همزمان با وقوع بحران براي تصميم‌‌گيرندگان فراهم مي‌كند. اين مسئله را به صورت دو مدل غيرخطي در حالت ايستا و پويا، و با رويكرد شبكة جريان مدل‌سازي مي‌كنيم. علاوه بر اين يك مدل استوار پويا براي مسئلة تخليه-مكان‌يابي توسعه داده‌ايم تا عدم قطعيت مربوط به ظرفيت مسيرها در هنگام رخداد بحران را نيز در نظر بگيريم. در اين مقاله، براي نخستين بار متغير تصميم مكان‌يابي را در مدل بيشينه جريان وارد كرده‌ايم. سپس با استفاده از ساختار مدل‌ها دو كران بالا و دو الگوريتم بهينه براي حل آنها توسعه مي‌دهيم. الگوريتم‌هاي بهينه را بر پايه‌ي تركيب روش‌هاي موجود براي بيشينه‌سازي جريان شبكه با روش شاخه و كران توسعه داده‌ايم. عملكرد كران‌هاي بالا را با حل مسئله‌هاي تصادفي هم از نظر زمان حل و هم فاصله با حل بهينه مي‌سنجيم. زمانِ اجراي الگوريتم‌هاي دقيق را نيز بر روي همين مسئله‌هاي تصادفي مي‌آزماييم و نتيجة مقايسه را گزارش مي‌نماييم. در پايان نيز، الگوريتم‌هاي پيشنهادي را براي داده‌هاي واقعي يك شبكه شهري به كار گرفته و نتايج آن را گزارش كرده‌ايم.

Evacuating people to the safe zones is the most crucial operation in managing many disasters. We have presented mathematical models in this paper, in order to combine the locational decisions with the max-flow problem in order to select the safe destination that maximizes the number of dispatched people, both for the static and dynamic cases. Existing frameworks for emergency logistics, address the evacuation process based on fixed and pre-determined destinations usually with a strategic perspective. The unpredictable and turbulent nature of a disaster may, however, disrupt the predictions. Furthermore, the primary goal in emergency situations is to dispatch people from the danger zone to a safe place, no matter where. A non-linear integer programming model is developed in this paper for selecting one destination in a capacitated network. We have also formulated the robust counterpart of the dynamic model in order to contribute the uncertainty of the capacity of routes during a disaster. The special structure of the model and its similarity to the max-flow problem let us develop exact algorithms and heuristics for the single destination location problem. The solution methods are based on combining a branch and bound approach with the existing algorithms for the max-flow problem. Our proposed heuristics use the idea of adding a super-sink to the network to generate upper bounds very fast. The exact algorithms as well as the heuristics are tested on randomly generated instances as well as a real world network. The mean and variance of their computation times are reported. They are compared according to their performance (gap to optimality) and their behavior amongst different categories of the graphs. We have also used the real data for Mitte-center Berlin to implement our algorithms for an existing data set. The results of the algorithms for this case are also reported in the results section.