General information
Latest issue
Impact factor

Search papers
Search references

Latest issue
Current issues
Archive issues
What is RSS

Vestn. Udmurtsk. Univ. Mat. Mekh. Komp. Nauki:

Personal entry:
Save password
Forgotten password?

Vestn. Udmurtsk. Univ. Mat. Mekh. Komp. Nauki, 2014, Issue 2, Pages 56–75 (Mi vuu427)  

This article is cited in 6 scientific papers (total in 6 papers)


Local dynamic programming incuts in routing problems with restrictions

A. A. Petunina, A. G. Chentsovb, P. A. Chentsovb

a Institute of Mechanics and Machine-Building, Ural Federal University, ul. Mira, 19, Yekaterinburg, 620002, Russia
b N. N. Krasovskii Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciences, ul. S. Kovalevskoi, 16, Yekaterinburg, 620990, Russia

Abstract: The article is concerned with the procedure of insertion of optimizable fragments of route solutions into the global solutions of the «big» problem defined by heuristic algorithms. Setting of the route problem takes into account some singularities of the engineering problem about the sequential cutting of details each having one exterior and probably several interior contours. The latter ones must be subjected to cutting previously in comparison with the exterior contour, which leads to a great number of given preceding conditions. These conditions are actively used to decrease the computational complexity. Nevertheless, the problem dimensionality remains sufficiently large that does not permit to use «global» dynamic programming and forces heuristic algorithms to be used (the problem under investigation is a hard-solvable problem in the traditional sense). Therefore, it is interesting to develop the methods for correction of solutions based on the above-mentioned algorithms. In the present investigation, such correction is realized by the replacement of fragments (of the above-mentioned solutions) having a moderate dimensionality by optimal «blocks» constructed by dynamic programming with local preceding conditions which are compatible with the constraints of the initial «big» problem. The proposed replacement does not deteriorate, but, in typical cases, improves the quality of the initial heuristic solution. This is verified by the computing experiment on multi-core computer.
The proposed algorithm is realized in the iterated regime: the solution (in the form of «route-trace») obtained after the first insertion on the basis of dynamic programming is taken as an initial solution for which the insertion is constructed again. In addition, the beginning of the new insertion is chosen randomly in the bounds defined by the possibilities of formation of a sliding «window» of the appreciable dimensionality which is in fact sufficient for the employment of the economical version of dynamic programming. Further, the procedure is repeated. The operation of the iterated algorithm is illustrated by solution of model problems including the versions with sufficiently dense «packing» of parts on a sheet, which is typical for the engineering production.

Keywords: routing problem, preceding conditions.

Full text: PDF file (577 kB)
References: PDF file   HTML file
UDC: 519.6
MSC: 93CXX, 93С15
Received: 01.03.2014

Citation: A. A. Petunin, A. G. Chentsov, P. A. Chentsov, “Local dynamic programming incuts in routing problems with restrictions”, Vestn. Udmurtsk. Univ. Mat. Mekh. Komp. Nauki, 2014, no. 2, 56–75

Citation in format AMSBIB
\by A.~A.~Petunin, A.~G.~Chentsov, P.~A.~Chentsov
\paper Local dynamic programming incuts in routing problems with restrictions
\jour Vestn. Udmurtsk. Univ. Mat. Mekh. Komp. Nauki
\yr 2014
\issue 2
\pages 56--75

Linking options:

    SHARE: FaceBook Twitter Livejournal

    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    This publication is cited in the following articles:
    1. A. G. Chentsov, “Bellmanovskie vstavki v zadache marshrutizatsii s ogranicheniyami i uslozhnennymi funktsiyami stoimosti”, Vestn. Udmurtsk. un-ta. Matem. Mekh. Kompyut. nauki, 2014, no. 4, 122–141  mathnet
    2. A. G. Chentsov, “Optimiziruyuschie vstavki v zadachakh marshrutizatsii i ikh realizatsiya na osnove dinamicheskogo programmirovaniya”, Vestn. Udmurtsk. un-ta. Matem. Mekh. Kompyut. nauki, 26:4 (2016), 565–578  mathnet  crossref  mathscinet  elib
    3. 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”, Autom. Remote Control, 78:4 (2017), 666–681  mathnet  crossref  isi  elib
    4. A. G. Chentsov, A. M. Grigorev, “Optimiziruyuschie multivstavki v zadachakh marshrutizatsii s ogranicheniyami”, Vestn. Udmurtsk. un-ta. Matem. Mekh. Kompyut. nauki, 28:4 (2018), 513–530  mathnet  crossref  elib
    5. A. G. Chentsov, A. A. Chentsov, “K voprosu o marshrutizatsii peremeschenii v zadache s dinamicheskimi ogranicheniyami”, Vestn. Udmurtsk. un-ta. Matem. Mekh. Kompyut. nauki, 29:3 (2019), 363–381  mathnet  crossref
    6. A. A. Petunin, E. G. Polishchuk, S. S. Ukolov, “On the new algorithm for solving continuous cutting problem”, IFAC PAPERSONLINE, 52:13 (2019), 2320–2325  crossref  isi  scopus
  • Вестник Удмуртского университета. Математика. Механика. Компьютерные науки
    Number of views:
    This page:254
    Full text:95

    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2020