Solving a routing problem with the aid of an independent computations scheme

A. G. Chentsov ; A. M. Grigoryev ; A. A. Chentsov

Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie, Tome 11 (2018) no. 1, pp. 60-74

Résumé

This paper is devoted to the issues in development and implementation of parallel algorithms for solving practical problems. We consider a routing problem with constraints and complicated cost functions. The visited objects are assumed to be clusters, or megalopolises (nonempty finite sets), and the visit to each one entails certain tasks, which we call interior jobs. The order of visits is subject to precedence constraints. The costs of movements depend on the set of pending tasks (not yet complete at the time of the movement), which is also referred to as "sequence dependence", "position dependence", and "state dependence". Such dependence arises, in particular, in routing problems concerning emergencies at nuclear power plants, similar to the Chernobyl and Fukushima Daiichi incidents. For example, one could consider a disaster recovery problem concerned with sequential dismantlement of radiation sources; in this case, the crew conducting the dismantlement is exposed to the radiation from the sources that have not yet been dealt with. Hence the dependence on pending tasks in the cost functions that measure the crew's radiation exposure. The latter dependence reflects the "shutdown" operations for the corresponding radiation sources. This paper sets forth an approach to a parallel solution for this problem, which was implemented and run on the URAN supercomputer. The results of the computational experiment are presented.

Détail

Keywords: dynamic programming; route; sequencing; precedence constraints; parallel computation.

Bibliographie

[1] Garey M. R., Johnson D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, N.Y., 1979 | MR

[2] Gutin G., Punnen A. P., The Traveling Salesman Problem and Its Variations, Springer, N.Y., 2002 | MR

[3] Cook W. J., In Pursuit of the Traveling Salesman. Mathematics at the Limits of Computation, Princeton University Press, New Jersey, 2012 | MR

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

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

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

[7] Little L. D. C., Murty K. G., Sweeney D. W., Karel C., “An Algorithm for the Travelling Salesman Problem”, Operations Research, 11:6 (1963), 972–990 ; Dzh. Litl, K. Murti, D. Suini, K. Kerel, “Algoritm dlya resheniya zadachi o kommivoyazhere”, Ekonomika i matematicheskie metody, 1:1 (1965), 94–107 | DOI

[8] Bellman R., “Dynamic Programming Treatment of the Travelling Salesman Problem”, Journal of the Association for Computing Machinery, 9 (1962), 61–63 ; R. Bellman, “Primenenie dinamicheskogo programmirovaniya k zadache o kommivoyazhere”, Kiberneticheskii sbornik, 9, Mir, M., 1964, 219–228 | DOI | MR

[9] Held M., Karp R. M., “A Dynamic Programming Approach to Sequencing Problems”, Journal of the Society for Industrial and Applied Mathematics, 10:1 (1962), 196–210 ; M. Kheld, R.M. Karp, “Primenenie dinamicheskogo programmirovaniya k zadacham uporyadocheniya”, Kiberneticheskii sbornik, 9, Mir, M., 1964, 202–218 | DOI | MR

[10] Leon V. J., Peters B. A., “Replanning and Analysis of Partial Setup Strategies in Printed Circuit Board Assembly Systems”, International Journal of Flexible Manufacturing Systems, 8 (1996), 389–411 | DOI

[11] Alkaya A. F., Duman E., “A New Generalization of the Traveling Salesman Problem”, Applied and Computational Mathematics, 9:2 (2010), 162–175 | MR

[12] Kinable J., Cire A., van Hoeve W. J., “Hybrid Optimization Methods for Time-Dependent Sequencing Problems”, European Journal of Operational Research, 259:3 (2017), 887–897 | DOI | MR

[13] Chentsov A. G., Extreme Problems of Routing and Tasks Distribution: Regular and Chaotic Dynamics, Izhevsk Institute of Computer Research, Izhevsk, 2008 (in Russian)

[14] Korobkin V. V., Sesekin A. N., Tashlykov O. L., Chentsov A. G., Routing Methods and Their Applications to the Enhancement of Safety and Efficiency of Nuclear Plant Operation, Novye tekhnologii, M., 2012 (in Russian)

[15] Tashlykov O. L., Personnel Dose Costs in the Nuclear Industry. Analysis. Ways to Decrease. Optimization, LAP LAMBERT Academic Publishing GmbH Co. RG., Saarbruke, 2011

[16] Petunin A. A., “About Some Strategies of the Tool Path Modelling at the Control Programs Generation for the Flame Cutting Machines”, Vestnik UGATU, 13:2 (2009), 280–286 (in Russian)

[17] Petunin A. A., Chentsov A. G., Chentsov P. A., “On Routing Tool Motion on the Sheet Cutting NPC Machines”, St. Petersburg State Polytechnical University Journal. Computer Science. Telecommunication and Control Systems, 2013, no. 2, 103–111 (in Russian)

[18] Frolovskii V. D., “Computer-Aided Design of the Control Programs for Thermal Metal Cutting on NPC Machines”, The scientific and technical journal “Information Technology of Cad/Cam/Cae” (ITDP), 2005, no. 4, 63–66 (in Russian)

[19] Wang G. G., Xie S. Q., “Optimal Process Planning for a Combined Punch-and-Laser Cutting Machine Using ant Colony Optimization”, International Journal of Production Research, 43:11 (2005), 2195–2216 | DOI

[20] Dewil R., Vansteenwegen P., Cattrysse D., “Construction Heuristics for Generating Tool Paths for Laser Cutters”, International Journal of Production Research, 52:20 (2014), 1–20 | DOI

[21] Chentsov A. G., Chentsov P. A., “Routing Under Constraints: Problem of Visit to Megalopolises”, Automation and Remote Control, 77:11 (2016), 1957–1974 | DOI | MR

[22] Dieudonne J., Foundations of Modern Analysis, Academic, N.Y., 1960 | MR

[23] Cormen T. H., Leizerson C. E., Rivest R. L., Introduction to Algorithms, MIT Press, Cambridge, 1990 | MR

[24] Chentsov A. G., “To Question of Routing of Works Complexes”, Vestnik Udmurtskogo universiteta. Matematika. Mekhanika. Kompyuternye nauki, 2013, no. 1, 59–82 (in Russian) | DOI | MR

[25] Chentsov A. G., Chentsov A. A., “Route Problem with Constraints Depending on a List of Tasks”, Doklady Mathematics, 92:3 (2015), 685–688 | DOI | MR

[26] Chentsov A. G., Chentsov A. A., “On the Problem of Obtaining the Value of Routing Problem with Constraints”, Journal of Automation and Information Sciences, 6 (2016), 41–54 | MR

[27] Lawler E. L., “Efficient Implementation of Dynamic Programming Algorithms for Sequencing Problems”, CWI Technical report. Stichting Mathematisch Centrum. Mathematische Besliskunde-BW, 106:79 (1979), 1–16

[28] Chentsov A. G., “One Parallel Procedure for the Construction of the Bellman Function in the Generalized Problem of the Courier with the Inner Workings”, Automation and Remote Control, 3 (2012), 134–149 | MR

[29] Chentsov A. G., “One Parallel Procedure for the Construction of the Bellman Function in the Generalized Problem of the Courier with the Inner Workings”, Bulletin of the South Ural State University. Series: Mathematical Modelling, Programming and Computer Software, 2012, no. 18(277), 53–76 (in Russian) | MR

[30] Chentsov A. G., Grigoryev A. M., “Dynamic Programming Method in the Route Problem: the Scheme of Independent Calculations”, Mekhatronika, avtomatizatsiya, upravlenie, 17:12 (2016), 834–846 | DOI

[31] Schmidt G., Strohlein T., Relations and Graphs: Discrete Mathematics for Computer Scientists, EATCS Monographs on Theoretical Computer Science, Springer-Verlag, London, 1993 | MR

[32] Steiner G., “On the Complexity of Dynamic Programming for Sequencing Problems with Precedence Constraints”, Annals of Operations Research, 26:1 (1990), 103–123 | DOI | MR