General information
Latest issue
Impact factor
Guidelines for authors
Submit a manuscript

Search papers
Search references

Latest issue
Current issues
Archive issues
What is RSS

Avtomat. i Telemekh.:

Personal entry:
Save password
Forgotten password?

Avtomat. i Telemekh., 2016, Issue 11, Pages 96–117 (Mi at14599)  

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

Topical issue

Routing under constraints: problem of visit to megalopolises

A. G. Chentsovab, P. A. Chentsovab

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

Abstract: Consideration was given to the problems of routing transfers under conditions of precedence and dynamic constraints including the dependence of the list of jobs both already completed by the instant of transfer or, on the contrary, not yet completed. The transfer costs also can be dependent on the list of jobs. The megalopolises (nonempty finite sets) are the objects of visits, which corresponds to the possible multiple-choice of transfers. The widely understood dynamic programming in a realization not requiring (under the precedence conditions) construction of the entire array of the Bellman function values is used as the basic method of study. The procedure of constructing a “complete” solution including determination of the optimal solution route and track (trajectory) and the procedure determining the problem value (global extremum) can be used separately to test the heuristic algorithms. An efficient heuristic algorithm was constructed to solve the routing problems of great dimension complicated by the constraints typical of the sheet cutting on the machines with computerized numerical control. For moderate problems, the results obtained were compared with the optimal result provided by the dynamic programming.

Funding Agency Grant Number
Ministry of Education and Science of the Russian Federation 02.A03.21.0006
Russian Foundation for Basic Research 16-01-00649
This work was supported by the Decree no. 211 of the Government of Russian Federation, contract no. 02.A03.21.0006, and the Russian Foundation for Basic Research, project no. 16-01-00649.

Full text: PDF file (3400 kB)
References: PDF file   HTML file

English version:
Automation and Remote Control, 2016, 77:11, 1957–1974

Bibliographic databases:

Presented by the member of Editorial Board: А. А. Лазарев

Received: 04.02.2016

Citation: A. G. Chentsov, P. A. Chentsov, “Routing under constraints: problem of visit to megalopolises”, Avtomat. i Telemekh., 2016, no. 11, 96–117; Autom. Remote Control, 77:11 (2016), 1957–1974

Citation in format AMSBIB
\by A.~G.~Chentsov, P.~A.~Chentsov
\paper Routing under constraints: problem of visit to megalopolises
\jour Avtomat. i Telemekh.
\yr 2016
\issue 11
\pages 96--117
\jour Autom. Remote Control
\yr 2016
\vol 77
\issue 11
\pages 1957--1974

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. A. Petunin, A. G. Chentsov, P. A. Chentsov, “K voprosu o marshrutizatsii peremeschenii pri listovoi rezke detalei”, Vestn. YuUrGU. Ser. Matem. modelirovanie i programmirovanie, 10:3 (2017), 25–39  mathnet  crossref  elib
    2. A. G. Chentsov, A. A. Chentsov, “Modelnyi variant zadachi o posledovatelnoi utilizatsii istochnikov izlucheniya (iteratsii na osnove optimiziruyuschikh vstavok)”, Izv. IMI UdGU, 50 (2017), 83–109  mathnet  crossref  elib
    3. A. G. Chentsov, A. A. Chentsov, A. M. Grigorev, “Ob odnoi zadache marshrutizatsii, modeliruyuschei peremescheniya v radiatsionnykh polyakh”, Vestn. Udmurtsk. un-ta. Matem. Mekh. Kompyut. nauki, 27:4 (2017), 540–557  mathnet  crossref  elib
    4. A. G. Chentsov, A. M. Grigoryev, A. A. Chentsov, “Solving a routing problem with the aid of an independent computations scheme”, Vestn. YuUrGU. Ser. Matem. modelirovanie i programmirovanie, 11:1 (2018), 60–74  mathnet  crossref  elib
    5. A. G. Chentsov, P. A. Chentsov, “Optimizatsiya tochki starta v zadache posledovatelnogo obkhoda megapolisov pri nalichii uslovii predshestvovaniya”, Vestn. YuUrGU. Ser. Matem. modelirovanie i programmirovanie, 11:2 (2018), 83–95  mathnet  crossref  elib
    6. A. G. Chentsov, P. A. Chentsov, A. A. Petunin, A. N. Sesekin, “Model of megalopolises in the tool path optimisation for CNC plate cutting machines”, Int. J. Prod. Res., 56:14 (2018), 4819–4830  crossref  isi  scopus
    7. Alexander G. Chentsov, Alexey M. Grigoriev, Alexey A. Chentsov, “Optimizing the starting point in a precedence constrained routing problem with complicated travel cost functions”, Ural Math. J., 4:2 (2018), 43–55  mathnet  crossref  mathscinet
    8. A. G. Chentsov, P. A. Chentsov, “Ob odnoi zadache marshrutizatsii s optimizatsiei tochki starta–finisha”, Izv. IMI UdGU, 52 (2018), 103–115  mathnet  crossref  elib
    9. Petunin A.A., Chentsov A.G., Chentsov P.A., “Optimizing Insertions in a Constraint Routing Problem With Complicated Cost Functions”, J. Comput. Syst. Sci. Int., 58:1 (2019), 113–125  crossref  isi  scopus
    10. A. G. Chentsov, P. A. Chentsov, “The routing problems with optimization of the starting point: dynamic programming”, Izv. IMI UdGU, 54 (2019), 102–121  mathnet  crossref  elib
    11. 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
  • Avtomatika i Telemekhanika
    Number of views:
    This page:182
    Full text:13
    First page:18

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