Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на этот ресурс:
http://elar.urfu.ru/handle/10995/35990
Полная запись метаданных
Поле DC | Значение | Язык |
---|---|---|
dc.contributor.author | Salii, Y. | en |
dc.date.accessioned | 2016-01-07T10:37:01Z | - |
dc.date.available | 2016-01-07T10:37:01Z | - |
dc.date.issued | 2015 | - |
dc.identifier.citation | Salii Y. Restricted Dynamic Programming Heuristic for Precedence Constrained Bottleneck Generalized TSP / Y. Salii // Proceedings of the 1st Ural Workshop on Parallel, Distributed, and Cloud Computing for Young Scientists (Ural-PDC 2015). — Yekaterinburg, 2015. — P. 85-108. — (CEUR Workshop Proceedings ; vol. 1513). | en |
dc.identifier.issn | 1613-0073 | - |
dc.identifier.other | http://ceur-ws.org/Vol-1513/#paper-10 | - |
dc.identifier.uri | http://elar.urfu.ru/handle/10995/35990 | - |
dc.description.abstract | We develop a restricted dynamical programming heuristic for a complicated traveling salesman problem: a) cities are grouped into clusters, resp. Generalized TSP; b) precedence constraints are imposed on the order of visiting the clusters, resp. Precedence Constrained TSP; c) the costs of moving to the next cluster and doing the required job inside one are aggregated in a minimax manner, resp. Bottleneck TSP; d) all the costs may depend on the sequence of previously visited clusters, resp. Sequence-Dependent TSP or Time Dependent TSP. Such multiplicity of constraints complicates the use of mixed integer-linear programming, while dynamic programming (DP) benefits from them; the latter may be supplemented with a branch-and-bound strategy, which necessitates a “DP-compliant” heuristic. The proposed heuristic always yields a feasible solution, which is not always the case with heuristics, and its precision may be tuned until it becomes the exact DP. | en |
dc.format.mimetype | application/pdf | en |
dc.language.iso | en | en |
dc.publisher | Уральский федеральный университет | ru |
dc.relation.ispartof | CEUR Workshop Proceedings. Vol. 1513 : Proceedings of the 1st Ural Workshop on Parallel, Distributed, and Cloud Computing for Young Scientists (Ural-PDC 2015). — Yekaterinburg, 2015 | en |
dc.subject | SEQUENTIAL ORDERING PROBLEM | en |
dc.subject | TRAVELING SALESMAN | en |
dc.subject | DYNAMIC PROGRAMMING | en |
dc.subject | PRECEDENCE CONSTRAINTS | en |
dc.subject | GENERALIZED TRAVELING SALESMAN | en |
dc.subject | BOTTLENECK TRAVELING SALESMAN | en |
dc.title | Restricted Dynamic Programming Heuristic for Precedence Constrained Bottleneck Generalized TSP | en |
dc.type | Conference Paper | en |
dc.type | info:eu-repo/semantics/conferenceObject | en |
dc.type | info:eu-repo/semantics/publishedVersion | en |
dc.conference.name | 1st Ural Workshop on Parallel, Distributed, and Cloud Computing for Young Scientists (Ural-PDC 2015) | en |
dc.conference.date | 17.11.2015 | - |
local.contributor.subdepartment | Институт математики и компьютерных наук | ru |
Располагается в коллекциях: | Конференции, семинары |
Файлы этого ресурса:
Файл | Описание | Размер | Формат | |
---|---|---|---|---|
ural_pdc-2015-10.pdf | 578,58 kB | Adobe PDF | Просмотреть/Открыть |
Все ресурсы в архиве электронных ресурсов защищены авторским правом, все права сохранены.