Elements of dynamic programming in local improvement constructions for heuristic solutions of routing problems with constraints

A. A. Petunin; A. A. Chentsov; A. G. Chentsov; P. A. Chentsov

doi:10.1134/S0005117917040087

Elements of dynamic programming in local improvement constructions for heuristic solutions of routing problems with constraints

Authors: Petunin A.A.¹, Chentsov A.A.², Chentsov A.G.¹^,2, Chentsov P.A.¹^,2
Affiliations:
1. Ural Federal University
2. Institute of Mathematics and Mechanics
Issue: Vol 78, No 4 (2017)
Pages: 666-681
Section: System Analysis and Operations Research
URL: https://ogarev-online.ru/0005-1179/article/view/150578
DOI: https://doi.org/10.1134/S0005117917040087
ID: 150578

Cite item

Full Text

Open Access
Restricted Access

Access granted
Restricted Access

Subscription Access

Abstract
About the authors
References
Supplementary files
Statistics

Abstract

We consider methods for solving routing problems with precedence constraints that use iterative modes based on Bellman insertions while recomputing precedence constraints of the original problem; we assume that the dimension of the latter is sufficiently large, which does not let us, due to complexity of computations, immediately apply dynamic programming in the “global” version.