A Scheme of Independent Calculations in a Precedence Constrained Routing Problem / Chentsov Alexander G.,Grigoryev Alexey M. // . - 2016. - V. 9869, l. . - P. 121-135.

ISSN/EISSN:

0302-9743 / нет данных

Type:

Proceedings Paper

Abstract:

We consider a routing problem with constraints. To solve this problem, we employ a variant of the dynamic programming method, where the significant part (that is, the part that matters in view of precedence constraints) of the Bellman function is calculated by means of an independent calculations scheme. We propose a parallel implementation of the algorithm for a supercomputer, where the construction of position space layers for the hypothetical processors is conducted with use of discrete dynamic systems' apparatus.

Author keywords:

Dynamic programming; Routing problem; Precedence constraints; Sequential ordering problem; Parallel algorithms TRAVELING SALESMAN PROBLEM; OPTIMIZATION

DOI:

10.1007/978-3-319-44914-2\_10

Web of Science ID:

ISI:000387730300010

Соавторы в МНС:

—

Другие поля

Поле	Значение
Editor	Kochetov, Y and Khachay, M and Beresnev, V and Nurminski, E and Pardalos, P
Booktitle	DISCRETE OPTIMIZATION AND OPERATIONS RESEARCH, DOOR 2016
Series	Lecture Notes in Computer Science
Note	9th International Conference on Discrete Optimization and Operations Research (DOOR), Vladivostok, RUSSIA, SEP 19-23, 2016
Organization	Far E Fed Univ; Sobolev Inst Math; Krasovsky Inst Math \& Mech; Novosibirsk State Univ; Higher Sch Econ Nizhny Novgorod; Russian Fdn Basic Res; Lab Algorithms \& Technologies Networks Anal
Publisher	SPRINGER INT PUBLISHING AG
Address	GEWERBESTRASSE 11, CHAM, CH-6330, SWITZERLAND
Language	English
ISBN	978-3-319-44914-2; 978-3-319-44913-5
Keywords-Plus	TRAVELING SALESMAN PROBLEM; OPTIMIZATION
Research-Areas	Computer Science; Engineering; Operations Research \& Management Science
Web-of-Science-Categories	Computer Science, Theory \& Methods; Engineering, Electrical \& Electronic; Operations Research \& Management Science
Author-Email	chentsov@imm.uran.ru ag@uran.ru
Number-of-Cited-References	26
Usage-Count-Since-2013	1
Doc-Delivery-Number	BG2WI