• FENS

IE-OPIM Joint Graduate Seminar: Vahid Akbari (Koç University)

Multi-vehicle Synchronized Arc Routing Problems to Restore Post-Disaster Network Connectivity

Date: Wednesday, April 20, 2016
Time: 13:40 – 14:30
Location: FENS L063

Abstract: A common consequence of natural disasters is the destruction of buildings and bridges resulting in blocking road segments by the fallen debris of the buildings or lampposts. In the immediate disaster response phase, roads should be recovered by clearing the debris or reconstructing damaged segments to ensure accessibility to all the critical regions. We study an arc routing problem that seeks for the optimized routes of multiple work troops that are originally positioned in a supply node, to dispatch and regain the connectivity of the network by clearing a subset of the blocked roads, and distribute the emergency goods to affected areas. We study two different objective functions for this problem. In the first objective function we minimize the total required time to make the entire roads network connected and in the second objective function we maximize the total prize gained by reconnecting roads network components within a specified time limit. The main objective of this research is to provide an efficient solution method to generate a synchronized work schedule for the work troops so that none of the closed roads are traversed unless their unblocking/clearing procedure is finished. We developed an exact MIP formulation to solve these problems. However these formulations fall short to solve larger instances, hence, for the first objective function we propose a math-heuristic that is based on an MIP-relaxation and a local search algorithm. For the second objective function, we developed a math-heuristic method to derive upper bounds. In this method, we solve a relaxation of the exact formulation using Lagrangian relaxation. We developed another math-heuristic method by separating the problem into single vehicle problems and updating the prizes to obtain a lower bound to the addressed problem. We compare the results from the proposed methods computationally on both systematically generated and Istanbul road data.

Bio: Vahid Akbari is a PhD candidate in the Industrial Engineering and Operations Management program at Koç University, Istanbul, Turkey. He received his B.Sc. degree in Industrial Engineering at Sharif University of Technology, Tehran, Iran in 2012. His current research interests include mathematical programming, heuristic methods and algorithms, network models and optimization with applications in disaster management and logistics.