Publication:
Routing multiple work teams to minimize latency in post-disaster road network restoration

Thumbnail Image

School / College / Institute

Program

KU Authors

Co-Authors

Ajam, M.
Akbari V.

Publication Date

Language

Embargo Status

NO

Journal Title

Journal ISSN

Volume Title

Alternative Title

Abstract

After a disaster, often roads are damaged and blocked, hindering accessibility for relief efforts. It is essential to dispatch work teams to restore the blocked roads by clearance or repair operations. With the goal of enabling access between critical locations in the disaster area in shortest time, we propose algorithms that determine the schedule and routes of multiple work teams. We minimize the total latency of reaching the critical locations, where the latency of a location is defined as the time it takes from the start of the operation until its first visit by one of the work teams. Coordination among the teams is needed since some blocked edges might be opened by a certain team and utilized by other teams later on. First, we develop an exact mathematical model that handles the coordination requirement. After observing the intractability of this formulation, we introduce two heuristic methods and a lower bounding procedure. In the first method, we develop a mathematical model based on a novel multi-level network representation that yields solutions with disjoint paths. Given that it does not coordinate the teams, we present a matheuristic based on a cluster-first-route-second approach embedded into a local search algorithm together with an additional coordination step to obtain alternative solutions with higher quality and in a shorter time. We test our heuristics on data sets coming from a real network from the literature (180 instances) and randomly generated ones (640 instances) and observe the superiority of the solutions obtained by incorporation of coordination.

Source

Publisher

Elsevier

Subject

Vehicle routing problem, Metaheuristics, Cycle cover

Citation

Has Part

Source

European Journal of Operational Research

Book Series Title

Edition

DOI

10.1016/j.ejor.2021.07.048

item.page.datauri

Link

Rights

Copyrights Note

Endorsement

Review

Supplemented By

Referenced By

0

Views

5

Downloads

View PlumX Details