Please use this identifier to cite or link to this item: http://hdl.handle.net/10995/95301
Title: On Routing Problem with Starting Point Optimization
Authors: Chentsov, Alexander G.
Chentsov, Pavel A.
Issue Date: 2020
Publisher: N.N. Krasovskii Institute of Mathematics and Mechanics of the Ural Branch of Russian Academy of Sciences
Ural Federal University named after the first President of Russia B.N. Yeltsin
Citation: Chentsov A. G. On Routing Problem with Starting Point Optimization / Alexander G. Chentsov, Pavel A. Chentsov. — DOI 10.15826/umj.2020.2.005. — Text : electronic // Ural Mathematical Journal. — 2020. — Volume 6. — № 2. — С. 44-62.
Abstract: One problem focused on engineering applications is considered. It is assumed that sequential visits to megacities have been implemented. After all visits have been made, it is required to return to the starting point (a more complex dependence on the starting point is also considered). But the last requirement is not strict: some weakening of the return condition is acceptable. Under these assumptions, it is required to optimize the choice of starting point, route, and specific trajectory. The well-known dynamic programming (DP) is used for the solution. But when using DP, significant difficulties arise associated with the dependence of the terminal component of the criterion on the starting point. Starting point enumeration is required. We consider the possibility of reducing the enumeration associated with applied variants of universal (relative to the starting point) dynamic programming. Of course, this approach requires some transformation of the problem.
Keywords: DYNAMIC PROGRAMMING
PRECEDENCE CONDITIONS
ROUTE
URI: http://hdl.handle.net/10995/95301
Access: Creative Commons Attribution License
License text: https://creativecommons.org/licenses/by/4.0/
ISSN: 2414-3952
DOI: 10.15826/umj.2020.2.005
metadata.dc.description.sponsorship: This work was supported by the Russian Foundation for Basic Research (projects No.20-08-00873 (Sections 1–4) and No.18-07-00637 (Sections 5–7)).
Origin: Ural Mathematical Journal. 2020. Volume 6. № 2
Appears in Collections:Ural Mathematical Journal

Files in This Item:
File Description SizeFormat 
umj_2020_6_2_44-62.pdf588,81 kBAdobe PDFView/Open


This item is licensed under a Creative Commons License Creative Commons