Distance-Constrained Line Routing Problem

Standard

Distance-Constrained Line Routing Problem. / Erzin, Adil; Plotnikov, Roman.

Optimization and Applications - 10th International Conference, OPTIMA 2019, Revised Selected Papers. ed. / Milojica Jaćimović; Michael Khachay; Vlasta Malkova; Mikhail Posypkin. Springer Gabler, 2020. p. 43-55 (Communications in Computer and Information Science; Vol. 1145 CCIS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review

Harvard

Erzin, A & Plotnikov, R 2020, Distance-Constrained Line Routing Problem. in M Jaćimović, M Khachay, V Malkova & M Posypkin (eds), Optimization and Applications - 10th International Conference, OPTIMA 2019, Revised Selected Papers. Communications in Computer and Information Science, vol. 1145 CCIS, Springer Gabler, pp. 43-55, 10th International Conference on Optimization and Applications, OPTIMA 2019, Petrovac, Montenegro, 30.09.2019. https://doi.org/10.1007/978-3-030-38603-0_4

APA

Erzin, A., & Plotnikov, R. (2020). Distance-Constrained Line Routing Problem. In M. Jaćimović, M. Khachay, V. Malkova, & M. Posypkin (Eds.), Optimization and Applications - 10th International Conference, OPTIMA 2019, Revised Selected Papers (pp. 43-55). (Communications in Computer and Information Science; Vol. 1145 CCIS). Springer Gabler. https://doi.org/10.1007/978-3-030-38603-0_4

Vancouver

Erzin A, Plotnikov R. Distance-Constrained Line Routing Problem. In Jaćimović M, Khachay M, Malkova V, Posypkin M, editors, Optimization and Applications - 10th International Conference, OPTIMA 2019, Revised Selected Papers. Springer Gabler. 2020. p. 43-55. (Communications in Computer and Information Science). doi: 10.1007/978-3-030-38603-0_4

Author

Erzin, Adil ; Plotnikov, Roman. / Distance-Constrained Line Routing Problem. Optimization and Applications - 10th International Conference, OPTIMA 2019, Revised Selected Papers. editor / Milojica Jaćimović ; Michael Khachay ; Vlasta Malkova ; Mikhail Posypkin. Springer Gabler, 2020. pp. 43-55 (Communications in Computer and Information Science).

BibTeX

@inproceedings{5c10cfb4411f4915b3f9729e9a47d1cd,

title = "Distance-Constrained Line Routing Problem",

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.",

keywords = "Barrier covering, Distance-constrained line routing, Mobile sensors",

author = "Adil Erzin and Roman Plotnikov",

note = "Publisher Copyright: {\textcopyright} Springer Nature Switzerland AG 2020. Copyright: Copyright 2020 Elsevier B.V., All rights reserved.; 10th International Conference on Optimization and Applications, OPTIMA 2019 ; Conference date: 30-09-2019 Through 04-10-2019",

year = "2020",

month = jan,

day = "1",

doi = "10.1007/978-3-030-38603-0_4",

language = "English",

isbn = "9783030386023",

series = "Communications in Computer and Information Science",

publisher = "Springer Gabler",

pages = "43--55",

editor = "Milojica Ja{\'c}imovi{\'c} and Michael Khachay and Vlasta Malkova and Mikhail Posypkin",

booktitle = "Optimization and Applications - 10th International Conference, OPTIMA 2019, Revised Selected Papers",

address = "Germany",

}

RIS

TY - GEN

T1 - Distance-Constrained Line Routing Problem

AU - Erzin, Adil

AU - Plotnikov, Roman

PY - 2020/1/1

Y1 - 2020/1/1

N2 - 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.

AB - 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.

KW - Barrier covering

KW - Distance-constrained line routing

KW - Mobile sensors

UR - http://www.scopus.com/inward/record.url?scp=85078398234&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-38603-0_4

DO - 10.1007/978-3-030-38603-0_4

M3 - Conference contribution

AN - SCOPUS:85078398234

SN - 9783030386023

T3 - Communications in Computer and Information Science

SP - 43

EP - 55

BT - Optimization and Applications - 10th International Conference, OPTIMA 2019, Revised Selected Papers

A2 - Jaćimović, Milojica

A2 - Khachay, Michael

A2 - Malkova, Vlasta

A2 - Posypkin, Mikhail

PB - Springer Gabler

T2 - 10th International Conference on Optimization and Applications, OPTIMA 2019

Y2 - 30 September 2019 through 4 October 2019

ER -

ID: 23261343