Distance-Constrained Line Routing Problem

Adil Erzin, Roman Plotnikov

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

Abstract

On the plane, the barrier is a line segment, and the mobile sensors are initially located at some points (depots). Each sensor can travel a limited-length path, starting and ending at its depot. That part of the barrier, along which sensor moved, is covered by this sensor. It is required to find a min-power subset of sensors covering the entire barrier. The complexity of this problem is not known. In this paper, we have found the special cases of polynomial solvability and state some necessary and sufficient conditions for the existence of the solution. An efficient (polynomial) algorithm for checking the existence of the solution is proposed. Moreover, we have developed some approximation algorithms. In particular, an efficient implementation of the dynamic programming algorithm, which in some special cases yields an optimal solution, is proposed.

Original languageEnglish
Title of host publicationOptimization and Applications - 10th International Conference, OPTIMA 2019, Revised Selected Papers
EditorsMilojica Jaćimović, Michael Khachay, Vlasta Malkova, Mikhail Posypkin
PublisherSpringer Gabler
Pages43-55
Number of pages13
ISBN (Print)9783030386023
DOIs
Publication statusPublished - 1 Jan 2020
Event10th International Conference on Optimization and Applications, OPTIMA 2019 - Petrovac, Montenegro
Duration: 30 Sep 20194 Oct 2019

Publication series

NameCommunications in Computer and Information Science
Volume1145 CCIS
ISSN (Print)1865-0929
ISSN (Electronic)1865-0937

Conference

Conference10th International Conference on Optimization and Applications, OPTIMA 2019
CountryMontenegro
CityPetrovac
Period30.09.201904.10.2019

Keywords

  • Barrier covering
  • Distance-constrained line routing
  • Mobile sensors

Fingerprint

Dive into the research topics of 'Distance-Constrained Line Routing Problem'. Together they form a unique fingerprint.

Cite this