Geodesic
A model of “nonadditive” routing problem where the costs depend on the set of pending tasks
Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie, Tome 8 (2015) no. 1, pp. 24-45 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

We consider a generalization of the bottleneck (minimax) routing problem. The problem is to successively visit a number of megalopolises, complicated by precedence of constraints imposed on the order of megalopolises visited and the fact that the cost functions (of movement between megalopolises and of interior tasks) may explicitly depend on the list of tasks that are not completed at the present time. The process of movement is considered to be a sequence of steps, which include the exterior movement to the respective megalopolis and the following completion of (essentially interior) jobs connected with the megalopolis. The quality of the whole process is represented by the maximum cost of steps it consists of; the problem is to minimize the mentioned criterion (which yields a minimax problem, usually referred to as a “bottleneck problem”). Optimal solutions, in the form of a route-track pair (a track, or trajectory, conforms to a specific instance of a tour over the megalopolises, which are numbered in accordance with the route; the latter is defined by the transposition of indices), are constructed through a “nonstandard” variant of the dynamic programming method, which allows to avoid the process of constructing of all the values of the Bellman function whenever precedence constraints are present.
Keywords: dynamic programming; route; precedence constraints; sequential ordering problem. 
@article{VYURU_2015_8_1_a1,
     author = {A. G. Chentsov and Ya. V. Salii},
     title = {A model of {\textquotedblleft}nonadditive{\textquotedblright} routing problem where the costs depend on the set of pending tasks},
     journal = {Vestnik \^U\v{z}no-Uralʹskogo gosudarstvennogo universiteta. Seri\^a, Matemati\v{c}eskoe modelirovanie i programmirovanie},
     pages = {24--45},
     year = {2015},
     volume = {8},
     number = {1},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/VYURU_2015_8_1_a1/}
}
TY  - JOUR
AU  - A. G. Chentsov
AU  - Ya. V. Salii
TI  - A model of “nonadditive” routing problem where the costs depend on the set of pending tasks
JO  - Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie
PY  - 2015
SP  - 24
EP  - 45
VL  - 8
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/VYURU_2015_8_1_a1/
LA  - en
ID  - VYURU_2015_8_1_a1
ER  - 
%0 Journal Article
%A A. G. Chentsov
%A Ya. V. Salii
%T A model of “nonadditive” routing problem where the costs depend on the set of pending tasks
%J Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie
%D 2015
%P 24-45
%V 8
%N 1
%U http://geodesic.mathdoc.fr/item/VYURU_2015_8_1_a1/
%G en
%F VYURU_2015_8_1_a1
A. G. Chentsov; Ya. V. Salii. A model of “nonadditive” routing problem where the costs depend on the set of pending tasks. Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie, Tome 8 (2015) no. 1, pp. 24-45. http://geodesic.mathdoc.fr/item/VYURU_2015_8_1_a1/

[1] Garey M. R., Johnson D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman and Company, San Francisco, 1979, 338 pp. | MR | MR | Zbl

[2] Melamed I. I., Sergeev S. I., Sigal I. Kh., “The Travelling Salesman Problem. Issues in Theory”, Automation and Remote Control, 50:9 (1989), 1147–1173 | MR | Zbl

[3] Melamed I. I., Sergeev S. I., Sigal I. Kh., “The Travelling Salesman Problem. Exact Methods”, Automation and Remote Control, 50:10 (1989), 1303–1324 | MR | Zbl

[4] Melamed I. I., Sergeev S. I., Sigal I. Kh., “The Travelling Salesman Problem. Approximate Algorithms”, Automation and Remote Control, 50:11 (1989), 1459–1479 | MR | Zbl

[5] Bellman R., “Dynamic Programming Treatment of the Travelling Salesman Problem”, Journal of the ACM, 9:1 (1962), 61–63 | DOI | MR | MR | Zbl

[6] Held M., Karp R., “A Dynamic Programming Approach to Sequencing Problems”, Journal of the Society for Industrial Applied Mathematics, 10:1 (1962), 196–210 | DOI | MR | Zbl

[7] Little J. D., Murty K. G., Sweeney D. W., Karel C., “An Algorithm for the Travelling Salesman Problem”, Operations Research, 11:6 (1963), 972–989 | DOI | Zbl

[8] Gutin G. Z., Punnen A. P. (eds.), The Travelling Salesman Problem and Its Variations, Combinatorial Optimization, 12, Kluwer Academic Publishers, Dordrecht, 2002, 830 pp. | MR

[9] Sergeev S. I., “Algorithms for the Minimax Problem of the Travelling Salesman. I: An Approach Based on Dynamic Programming”, Automation and Remote Control, 56:7 (1995), 1027–1032 | MR | Zbl

[10] Sesekin A. N., Chentsov A. A., Chentsov A. G., “Routing with an Abstract Function of Travel Cost Aggregation”, Proceedings of the IMM UB RAS, 16, no. 3, 2010, 240–264 (in Russian)

[11] Kuratowski K., Mostowski A., Set Theory, North-Holland, Amsterdam, 1967 | MR | MR

[12] Dieudonné J., Foundations of Modern Analysis, Academic Press, N.Y., 1960, 361 pp. | MR | Zbl

[13] Chentsov A. G., A Theoretical Treatment of Extremal Problems in Routing and Scheduling, Regular and Chaotic Dinamics, M.–Izhevsk, 2008, 240 pp.

[14] Chentsov A. A., Chentsov A. G., “Extremal Bottleneck Routing Problem with Constraints in the Form of Precedence Conditions”, Proceedings of the Steklov Institute of Mathematics, 263, no. 2, 2008, 23–36 | DOI | MR | Zbl

[15] Cheblokov I. B., Chentsov A. G., “About one Route Problem with Interior Tasks”, Journal of Udmurt University. Mathematics, Mechanics and Computer Science, 2012, no. 1, 96–119 (in Russian) | Zbl

[16] Chentsov A. G., “To Question of Routing of Works Complexes”, Journal of Udmurt University. Mathematics, Mechanics and Computer Science, 2013, no. 1, 59–82 (in Russian) | Zbl