License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.SCOR.2014.76
URN: urn:nbn:de:0030-drops-46714
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2014/4671/
Go to the corresponding OASIcs Volume Portal

Akbari, Vahid ; Salman, Sibel

A Model-Based Heuristic to the Min Max K-Arc Routing for Connectivity Problem

pdf-format:
8.pdf (1 MB)

Abstract

We consider the post-disaster road clearing problem with the goal of restoring network connectivity in shortest time. Given a set of blocked edges in the road network, teams positioned at depot nodes are dispatched to open a subset of them that reconnects the network. After a team finishes working on an edge, others can traverse it. The problem is to find coordinated routes for the teams. We generate a feasible solution using a constructive heuristic algorithm after solving a relaxed mixed integer program. In almost 70 percent of the instances generated both randomly and from Istanbul data, the relaxation solution turned out to be feasible, i.e. optimal for the original problem.

BibTeX - Entry

@InProceedings{akbari_et_al:OASIcs:2014:4671,
  author =	{Vahid Akbari and Sibel Salman},
  title =	{{A Model-Based Heuristic to the Min Max K-Arc Routing for Connectivity Problem}},
  booktitle =	{4th Student Conference on Operational Research},
  pages =	{76--88},
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-67-5},
  ISSN =	{2190-6807},
  year =	{2014},
  volume =	{37},
  editor =	{Pedro Crespo Del Granado and Martim Joyce-Moniz and Stefan Ravizza},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2014/4671},
  URN =		{urn:nbn:de:0030-drops-46714},
  doi =		{10.4230/OASIcs.SCOR.2014.76},
  annote =	{Keywords: Arc Routing Problem, Mixed Integer Programming, Heuristic, Network Connectivity, Road Clearance}
}

Keywords: Arc Routing Problem, Mixed Integer Programming, Heuristic, Network Connectivity, Road Clearance
Collection: 4th Student Conference on Operational Research
Issue Date: 2014
Date of publication: 06.08.2014

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI