Generalized a bottleneck routing problem: dynamic programming and the start point optimization

被引：0

作者：

Chentsov, Alexei A. ^{[1
]}

Chentsov, Alexander G. ^{[1
,2
]}

Sesekin, Alexander N. ^{[1
,2
]}

机构：

[1] Inst Math & Mech UB RAS, Ekaterinburg, Russia

[2] Ural Fed Univ, Ekaterinburg, Russia

来源：

IFAC PAPERSONLINE | 2018年 / 51卷 / 32期

关键词：

Routing problem; nonadditive criterion; dynamic programming;

D O I：

10.1016/j.ifacol.2018.11.412

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

One routing problem with constraints is considered. These constraints are reduced to precedence conditions which be to visiting sequence of megalopolises. This sequence is selected together with concrete trajectory and initial state for minimization of nonadditive criterion. These criterion is some generalization of known criterion for the bottleneck routing problem. The basis singularity of the used solving method consists of using of unique dynamic programming procedure for all initial states. The used criterion includes a controlled parameter influences on significance of different fragments of solution. (C) 2018, IFAC (International Federation of Automatic Control) Hosting by Elsevier Ltd. All rights reserved.

引用

页码：373 / 377

页数：5

共 12 条

[1]

[Anonymous], 2008, Extreme tasks of routing and distribution of tasks: theory questions

[2]

[Anonymous], 1958, On a Routing Problem Quarterly of Applied Mathematics

[3] On a parallel procedure for constructing the Bellman function in the generalized problem of courier with internal jobs [J].

Chentsov, A. G. .

AUTOMATION AND REMOTE CONTROL, 2012, 73 (03) :532-546

[4]

Chentsov A. G., 2013, VESTN UDGU MAT MEKH, V1, P59

[5]

[Ченцов Александр Георгиевич Chentsov Aleksandr Georgievich], 2016, [Вестник Удмуртского университета. Математика. Механика. Компьютерные науки, Bulletin of Udmurt University. Mathematics. Mechanics. Computer Science, Vestnik Udmurtskogo universiteta. Matematika. Mekhanika. Komp'yuternye nauki], V26, P121, DOI 10.20537/vm160110

[6]

Cook W., 2012, In pursuit of the traveling salesman: mathematics at the limits of computation

[7]

Dieudonne J., 1960, FOUDATIONS MODERN AN

[8]

Gimadi EKh., 2016, Extremal Problems on Sets of Permutations

[9]

Gutin G., 2002, TRAVELING SALESMAN P

[10] A DYNAMIC PROGRAMMING APPROACH TO SEQUENCING PROBLEMS [J].

HELD, M ;

KARP, RM .

JOURNAL OF THE SOCIETY FOR INDUSTRIAL AND APPLIED MATHEMATICS, 1962, 10 (01) :196-210

← 1 2 →