A new application of the generalized traveling salesman problem in industry 4.0 and 5.0

• Authors: Zerovnik Janez , Herakoviˇc Niko
• Languages of publication: EN

Abstracts

EN

A novel application of the generalized traveling salesman is pro- posed. The practical problem considered is optimization of different optimization criteria in various models of a mixed assembly worksta- tion. Several models that give rise to interesting optimization problems are discussed.

Keywords

EN

Generalized traveling salesman problem; Flexible assembly workstation

• Publisher: Uniwersytet Ekonomiczny w Katowicach
• Journal: Multiple Criteria Decision Making
• Year: 2021
• Volume: 16
• Pages: 153-163

Contributors

author

Zerovnik Janez

• University of Ljubljana, Faculty of Mechanical Engineering, Ljubljana, Slovenia

author

Herakoviˇc Niko

• University of Ljubljana, Faculty of Mechanical Engineering, Ljubljana, Slovenia

References

• Arora S., Lund C., Motwani R., Sudan M., Szegedy M. (1992), Proof Verification and Hardness of Approximation Problems, Proceedings 33rd Annual Symposium on Foundations of Computer Science, 14–23.
• Borgss S.P., La Delfa N.J., Dickerson C.R. (2019), An Evaluation of Off-axis Manual Forces and Upper Extremity Joint Moments during Unilateral Pushing and Pulling Exertions, Advances in Production Engineering & Management, 13(1), 107–117.
• Brest J., ˇZerovnik J. (1999), An Approximation Algorithm for the Asymmetric Traveling Sales-man Problem, Ricerca Operativa, 28, 59–67.
• Brest J., ˇZerovnik J. (2005), A Heuristic for the Asymmetric Traveling Salesman Problem, Proceedings of the 6th Metaheuristics International Conference (MIC ’05), Vienna, Austria, 145–150.
• Christofides N. (1976), Worst-case Analysis of a New Heuristic for the Travelling Salesman Problem, Technical Report 388, Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh, PA.
• de Mattos D.L., Netob R.A., Merinoa E.A.D, Forcellini F.A. (2018), Simulating the Influence of Physical Overload on Assembly Line Performance: A Case Study in an Automotive Electrical Component Plant, Applied Ergonomics, 79, 107–121.
• Dianat I., Molenbroek J., Castellucci H.I. (2018), A Review of the Methodology and Applications of Anthropometry in Ergonomics and Product Design, Ergonomics, 61(12), 1696–1720.
• Elbassioni K., Fishkin A., Sitters R. (2009), Approximation Algorithms for Euclidean Traveling Salesman Problem with Discrete and Continuous Neighbourhoods, Int. J. Comput. Geom. Appl., 19, 173–193.
• Fischetti M., Gonzalez J.J.S., Toth P. (1997), A Branch-and-cut Algorithm for the Symmetric Generalized Traveling Salesman Problem, Oper. Res., 45(3), 378–394.
• Gentilini I., Margot F., Shimada K. (2013), The Travelling Salesman Problem with Neighbour-hoods: MINLP Solution, Optimization Methods and Software, 28(2), 364–378.
• Gulczynski D.J., Heath J.W., Price C.C. (2006), The Close Enough Traveling Salesman Problem: A Discussion of Several Heuristics, Perspectives in Operations Research, 36, 271–283.
• Gutin G., Karapetyan D. (2009), Generalized Traveling Salesman Problem Reduction Algorithms, Algorithmic Operations Research, 4(2), 144–154.
• Helsgaun K. (2015), Solving the Equality Generalized Traveling Salesman Problem Using the Lin-Kernighan-Helsgaun Algorithm, Math. Prog. Comp., 7, 269–287.
• Jaillet P. (1988), A Priori Solution of a Traveling Salesman Problem in which a Random Subset of the Customers Are Visited, Operation Research, 36, 929–936.
• Lahyani R., Khemakhem M., Semet F. (2017), A Unified Matheuristic for Solving Multicon-strained Traveling Salesman Problems with Profits, EURO Journal on Computational Optimization, 5(3), 393–422.
• Lanzottia A., Vanacorea A., Taralloa A., Nathan-Robertsb D., Coccoresec D., Minopolia V., Carbonea F., d’Angelod R., Grassoe C., Di Gironimoa G., Papaa S. (2019), Interactive Tools for Safety 4.0: Virtual Ergonomics and Serious Games in Real Working Contexts, Ergonomics, 63(3), 324–333.
• Laporte G., Asef-Vaziri A., Sriskandarajah C. (1996), Some Applications of the Generalized Travelling Salesman Problem, The Journal of the Operational Research Society, 47(12), 1461–1467.
• Laporte G., Mercure H., Nobert Y. (1987), Generalized Travelling Salesman Problem Throughn sets of Nodes: The Asymmetrical Case, Discrete Applied Mathematics, 18(2), 185–197.
• Leber M., Bastiˇc M., Moody L., Schmidt Krajnc M. (2018), A Study of the Impact of Ergonomically Designed Workplaces on Employee Productivity, Ergonomics, 62(1), 52–64.
• Nobert Y., Laporte G. (1983), Generalized Travelling Salesman Problem through n sets of Nodes: An Integer Programming Approach, INFOR Inf. Syst. Oper. Res., 21(1), 61–75.
• Nogueira H.C., Locks F., Barbieri D.F., Oliveira A.B. (2018), How Does the Biomechanical Exposure of the Upper Body in Manual Box Handling Differ from Exposure in Other Tasks in the Real Industrial Context? International Journal of Industrial Ergonomics, 68, 8–14.
• Noon C.E., Bean J.C. (1991), A Lagrangian Based Approach for the Asymmetric Generalized Traveling Salesman Problem, Oper. Res., 39(4), 623–632.
• Noon C.E., Bean J.C. (1993), An Efficient Transformation of the Generalized Traveling Salesman Problem, INFOR: Information Systems and Operational Research, 31(1), 39–44.
• Pesek I., Schaerf A., ˇZerovnik J. (2007), Hybrid Local Search Techniques for the Resource- constrained Project Scheduling Problem, Lecture Notes in Computer Science, 4771, 57–68.
• Pintea C.M., Pop P.C., Chira C. (2017), The Generalized Traveling Salesman Problem Solved with Ant Algorithms, Complex Adaptive Systems Modeling, 5(8), 1–9.
• Rasmussen C.D.N., Hojberg H., Bengtsen E., Jorgensen M.B. (2018), Identifying Knowledge Gaps between Practice and Research for Implementation Components of Sustainable Interventions to Improve the Working Environment - A Rapid Review, Applied Ergonomics, 67, 178–192.
• Renaud J., Boctor F.F. (1998), An Efficient Composite Heuristic for the Symmetric Generalized Traveling Salesman Problem, Eur. J. Oper. Res., 108(3), 571–584.
• Sahni S., Gonzalez T. (1976), P-complete Approximation Problems, J. Assoc. Comput. Mach., 23, 555–565.
• Silberholz J., Golden B. (2007), The Generalized Traveling Salesman Problem: A New Genetic Algorithm Approach, Springer US, Boston, MA, 165–181.
• Snyder L.V., Daskin M.S. (2006), A Random-key Genetic Algorithm for the Generalized Traveling Salesman Problem, Eur. J. Oper. Res., 174(1), 38–53.
• Svensson O., Tarnawski J., V ́egh L.A. (2020), A Constant-factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem, JACM, 67(6), 37–53.
• Tornstrom L., Amprazis J., Christmansson M., Eklund J. (2008), A Corporate Workplace Model for Ergonomic Assessments and Improvements, Appl. Ergon., 39(2), 219–228.
• Turk M., Pipan M., Simiˇc M., Herakoviˇc N. (2020a), A Smart Algorithm for Personalizing the Workstation in the Assembly Process, Applied Sciences, 10(23), 1–19.
• Turk M., Pipan M., Simiˇc M., Herakoviˇc N. (2020b), Simulation-based Time Evaluation of Basic Manual Assembly Tasks, Advances in Production Engineering & Management, 15(3), 331–344.
• ˇZerovnik J. (1995), A Heuristics for the Probabilistic Traveling Salesman Problem, Proceedings, Symposium on Operation Research ’95, Portoro, Slovenia, 165–172.
• ˇZerovnik J. (2015), Heuristics for NP-hard Optimization Problems Simpler Is Better?!? Logistics & Sustainable Transport, 6(1), 1–10.
• Zupan H., Herakoviˇc N., ˇZerovnik J. (2016), A Heuristic for the Job Shop Scheduling Problem, Bioinspired Optimization Methods and Their Applications: Proceedings of the Seventh International Conference on Bioinspired Optimization Methods and their Applications BIOMA 2016, 187–198.
• (www 1) The set traveling salesman problem. https://en.wikipedia.org/wiki/Set TSP problem (accessed: 11.03.2021).
• (www 2) Travelling salesman problem. https://en.wikipedia.org/wiki/Travelling salesman problem (accessed: 19.02.2020).

Identifiers

ISSN

2084-1531