Afet sonucu ağ bağlanırlığının sağlanması için lojistik planlama

In a natural disaster; e.g., earthquake, flood, landslide, road networks can be damaged, and consequently some parts of the roads may be blocked by building or lamppost debris or may collapse due to ground liquefaction. As a result, the road network may become disconnected. In order to ensure connectivity, necessary actions should be taken after a disaster. In the immediate disaster response phase, to facilitate emergency transportation, a critical subset of the blocked roads should be cleared to restore network connectivity as soon as possible. A fleet of machinery with required personnel and equipment which are initially positioned at various locations, e.g. depots, should be dispatched for this task. We define an optimization problem to generate a coordinated work schedule. We represent the road network by a directed graph with estimated arc traversal times for work vehicles. We assume that time to open each blocked arc will be estimated after the disaster by gathering information on road conditions. The problem is to determine which blocked arcs to open and a walk for each vehicle starting at its depot that collectively cover the selected blocked arcs. The objective is to minimize the total time of the longest walk, i.e. the makespan. We name this problem that combines network design, scheduling and arc routing aspects, Arc Routing for Connectivity Problem with K Vehicles (K-ARCP). We prove that K-ARCP is NP-hard even when a single vehicle exists. We characterize some properties of feasible and optimal solutions. We formulate a mixed integer program using flow variables for the walks. We define two relaxations to obtain lower bounds and test their performance computationally. We generate instances using data of Istanbul highway network and analyze the effects of the number of disconnected components, the number of vehicles and depot locations on solution time and quality.