A. A. Petunin, A. A. Chentsov, A. G. Chentsov, P. A. Chentsov, “Elements of dynamic programming in local improvement constructions for heuristic solutions of routing problems with constraints”, Avtomat. i Telemekh., 2017, Issue 4,Pages <nobr>106

This article is cited in 5 papers

System Analysis and Operations Research

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

A. A. Petunin^a, A. A. Chentsov^b, A. G. Chentsov^ba, P. A. Chentsov^ba

^a Ural Federal University, Yekaterinburg, Russia
^b Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciences, Yekaterinburg, Russia

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.

Keywords: dynamic programming, route, precedence constraints.

Presented by the member of Editorial Board: A. A. Lazarev

Received: 13.10.2014