A discrete-continuous routing problem with precedence conditions

A. G. Chentsov ; A. A. Chentsov

Trudy Instituta matematiki i mehaniki, Tome 23 (2017) no. 1, pp. 275-292

Résumé

We consider the problem of visiting closed sets in a compact metric space complicated by constraints in the form of precedence conditions and a possible dependence of the cost function on a list of tasks. We study a variant of the approximate realization of the extremum by applying models that involve problems of sequential visits to megalopolises (nonempty finite sets). This variant is naturally embedded into a more general construction that implements sequential visits to nonempty closed sets (NCSs) from a finite system in a metrizable compactum. The space of NCSs is equipped with the Hausdorff metric, which is used to estimate (under the corresponding condition that the sections of the cost functions are continuous) the proximity of the extrema in the problem of sequential visits for any two systems of NCSs (it is assumed that the numbers or NCSs in the systems are the same). The constraints in the form of precedence conditions are preserved.

Détail

Mots-clés : route
Keywords: path, precedence conditions.

Bibliographie

[1] Petunin A.A., “O nekotorykh strategiyakh formirovaniya marshruta instrumenta pri razrabotke upravlyayuschikh programm dlya mashin termicheskoi rezki materiala”, Vestn. UGATU (Upravlenie, vychislitelnaya tekhnika i informatika.), 13:2(35) (2009), 280–286

[2] Frolovskii V.D., “Avtomatizatsiya proektirovaniya upravlyayuschikh programm teplovoi rezki metalla na oborudovanii s ChPU”, Inform. tekhnologii v proektir. i proizv., 2005, no. 4, 63–66

[3] Verkhoturov M.A., Tarasenko P.Yu., “Matematicheskoe obespechenie zadachi optimizatsii puti rezhuschego instrumenta pri ploskom figurnom raskroe na osnove tsepnoi rezki”, Vestn. UGATU (Upravlenie, vychislitelnaya tekhnika i informatika.), 10:2(27) (2008), 123–130

[4] V.V. Korobkin, A.N. Sesekin, O.L. Tashlykov, A.G. Chentsov, Metody marshrutizatsii i ikh prilozheniya v zadachakh povysheniya bezopasnosti i effektivnosti ekspluatatsii atomnykh stantsii, Novye tekhnologii, M., 2012, 234 pp.

[5] Chentsov A.G., “Zadacha posledovatelnogo obkhoda megapolisov s usloviyami predshestvovaniya”, Avtomatika i telemekhanika, 2014, no. 4, 170–190 | Zbl

[6] Chentsov A.G., Chentsov A.A., “Dinamicheskoe programmirovanie v zadache marshrutizatsii s ogranicheniyami i stoimostyami, zavisyaschimi ot spiska zadanii”, Dokl. RAN, 453:1 (2013), 20–23 | DOI | MR | Zbl

[7] Chentsov A.A., Chentsov A.G., Chentsov P.A., “Elementy dinamicheskogo programmirovaniya v ekstremalnykh zadachakh marshrutizatsii”, Problemy upravleniya, 2013, no. 5, 12–21

[8] Chentsov A.A., Chentsov A.G., “Dynamic programming method in the generalized traveling salesman problem: the influence of inexact calculations”, Math. Comput. Modelling, 33 (2001), 801–819 | DOI | MR | Zbl

[9] Melamed I.I., Sergeev S.I., Sigal I.Kh., “Zadacha kommivoyazhera. Voprosy teorii”, Avtomatika i telemekhanika, 1989, no. 9, 3–34

[10] Melamed I.I., Sergeev S.I., Sigal I.Kh., “Zadacha kommivoyazhera. Tochnye algoritmy”, Avtomatika i telemekhanika, 1989, no. 10, 3–29 | Zbl

[11] Melamed I.I., Sergeev S.I., Sigal I.Kh., “Zadacha kommivoyazhera. Priblizhennye algoritmy”, Avtomatika i telemekhanika, 1989, no. 11, 3–26 | Zbl

[12] Gutin G., Punnen A.P., The traveling salesman problem and its variations, Springer-Verlag, Berlin, 2002, 850 pp. | MR

[13] Cook William J., In pursuit of the traveling salesman: mathematics at the limits of computation, Princeton University Press, Princeton, 2012, 228 pp. | MR | Zbl

[14] Chentsov A.G., Ekstremalnye zadachi marshrutizatsii i raspredeleniya zadanii: voprosy teorii, NITs “Regulyarnaya i khaoticheskaya dinamika”, M.; Izhevsk, 2008, 238 pp.

[15] Kheld M., Karp R.M., “Primenenie dinamicheskogo programmirovaniya k zadacham uporyadocheniya”, Kiberneticheskii sb., v. 9, Mir, M., 1964, 202–218

[16] Bellman R., “Primenenie dinamicheskogo programmirovaniya k zadache o kommivoyazhere”, Kiberneticheskii sb., v. 9, Mir, M., 1964, 219–228

[17] Chentsov A.G., Chentsov A.A., “Zadacha marshrutizatsii s ogranicheniyami, zavisyaschimi ot spiska zadanii”, Dokl. RAN, 465:2 (2015), 154–158 | DOI | Zbl

[18] Kosheleva M.S., Chentsov A.A., Chentsov A.G., “O zadache marshrutizatsii s ogranicheniyami, vklyuchayuschimi zavisimost ot spiska zadanii”, Tr. In-ta matematiki i mekhaniki UrO RAN, 21:4 (2015), 178–195 | MR

[19] Chentsov A.G., Salii J.V., “A model of “nonadditive” routing problem where the costs depend on the set of pending tasks”, Vestn. Yuzh.-Ural. gos. un-ta (Mat. modelirovanie i programmirovanie.), 8:1 (2015), 24–45 | Zbl

[20] Chentsov A.G., Chentsov A.A., “Marshrutizatsiya peremeschenii pri dinamicheskikh ogranicheniyakh: zadacha “na uzkie mesta””, Vestn. Udmurt. un-ta (Matematika. Mekhanika. Kompyuternye nauki.), 26:1 (2016), 121–140 | MR

[21] Kuratovskii K., Mostovskii A., Teoriya mnozhestv, Mir, M., 1970, 416 pp. | MR

[22] Kormen T., Leizerson Ch., Rivest R., Algoritmy: postroenie i analiz, MTsNMO, M., 1999, 960 pp.

[23] Dedonne Zh., Osnovy sovremennogo analiza, Mir, M., 1964, 430 pp.

[24] Engelking R., Obschaya topologiya, Mir, M., 1986, 751 pp.

[25] Petunin A.A., Chentsov A.G., Chentsov P.A., “K voprosu o marshrutizatsii dvizheniya instrumenta v mashinakh listovoi rezki s chislovym programmnym upravleniem”, NTV SPbGPU, 2013, no. 2(169), 103–111

[26] Petunin A.A., Chentsov A.G., Chentsov P.A., “Ob odnoi zadache marshrutizatsii peremeschenii instrumenta pri listovoi rezke detalei”, Modelirovanie i analiz informatsionnykh sistem, 22:2 (2015), 278–294 | MR

[27] Minu M., Matematicheskoe programmirovanie, Nauka, M., 1990, 488 pp.