About a routing problem of the tool motion on sheet cutting

A. A. Petunin ; A. G. Chentsov ; P. A. Chentsov

Modelirovanie i analiz informacionnyh sistem, Tome 22 (2015) no. 2, pp. 278-294.

Résumé

For the routing problem of tool permutations under the thermal cutting of parts from sheet material realized on CNC machines, questions connected with constructing precise (optimal) and heuristic algorithms used on the stage of mathematical simulation of route elements under sequential megalopolises circuit are investigated. Cutting points and points of tool cut-off are items (cities) of the above-mentioned megalopolises. In each megalopolis, interior works are provided. These works are connected with motion to the equidistant curve of the cut contour of a part from the cutting point and (with cutting completed) with motion from the equidistant curve to the tool cut-off (we keep in mind a working run). The problem about the time-optimal process of cutting which is a special variant of the generalized courier problem is investigated (the problem of the routing on the megalopolises with precedence conditions). An optimal procedure based on the dynamic programming and an effective heuristic algorithm realized on a multicore computer are proposed. A dynamic programming based procedure uses a special extension of the main problem. This extension provides the replacement of admissibility by precedence with the admissibility by deletion (from the list of tasks). Precedence conditions are used for decreasing computational complexity: it excludes the building of the whole array of the Bellman function values (this function is replaced by the layers system).

Détail

Keywords: routing problem, preceding condition.

Bibliographie

[1] Melamed I. I., Sergeev S. I., Sigal I. Kh., “The traveling salesman problem. Issues in theory”, Automation and Remote Control, 50:9 (1989), 1147–1173 | MR | Zbl

[2] Melamed I. I., Sergeev S. I., Sigal I. Kh., “The traveling salesman's problem. Exact methods”, Automation and Remote Control, 50:10 (1989), 1303–1324 | MR | Zbl

[3] Melamed I. I., Sergeev S.I., Sigal I. Kh., “The traveling salesman problem. Approximate algorithms”, Automation and Remote Control, 50:11 (1989), 1459–1479 | MR | Zbl

[4] Sigal I. Kh., “A decomposition approach to solving a travelling salesman problem of lange dimensionality and some applications”, Soviet journal of Computer and Systems Sciences, 1991, no. 6, 48–60 | MR | Zbl

[5] Schrijver A, Combinatorial Optimization, Springer, Berlin, 2003, 648 pp. | Zbl

[6] Chentsov A. G., Ekstremalnye zadachi marshrutizatsii i raspredeleniya zadaniy: voprosy teorii, NITs “Regulyarnaya i khaoticheskaya dinamika”. Izhevskiy institut kompyuternykh issledovaniy, M.–Izhevsk, 2008, 240 pp. (in Russian)

[7] Petunin A. A., “O nekotorykh strategiyakh formirovaniya marshruta instrumenta pri razrabotke upravlyayushchikh programm dlya mashin termicheskoy rezki materiala”, Vestnik UGATU. Ser. Upravlenie, vychislitelnaya tekhnika i informatika, 13:2(35) (2009), 280–286 (in Russian)

[8] Chentsov A. G., “K voprosu o marshrutizatsii kompleksov rabot”, Vestn. UdGU. Matematika. Mekhanika. Kompyuternye nauki, 2013, no. 1, 59–82 (in Russian) | Zbl

[9] Burkard R., Dell'Amico M., Martello S., Assignment Problem, SIAM, Philadelphia, 2009, 382 pp. | MR

[10] Gutin G., Punnen A., The Traveling Salesman Problem and Its Variations, Springer, Berlin, 2002, 850 pp. | MR

[11] Chentsov A. A., Chentsov A. G., “Dynamic Programming Method in the Generalized Traveling Salesman Problem: The Influence of Inexact Calculations”, Mathl. Comput. Modelling, 33 (2001), 801–819 | MR | Zbl

[12] Chentsov A. G., Korotayeva L. N., “The Dynamic Programming Method in the Generalized Salesman Problem”, Mathl. Comput. Modelling, 25:1 (1997), 93–105 | DOI | MR | Zbl

[13] Renaud J., Boctor F. F., Ouenniche J., “A heuristic for the pickup and delivery traveling salesman problem”, Computers Operations Research, 27:9 (2000), 905–916 | DOI | MR | Zbl

[14] Garey M., Johnson D., Computers and Intractability: A Guide to the Theory of NP-Completeness, ed. W. H. Freeman, 1979, 338 pp. ; Geri M., Dzhonson D., Vychislitelnye mashiny i trudnoreshaemye zadachi, Mir, M., 1982, 416 pp. | MR | MR

[15] Bellman R., “On a Routing Problem”, Quart. Appl. Math., 16 (1958), 87–90 | MR | Zbl

[16] 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 | DOI | MR | Zbl

[17] Castelino K., D'Souza R., Wright P., “Toolpath optimization for minimizing airtime during machining”, Journal of Manufacturing Systems, 22:3 (2003), 173–180 | DOI

[18] Dewil R., Vansteenwegen P., Cattrysse D., “Cutting Path Optimization Using Tabu Search”, Key Engineering Materials, 473 (2011), 739–748 | DOI

[19] Jing Y., Zhige C., “An Optimized Algorithm of Numerical Cutting-Path Control in Garment Manufacturing”, Advanced Materials Research, 796 (2013), 454–457 | DOI

[20] 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

[21] Kuratowski K., Mostowski A., Set Theory, North-Holland Publishing Company, Amsterdam, 1967, 417 pp. | MR | MR

[22] Dieudonne J., Foundations of Modern Analysis, Academic Press, New York, 1960, 361 pp. | MR | MR | Zbl

[23] Warga J., Optimal Control of Differential and Functional Equations, Academic Press, 1972, 546 pp. | MR | MR | Zbl

[24] Cormen Th. H., Leiserson Ch. E., Rivest R. L., Introduction to Algorithms, MIT Press and McGraw-Hill, 1990 | MR | Zbl

[25] Engelking R., General Topology, Polish Scientific Publishers, 1977, 626 pp. | MR | MR | Zbl

[26] Dewil R., Vansteenwegen P., Cattrysse D., “Construction heuristics for generating tool paths for laser cutters”, International Journal of Production Research, 2014, 1–20