Please use this identifier to cite or link to this item: http://hdl.handle.net/10995/35990
Title: Restricted Dynamic Programming Heuristic for Precedence Constrained Bottleneck Generalized TSP
Authors: Salii, Y.
Issue Date: 2015
Publisher: Уральский федеральный университет
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).
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.
Keywords: SEQUENTIAL ORDERING PROBLEM
TRAVELING SALESMAN
DYNAMIC PROGRAMMING
PRECEDENCE CONSTRAINTS
GENERALIZED TRAVELING SALESMAN
BOTTLENECK TRAVELING SALESMAN
URI: http://hdl.handle.net/10995/35990
Conference name: 1st Ural Workshop on Parallel, Distributed, and Cloud Computing for Young Scientists (Ural-PDC 2015)
Conference date: 17.11.2015
ISSN: 1613-0073
Origin: 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
Appears in Collections:Конференции, семинары

Files in This Item:
File Description SizeFormat 
ural_pdc-2015-10.pdf578,58 kBAdobe PDFView/Open
Show full item record   Google Scholar





Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.