On an iterative procedure for solving a routing problem with constraints

A. A. Chentsov   ; A. G. Chentsov

Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 18 (2012) no. 3, pp. 261-281

Résumé

The generalized courier problem in the case when travel costs depend explicitly on the list of tasks that have not been performed (by the time of the travel) is considered. The original routing problem with dependent variables is represented in terms of an equivalent extremal problem with independent variables. An iterative method based on this representation is proposed for solving the original problem. The algorithm based on this method is implemented as a computer program.

Détail

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

Bibliographie

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

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

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

[4] Bellman R., “Primenenie dinamicheskogo programmirovaniya k zadache o kommivoyazhere”, Kibernet. sb., 9, 1964, 219–228

[5] Kheld M., Karp R. M., “Primenenie dinamicheskogo programmirovaniya k zadacham uporyadocheniya”, Kibernet. sb., 9, 1964, 202–218

[6] Henry-Labordere A. L., “The record-balancing problem: a dynamic programming solution of a generalized travelling salesman problem”, R.I.R.O., 3:2 (1969), 43–49 | Zbl

[7] Laporte G., Nobert Y., “Generalized traveling salesman problem through $n$-sets of nodes: an integer programming approach”, INFOR, 21:1 (1983), 61–75 | MR | Zbl

[8] Leiten A. K., “Nekotorye modifikatsii zadachi kommivoyazhera”, Tr. VTs Tart. un-ta, 28, 1973, 44–58 | MR

[9] Chentsov A. G., Ekstremalnye zadachi marshrutizatsii i raspredeleniya zadanii: voprosy teorii, NITs Regulyarnaya i khaoticheskaya dinamika, M.–Izhevsk, 2008, 240 pp.

[10] Chentsov A. A., Chentsov A. G., “Reduktsiya zadach marshrutnoi optimizatsii”, Avtomatika i telemekhanika, 2000, no. 10, 136–150 | MR | Zbl

[11] Chentsov A. A., Chentsov A. G., “Ob odnom priblizhennom metode resheniya zadach marshrutnoi optimizatsii”, Algoritmy i program. sredstva paral. vychislenii, 4, UrO RAN, Ekaterinburg, 2000, 287–302

[12] Chentsov A. A., Chentsov A. G., “K voprosu o reshenii zadachi posledovatelnogo obkhoda mnozhestv s ispolzovaniem nezamknutoi zadachi kommivoyazhera”, Avtomatika i telemekhanika, 2002, no. 11, 151–166 | MR | Zbl

[13] Chentsov A. A., “Metod iteratsii v obobschennoi zadache kommivoyazhera na uzkie mesta”, Algoritmy i program. sredstva paral. vychislenii, 5, UrO RAN, Ekaterinburg, 2001, 287–302

[14] Chentsov A. A., “Metod iteratsii v zadache posledovatelnogo obkhoda mnozhestv (obobschennaya zadacha kommivoyazhera na uzkie mesta)”, Algoritmy i program. sredstva paral. vychislenii, 6, UrO RAN, Ekaterinburg, 2002, 209–230 | MR

[15] Chentsov A. A., Chentsov A. G., Chentsov P. A., “Ekstremalnaya zadacha marshrutizatsii peremeschenii s ogranicheniyami i vnutrennimi poteryami”, Izv. vuzov. Matematika, 2010, no. 6, 64–81 | MR | Zbl

[16] Chentsov A. G., “Ob optimalnoi marshrutizatsii v usloviyakh ogranichenii”, Dokl. RAN, 423:3 (2008), 303–307 | MR | Zbl

[17] Chentsov A. A., Chentsov A. G., Chentsov P. A., “Metod iteratsii v zadache marshrutizatsii s vnutrennimi poteryami”, Tr. Instituta matematiki i mekhaniki UrO RAN, 15, no. 4, 2009, 270–289

[18] Sesekin A. N., Tashlykov O. L., Scheklein S. E., Kuklin M. Yu., Chentsov A. G., Kadnikov A. A., “Ispolzovanie metoda dinamicheskogo programmirovaniya dlya optimizatsii traektorii peremescheniya rabotnikov v radiatsionno opasnykh zonakh s tselyu minimizatsii oblucheniya”, Izv. vuzov. Yadernaya energetika, 2006, no. 2, 41–48

[19] Tashlykov O. L., Sesekin A. N., Chentsov A. G., Scheklein S. E., Balushkin F. A., Khomyakov A. P., “Voprosy matematicheskikh metodov modelirovaniya v reshenii problemy snizheniya obluchaemosti personala”, Voprosy radiatsionnoi bezopasnosti, 2009, no. 4, 47–57

[20] Sesekin A. N., Chentsov A. A., Chentsov A. G., “Obobschennaya zadacha kurera s funktsiei zatrat, zavisyaschei ot spiska zadanii”, Izv. RAN. TiSU, 2010, no. 3, 68–77 | MR

[21] Tashlykov O. L., Sesekin A. N., Scheklein S. E., Chentsov A. G., “Razrabotka optimalnykh algoritmov vyvoda AES iz ekspluatatsii s ispolzovaniem metodov matematicheskogo modelirovaniya”, Izv. vuzov. Yadernaya energetika, 2009, no. 2, 115–120

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

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

[24] Balushkin F. A., Sesekin A. N., Freiberg Yu. A., Chentsov A. G., “Ob odnom variante zadachi kommivoyazhera”, Vestn. kompyuternykh i inform. tekhnologii, 2009, no. 12, 45–50