Publication:
Multi-vehicle prize collecting arc routing for connectivity problem

Placeholder

School / College / Institute

Program

KU Authors

Co-Authors

Publication Date

Language

Embargo Status

Journal Title

Journal ISSN

Volume Title

Alternative Title

Abstract

For effective disaster response, roads should be cleared or repaired to provide accessibility and relief services to the affected people in shortest time. We study an arc routing problem that aims to regain the connectivity of the road network components by clearing a subset of the blocked roads. In this problem, we maximize the total prize gained by reconnecting disconnected network components within a specified time limit. The solution should determine the coordinated routes of each work troop starting at a depot node such that none of the closed roads can be traversed unless their unblocking/clearing procedure is finished. We develop an exact Mixed Integer Program (MIP) and a matheuristic method. The matheuristic solves single vehicle problems sequentially with updated prizes. To obtain an upper bound, we first relax the timing elements in the exact formulation and then solve its relaxed MIP, which decomposes into single vehicle problems, by Lagrangian Relaxation. We show the effectiveness of the proposed methods computationally on both random Euclidean and Istanbul road network data generated with respect to predicted earthquake scenarios. (C) 2017 Elsevier Ltd. All rights reserved.

Source

Publisher

Pergamon-Elsevier Science Ltd

Subject

Computer science, Engineering, Industrial engineering, Operations research, Management science

Citation

Has Part

Source

Computers & Operations Research

Book Series Title

Edition

DOI

10.1016/j.cor.2017.01.007

item.page.datauri

Link

Rights

Copyrights Note

Endorsement

Review

Supplemented By

Referenced By

0

Views

0

Downloads

View PlumX Details