Skip to main content

Research Repository

Advanced Search

Multi-vehicle prize collecting arc routing for connectivity problem

Akbari, Vahid; Salman, F. Silbel

Multi-vehicle prize collecting arc routing for connectivity problem Thumbnail


Vahid Akbari


© 2017 Elsevier Ltd 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.


Akbari, V., & Salman, F. S. (2017). Multi-vehicle prize collecting arc routing for connectivity problem. Computers and Operations Research, 82, 52-68.

Journal Article Type Article
Acceptance Date Jan 17, 2017
Online Publication Date Jan 18, 2017
Publication Date 2017-06
Deposit Date Oct 1, 2018
Publicly Available Date Oct 2, 2018
Journal Computers & Operations Research
Print ISSN 0305-0548
Publisher Elsevier
Peer Reviewed Peer Reviewed
Volume 82
Pages 52-68
Keywords arc routing, prize collecting, network connectivity, road clearance, disaster response, mixed integer programming, matheuristic
Public URL
Publisher URL
Contract Date Oct 1, 2018


You might also like

Downloadable Citations