Abstract
We consider knowledge-oriented models, problems, and algorithms for routing traveling salesmen in complex networks. The formalization leads to models of pseudo-Boolean discrete optimization with constraints that take into account the specifics of the multiple traveling salesmen problem. We consider a class of problems that can be represented in the form of pseudo-Boolean optimization models with separable objective functions (monotone, linear) and constraints in the form of disjunctive normal forms (DNFs). We demonstrate the possibility of an approximate synthesis of DNF constraints based on precedent information. The methodology, theoretical principles, and algorithms for solving problems of this class are presented. It is shown that the solution of routing problems can be based on the application of a multiagent approach in combination with clustering of the original problem, pseudo-Boolean optimization algorithms with disjunctive constraints, and metaheuristics.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
REFERENCES
Antamoshkin, A.A. and Masich, I.S., Search algorithms for pseudo-Boolean optimization, Sist. Upr. Svyazi Bezop., 2016, pp. 103–145.
Germanchuk, M.S., Kozlova, M.G., and Luk’yanenko, V.A., Knowledge-oriented routing models of many traveling salesmen, Intellektualizatsiya obrabotki informatsii. Tez. dokl. 13-i Mezhdunar. konf. (Intellectualization of Information Processing. Proc. 13th Int. Conf.) (Moscow, 2020), pp. 352–355.
Donskoi, V.I. and Bashta, A.I., Diskretnye modeli prinyatiya reshenii pri nepolnoi informatsii (Discrete Decision-Making Models with Incomplete Information), Simferopol: Tavriya, 1992.
Donskoi, V.I., Pseudo-Boolean optimization with a disjunctive constraint, Comput. Math. Math. Phys., 1994, vol. 34, no. 3, pp. 389–398.
Donskoy, V. and Perekhod, I., Multiple criteria models with the linear pseudoboolean functions and disjunctive restrictions, in Multiple Criteria Decision Making. Lecture Notes in Economics and Mathematical Systems. Vol. 448, Fandel, G. and Gal, T., Eds., Berlin–Heidelberg: Springer, 1997. https://doi.org/10.1007/978-3-642-59132-7_2
Donskoy, V.I., A Synthesis of pseudo-Boolean empirical models by precedential information, Bull. SUSU MMCS, 2018, vol. 11, no. 2, pp. 96–107.
Kozlova, M.G., Knowledge-oriented decision making models, Uchen. Zap. Simferopol. Gos. Univ., 1998, no. 7(46), pp. 76–83.
Kozlova, M.G., Multicriteria decision-making models with linear pseudo-Boolean functions and disjunctive constraints, Iskusstv. Intellekt, 2000, no. 2, pp. 67–73.
Kozlova, M.G., Synthesis of tapering requests, Din. Sist., 2000, no. 16, pp. 208–211.
Masich, I.S., Poiskovye algoritmy uslovnoi optimizatsii: monografiya (Search Algorithms for Conditional Optimization: a Monograph), Krasnoyarsk: SibGAU, 2013.
Melamed, I.I., Sergeev, S.I., and Sigal, I.K., The traveling salesman problem. Issues in theory, Autom. Remote Control, 1989, vol. 50, no. 9, pp. 1147–1173.
Melamed, I.I., Sergeev, S.I., and Sigal, I.K., The traveling salesman problem. Exact methods, Autom. Remote Control, 1989, vol. 50, no. 10, pp. 1303–1324.
Melamed, I.I., Sergeev, S.I., and Sigal, I.K., The traveling salesman problem. Approximate algorithms, Autom. Remote Control, 1989, vol. 50, no. 11, pp. 1459–1479.
Germanchuk, M.S., Lemtyuzhnikova, D.V., and Luk’yanenko, V.A., Metaheuristic algorithms for multiagent routing problems, Probl. Upr., 2020, vol. 6, pp. 3–13.
Grama, Y. and Hammer, P.L., Boolean Functions: Theory, Algorithms and Applications, New York: Cambridge Univ. Press, 2011.
Hammer, P.L. and Rudeanu, S., Boolean Methods in Operations Research and Related Areas, Berlin–Heidelberg–New York: Springer-Verlag, 1968.
Foldes, S. and Hammer, P.L., Disjunctive and cojunctive normal forms of pseudo-Boolean functions, Discrete Appl. Math., 2000, no. 107, pp. 1–26.
Boros, E. and Hammer, P.L., Pseudo-Boolean optimization, Discrete Appl. Math., 2002, no. 123, pp. 155–225.
Hammer, P.L., Pseudo-Boolean remarks on balanced graphs, Int. Ser. Numer. Math., 1977, no. 36, pp. 69–78.
Ebenegger, Ch., Hammer, P.L., and de Werra, D., Pseudo-Boolean functions and stability of graphs, Ann. Discrete Math., 1984, no. 19, pp. 83–97.
Zhuravlev, Yu.I., Local algorithms over disjunctive normal forms, Dokl. Akad. Nauk SSSR, 1979, vol. 245, no. 2, pp. 289–292.
Zhuravlev, Yu.I. and Kogan, A.Yu., Implementation of Boolean functions with a small number of zeros by disjunctive normal forms and related problems, Dokl. Akad. Nauk SSSR, 1985, vol. 285, no. 4, pp. 795–799.
Hammer, P.L. and Rudeanu, S., Pseudo-Boolean methods for bivalent programming, Lect. Notes Math., September 2–7, 1966.
Sapozhenko, A.A., On the search for the maximum upper zero of monotone functions on ranked sets, U.S.S.R. Comput. Math. Math. Phys., 1991, vol. 31, no. 12, pp. 79–89.
Germanchuk, M.S., Kozlova, M.G., and Luk’yanenko, V.A., Practical routing problems, Analiz, modelirovanie, upravlenie, razvitie sotsial’no-ekonomicheskikh sistem. Sb. nauch. tr. XI Mezhdunar. shkoly-simpoziuma AMUR (Analysis, Modeling, Management, Development of Socio-Economic Systems. Proc. XI Int. School-Symp. AMUR) (2017), pp. 116–120.
Author information
Authors and Affiliations
Corresponding authors
Additional information
Translated by V. Potapchouck
Rights and permissions
About this article
Cite this article
Germanchuk, M.S., Kozlova, M.G. & Lukianenko, V.A. Pseudo-Boolean Conditional Optimization Models for a Class of Multiple Traveling Salesmen Problems. Autom Remote Control 82, 1651–1667 (2021). https://doi.org/10.1134/S0005117921100040
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1134/S0005117921100040