{"id":362180,"date":"2024-05-21T01:29:24","date_gmt":"2024-05-21T01:29:24","guid":{"rendered":"http:\/\/savepearlharbor.com\/?p=362180"},"modified":"-0001-11-30T00:00:00","modified_gmt":"2024-05-21T01:29:24","slug":"","status":"publish","type":"post","link":"https:\/\/savepearlharbor.com\/?p=362180","title":{"rendered":"<span>\u041f\u043b\u0430\u043d\u0438\u0440\u0443\u0435\u043c \u043f\u0443\u0442\u0435\u0448\u0435\u0441\u0442\u0432\u0438\u0435 \u2014 \u0437\u0430\u0434\u0430\u0447\u0430 \u043a\u043e\u043c\u043c\u0438\u0432\u043e\u044f\u0436\u0435\u0440\u0430 (TSP) \u0434\u043b\u044f \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u044f \u043e\u043f\u0442\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u043c\u0430\u0440\u0448\u0440\u0443\u0442\u0430<\/span>"},"content":{"rendered":"<div><!--[--><!--]--><\/div>\n<div id=\"post-content-body\">\n<div>\n<div class=\"article-formatted-body article-formatted-body article-formatted-body_version-2\">\n<div xmlns=\"http:\/\/www.w3.org\/1999\/xhtml\">\n<figure class=\"\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/post_images\/390\/048\/575\/39004857571b77d62f2c449b916f93d3.png\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/390\/048\/575\/39004857571b77d62f2c449b916f93d3.png\"\/><\/figure>\n<p>\u0421 \u0432\u0430\u043c\u0438 \u0410\u043b\u0435\u043a\u0441\u0435\u0439 \u041b\u043e\u0436\u043a\u0438\u043d\u0441, \u044d\u043a\u0441\u043f\u0435\u0440\u0442 \u043f\u043e \u0430\u043d\u0430\u043b\u0438\u0437\u0443 \u0434\u0430\u043d\u043d\u044b\u0445 \u0438 \u043c\u0430\u0448\u0438\u043d\u043d\u043e\u043c\u0443 \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u044e \u0432 \u041f\u0413\u041a \u0414\u0438\u0434\u0436\u0438\u0442\u0430\u043b. \u041c\u044b \u0440\u0430\u0437\u0440\u0430\u0431\u0430\u0442\u044b\u0432\u0430\u0435\u043c \u0446\u0438\u0444\u0440\u043e\u0432\u044b\u0435 \u043f\u0440\u043e\u0434\u0443\u043a\u0442\u044b \u0434\u043b\u044f \u043b\u043e\u0433\u0438\u0441\u0442\u0438\u0447\u0435\u0441\u043a\u043e\u0439 \u043e\u0442\u0440\u0430\u0441\u043b\u0438, \u0432 \u043f\u0435\u0440\u0432\u0443\u044e \u043e\u0447\u0435\u0440\u0435\u0434\u044c, \u0434\u043b\u044f \u0436\/\u0434 \u043f\u0435\u0440\u0435\u0432\u043e\u0437\u043e\u043a.<\/p>\n<p>\u0412 \u043a\u0443\u043b\u0443\u0430\u0440\u0430\u0445 \u043c\u043e\u0441\u043a\u043e\u0432\u0441\u043a\u043e\u0433\u043e \u043e\u0444\u0438\u0441\u0430 \u041f\u0413\u041a \u043c\u044b \u043e\u0431\u0441\u0443\u0436\u0434\u0430\u0435\u043c \u0438 \u043d\u0435\u0440\u0430\u0431\u043e\u0447\u0438\u0435 \u0442\u0435\u043c\u044b. \u0422\u043e\u043f\u043e\u0432\u0443\u044e \u0441\u0442\u0440\u043e\u0447\u043a\u0443 \u0432 \u0442\u0435\u043c\u0430\u0445 \u043d\u0435\u0444\u043e\u0440\u043c\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u043e\u0431\u0449\u0435\u043d\u0438\u044f \u0437\u0430\u043d\u0438\u043c\u0430\u0435\u0442 \u043e\u0442\u043f\u0443\u0441\u043a. \u041c\u044b \u0440\u0435\u0448\u0438\u043b\u0438 \u0440\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0435\u0442\u044c \u0437\u0430\u0434\u0430\u0447\u0443 \u043f\u043b\u0430\u043d\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f \u043e\u0442\u043f\u0443\u0441\u043a\u0430, \u043a\u0430\u043a \u0437\u0430\u0434\u0430\u0447\u0443 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u0438 \u043c\u0430\u0440\u0448\u0440\u0443\u0442\u0430 \u043f\u043e \u0432\u044b\u0431\u0440\u0430\u043d\u043d\u044b\u043c \u0434\u043e\u0441\u0442\u043e\u043f\u0440\u0438\u043c\u0435\u0447\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044f\u043c. \u0414\u043b\u044f \u044d\u0442\u043e\u0433\u043e \u0432\u043e\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043b\u0438\u0441\u044c \u043a\u043b\u0430\u0441\u0441\u0438\u0447\u0435\u0441\u043a\u043e\u0439 \u043f\u043e\u0441\u0442\u0430\u043d\u043e\u0432\u043a\u043e\u0439 \u0437\u0430\u0434\u0430\u0447\u0438 \u043a\u043e\u043c\u043c\u0438\u0432\u043e\u044f\u0436\u0435\u0440\u0430.<\/p>\n<p>\u041c\u043e\u0434\u0435\u043b\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435 \u043c\u0430\u0440\u0448\u0440\u0443\u0442\u0430 \u0432 \u0432\u0438\u0434\u0435 \u0437\u0430\u0434\u0430\u0447\u0438 \u043a\u043e\u043c\u043c\u0438\u0432\u043e\u044f\u0436\u0435\u0440\u0430 \u043f\u043e\u0437\u0432\u043e\u043b\u0438\u0442 \u043f\u043e\u0441\u0442\u0440\u043e\u0438\u0442\u044c \u043c\u0430\u0440\u0448\u0440\u0443\u0442 \u043f\u043e \u0432\u0441\u0435\u043c \u0437\u0430\u043f\u043b\u0430\u043d\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u043c \u043b\u043e\u043a\u0430\u0446\u0438\u044f\u043c \u0431\u0435\u0437 \u043f\u043e\u0432\u0442\u043e\u0440\u0435\u043d\u0438\u0439 \u0441 \u0437\u0430\u0434\u0430\u043d\u043d\u044b\u043c \u043a\u0440\u0438\u0442\u0435\u0440\u0438\u0435\u043c \u043a\u0430\u0447\u0435\u0441\u0442\u0432\u0430 (\u0432\u0440\u0435\u043c\u044f, \u0441\u0442\u043e\u0438\u043c\u043e\u0441\u0442\u044c). \u0420\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u043f\u043e\u0434\u0445\u043e\u0434\u043e\u0432 \u043a \u0440\u0435\u0448\u0435\u043d\u0438\u044e \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u043e\u043d\u043d\u043e\u0439 \u0437\u0430\u0434\u0430\u0447\u0438 (TSP) \u0441 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u0435\u043c \u043f\u0430\u043a\u0435\u0442\u0430 ORTools.<\/p>\n<h2>\u041e \u0437\u0430\u0434\u0430\u0447\u0435 \u043a\u043e\u043c\u043c\u0438\u0432\u043e\u044f\u0436\u0435\u0440\u0430 (TSP)<\/h2>\n<p>\u0414\u043e\u0441\u0442\u0430\u0432\u043a\u0430 \u0440\u0430\u0437\u043d\u044b\u0445 \u0442\u043e\u0432\u0430\u0440\u043e\u0432 \u043e\u0447\u0435\u043d\u044c \u043f\u043e\u043f\u0443\u043b\u044f\u0440\u043d\u0430\u044f \u0443\u0441\u043b\u0443\u0433\u0430 \u0441\u0435\u0433\u043e\u0434\u043d\u044f. \u0427\u0442\u043e\u0431\u044b \u0441\u043d\u0438\u0437\u0438\u0442\u044c \u0441\u0435\u0431\u0435\u0441\u0442\u043e\u0438\u043c\u043e\u0441\u0442\u044c \u0438 \u0446\u0435\u043d\u0443 \u043d\u0430 \u0443\u0441\u043b\u0443\u0433\u0438 \u0434\u043b\u044f \u043f\u043e\u0442\u0440\u0435\u0431\u0438\u0442\u0435\u043b\u044f, \u0437\u0430\u043a\u0430\u0437\u044b \u043e\u0431\u044a\u0435\u0434\u0438\u043d\u044f\u044e\u0442 \u0438 \u0434\u043e\u0441\u0442\u0430\u0432\u043b\u044f\u044e\u0442\u0441\u044f \u043e\u0434\u043d\u0438\u043c \u043a\u0443\u0440\u044c\u0435\u0440\u043e\u043c. \u0417\u0434\u0435\u0441\u044c \u043f\u043e\u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0442\u0430\u043a \u043d\u0430\u0437\u044b\u0432\u0430\u0435\u043c\u044b\u0439 \u044d\u0444\u0444\u0435\u043a\u0442 \u043c\u0430\u0441\u0448\u0442\u0430\u0431\u0430, \u043a\u043e\u0433\u0434\u0430 \u0441\u0435\u0431\u0435\u0441\u0442\u043e\u0438\u043c\u043e\u0441\u0442\u044c \u0434\u043e\u0441\u0442\u0430\u0432\u043a\u0438 \u0435\u0434\u0438\u043d\u0438\u0446\u044b \u0437\u0430\u043a\u0430\u0437\u0430 \u0441\u043d\u0438\u0436\u0430\u0435\u0442\u0441\u044f \u0441 \u0443\u0432\u0435\u043b\u0438\u0447\u0435\u043d\u0438\u0435\u043c \u0438\u0445 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0430.<\/p>\n<p>\u041f\u0440\u0438 \u0440\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0435\u043d\u0438\u0438 \u043e\u0434\u043d\u043e\u0433\u043e \u043a\u0443\u0440\u044c\u0435\u0440\u0430 \u0438 \u043f\u0443\u043b\u0430 \u0437\u0430\u043a\u0430\u0437\u043e\u0432, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043e\u043d \u0434\u043e\u043b\u0436\u0435\u043d \u0434\u043e\u0441\u0442\u0430\u0432\u0438\u0442\u044c, \u0432\u043e\u0437\u043d\u0438\u043a\u0430\u0435\u0442 \u043a\u043b\u0430\u0441\u0441\u0438\u0447\u0435\u0441\u043a\u0430\u044f \u0437\u0430\u0434\u0430\u0447\u0430 \u043a\u043e\u043c\u043c\u0438\u0432\u043e\u044f\u0436\u0435\u0440\u0430. \u0412 \u0431\u043e\u043b\u0435\u0435 \u0441\u043b\u043e\u0436\u043d\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435, \u043a\u043e\u0433\u0434\u0430 \u0443 \u043d\u0430\u0441 \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u043a\u0443\u0440\u044c\u0435\u0440\u043e\u0432, \u0437\u0430\u0434\u0430\u0447\u0430 \u043a\u043e\u043c\u043c\u0438\u0432\u043e\u044f\u0436\u0435\u0440\u0430 \u044d\u0432\u043e\u043b\u044e\u0446\u0438\u043e\u043d\u0438\u0440\u0443\u0435\u0442 \u0432 <a href=\"https:\/\/en.wikipedia.org\/wiki\/Vehicle_routing_problem\">vehicle routing problem<\/a>, \u043d\u043e \u044d\u0442\u043e \u0443\u0436\u0435 \u0434\u0440\u0443\u0433\u0430\u044f \u0438\u0441\u0442\u043e\u0440\u0438\u044f.<\/p>\n<p>\u0417\u0434\u0435\u0441\u044c \u0440\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u0437\u0430\u0434\u0430\u0447\u0438 \u043a\u043e\u043c\u043c\u0438\u0432\u043e\u044f\u0436\u0435\u0440\u0430 \u0434\u043b\u044f \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u044f \u0442\u0443\u0440\u0438\u0441\u0442\u0438\u0447\u0435\u0441\u043a\u043e\u0433\u043e \u043c\u0430\u0440\u0448\u0440\u0443\u0442\u0430 \u043d\u0430 \u043f\u0440\u0438\u043c\u0435\u0440\u0435 \u043b\u043e\u043a\u0430\u0446\u0438\u0439 \u043d\u0430 \u0442\u0435\u0440\u0440\u0438\u0442\u043e\u0440\u0438\u0438 \u0420\u043e\u0441\u0441\u0438\u0438. \u0422\u0440\u0435\u0431\u043e\u0432\u0430\u043d\u0438\u044f \u043a \u043c\u0430\u0440\u0448\u0440\u0443\u0442\u0443 \u043c\u043e\u0433\u0443\u0442 \u0431\u044b\u0442\u044c \u0440\u0430\u0437\u043d\u044b\u043c\u0438, \u0440\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u043d\u0430\u0438\u0431\u043e\u043b\u0435\u0435 \u043f\u043e\u043f\u0443\u043b\u044f\u0440\u043d\u044b\u0435: \u0441\u0430\u043c\u044b\u0439 \u0431\u044b\u0441\u0442\u0440\u044b\u0439 \u0438\u043b\u0438 \u0441\u0430\u043c\u044b\u0439 \u0434\u0435\u0448\u0435\u0432\u044b\u0439.<\/p>\n<h2>\u0422\u0443\u0440\u0438\u0441\u0442\u0438\u0447\u0435\u0441\u043a\u0438\u0435 \u043b\u043e\u043a\u0430\u0446\u0438\u0438: \u0434\u0430\u043d\u043d\u044b\u0435<\/h2>\n<p>\u041a\u0443\u0434\u0430 \u043c\u044b \u0445\u043e\u0442\u0438\u043c \u043f\u043e\u0435\u0445\u0430\u0442\u044c? \u0421\u043e\u0431\u0435\u0440\u0435\u043c \u043f\u043e\u0436\u0435\u043b\u0430\u043d\u0438\u044f \u0432 \u0441\u043f\u0438\u0441\u043e\u043a. \u0414\u0430\u0440\u044c\u044f \u0412\u0430\u0441\u0438\u043b\u044c\u0435\u0432\u0430 (\u043a\u043e\u043e\u0440\u0434\u0438\u043d\u0430\u0442\u043e\u0440 \u0443\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u0438\u044f \u0430\u043d\u0430\u043b\u0438\u0437\u0430 \u0434\u0430\u043d\u043d\u044b\u0445 \u0438 \u043c\u0430\u0448\u0438\u043d\u043d\u043e\u0433\u043e \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u044f)\u043f\u043e\u0434\u0433\u043e\u0442\u043e\u0432\u0438\u043b\u0430 \u0441\u0432\u043e\u0439 \u0432\u0430\u0440\u0438\u0430\u043d\u0442 \u0442\u0430\u043a\u043e\u0433\u043e \u0441\u043f\u0438\u0441\u043a\u0430, \u0441 \u043a\u043e\u0442\u043e\u0440\u044b\u043c \u043c\u043e\u0436\u043d\u043e \u043e\u0437\u043d\u0430\u043a\u043e\u043c\u0438\u0442\u044c\u0441\u044f <a href=\"https:\/\/github.com\/Lozkins\/mos\/blob\/master\/data\/06_tsp_coord.csv\">\u0437\u0434\u0435\u0441\u044c<\/a>, \u043e\u0442\u0434\u0435\u043b\u044c\u043d\u043e\u0435 \u0441\u043f\u0430\u0441\u0438\u0431\u043e \u0435\u0439 \u0437\u0430 \u044d\u0442\u043e! \u041f\u043e\u043c\u0438\u043c\u043e \u043b\u043e\u043a\u0430\u0446\u0438\u0439 \u043f\u043e\u0442\u0440\u0435\u0431\u0443\u044e\u0442\u0441\u044f \u0440\u0435\u0431\u0440\u0430 &#8212; \u0441\u0432\u044f\u0437\u044c \u043c\u0435\u0436\u0434\u0443 \u043b\u043e\u043a\u0430\u0446\u0438\u044f\u043c\u0438.<\/p>\n<figure class=\"\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/post_images\/eb4\/182\/00c\/eb418200c65a8d09c124da29dda34bdc.png\" alt=\"\u0420\u0435\u043a\u043e\u043c\u0435\u043d\u0434\u0443\u0435\u043c\u044b\u0435 \u043b\u043e\u043a\u0430\u0446\u0438\u0438 \u043a \u043f\u043e\u0441\u0435\u0449\u0435\u043d\u0438\u044e\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/eb4\/182\/00c\/eb418200c65a8d09c124da29dda34bdc.png\"\/><\/p>\n<div><figcaption>\u0420\u0435\u043a\u043e\u043c\u0435\u043d\u0434\u0443\u0435\u043c\u044b\u0435 \u043b\u043e\u043a\u0430\u0446\u0438\u0438 \u043a \u043f\u043e\u0441\u0435\u0449\u0435\u043d\u0438\u044e<\/figcaption><\/div>\n<\/figure>\n<p>\u0420\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u043d\u0435\u043f\u043e\u043b\u043d\u044b\u0439 \u0433\u0440\u0430\u0444 (\u0432\u043e\u0437\u043c\u043e\u0436\u043d\u044b \u043d\u0435 \u0432\u0441\u0435 \u0441\u043e\u0435\u0434\u0438\u043d\u0435\u043d\u0438\u044f \u043c\u0435\u0436\u0434\u0443 \u0433\u043e\u0440\u043e\u0434\u0430\u043c\u0438, \u0430 \u043d\u0430\u0438\u0431\u043e\u043b\u0435\u0435 \u0440\u0430\u0446\u0438\u043e\u043d\u0430\u043b\u044c\u043d\u044b\u0435 \u0440\u0435\u0431\u0440\u0430). \u0413\u0435\u043e\u0433\u0440\u0430\u0444\u0438\u044f \u043f\u0440\u0435\u0434\u043b\u0430\u0433\u0430\u0435\u043c\u044b\u0445 \u043c\u0435\u0441\u0442 \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u043e\u0431\u0448\u0438\u0440\u043d\u0430\u044f, \u0438 \u0432\u0440\u0435\u043c\u044f \u0441\u043b\u0435\u0434\u043e\u0432\u0430\u043d\u0438\u044f \u0436\/\u0434 \u0438\u043b\u0438 \u0430\u0432\u0442\u043e \u0442\u0440\u0430\u043d\u0441\u043f\u043e\u0440\u0442\u043e\u043c \u043c\u043e\u0436\u0435\u0442 \u0437\u0430\u043d\u0438\u043c\u0430\u0442\u044c \u0440\u0430\u0431\u043e\u0447\u0443\u044e \u043d\u0435\u0434\u0435\u043b\u044e, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u0441\u0434\u0435\u043b\u0430\u043b\u0438 \u0430\u043a\u0446\u0435\u043d\u0442 \u043d\u0430 \u0430\u0432\u0438\u0430\u043f\u0435\u0440\u0435\u0432\u043e\u0437\u043a\u0438. \u0415\u0441\u043b\u0438 \u0445\u043e\u0442\u0438\u0442\u0435 \u043d\u0430\u0441\u044b\u0442\u0438\u0442\u044c \u043f\u043e\u0435\u0437\u0434\u043a\u0443 \u0436\/\u0434 \u0430\u043d\u0442\u0443\u0440\u0430\u0436\u0435\u043c, \u0442\u043e \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u043d\u0430\u043f\u043e\u043b\u043d\u0438\u0442\u044c \u0432\u0445\u043e\u0434\u043d\u044b\u0435 \u0434\u0430\u043d\u043d\u044b\u0435 \u0442\u0430\u0440\u0438\u0444\u0430\u043c\u0438 \u0438 \u0432\u0440\u0435\u043c\u0435\u043d\u0435\u043c \u0432 \u0445\u043e\u0434\u0443 \u0434\u043b\u044f \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u0443\u044e\u0449\u0438\u0445 \u0440\u0435\u0431\u0435\u0440. \u041c\u043e\u0434\u0435\u043b\u044c \u043c\u043e\u0436\u043d\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u0438 \u0434\u043b\u044f \u0433\u0440\u0443\u0437\u043e\u043f\u0435\u0440\u0435\u0432\u043e\u0437\u043e\u043a \u043f\u043e \u0436\u0435\u043b\u0435\u0437\u043d\u043e\u0439 \u0434\u043e\u0440\u043e\u0433\u0435 \u0432 \u0442\u043e\u043c \u0447\u0438\u0441\u043b\u0435. \u0421 \u0433\u0440\u0430\u0444\u043e\u043c \u0434\u043e\u043f\u0443\u0441\u0442\u0438\u043c\u044b\u0445 \u043f\u0435\u0440\u0435\u043c\u0435\u0449\u0435\u043d\u0438\u0439 \u043c\u043e\u0436\u043d\u043e \u043e\u0437\u043d\u0430\u043a\u043e\u043c\u0438\u0442\u044c\u0441\u044f <a href=\"https:\/\/github.com\/Lozkins\/mos\/blob\/master\/data\/06_tsp_dist.csv\">\u0437\u0434\u0435\u0441\u044c<\/a>.<\/p>\n<figure class=\"\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/post_images\/c78\/089\/eb5\/c78089eb5a3fd31e1fbe038a0d7b4fea.png\" alt=\"\u0420\u0435\u0431\u0440\u0430 \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u0435\u043c\u043e\u0433\u043e \u0433\u0440\u0430\u0444\u0430\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/c78\/089\/eb5\/c78089eb5a3fd31e1fbe038a0d7b4fea.png\"\/><\/p>\n<div><figcaption>\u0420\u0435\u0431\u0440\u0430 \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u0435\u043c\u043e\u0433\u043e \u0433\u0440\u0430\u0444\u0430<\/figcaption><\/div>\n<\/figure>\n<h2>\u0422\u0435\u0445\u043d\u0438\u0447\u0435\u0441\u043a\u0438\u0439 \u0441\u0442\u044d\u043a<\/h2>\n<p>\u041f\u0440\u0435\u0436\u0434\u0435 \u0447\u0435\u043c \u043f\u0435\u0440\u0435\u0445\u043e\u0434\u0438\u0442\u044c \u043a \u0442\u0435\u0445\u043d\u0438\u0447\u0435\u0441\u043a\u043e\u0439 \u0447\u0430\u0441\u0442\u0438, \u043e\u0431\u0441\u0443\u0434\u0438\u043c \u0438\u043d\u0441\u0442\u0440\u0443\u043c\u0435\u043d\u0442\u044b \u0438 \u043f\u043e\u0434\u0445\u043e\u0434. \u041c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u0438\u0439 \u0430\u043f\u043f\u0430\u0440\u0430\u0442 \u0434\u043b\u044f \u043c\u043e\u0434\u0435\u043b\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f \u0437\u0430\u0434\u0430\u0447\u0438 &#8212; \u0446\u0435\u043b\u043e\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u043e\u0435 \u043b\u0438\u043d\u0435\u0439\u043d\u043e\u0435 \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435 (ILP), \u043e\u0442\u043d\u043e\u0441\u0438\u0442\u0441\u044f \u043a \u0442\u043e\u0447\u043d\u044b\u043c \u043c\u0435\u0442\u043e\u0434\u0430\u043c. \u041f\u043e\u0441\u0442\u0430\u043d\u043e\u0432\u043a\u0430 \u0432 ILP \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u043f\u0440\u0438\u043c\u0435\u043d\u0438\u0442\u044c \u0443\u0436\u0435 \u0433\u043e\u0442\u043e\u0432\u044b\u0435 \u043f\u0430\u043a\u0435\u0442\u044b (\u0441\u043e\u043b\u0432\u0435\u0440\u044b) \u0434\u043b\u044f \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u043e\u043d\u043d\u043e\u0439 \u0437\u0430\u0434\u0430\u0447\u0438 \u0438 \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c \u0442\u043e\u0447\u043d\u043e\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u043d\u0430 \u0432\u044b\u0445\u043e\u0434\u0435.<\/p>\n<p>\u0421\u043e\u043b\u0432\u0435\u0440\u044b \u043c\u043e\u0436\u043d\u043e \u0440\u0430\u0437\u0434\u0435\u043b\u0438\u0442\u044c \u043d\u0430 \u0431\u0435\u0441\u043f\u043b\u0430\u0442\u043d\u044b\u0435 open-source \u0441\u043e\u043b\u0432\u0435\u0440\u044b (cbc, scip, highs, glpk \u0438 \u0434\u0440.) \u0438 \u043a\u043e\u043c\u043c\u0435\u0440\u0447\u0435\u0441\u043a\u0438\u0435 (gurobi, copt, cplex, optverse \u0438 \u0434\u0440.). \u0422\u0430\u043a \u043a\u0430\u043a \u0441\u043e\u043b\u0432\u0435\u0440\u044b \u043f\u0440\u0438\u043c\u0435\u043d\u044f\u044e\u0442\u0441\u044f \u0442\u043e\u043b\u044c\u043a\u043e \u0434\u043b\u044f \u043c\u043e\u0434\u0435\u043b\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f \u0438 \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u0437\u0430\u0434\u0430\u0447, \u0442\u043e \u0441\u043f\u0435\u043a\u0442\u0440 \u043e\u0442\u043b\u0438\u0447\u0438\u0439 \u0443 \u043d\u0438\u0445 \u043d\u0435 \u0431\u043e\u043b\u044c\u0448\u043e\u0439: API \u0438 \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c. \u0412\u043e\u043f\u0440\u043e\u0441 API \u0440\u0435\u0448\u0430\u0435\u0442\u0441\u044f \u0441\u0442\u043e\u0440\u043e\u043d\u043d\u0438\u043c\u0438 \u043e\u0431\u0435\u0440\u0442\u043a\u0430\u043c\u0438 \u043d\u0430\u0434 \u0441\u043e\u043b\u0432\u0435\u0440\u0430\u043c\u0438, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u044e\u0442 \u043c\u043e\u0434\u0435\u043b\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0438 \u043f\u043e\u0434\u043a\u043b\u044e\u0447\u0430\u0442\u044c \u0440\u0430\u0437\u043b\u0438\u0447\u043d\u044b\u0435 \u0441\u043e\u043b\u0432\u0435\u0440\u044b \u0434\u043b\u044f \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u0437\u0430\u0434\u0430\u0447 (\u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, PuLP, Pyomo, ORTools, FeLooPy, GAMS \u0438 \u0434\u0440.). \u041a\u0430\u043a \u0441\u043b\u0435\u0434\u0441\u0442\u0432\u0438\u0435, \u043a\u043e\u043c\u043c\u0435\u0440\u0447\u0435\u0441\u043a\u0438\u0435 \u0441\u043e\u043b\u0432\u0435\u0440\u044b &#171;\u043f\u043e\u0447\u0442\u0438 \u0432\u0435\u0437\u0434\u0435&#187; \u043f\u0440\u0435\u0432\u043e\u0441\u0445\u043e\u0434\u044f\u0442 \u043f\u043e \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438 open-source, \u0431\u043e\u043b\u044c\u0448\u0435 \u0444\u0430\u043a\u0442\u043e\u0432 <a href=\"https:\/\/plato.asu.edu\/ftp\/milp.html\">\u0437\u0434\u0435\u0441\u044c<\/a>.<\/p>\n<p>\u0417\u0430\u0444\u0438\u043a\u0441\u0438\u0440\u0443\u0435\u043c \u0441\u0442\u044d\u043a. \u0420\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044e \u043c\u043e\u0434\u0435\u043b\u0438 \u0441\u0434\u0435\u043b\u0430\u0435\u043c \u043d\u0430 python, \u0441\u0440\u0435\u0434\u0430 \u0434\u043b\u044f \u043c\u043e\u0434\u0435\u043b\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f <a href=\"https:\/\/developers.google.com\/optimization?hl=en\">ORTools<\/a>, \u0441\u043e\u043b\u0432\u0435\u0440 open-source cp-sat (ORTools), \u0432\u0438\u0437\u0443\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044e \u0431\u0443\u0434\u0435\u043c \u043f\u0440\u043e\u0432\u043e\u0434\u0438\u0442\u044c \u0432 plotly, \u043d\u0435\u043c\u043d\u043e\u0433\u043e \u043f\u043e\u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u043c pandas \u0438 networkx.<\/p>\n<p>\u041f\u043e \u043f\u043e\u0432\u043e\u0434\u0443 \u0441\u043e\u043b\u0432\u0435\u0440\u0430, cp-sat \u043d\u0435 \u0441\u043e\u0432\u0441\u0435\u043c \u0440\u0435\u0448\u0430\u0442\u0435\u043b\u044c \u0437\u0430\u0434\u0430\u0447 \u0446\u0435\u043b\u043e\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u043e\u0433\u043e \u043b\u0438\u043d\u0435\u0439\u043d\u043e\u0433\u043e \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f, \u043d\u043e \u0432 \u0442\u043e\u043c \u0447\u0438\u0441\u043b\u0435 \u043f\u043e\u043a\u0440\u044b\u0432\u0430\u0435\u0442 \u044d\u0442\u043e\u0442 \u043a\u043b\u0430\u0441\u0441 \u0437\u0430\u0434\u0430\u0447. \u0414\u0435\u0442\u0430\u043b\u044c\u043d\u043e \u0432 \u0441\u043f\u0435\u0446\u0438\u0444\u0438\u043a\u0443 \u043d\u0435 \u0431\u0443\u0434\u0435\u043c \u0443\u0445\u043e\u0434\u0438\u0442\u044c (\u043a\u043b\u044e\u0447\u0435\u0432\u044b\u0435 \u0441\u043b\u043e\u0432\u0430 \u0434\u043b\u044f \u0442\u0435\u0445 \u043a\u0442\u043e \u0445\u043e\u0447\u0435\u0442: constraint programming, boolean satisfability). \u041a\u0440\u043e\u043c\u0435 \u0442\u043e\u0433\u043e, ORTools \u0438\u043c\u0435\u0435\u0442 \u043e\u0442\u0434\u0435\u043b\u044c\u043d\u044b\u0439 \u043d\u0430\u0431\u043e\u0440 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u0432 \u0434\u043b\u044f \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u0437\u0430\u0434\u0430\u0447\u0438 vehicle routing problem, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u0432 \u0447\u0430\u0441\u0442\u043d\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u044d\u043a\u0432\u0438\u0432\u0430\u043b\u0435\u043d\u0442\u043d\u0430 \u0437\u0430\u0434\u0430\u0447\u0435 TSP. \u0412\u043e\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u043c\u0441\u044f \u044d\u0442\u0438\u043c\u0438 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430\u043c\u0438 \u0434\u043b\u044f \u0432\u0430\u043b\u0438\u0434\u0430\u0446\u0438\u0438 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u0430 \u043c\u043e\u0434\u0435\u043b\u0438 ILP.<\/p>\n<h2>\u041c\u043e\u0434\u0435\u043b\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435<\/h2>\n<p>\u0412\u043e\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u043c\u0441\u044f \u0441\u0438\u043c\u043c\u0435\u0442\u0440\u0438\u0447\u043d\u043e\u0441\u0442\u044c\u044e \u043c\u0430\u0442\u0440\u0438\u0446\u044b \u043f\u0435\u0440\u0435\u0445\u043e\u0434\u043e\u0432 \u043c\u0435\u0436\u0434\u0443 \u0443\u0437\u043b\u0430\u043c\u0438 \u0438 \u0441\u0444\u043e\u0440\u043c\u0443\u043b\u0438\u0440\u0443\u0435\u043c \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u0438\u0441\u0442\u0438\u0447\u043d\u0443\u044e \u043c\u043e\u0434\u0435\u043b\u044c ILP \u0437\u0430\u0434\u0430\u0447\u0438 \u043f\u043b\u0430\u043d\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f \u043c\u0430\u0440\u0448\u0440\u0443\u0442\u0430 \u043d\u0430 \u0443\u0441\u043b\u043e\u0432\u0438\u044f\u0445 TSP.  \u0412\u0432\u0435\u0434\u0435\u043c \u043e\u0431\u043e\u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f, \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f \u0438 \u0446\u0435\u043b\u0435\u0432\u0443\u044e \u0444\u0443\u043d\u043a\u0446\u0438\u044e:<\/p>\n<p><img decoding=\"async\" class=\"formula inline\" source=\"i, j \\in N\" alt=\"i, j \\in N\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/5\/5d\/5d7\/5d70a845ad0a851af4ea09d9280219f1.svg\" width=\"auto\" height=\"auto\"\/> &#8212; \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e \u0443\u0437\u043b\u043e\u0432 \u0441\u0435\u0442\u0438;<\/p>\n<p><img decoding=\"async\" class=\"formula inline\" source=\"d_{ij}\" alt=\"d_{ij}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/a\/a3\/a38\/a38dbe819cd26b5066df29fcda127e9f.svg\" width=\"auto\" height=\"auto\"\/> &#8212; \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0435\/\u0437\u0430\u0442\u0440\u0430\u0442\u044b\/\u0432\u0440\u0435\u043c\u044f \u0434\u0432\u0438\u0436\u0435\u043d\u0438\u044f \u043f\u043e \u0440\u0435\u0431\u0440\u0443 <img decoding=\"async\" class=\"formula inline\" source=\"i-j\" alt=\"i-j\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/d\/d6\/d6c\/d6ce2c1034e7f9f6b4476d264318d689.svg\" width=\"auto\" height=\"auto\"\/>;<\/p>\n<p><img decoding=\"async\" class=\"formula inline\" source=\"x_{ij}\" alt=\"x_{ij}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/8\/87\/875\/875a419bb0507ba4a52426c52163635b.svg\" width=\"auto\" height=\"auto\"\/> &#8212; \u0431\u0438\u043d\u0430\u0440\u043d\u0430\u044f \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u0430\u044f, \u0438\u043d\u0434\u0438\u043a\u0430\u0442\u043e\u0440 \u0432\u044b\u0431\u043e\u0440\u0430 \u0440\u0435\u0431\u0440\u0430 \u0432 \u043c\u0430\u0440\u0448\u0440\u0443\u0442 (=1 \u0435\u0441\u043b\u0438 \u0440\u0435\u0431\u0440\u043e \u0432 \u043c\u0430\u0440\u0448\u0440\u0443\u0442\u0435, 0 &#8212; \u0432 \u043f\u0440\u043e\u0442\u0438\u0432\u043d\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435);<\/p>\n<p><img decoding=\"async\" class=\"formula\" source=\"\\begin{align}\\min \\sum_{i,j} d_{ij} x_{ij} \\\\\\sum_{j} x_{ij} = 2 &amp; \\quad \\forall  i \\in N &amp; (1) \\\\\\sum_{i,j \\in S : i&lt;j} x_{ij} \\le |S|-1 &amp; \\quad \\forall S \\subset N, 2 \\le |S| \\le |N|-2 \\quad &amp; (2) \\\\x_{ij} = x_{ji} &amp; \\quad \\forall i,j \\in N &amp; (3) \\\\x_{ij} \\in \\{0,1\\} &amp; \\quad \\forall i,j \\in N &amp; (4) \\\\\\end{align}\" alt=\"\\begin{align}\\min \\sum_{i,j} d_{ij} x_{ij} \\\\\\sum_{j} x_{ij} = 2 &amp; \\quad \\forall  i \\in N &amp; (1) \\\\\\sum_{i,j \\in S : i&lt;j} x_{ij} \\le |S|-1 &amp; \\quad \\forall S \\subset N, 2 \\le |S| \\le |N|-2 \\quad &amp; (2) \\\\x_{ij} = x_{ji} &amp; \\quad \\forall i,j \\in N &amp; (3) \\\\x_{ij} \\in \\{0,1\\} &amp; \\quad \\forall i,j \\in N &amp; (4) \\\\\\end{align}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/c\/cc\/cc4\/cc4190d08d71244928b59f312de114d3.svg\" width=\"auto\" height=\"auto\"\/><\/p>\n<p>\u041d\u0430\u0447\u043d\u0435\u043c \u0440\u0430\u0437\u0431\u043e\u0440 \u043c\u043e\u0434\u0435\u043b\u0438 \u0441 \u0446\u0435\u043b\u0435\u0432\u043e\u0439 \u0444\u0443\u043d\u043a\u0446\u0438\u0438 &#8212; \u0442\u0440\u0430\u0434\u0438\u0446\u0438\u043e\u043d\u043d\u043e \u044d\u0442\u043e \u043c\u0438\u043d\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u044f \u0434\u043b\u0438\u043d\u044b \u043c\u0430\u0440\u0448\u0440\u0443\u0442\u0430, \u043d\u043e \u043a\u0430\u043a \u0432\u0430\u0440\u0438\u0430\u0446\u0438\u0438 \u043c\u043e\u0433\u0443\u0442 \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u0442\u044c\u0441\u044f \u043c\u0438\u043d\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u044f \u0437\u0430\u0442\u0440\u0430\u0442 \u0438\u043b\u0438 \u043c\u0438\u043d\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u044f \u0432\u0440\u0435\u043c\u0435\u043d\u0438 \u0432 \u043f\u0443\u0442\u0438, \u0434\u0440\u0443\u0433\u0438\u0435 \u0432\u0430\u0440\u0438\u0430\u043d\u0442\u044b \u0442\u043e\u0436\u0435 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u044b. \u041e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0435 (1) \u043e\u0431\u044f\u0437\u044b\u0432\u0430\u0435\u0442 \u043c\u043e\u0434\u0435\u043b\u044c \u043e\u0440\u0433\u0430\u043d\u0438\u0437\u043e\u0432\u0430\u0442\u044c \u043e\u0434\u0438\u043d \u0432\u0445\u043e\u0434 \u0438 \u043e\u0434\u0438\u043d \u0432\u044b\u0445\u043e\u0434. \u0414\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u043f\u043e\u0434\u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430 <img decoding=\"async\" class=\"formula inline\" source=\"N\" alt=\"N\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/8\/8d\/8d9\/8d9c307cb7f3c4a32822a51922d1ceaa.svg\" width=\"auto\" height=\"auto\"\/> \u0441\u043e\u0437\u0434\u0430\u0435\u043c \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f \u0442\u0438\u043f\u0430 (2), \u043e\u043d\u0438 \u043e\u0431\u0435\u0441\u043f\u0435\u0447\u0438\u0432\u0430\u044e\u0442 \u0441\u043e\u0437\u0434\u0430\u043d\u0438\u0435 \u0441\u0432\u044f\u0437\u043d\u043e\u0433\u043e \u043c\u0430\u0440\u0448\u0440\u0443\u0442\u0430. \u041e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0435 \u0441\u0438\u043c\u043c\u0435\u0442\u0440\u0438\u0438 (3), \u043d\u0435\u0432\u0430\u0436\u043d\u043e, \u0432 \u043a\u0430\u043a\u043e\u043c \u043d\u0430\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u0438\u0438 \u0438\u0434\u0435\u043c \u043f\u043e \u0440\u0435\u0431\u0440\u0443, \u0432\u0430\u0436\u043d\u043e \u0447\u0442\u043e \u0438\u0434\u0435\u043c (\u043c\u0430\u0442\u0440\u0438\u0446\u0430 \u043f\u0435\u0440\u0435\u0445\u043e\u0434\u043e\u0432 \u0441\u0438\u043c\u043c\u0435\u0442\u0440\u0438\u0447\u043d\u0430\u044f). \u041e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f (4) &#8212; \u0431\u0438\u043d\u0430\u0440\u043d\u043e\u0441\u0442\u044c \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0445.<\/p>\n<p>\u041a\u043e\u043c\u043c\u0435\u043d\u0442\u0430\u0440\u0438\u0438 \u043a \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f\u043c. \u041e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f \u0442\u0438\u043f\u0430 (3) \u0441\u043e\u043a\u0440\u0430\u0442\u044f\u0442\u0441\u044f \u043d\u0430 presolve \u044d\u0442\u0430\u043f\u0435 \u0441\u043e\u043b\u0432\u0435\u0440\u0430. \u041c\u043e\u0436\u043d\u043e \u0441\u0444\u043e\u0440\u043c\u0443\u043b\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u043c\u043e\u0434\u0435\u043b\u044c \u0431\u0435\u0437 \u044d\u0442\u043e\u0433\u043e \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f, \u043d\u043e \u0437\u0430\u043f\u0438\u0441\u044c \u043c\u043e\u0434\u0435\u043b\u0438 \u0431\u0443\u0434\u0435\u0442 \u043d\u0435\u043c\u043d\u043e\u0433\u043e \u0441\u043b\u043e\u0436\u043d\u0435\u0435. \u041a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0439 \u0442\u0438\u043f\u0430 (2) \u0440\u0430\u0441\u0442\u0435\u0442 \u044d\u043a\u0441\u043f\u043e\u043d\u0435\u043d\u0446\u0438\u0430\u043b\u044c\u043d\u043e \u0432 \u0437\u0430\u0432\u0438\u0441\u0438\u043c\u043e\u0441\u0442\u0438 \u043e\u0442 <img decoding=\"async\" class=\"formula inline\" source=\"|N|\" alt=\"|N|\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/2\/24\/24e\/24eb46e832268b3a8c101a6ec5c9084a.svg\" width=\"auto\" height=\"auto\"\/>, \u0447\u0442\u043e \u0432\u044b\u0433\u043b\u044f\u0434\u0438\u0442 \u043d\u0435 \u043e\u0447\u0435\u043d\u044c \u043f\u0440\u0430\u043a\u0442\u0438\u0447\u043d\u043e. \u0421 \u044d\u0442\u0438\u043c \u043f\u043e\u0431\u043e\u0440\u0435\u043c\u0441\u044f \u0434\u0430\u043b\u0435\u0435.<\/p>\n<h2>Python \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f \u043c\u043e\u0434\u0435\u043b\u0438<\/h2>\n<p>\u041f\u043e\u0441\u0442\u0440\u043e\u0438\u043c \u043c\u043e\u0434\u0435\u043b\u044c \u0431\u0435\u0437 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f (2), \u043f\u043e\u0441\u043c\u043e\u0442\u0440\u0438\u043c, \u0447\u0442\u043e \u043e\u0437\u043d\u0430\u0447\u0430\u0435\u0442 \u0441\u0432\u044f\u0437\u043d\u043e\u0441\u0442\u044c \u043c\u0430\u0440\u0448\u0440\u0443\u0442\u0430 \u043d\u0430 \u043f\u0440\u0430\u043a\u0442\u0438\u043a\u0435. \u0412 \u043a\u0430\u0447\u0435\u0441\u0442\u0432\u0435 \u0446\u0435\u043b\u0435\u0432\u043e\u0439 \u0444\u0443\u043d\u043a\u0446\u0438\u0438 \u0431\u0443\u0434\u0435\u043c \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u043c\u0438\u043d\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u044e \u0437\u0430\u0442\u0440\u0430\u0442 \u043d\u0430 \u0442\u0440\u0430\u043d\u0441\u0444\u0435\u0440 \u043c\u0435\u0436\u0434\u0443 \u043b\u043e\u043a\u0430\u0446\u0438\u044f\u043c\u0438.<\/p>\n<details class=\"spoiler\">\n<summary>\u0420\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f \u0443\u043f\u0440\u043e\u0449\u0435\u043d\u043d\u043e\u0439 \u0432\u0435\u0440\u0441\u0438\u0438 \u043c\u043e\u0434\u0435\u043b\u0438 \u0431\u0435\u0437 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0439 \u0442\u0438\u043f\u0430 (2)<\/summary>\n<div class=\"spoiler__content\">\n<pre><code class=\"python\"># \u0423\u043f\u0440\u043e\u0449\u0435\u043d\u043d\u0430\u044f \u0432\u0435\u0440\u0441\u0438\u044f \u043c\u043e\u0434\u0435\u043b\u0438 \u0431\u0435\u0437 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0439 \u0442\u0438\u043f\u0430 (2) from ortools.sat.python import cp_model import pandas as pd import numpy as np  # \u0421\u0447\u0438\u0442\u0430\u0435\u043c \u0432\u0445\u043e\u0434\u043d\u044b\u0435 \u0434\u0430\u043d\u043d\u044b\u0435 df_dist = df_cab = pd.read_csv(\"https:\/\/raw.githubusercontent.com\/Lozkins\/mos\/master\/data\/06_tsp_dist.csv\", sep=\";\", encoding=\"cp1251\") df_location = df_cab = pd.read_csv(\"https:\/\/raw.githubusercontent.com\/Lozkins\/mos\/master\/data\/06_tsp_coord.csv\", sep=\";\", encoding=\"cp1251\")  obj_type = \"cost\"  # \u0422\u0438\u043f \u0446\u0435\u043b\u0435\u0432\u043e\u0439 \u0444\u0443\u043d\u043a\u0446\u0438\u0438. \u0414\u043e\u043f\u0443\u0441\u0442\u0438\u043c\u044b\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f [\"cost\", \"travel_time\"]  m = cp_model.CpModel()  # \u0418\u043d\u0438\u0446\u0438\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0445 df_dist[\"var_id\"] = np.ogrid[:df_dist.shape[0]] df_dist[\"var\"] = df_dist[\"var_id\"].apply(lambda x: m.NewBoolVar(f\"x_{x}\"))  # \u0421\u043e\u0437\u0434\u0430\u0435\u043c \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f \u0442\u0438\u043f\u0430 (1) dct_constr_1 = df_dist.groupby(\"to\")[\"var\"].sum().to_dict() for from_node, var_sum in dct_constr_1.items():   m.Add(var_sum == 2)  # \u0421\u043e\u0437\u0434\u0430\u0435\u043c \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f \u0442\u0438\u043f\u0430 (3) dct_constr_3 = df_dist.set_index([\"from\", \"to\"]).to_dict()[\"var\"] for (from_node,  to_node), var_ in dct_constr_3.items():   m.Add(var_ == dct_constr_3[to_node, from_node])  m.Minimize(sum(df_dist[obj_type] * df_dist[\"var\"]))  # \u0418\u043d\u0438\u0446\u0438\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f solver solver = cp_model.CpSolver() solver.parameters.log_search_progress = True  # \u0420\u0435\u0448\u0435\u043d\u0438\u0435 \u0437\u0430\u0434\u0430\u0447\u0438 status = solver.Solve(m)  # \u041f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u043c \u0441\u0442\u0430\u0442\u0443\u0441 if status == cp_model.OPTIMAL:   print(\"-\" * 40)   gap_val = abs((solver.ObjectiveValue() - solver.BestObjectiveBound()) \/ max(1, solver.ObjectiveValue()))   # \u0418\u0437\u0432\u043b\u0435\u043a\u0430\u0435\u043c \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442   df_dist[\"sol\"] = df_dist[\"var\"].apply(lambda x: solver.Value(x))   df_dist_opt = df_dist[df_dist[\"sol\"] > 0]    print(f\"-- Found solution {solver.ObjectiveValue()}\")   print(f\"-- GAP: {round(gap_val, 2)}%\")   print(f\"-- Solved in {solver.WallTime()} sec.\")   print(f\"-- Costs {df_dist_opt['cost'].sum() \/ 2} rub\")   print(f\"-- Duration {df_dist_opt['travel_time'].sum() \/ 2} h\") <\/code><\/pre>\n<\/div>\n<\/details>\n<details class=\"spoiler\">\n<summary>\u0424\u0443\u043d\u043a\u0446\u0438\u044f \u0432\u0438\u0437\u0443\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u0432 plotly<\/summary>\n<div class=\"spoiler__content\">\n<pre><code class=\"python\"># \u041d\u0430\u043d\u0435\u0441\u0435\u043d\u0438\u0435 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u0430 \u043d\u0430 \u043a\u0430\u0440\u0442\u0443 import plotly.graph_objects as go  def plot_route(df_graph: pd.DataFrame):   # \u041d\u0430\u0447\u0430\u043b\u043e \u0438 \u043e\u043a\u043e\u043d\u0447\u0430\u043d\u0438\u0435 \u043c\u0430\u0440\u0448\u0440\u0443\u0442\u0430 \u0432 \u041c\u0421\u041a   df_location[\"color\"] = np.where(df_location[\"id\"] == 0, \"red\", \"blue\")   df_location[\"size\"] = np.where(df_location[\"id\"] == 0, 14, 10)   df_location['text'] = df_location[\"id\"].astype(str) + \", \" + df_location[\"name\"]    # \u0414\u043e\u0431\u0430\u0432\u043b\u044f\u0435\u043c \u043a\u043e\u043e\u0440\u0434\u0438\u043d\u0430\u0442\u044b \u0438 \u043d\u0430\u0438\u043c\u0435\u043d\u043e\u0432\u0430\u043d\u0438\u0435 \u0442\u043e\u0447\u0435\u043a \u043e\u0442\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u0438\u044f \u0438 \u043f\u0440\u0438\u0431\u044b\u0442\u0438\u044f   df_loc_from = df_location.copy()   df_loc_from.columns = [col + \"_from\" for col in df_loc_from.columns]   df_loc_to = df_location.copy()   df_loc_to.columns = [col + \"_to\" for col in df_loc_to.columns]    df_travel_map = df_graph.merge(df_loc_from, how=\"left\", left_on=\"from\",                               right_on=\"id_from\")   df_travel_map = df_travel_map.merge(df_loc_to, how=\"left\", left_on=\"to\",                               right_on=\"id_to\")    # \u041d\u0430\u043d\u043e\u0441\u0438\u043c \u0432\u0435\u0440\u0448\u0438\u043d\u044b   fig = go.Figure(data=go.Scattergeo(           lon = df_location['lon'],           lat = df_location['lat'],           text = df_location['text'],           mode = 'markers',           name = \"\u041b\u043e\u043a\u0430\u0446\u0438\u0438\",           marker = dict(               size = df_location[\"size\"],               opacity = 0.8,               color = df_location[\"color\"],               ),           ))    # \u041d\u0430\u043d\u043e\u0441\u0438\u043c \u0440\u0435\u0431\u0440\u0430   for row in df_travel_map.itertuples():     fig.add_trace(             go.Scattergeo(                 lon = [row.lon_from, row.lon_to],                 lat = [row.lat_from, row.lat_to],                 mode = 'lines',                 line = dict(width = 1,color = 'blue'),                 opacity = 0.8,                 name=row.name_from + \" - \" + row.name_to             ),         )    fig.update_layout(           title = 'Travel route in Russia &lt;br>',           geo = dict(               showland = True,               landcolor = \"rgb(250, 250, 250)\",               subunitcolor = \"rgb(217, 217, 217)\",               countrycolor = \"rgb(217, 217, 217)\",               countrywidth = 0.5,               subunitwidth = 0.5           ),       )    fig.show() <\/code><\/pre>\n<\/div>\n<\/details>\n<p>\u0421 \u0446\u0435\u043b\u0435\u0432\u043e\u0439 \u0444\u0443\u043d\u043a\u0446\u0438\u0435\u0439 \u043c\u0438\u043d\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u0438 \u0437\u0430\u0442\u0440\u0430\u0442 \u043f\u043e\u043b\u0443\u0447\u0438\u043b\u0438 \u043e\u043f\u0442\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u0437\u0430\u0434\u0430\u0447\u0438 \u0441 \u043e\u0431\u0449\u0438\u043c\u0438 \u0437\u0430\u0442\u0440\u0430\u0442\u0430\u043c\u0438 93 876 \u0440\u0443\u0431 (115.05 \u0447\u0430\u0441\u043e\u0432). \u041f\u0430\u0440\u0430\u043c\u0435\u0442\u0440 <code>obj_type<\/code> \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u043f\u0435\u0440\u0435\u043a\u043b\u044e\u0447\u0438\u0442\u044c \u0446\u0435\u043b\u0435\u0432\u0443\u044e \u0444\u0443\u043d\u043a\u0446\u0438\u044e \u043d\u0430 \u043c\u0438\u043d\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u044e \u0432\u0440\u0435\u043c\u0435\u043d\u0438 \u0432 \u043f\u0443\u0442\u0438, \u0442\u043e\u0433\u0434\u0430 \u043e\u043f\u0442\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u0431\u0443\u0434\u0435\u0442 70.9 \u0447\u0430\u0441\u043e\u0432 (131 493 \u0440\u0443\u0431). \u041d\u0430\u043d\u0435\u0441\u0435\u043c \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 \u043d\u0430 \u043a\u0430\u0440\u0442\u0443 \u0434\u043b\u044f \u0446\u0435\u043b\u0435\u0432\u043e\u0439 \u0444\u0443\u043d\u043a\u0446\u0438\u0438 \u043c\u0438\u043d\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u0438 \u0437\u0430\u0442\u0440\u0430\u0442.<\/p>\n<figure class=\"\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/post_images\/63e\/a22\/bd1\/63ea22bd1e626533cfe2f73bef3f161a.png\" alt=\"\u041f\u0435\u0440\u0432\u0430\u044f \u043f\u043e\u043f\u044b\u0442\u043a\u0430 \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u0437\u0430\u0434\u0430\u0447\u0438: \u041d\u0435\u0441\u0432\u044f\u0437\u043d\u044b\u0439 \u043f\u0443\u0442\u044c\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/63e\/a22\/bd1\/63ea22bd1e626533cfe2f73bef3f161a.png\"\/><\/p>\n<div><figcaption>\u041f\u0435\u0440\u0432\u0430\u044f \u043f\u043e\u043f\u044b\u0442\u043a\u0430 \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u0437\u0430\u0434\u0430\u0447\u0438: \u041d\u0435\u0441\u0432\u044f\u0437\u043d\u044b\u0439 \u043f\u0443\u0442\u044c<\/figcaption><\/div>\n<\/figure>\n<p>\u041d\u0435 \u0442\u0430\u043a\u043e\u0439 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 \u043c\u044b \u0441 \u0432\u0430\u043c\u0438 \u043e\u0436\u0438\u0434\u0430\u043b\u0438, \u043c\u0430\u0440\u0448\u0440\u0443\u0442 \u043f\u043e\u043b\u0443\u0447\u0438\u043b\u0441\u044f \u0440\u0430\u0437\u0431\u0438\u0442\u044b\u043c \u043d\u0430 \u0447\u0430\u0441\u0442\u0438 &#8212; \u043d\u0435\u0441\u0432\u044f\u0437\u043d\u044b\u043c. \u041e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f \u0442\u0438\u043f\u0430 (2) \u0443\u0441\u0442\u0440\u0430\u043d\u044f\u044e\u0442 \u044d\u0442\u0443 \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u0443, \u043d\u043e \u0446\u0435\u043d\u0430 \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u0432\u044b\u0441\u043e\u043a\u0430 &#8212; \u0433\u0440\u043e\u043c\u0430\u0434\u043d\u0435\u0439\u0448\u0430\u044f \u043c\u043e\u0434\u0435\u043b\u044c. \u041f\u0440\u0435\u0434\u043b\u043e\u0436\u0435\u043d\u0438\u0435 &#8212; \u0440\u0435\u0448\u0430\u0442\u044c \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u044b \u043f\u043e \u043c\u0435\u0440\u0435 \u0438\u0445 \u043f\u043e\u0441\u0442\u0443\u043f\u043b\u0435\u043d\u0438\u044f.<\/p>\n<p>\u0418\u0441\u0445\u043e\u0434\u044f \u0438\u0437 \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u0437\u0430\u0434\u0430\u0447\u0438, \u043c\u044b \u043c\u043e\u0436\u0435\u043c \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u0442\u044c \u043d\u0435\u0441\u0432\u044f\u0437\u043d\u044b\u0435 \u043f\u043e\u0434\u0433\u0440\u0430\u0444\u044b \u0438 \u0441\u043f\u0435\u0446\u0438\u0430\u043b\u044c\u043d\u043e \u0434\u043b\u044f \u043d\u0438\u0445 \u0441\u043e\u0437\u0434\u0430\u0442\u044c \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f \u0442\u0438\u043f\u0430 (2) &#8212; \u0434\u043e\u0431\u0430\u0432\u0438\u043c \u0437\u0430\u043f\u043b\u0430\u0442\u043a\u0443. \u0421\u0430\u043c\u043e \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0435 &#171;\u0440\u0430\u0437\u0440\u044b\u0432\u0430\u0435\u0442&#187; \u043b\u043e\u043a\u0430\u043b\u044c\u043d\u044b\u0435 \u0446\u0438\u043a\u043b\u044b, \u043e\u0431\u044f\u0437\u044b\u0432\u0430\u044f \u0441\u043e\u0437\u0434\u0430\u0432\u0430\u0442\u044c \u0445\u043e\u0442\u044f \u0431\u044b \u043e\u0434\u043d\u0443 \u0441\u0432\u044f\u0437\u044c \u0441 \u0432\u043d\u0435\u0448\u043d\u0438\u043c \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e\u043c \u0432\u0435\u0440\u0448\u0438\u043d. \u041d\u043e\u0432\u044b\u0435 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f \u043f\u0440\u0438\u0432\u043e\u0434\u044f\u0442 \u043a \u0438\u0437\u043c\u0435\u043d\u0435\u043d\u0438\u044e \u043c\u043e\u0434\u0435\u043b\u0438, \u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e, \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u0438\u0441\u043a\u0430\u0442\u044c \u043d\u043e\u0432\u043e\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435.<\/p>\n<p>\u0412 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u0441\u043e\u043b\u0432\u0435\u0440\u0430\u0445 \u0435\u0441\u0442\u044c \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u0441\u043e\u0437\u0434\u0430\u0432\u0430\u0442\u044c \u043b\u0435\u043d\u0438\u0432\u044b\u0435 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f (lazy constraints). \u042d\u0442\u043e \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0438\u0437\u043d\u0430\u0447\u0430\u043b\u044c\u043d\u043e \u043d\u0430\u0445\u043e\u0434\u044f\u0442\u0441\u044f \u0432 \u043d\u0435\u0430\u043a\u0442\u0438\u0432\u043d\u043e\u043c \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0438, \u043d\u043e \u043f\u0440\u0438 \u0438\u0445 \u043d\u0430\u0440\u0443\u0448\u0435\u043d\u0438\u0438 \u0438\u043b\u0438 \u043f\u043e \u0434\u0440\u0443\u0433\u0438\u043c \u043a\u0440\u0438\u0442\u0435\u0440\u0438\u044f\u043c \u0430\u043a\u0442\u0438\u0432\u0430\u0446\u0438\u0438 \u043e\u043d\u0438 \u0434\u043e\u0431\u0430\u0432\u043b\u044f\u044e\u0442\u0441\u044f \u0432 \u043c\u043e\u0434\u0435\u043b\u044c \u043d\u0435\u043f\u043e\u0441\u0440\u0435\u0434\u0441\u0442\u0432\u0435\u043d\u043d\u043e \u0432 \u043f\u0440\u043e\u0446\u0435\u0441\u0441\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u0437\u0430\u0434\u0430\u0447\u0438.<\/p>\n<p>\u0412\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u044f\u0441\u044c \u043a \u043d\u0430\u0448\u0435\u0439 \u0437\u0430\u0434\u0430\u0447\u0435. \u0411\u044b\u043b\u043e \u0431\u044b \u043d\u0435\u043f\u043b\u043e\u0445\u043e \u043b\u0435\u043d\u0438\u0432\u043e \u0441\u043e\u0437\u0434\u0430\u0432\u0430\u0442\u044c \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f \u0442\u0438\u043f\u0430 (2) \u043f\u0440\u0438 \u043f\u043e\u043b\u0443\u0447\u0435\u043d\u0438\u0438 \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u0441 \u043d\u0430\u0440\u0443\u0448\u0435\u043d\u0438\u0435\u043c \u0441\u0432\u044f\u0437\u043d\u043e\u0441\u0442\u0438. \u041d\u043e, \u043a \u0441\u043e\u0436\u0430\u043b\u0435\u043d\u0438\u044e, ortools \u043d\u0435 \u0438\u043c\u0435\u0435\u0442 \u043f\u0440\u0438\u043c\u0435\u0440\u043e\u0432 \u0438\u043b\u0438 \u0445\u043e\u0440\u043e\u0448\u0435\u0439 \u0434\u043e\u043a\u0443\u043c\u0435\u043d\u0442\u0430\u0446\u0438\u0438 \u043c\u0435\u0442\u043e\u0434\u0430 <a href=\"https:\/\/developers.google.com\/optimization\/reference\/python\/linear_solver\/pywraplp#set_is_lazy\">set_is_lazy<\/a>, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u043c\u044b \u0432\u043e\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u043c\u0441\u044f \u0446\u0438\u043a\u043b\u0430\u043c\u0438 python. \u0421\u0432\u044f\u0437\u043d\u044b\u0435 \u043f\u043e\u0434\u0433\u0440\u0430\u0444\u044b \u0431\u0443\u0434\u0435\u043c \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u0442\u044c \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a\u0438 networkx. \u041a\u0440\u0438\u0442\u0435\u0440\u0438\u0439 \u043e\u0441\u0442\u0430\u043d\u043e\u0432\u043a\u0438 &#8212; \u043f\u043e\u043b\u0443\u0447\u0435\u043d \u0441\u0432\u044f\u0437\u043d\u044b\u0439 \u043c\u0430\u0440\u0448\u0440\u0443\u0442.<\/p>\n<p>*\u0420\u0430\u0431\u043e\u0442\u0443 \u043b\u0435\u043d\u0438\u0432\u044b\u0445 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0439 \u043c\u043e\u0436\u043d\u043e \u043f\u043e\u0441\u043c\u043e\u0442\u0440\u0435\u0442\u044c \u0443 <a href=\"https:\/\/colab.research.google.com\/github\/Gurobi\/modeling-examples\/blob\/master\/traveling_salesman\/tsp.ipynb#scrollTo=qHXziB65CXsR\">Gurobi<\/a>, \u043d\u0435 \u0440\u0435\u043a\u043b\u0430\u043c\u0430.<\/p>\n<details class=\"spoiler\">\n<summary>\u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0438\u0442\u0435\u0440\u0430\u0442\u0438\u0432\u043d\u043e\u0433\u043e \u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u0438\u044f \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f \u0442\u0438\u043f\u0430 (2)<\/summary>\n<div class=\"spoiler__content\">\n<pre><code class=\"python\"># \u0418\u0442\u0435\u0440\u0430\u0442\u0438\u0432\u043d\u043e\u0435 \u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u0438\u0435 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0439 \u0442\u0438\u043f\u0430 (2) from ortools.sat.python import cp_model import networkx as nx import pandas as pd import numpy as np  # \u0421\u0447\u0438\u0442\u0430\u0435\u043c \u0432\u0445\u043e\u0434\u043d\u044b\u0435 \u0434\u0430\u043d\u043d\u044b\u0435 df_dist = df_cab = pd.read_csv(\"https:\/\/raw.githubusercontent.com\/Lozkins\/mos\/master\/data\/06_tsp_dist.csv\", sep=\";\", encoding=\"cp1251\") df_location = df_cab = pd.read_csv(\"https:\/\/raw.githubusercontent.com\/Lozkins\/mos\/master\/data\/06_tsp_coord.csv\", sep=\";\", encoding=\"cp1251\")  obj_type = \"travel_time\"  # \u0422\u0438\u043f \u0446\u0435\u043b\u0435\u0432\u043e\u0439 \u0444\u0443\u043d\u043a\u0446\u0438\u0438. \u0414\u043e\u043f\u0443\u0441\u0442\u0438\u043c\u044b\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f [\"cost\", \"travel_time\"]  m = cp_model.CpModel()  # \u0418\u043d\u0438\u0446\u0438\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0445 df_dist[\"var_id\"] = np.ogrid[:df_dist.shape[0]] df_dist[\"var\"] = df_dist[\"var_id\"].apply(lambda x: m.NewBoolVar(f\"x_{x}\"))  # \u0421\u043e\u0437\u0434\u0430\u0435\u043c \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f \u0442\u0438\u043f\u0430 (1) dct_constr_1 = df_dist.groupby(\"to\")[\"var\"].sum().to_dict() for from_node, var_sum in dct_constr_1.items():   m.Add(var_sum == 2)  # \u0421\u043e\u0437\u0434\u0430\u0435\u043c \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f \u0442\u0438\u043f\u0430 (3) dct_constr_3 = df_dist.set_index([\"from\", \"to\"]).to_dict()[\"var\"] for (from_node,  to_node), var_ in dct_constr_3.items():   m.Add(var_ == dct_constr_3[to_node, from_node])  m.Minimize(sum(df_dist[obj_type] * df_dist[\"var\"]))  # \u0418\u043d\u0438\u0446\u0438\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f solver solver = cp_model.CpSolver() solver.parameters.log_search_progress = True  # \u0420\u0435\u0448\u0435\u043d\u0438\u0435 \u0437\u0430\u0434\u0430\u0447\u0438 status = solver.Solve(m)  # \u0418\u0437\u0432\u043b\u0435\u043a\u0430\u0435\u043c \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 df_dist[\"sol\"] = df_dist[\"var\"].apply(lambda x: solver.Value(x)) df_dist_opt = df_dist[df_dist[\"sol\"] > 0]  # ----------- \u0418\u0442\u0435\u0440\u0430\u0446\u0438\u0438 \u043f\u043e \u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u0438\u044e \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0439 \u0442\u0438\u043f\u0430 (2). \u041d\u0410\u0427\u0410\u041b\u041e ------------------ # \u041a\u043e\u043b-\u0432\u043e \u0441\u0432\u044f\u0437\u043d\u044b\u0445 \u043f\u043e\u0434\u0433\u0440\u0430\u0444\u043e\u0432 route_tmp = nx.from_pandas_edgelist(df_dist_opt, \"from\", \"to\") lst_sg = list(nx.connected_components(route_tmp))  # \u0421\u043f\u0438\u0441\u043e\u043a \u0443\u0437\u043b\u043e\u0432 \u0432 \u0441\u0432\u044f\u0437\u043d\u044b\u0445 \u043f\u043e\u0434\u0433\u0440\u0430\u0444\u0430\u0445  # \u0414\u043b\u044f \u0441\u0442\u0430\u0442\u0438\u0441\u0442\u0438\u043a\u0438 cnt_constrs = 0  # \u041a\u043e\u043b-\u0432\u043e \u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u043d\u044b\u0445 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0439 \u0442\u0438\u043f\u0430 (2) cnt_iter = 0  # \u041a\u043e\u043b-\u0432\u043e \u0438\u0442\u0435\u0440\u0430\u0446\u0438\u0439 \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u0437\u0430\u0434\u0430\u0447\u0438 ILP solver_time = 0  # \u0421\u0443\u043c\u043c\u0430\u0440\u043d\u043e\u0435 \u0432\u0440\u0435\u043c\u044f \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u0437\u0430\u0434\u0430\u0447 \u0441\u043e\u043b\u0432\u0435\u0440\u043e\u043c  # \u041f\u043e\u0432\u0442\u043e\u0440\u044f\u0442\u044c, \u043f\u043e\u043a\u0430 \u0438\u043c\u0435\u0435\u043c \u0431\u043e\u043b\u0435\u0435 \u043e\u0434\u043d\u043e\u0433\u043e \u043d\u0435\u0441\u0432\u044f\u0437\u043d\u043e\u0433\u043e \u043f\u043e\u0434\u0433\u0440\u0430\u0444\u0430 while len(lst_sg) > 1:   cnt_iter += 1   for sg in lst_sg:     cnt_constrs += 1      # \u041e\u0442\u0431\u0438\u0440\u0430\u0435\u043c \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u044b\u0435 \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0435 \u0434\u043b\u044f \u0441\u0443\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f     filt_i = df_dist[\"from\"].isin(sg)     filt_j = df_dist[\"to\"].isin(sg)     filt_i_less_j = df_dist[\"from\"] &lt; df_dist[\"to\"]     filt_all = filt_i_less_j &amp; filt_i &amp; filt_j     var_sum = df_dist[filt_all][\"var\"].sum()      # \u0414\u043e\u0431\u0430\u0432\u043b\u044f\u0435\u043c \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0435 \u0442\u0438\u043f\u0430 (2) \u0432 \u043c\u043e\u0434\u0435\u043b\u044c     m.Add(var_sum &lt;= len(sg) - 1)    status = solver.Solve(m)   solver_time += solver.WallTime()    # \u0418\u0437\u0432\u043b\u0435\u043a\u0430\u0435\u043c \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442   df_dist[\"sol\"] = df_dist[\"var\"].apply(lambda x: solver.Value(x))   df_dist_opt = df_dist[df_dist[\"sol\"] > 0]    # \u041a\u043e\u043b-\u0432\u043e \u0441\u0432\u044f\u0437\u043d\u044b\u0445 \u043f\u043e\u0434\u0433\u0440\u0430\u0444\u043e\u0432   route_tmp = nx.from_pandas_edgelist(df_dist_opt, \"from\", \"to\")   lst_sg = list(nx.connected_components(route_tmp))  # \u0421\u043f\u0438\u0441\u043e\u043a \u0443\u0437\u043b\u043e\u0432 \u0432 \u0441\u0432\u044f\u0437\u043d\u044b\u0445 \u043f\u043e\u0434\u0433\u0440\u0430\u0444\u0430\u0445 # ----------- \u0418\u0442\u0435\u0440\u0430\u0446\u0438\u0438 \u043f\u043e \u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u0438\u044e \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0439 \u0442\u0438\u043f\u0430 (2). \u041a\u041e\u041d\u0415\u0426 ------------------  # \u041f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u043c \u0441\u0442\u0430\u0442\u0443\u0441 if status == cp_model.OPTIMAL:   print(\"-\" * 40)   gap_val = abs((solver.ObjectiveValue() - solver.BestObjectiveBound()) \/ max(1, solver.ObjectiveValue()))   print(f\"-- Found solution {solver.ObjectiveValue()}\")   print(f\"-- GAP: {round(gap_val, 2)}%\")   print(f\"-- Solved in {solver_time} sec.\")   print(f\"-- Constraints (2) added {cnt_constrs}\")   print(f\"-- Iterations count {cnt_iter}\")   print(f\"-- Costs {df_dist_opt['cost'].sum() \/ 2} rub\")   print(f\"-- Duration {df_dist_opt['travel_time'].sum() \/ 2} h\") <\/code><\/pre>\n<\/div>\n<\/details>\n<details class=\"spoiler\">\n<summary>\u041f\u043e\u043b\u043d\u0430\u044f \u0432\u0435\u0440\u0441\u0438\u044f \u0438\u0441\u0445\u043e\u0434\u043d\u043e\u0439 \u043c\u043e\u0434\u0435\u043b\u0438 (\u0432\u0441\u0435 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f \u0442\u0438\u043f\u0430 (2))<\/summary>\n<div class=\"spoiler__content\">\n<pre><code class=\"python\"># \u041f\u043e\u043b\u043d\u0430\u044f \u043c\u043e\u0434\u0435\u043b\u044c - \u0438\u043d\u0438\u0446\u0438\u0430\u043b\u0438\u0437\u0438\u0440\u0443\u0435\u043c \u0432\u0441\u0435 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f \u0442\u0438\u043f\u0430 (2) from ortools.sat.python import cp_model import pandas as pd import numpy as np from itertools import chain, combinations  # \u0421\u0447\u0438\u0442\u0430\u0435\u043c \u0432\u0445\u043e\u0434\u043d\u044b\u0435 \u0434\u0430\u043d\u043d\u044b\u0435 df_dist = df_cab = pd.read_csv(\"https:\/\/raw.githubusercontent.com\/Lozkins\/mos\/master\/data\/06_tsp_dist.csv\", sep=\";\", encoding=\"cp1251\") df_location = df_cab = pd.read_csv(\"https:\/\/raw.githubusercontent.com\/Lozkins\/mos\/master\/data\/06_tsp_coord.csv\", sep=\";\", encoding=\"cp1251\")  obj_type = \"travel_time\"  # \u0422\u0438\u043f \u0446\u0435\u043b\u0435\u0432\u043e\u0439 \u0444\u0443\u043d\u043a\u0446\u0438\u0438. \u0414\u043e\u043f\u0443\u0441\u0442\u0438\u043c\u044b\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f [\"cost\", \"travel_time\"]  m = cp_model.CpModel()  # \u0418\u043d\u0438\u0446\u0438\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0445 df_dist[\"var_id\"] = np.ogrid[:df_dist.shape[0]] df_dist[\"var\"] = df_dist[\"var_id\"].apply(lambda x: m.NewBoolVar(f\"x_{x}\"))  # \u0421\u043e\u0437\u0434\u0430\u0435\u043c \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f \u0442\u0438\u043f\u0430 (1) dct_constr_1 = df_dist.groupby(\"to\")[\"var\"].sum().to_dict() for from_node, var_sum in dct_constr_1.items():   m.Add(var_sum == 2)  # \u0421\u043e\u0437\u0434\u0430\u0435\u043c \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f \u0442\u0438\u043f\u0430 (2) def powerset(iterable):   s = list(iterable)   return chain.from_iterable(combinations(s, r) for r in range(len(s)+1) if 1 &lt; r &lt; len(s) - 1)  cnt_constrs = 0 for lst_nodes in powerset(df_location[\"id\"]):   cnt_constrs += 1    # \u041e\u0442\u0431\u0438\u0440\u0430\u0435\u043c \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u044b\u0435 \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0435 \u0434\u043b\u044f \u0441\u0443\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f   filt_i = df_dist[\"from\"].isin(lst_nodes)   filt_j = df_dist[\"to\"].isin(lst_nodes)   filt_i_less_j = df_dist[\"from\"] &lt; df_dist[\"to\"]   filt_all = filt_i_less_j &amp; filt_i &amp; filt_j   var_sum = df_dist[filt_all][\"var\"]    if len(var_sum) != 0:     cnt_constrs += 1     var_sum = var_sum.sum()     # \u0414\u043e\u0431\u0430\u0432\u043b\u044f\u0435\u043c \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0435 \u0442\u0438\u043f\u0430 (2) \u0432 \u043c\u043e\u0434\u0435\u043b\u044c     m.Add(var_sum &lt;= len(lst_nodes) - 1)  # \u0421\u043e\u0437\u0434\u0430\u0435\u043c \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f \u0442\u0438\u043f\u0430 (3) dct_constr_3 = df_dist.set_index([\"from\", \"to\"]).to_dict()[\"var\"] for (from_node,  to_node), var_ in dct_constr_3.items():   m.Add(var_ == dct_constr_3[to_node, from_node])  m.Minimize(sum(df_dist[obj_type] * df_dist[\"var\"]))  # \u0418\u043d\u0438\u0446\u0438\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f solver solver = cp_model.CpSolver() solver.parameters.log_search_progress = True  # \u0420\u0435\u0448\u0435\u043d\u0438\u0435 \u0437\u0430\u0434\u0430\u0447\u0438 status = solver.Solve(m)  # \u041f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u043c \u0441\u0442\u0430\u0442\u0443\u0441 if status == cp_model.OPTIMAL:   print(\"-\" * 40)   gap_val = abs((solver.ObjectiveValue() - solver.BestObjectiveBound()) \/ max(1, solver.ObjectiveValue()))   print(f\"-- Found solution {solver.ObjectiveValue()}\")   print(f\"-- GAP: {round(gap_val, 2)}%\")   print(f\"-- Solved in {solver.WallTime()} sec.\")   print(f\"-- Constraints (2) added {cnt_constrs}\")   print(f\"-- Costs {df_dist_opt['cost'].sum() \/ 2} rub\")   print(f\"-- Duration {df_dist_opt['travel_time'].sum() \/ 2} h\")    # \u0418\u0437\u0432\u043b\u0435\u043a\u0430\u0435\u043c \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442   df_dist[\"sol\"] = df_dist[\"var\"].apply(lambda x: solver.Value(x))   df_dist_opt = df_dist[df_dist[\"sol\"] > 0] <\/code><\/pre>\n<\/div>\n<\/details>\n<p>\u0427\u0442\u043e \u0438\u0437\u043c\u0435\u043d\u0438\u043b\u043e\u0441\u044c \u0432 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u0435? \u041f\u043e\u043b\u0443\u0447\u0435\u043d\u043d\u044b\u0439 \u043c\u0430\u0440\u0448\u0440\u0443\u0442 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u0442 \u0441\u043e\u0431\u043e\u0439 \u043e\u0434\u0438\u043d \u0431\u043e\u043b\u044c\u0448\u043e\u0439 \u0446\u0438\u043a\u043b \u0431\u0435\u0437 \u043f\u043e\u0432\u0442\u043e\u0440\u0435\u043d\u0438\u044f \u0432\u0435\u0440\u0448\u0438\u043d &#8212; \u0433\u0430\u043c\u0438\u043b\u044c\u0442\u043e\u043d\u043e\u0432 \u0446\u0438\u043a\u043b. \u042d\u0442\u043e \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442, \u043a \u043a\u043e\u0442\u043e\u0440\u043e\u043c\u0443 \u0441\u0442\u0440\u0435\u043c\u0438\u043b\u0438\u0441\u044c! \u0411\u0435\u0440\u0435\u043c \u043d\u0430 \u0437\u0430\u043c\u0435\u0442\u043a\u0443 \u0438 \u043e\u0442\u043f\u0440\u0430\u0432\u043b\u044f\u0435\u043c\u0441\u044f \u0432 \u043f\u0443\u0442\u044c!<\/p>\n<figure class=\"\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/post_images\/835\/440\/5ff\/8354405ffbc56c9ff9ffae69d62c66e0.png\" alt=\"\u0413\u0430\u043c\u0438\u043b\u044c\u0442\u043e\u043d\u043e\u0432 \u0446\u0438\u043a\u043b \u0441 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u043c\u0438 \u0437\u0430\u0442\u0440\u0430\u0442\u0430\u043c\u0438\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/835\/440\/5ff\/8354405ffbc56c9ff9ffae69d62c66e0.png\"\/><\/p>\n<div><figcaption>\u0413\u0430\u043c\u0438\u043b\u044c\u0442\u043e\u043d\u043e\u0432 \u0446\u0438\u043a\u043b \u0441 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u043c\u0438 \u0437\u0430\u0442\u0440\u0430\u0442\u0430\u043c\u0438<\/figcaption><\/div>\n<\/figure>\n<p>\u041f\u0440\u043e\u0432\u0435\u0440\u0438\u043c \u0440\u0435\u0448\u0435\u043d\u0438\u0435, \u0434\u043b\u044f \u044d\u0442\u043e\u0433\u043e \u0432\u043e\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u043c\u0441\u044f \u0433\u043e\u0442\u043e\u0432\u044b\u043c \u043c\u043e\u0434\u0443\u043b\u0435\u043c \u043e\u0442 ORTools \u0434\u043b\u044f \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u0437\u0430\u0434\u0430\u0447\u0438 VRP. \u041f\u043e\u0442\u0440\u0435\u0431\u0443\u0435\u0442\u0441\u044f \u043f\u043e\u0434\u0441\u0442\u0440\u043e\u0438\u0442\u044c \u0432\u0445\u043e\u0434\u043d\u044b\u0435 \u0434\u0430\u043d\u043d\u044b\u0435 \u043f\u043e\u0434 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c. \u041c\u0430\u0442\u0440\u0438\u0446\u0430 \u043f\u0435\u0440\u0435\u0445\u043e\u0434\u043e\u0432 \u043c\u0435\u0436\u0434\u0443 \u0443\u0437\u043b\u0430\u043c\u0438 \u0443 \u043d\u0430\u0441 \u043d\u0435\u043f\u043e\u043b\u043d\u0430\u044f, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u0432\u043e\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u043c\u0441\u044f \u0441\u0440\u0430\u0432\u043d\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u0431\u043e\u043b\u044c\u0448\u0438\u043c\u0438 \u0447\u0438\u0441\u043b\u0430\u043c\u0438 \u0432 \u043a\u0430\u0447\u0435\u0441\u0442\u0432\u0435 \u0437\u0430\u0433\u043b\u0443\u0448\u0435\u043a \u0434\u043b\u044f \u043f\u0440\u043e\u043f\u0443\u0449\u0435\u043d\u043d\u044b\u0445 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439. \u041a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0435\u0434\u0438\u043d\u0438\u0446 \u0442\u0440\u0430\u043d\u0441\u043f\u043e\u0440\u0442\u0430 = 1 \u0432 \u0441\u043b\u0443\u0447\u0430\u0435 \u0437\u0430\u0434\u0430\u0447\u0438 TSP, \u0443\u0437\u0435\u043b \u043d\u0430\u0447\u0430\u043b\u0430 \u0438 \u043e\u043a\u043e\u043d\u0447\u0430\u043d\u0438\u044f \u043c\u0430\u0440\u0448\u0440\u0443\u0442\u0430 &#8212; \u041c\u043e\u0441\u043a\u0432\u0430 (0). \u041e\u0442\u043c\u0435\u0447\u0443, \u0447\u0442\u043e \u043c\u0430\u0442\u0440\u0438\u0446\u0430 &#171;\u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0439&#187; \u0434\u043e\u043b\u0436\u043d\u0430 \u0431\u044b\u0442\u044c \u0446\u0435\u043b\u043e\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u043e\u0439.<\/p>\n<details class=\"spoiler\">\n<summary>\u041f\u0430\u043a\u0435\u0442\u043d\u0430\u044f \u0432\u0435\u0440\u0441\u0438\u044f \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u0437\u0430\u0434\u0430\u0447\u0438 VRP \u043e\u0442 ORTools<\/summary>\n<div class=\"spoiler__content\">\n<pre><code class=\"python\">from ortools.constraint_solver import routing_enums_pb2 from ortools.constraint_solver import pywrapcp  # \u0421\u0447\u0438\u0442\u0430\u0435\u043c \u0432\u0445\u043e\u0434\u043d\u044b\u0435 \u0434\u0430\u043d\u043d\u044b\u0435 df_dist = df_cab = pd.read_csv(\"https:\/\/raw.githubusercontent.com\/Lozkins\/mos\/master\/data\/06_tsp_dist.csv\", sep=\";\", encoding=\"cp1251\") df_location = df_cab = pd.read_csv(\"https:\/\/raw.githubusercontent.com\/Lozkins\/mos\/master\/data\/06_tsp_coord.csv\", sep=\";\", encoding=\"cp1251\")  obj_type = \"cost\"  # \u0422\u0438\u043f \u0446\u0435\u043b\u0435\u0432\u043e\u0439 \u0444\u0443\u043d\u043a\u0446\u0438\u0438. \u0414\u043e\u043f\u0443\u0441\u0442\u0438\u043c\u044b\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f [\"cost\", \"travel_time\"] large_M = 10**5 round_mult = 1  def create_data_model():     \"\"\"       \u041f\u043e\u0434\u0433\u043e\u0442\u043e\u0432\u043a\u0430 \u0434\u0430\u043d\u043d\u044b\u0445 \u043a \u0437\u0430\u043f\u0443\u0441\u043a\u0443     \"\"\"     data = {}     dct_dist = df_dist.set_index([\"from\", \"to\"]).to_dict()[obj_type]     # \u041c\u0430\u0442\u0440\u0438\u0446\u0430 \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0439     data[\"distance_matrix\"] = [         [int(dct_dist.get((i, j), 0 if i == j else large_M) * round_mult)  for j in range(df_location.shape[0])]         for i in range(df_location.shape[0])]     # \u041a\u043e\u043b-\u0432\u043e \u0442\u0440\u0430\u043d\u0441\u043f\u043e\u0440\u0442\u043d\u044b\u0445 \u0441\u0440\u0435\u0434\u0441\u0442\u0432 - \u0434\u043b\u044f \u0437\u0430\u0434\u0430\u0447\u0438 TSP - 1     data[\"num_vehicles\"] = 1     # \u0412\u0435\u0440\u0448\u0438\u043d\u0430 \u043d\u0430\u0447\u0430\u043b\u0430 \u0438 \u0437\u0430\u0432\u0435\u0440\u0448\u0435\u043d\u0438\u044f \u043c\u0430\u0440\u0448\u0440\u0443\u0442\u0430     data[\"depot\"] = 0     return data  def print_solution(manager, routing, solution):     \"\"\"       \u0412\u044b\u0432\u043e\u0434 \u0440\u0435\u0448\u0435\u043d\u0438\u044f     \"\"\"     print(f\"\u0417\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0446\u0435\u043b\u0435\u0432\u043e\u0439 \u0444\u0443\u043d\u043a\u0446\u0438\u0438: {solution.ObjectiveValue()} {obj_type}\")     index = routing.Start(0)     plan_output = \"\u041c\u0430\u0440\u0448\u0440\u0443\u0442:\\n\"     route_distance = 0     while not routing.IsEnd(index):         plan_output += f\" {manager.IndexToNode(index)} ->\"         previous_index = index         index = solution.Value(routing.NextVar(index))         route_distance += routing.GetArcCostForVehicle(previous_index, index, 0)     plan_output += f\" {manager.IndexToNode(index)}\\n\"      plan_output += f\"\u041f\u0430\u0440\u0430\u043c\u0435\u0442\u0440 \u043c\u0430\u0440\u0448\u0440\u0443\u0442\u0430: {route_distance} {obj_type}\\n\"  def get_routes(solution, routing, manager):   \"\"\"     \u0418\u0437\u0432\u043b\u0435\u0447\u0435\u043d\u0438\u0435 \u043c\u0430\u0440\u0448\u0440\u0443\u0442\u0430 \u0438\u0437 \u043c\u043e\u0434\u0435\u043b\u0438   \"\"\"   routes = []   for route_nbr in range(routing.vehicles()):     index = routing.Start(route_nbr)     route = [manager.IndexToNode(index)]     while not routing.IsEnd(index):       index = solution.Value(routing.NextVar(index))       route.append(manager.IndexToNode(index))     routes.append(route)   return routes  def main():     \"\"\"       \u0417\u0430\u043f\u0443\u0441\u043a \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430     \"\"\"     # \u0418\u043d\u0438\u0446\u0438\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f \u0434\u0430\u043d\u043d\u044b\u0445     data = create_data_model()      # \u0421\u043e\u0437\u0434\u0430\u043d\u0438\u0435 \u043c\u0435\u043d\u0435\u0434\u0436\u0435\u0440\u0430 \u043c\u0430\u0440\u0448\u0440\u0443\u0442\u0438\u0437\u0430\u0446\u0438\u0438     manager = pywrapcp.RoutingIndexManager(         df_location.shape[0], data[\"num_vehicles\"], data[\"depot\"])      # \u0418\u043d\u0438\u0446\u0438\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f \u043c\u043e\u0434\u0435\u043b\u0438 \u043c\u0430\u0440\u0448\u0440\u0443\u0442\u0438\u0437\u0430\u0446\u0438\u0438     routing = pywrapcp.RoutingModel(manager)      def distance_callback(from_index, to_index):         from_node = manager.IndexToNode(from_index)         to_node = manager.IndexToNode(to_index)         return data[\"distance_matrix\"][from_node][to_node]      transit_callback_index = routing.RegisterTransitCallback(distance_callback)      # \u041e\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u0435\u043c \u0432\u0435\u0441 \u0440\u0435\u0431\u0440\u0430 (\u0441\u0442\u043e\u0438\u043c\u043e\u0441\u0442\u044c \u0438\u043b\u0438 \u0432\u0440\u0435\u043c\u044f \u0432 \u043f\u0443\u0442\u0438)     routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)      # \u0418\u043d\u0438\u0446\u0438\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f \u043d\u0430\u0447\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u0440\u0435\u0448\u0435\u043d\u0438\u0439     search_parameters = pywrapcp.DefaultRoutingSearchParameters()     search_parameters.first_solution_strategy = (         routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC     )      # Solve the problem.     solution = routing.SolveWithParameters(search_parameters)      # Print solution on console.     if solution:         print_solution(manager, routing, solution)         routes = get_routes(solution, routing, manager)         # Display the routes.         for i, route in enumerate(routes):           print('Route', i, route)           return route  route = main()  # \u041f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u0443\u0435\u043c \u0432 \u0442\u0430\u0431\u043b\u0438\u0446\u0443 lst_pairs = list(zip(route[:-1], route[1:])) df_route_ortools = pd.DataFrame(lst_pairs, columns=[\"from\", \"to\"]) df_route_ortools = df_dist.merge(df_route_ortools, how=\"right\", on=[\"from\", \"to\"]) <\/code><\/pre>\n<\/div>\n<\/details>\n<p>\u0421\u0432\u0435\u0434\u0435\u043c \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u044b \u044d\u043a\u0441\u043f\u0435\u0440\u0438\u043c\u0435\u043d\u0442\u043e\u0432 \u0432 \u043e\u0434\u043d\u0443 \u0442\u0430\u0431\u043b\u0438\u0446\u0443. \u041f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u044e \u0442\u0440\u0438 \u0432\u0435\u0440\u0441\u0438\u0438 \u043c\u043e\u0434\u0435\u043b\u0438: \u043f\u043e\u043b\u043d\u0430\u044f \u043c\u043e\u0434\u0435\u043b\u044c \u0441\u043e \u0432\u0441\u0435\u043c\u0438 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f\u043c\u0438 \u0442\u0438\u043f\u0430 (2) (full), \u0438\u0442\u0435\u0440\u0430\u0442\u0438\u0432\u043d\u043e\u0435 \u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u0438\u0435 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f (2) (iter) \u0438 \u043f\u0430\u043a\u0435\u0442\u043d\u0430\u044f \u0432\u0435\u0440\u0441\u0438\u044f \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u0437\u0430\u0434\u0430\u0447\u0438 VRP \u043e\u0442 ORTools (ortools). \u0417\u0430\u043c\u0435\u0440\u044f\u0435\u043c\u044b\u0435 \u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u044b: \u0432\u0440\u0435\u043c\u044f \u0440\u0430\u0441\u0447\u0435\u0442\u0430, \u043a\u043e\u043b-\u0432\u043e \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0439 \u0442\u0438\u043f\u0430 (2), \u043a\u043e\u043b-\u0432\u043e \u0438\u0442\u0435\u0440\u0430\u0446\u0438\u0439 \u0440\u0435\u0448\u0435\u043d\u0438\u044f ILP, \u0437\u0430\u0442\u0440\u0430\u0442\u044b \u043d\u0430 \u043c\u0430\u0440\u0448\u0440\u0443\u0442\u0435 \u0438 \u0434\u043b\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c \u0434\u0432\u0438\u0436\u0435\u043d\u0438\u044f \u043f\u043e \u043c\u0430\u0440\u0448\u0440\u0443\u0442\u0443.<\/p>\n<figure class=\"\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/post_images\/f38\/873\/17c\/f3887317c5a428f103023f8e595fca32.png\" alt=\"\u0420\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u044b \u044d\u043a\u0441\u043f\u0435\u0440\u0438\u043c\u0435\u043d\u0442\u043e\u0432\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/f38\/873\/17c\/f3887317c5a428f103023f8e595fca32.png\"\/><\/p>\n<div><figcaption>\u0420\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u044b \u044d\u043a\u0441\u043f\u0435\u0440\u0438\u043c\u0435\u043d\u0442\u043e\u0432<\/figcaption><\/div>\n<\/figure>\n<h2>\u0420\u0435\u0437\u044e\u043c\u0435<\/h2>\n<p>\u0422\u0435\u043e\u0440\u0435\u0442\u0438\u0447\u0435\u0441\u043a\u0430\u044f \u043f\u043e\u0441\u0442\u0430\u043d\u043e\u0432\u043a\u0430 \u0437\u0430\u0434\u0430\u0447\u0438 \u0441\u043e \u0432\u0441\u0435\u043c\u0438 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f\u043c\u0438 \u0442\u0438\u043f\u0430 (2) \u043e\u043a\u0430\u0437\u0430\u043b\u0430\u0441\u044c \u043d\u0430\u0438\u043c\u0435\u043d\u0435\u0435 \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0439, \u0441 \u0442\u043e\u0447\u043a\u0438 \u0437\u0440\u0435\u043d\u0438\u044f \u0432\u0440\u0435\u043c\u0435\u043d\u0438 \u043f\u043e\u0438\u0441\u043a\u0430 \u043e\u043f\u0442\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u0440\u0435\u0448\u0435\u043d\u0438\u044f. \u0418\u0442\u0435\u0440\u0430\u0442\u0438\u0432\u043d\u0430\u044f \u043f\u043e\u0441\u0442\u0430\u043d\u043e\u0432\u043a\u0430 \u043f\u043e\u0434\u0440\u0430\u0437\u0443\u043c\u0435\u0432\u0430\u0435\u0442 \u0441\u043e\u0437\u0434\u0430\u043d\u0438\u0435 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0439 \u043f\u043e \u043c\u0435\u0440\u0435 \u0438\u0445 \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e\u0441\u0442\u0438, \u043a\u0430\u043a \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 &#8212; \u0441\u043e\u0437\u0434\u0430\u043d\u0438\u0435 \u0434\u043e 10 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0439 \u0442\u0438\u043f\u0430 (2) \u0432\u043c\u0435\u0441\u0442\u043e ~131\u043a \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0439 \u043d\u0430 \u043d\u0430\u0448\u0435\u043c \u0441\u0446\u0435\u043d\u0430\u0440\u0438\u0438. \u041c\u0430\u0441\u0448\u0442\u0430\u0431\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435 \u044d\u0444\u0444\u0435\u043a\u0442\u0430 \u0438\u0442\u0435\u0440\u0430\u0446\u0438\u0439 \u043d\u0430 \u0434\u0440\u0443\u0433\u0438\u0435 \u043d\u0430\u0431\u043e\u0440\u044b \u0434\u0430\u043d\u043d\u044b\u0445 \u043d\u0435 \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442. \u041e\u0441\u0442\u0430\u0435\u0442\u0441\u044f \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e\u0441\u0442\u044c \u0441\u0446\u0435\u043d\u0430\u0440\u0438\u044f, \u043a\u043e\u0433\u0434\u0430 \u0431\u0443\u0434\u0443\u0442 \u0433\u0435\u043d\u0435\u0440\u0438\u0440\u043e\u0432\u0430\u0442\u044c\u0441\u044f \u0437\u043d\u0430\u0447\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u0431\u041e\u043b\u044c\u0448\u0438\u0435 \u043e\u0431\u044a\u0435\u043c\u044b \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0439 \u0442\u0438\u043f\u0430 (2).<\/p>\n<p>\u042d\u043a\u0441\u043f\u0435\u0440\u0438\u043c\u0435\u043d\u0442\u044b \u043f\u0440\u043e\u0432\u043e\u0434\u0438\u043b\u0438 \u043d\u0430 \u0441\u0440\u0430\u0432\u043d\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u043c\u0430\u043b\u043e\u043c \u043a\u043e\u043b-\u0432\u0435 \u0432\u0435\u0440\u0448\u0438\u043d, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u0441\u0440\u0430\u0432\u043d\u0438\u0432\u0430\u0442\u044c \u0438\u0442\u0435\u0440\u0430\u0442\u0438\u0432\u043d\u0443\u044e \u043f\u043e\u0441\u0442\u0430\u043d\u043e\u0432\u043a\u0443 \u0438 ortools \u0431\u0443\u0434\u0435\u0442 \u043d\u0435\u0440\u0435\u043f\u0440\u0435\u0437\u0435\u043d\u0442\u0430\u0442\u0438\u0432\u043d\u043e. \u041e\u0436\u0438\u0434\u0430\u043d\u0438\u0435 &#8212; ortools \u0431\u0443\u0434\u0435\u0442 \u0431\u044b\u0441\u0442\u0440\u0435\u0435.<\/p>\n<p>\u0422\u0430\u043a \u043a\u0443\u0434\u0430 \u0436\u0435 \u0435\u0445\u0430\u0442\u044c? \u0423 \u043d\u0430\u0441 \u0431\u044b\u043b\u0430 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u043f\u043e\u0441\u0442\u0440\u043e\u0438\u0442\u044c \u0441\u0430\u043c\u044b\u0439 \u0431\u044b\u0441\u0442\u0440\u044b\u0439 \u0438 \u0441\u0430\u043c\u044b\u0439 \u0434\u0435\u0448\u0435\u0432\u044b\u0439 \u043c\u0430\u0440\u0448\u0440\u0443\u0442. \u0413\u043e\u0442\u043e\u0432\u044b\u0435 \u043c\u0430\u0440\u0448\u0440\u0443\u0442\u044b \u043f\u043e \u0442\u0443\u0440\u0438\u0441\u0442\u0438\u0447\u0435\u0441\u043a\u0438\u043c \u043c\u0435\u0441\u0442\u0430\u043c \u043e\u0442 \u0414\u0430\u0448\u0438 \u0412\u0430\u0441\u0438\u043b\u044c\u0435\u0432\u043e\u0439:<\/p>\n<p><strong>\u0421\u0430\u043c\u044b\u0439 \u0434\u0435\u0448\u0435\u0432\u044b\u0439 \u043c\u0430\u0440\u0448\u0440\u0443\u0442 (101 833 \u0440\u0443\u0431 \/ 124,3 \u0447):<\/strong> \u041c\u043e\u0441\u043a\u0432\u0430 -> \u0412\u043e\u043b\u0433\u043e\u0433\u0440\u0430\u0434 -> \u041a\u0430\u0440\u0435\u043b\u0438\u044f\/\u041f\u0435\u0442\u0440\u043e\u0437\u0430\u0432\u043e\u0434\u0441\u043a -> \u041f\u0441\u043a\u043e\u0432 -> \u0421\u0430\u043d\u043a\u0442-\u041f\u0435\u0442\u0435\u0440\u0431\u0443\u0440\u0433 -> \u0421\u0435\u043b\u043e \u0422\u0435\u0440\u0438\u0431\u0435\u0440\u043a\u0430\/\u041c\u0443\u0440\u043c\u0430\u043d\u0441\u043a -> \u041a\u0430\u043b\u0438\u043d\u0438\u043d\u0433\u0440\u0430\u0434 -> \u041b\u0438\u0441\u0442\u0432\u044f\u043d\u043a\u0430\/\u0418\u0440\u043a\u0443\u0442\u0441\u043a -> \u041a\u0440\u0430\u0441\u043d\u043e\u044f\u0440\u0441\u043a -> \u042e\u0436\u043d\u043e-\u0421\u0430\u0445\u0430\u043b\u0438\u043d\u0441\u043a  -> \u0411\u043b\u0430\u0433\u043e\u0432\u0435\u0449\u0435\u043d\u0441\u043a -> \u0428\u0435\u0440\u0435\u0433\u0435\u0448\/\u041d\u043e\u0432\u043e\u043a\u0443\u0437\u043d\u0435\u0446\u043a -> \u041d\u043e\u0432\u043e\u0441\u0438\u0431\u0438\u0440\u0441\u043a -> \u0410\u043b\u0442\u0430\u0439\/\u0413\u043e\u0440\u043d\u043e-\u0410\u043b\u0442\u0430\u0439\u0441\u043a -> \u041a\u0430\u0437\u0430\u043d\u044c -> \u0421\u043e\u0447\u0438 -> \u041c\u043e\u0441\u043a\u0432\u0430<\/p>\n<p><strong>\u0421\u0430\u043c\u044b\u0439 \u0431\u044b\u0441\u0442\u0440\u044b\u0439 \u043c\u0430\u0440\u0448\u0440\u0443\u0442 (137 770 \u0440\u0443\u0431 \/ 71,55 \u0447):<\/strong> \u041c\u043e\u0441\u043a\u0432\u0430 -> \u0421\u0435\u043b\u043e \u0422\u0435\u0440\u0438\u0431\u0435\u0440\u043a\u0430\/\u041c\u0443\u0440\u043c\u0430\u043d\u0441\u043a -> \u041a\u0430\u043b\u0438\u043d\u0438\u043d\u0433\u0440\u0430\u0434 -> \u041f\u0441\u043a\u043e\u0432 -> \u041a\u0430\u0440\u0435\u043b\u0438\u044f\/\u041f\u0435\u0442\u0440\u043e\u0437\u0430\u0432\u043e\u0434\u0441\u043a -> \u0412\u043e\u043b\u0433\u043e\u0433\u0440\u0430\u0434 -> \u0421\u0430\u043d\u043a\u0442-\u041f\u0435\u0442\u0435\u0440\u0431\u0443\u0440\u0433 -> \u041a\u0430\u0437\u0430\u043d\u044c -> \u0421\u043e\u0447\u0438 -> \u041b\u0438\u0441\u0442\u0432\u044f\u043d\u043a\u0430\/\u0418\u0440\u043a\u0443\u0442\u0441\u043a -> \u041a\u0440\u0430\u0441\u043d\u043e\u044f\u0440\u0441\u043a -> \u0411\u043b\u0430\u0433\u043e\u0432\u0435\u0449\u0435\u043d\u0441\u043a -> \u042e\u0436\u043d\u043e-\u0421\u0430\u0445\u0430\u043b\u0438\u043d\u0441\u043a  -> \u0410\u043b\u0442\u0430\u0439\/\u0413\u043e\u0440\u043d\u043e-\u0410\u043b\u0442\u0430\u0439\u0441\u043a -> \u041d\u043e\u0432\u043e\u0441\u0438\u0431\u0438\u0440\u0441\u043a -> \u0428\u0435\u0440\u0435\u0433\u0435\u0448\/\u041d\u043e\u0432\u043e\u043a\u0443\u0437\u043d\u0435\u0446\u043a -> \u041c\u043e\u0441\u043a\u0432\u0430<\/p>\n<hr\/>\n<p>\u0411\u0443\u0434\u0435\u043c \u0440\u0430\u0434\u044b \u0437\u0430 \u043f\u0440\u0435\u0434\u043b\u043e\u0436\u0435\u043d\u0438\u044f \u043f\u043e \u043b\u043e\u043a\u0430\u0446\u0438\u044f\u043c \u0438 \u043a\u0440\u0438\u0442\u0435\u0440\u0438\u044f\u043c. \u0411\u044b\u0442\u044c \u043c\u043e\u0436\u0435\u0442, \u043a\u0442\u043e-\u0442\u043e \u0438\u0437 \u043d\u0430\u0441 \u0440\u0435\u0448\u0438\u0442\u0441\u044f \u043d\u0430 \u0434\u043b\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0435 \u0442\u0443\u0440\u043d\u0435 \u0438 \u043e\u0431\u043a\u0430\u0442\u0430\u0435\u0442 \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u0432\u0436\u0438\u0432\u0443\u044e. \u0422\u0435\u0445\u043d\u0438\u0447\u0435\u0441\u043a\u0430\u044f \u0432\u0435\u0440\u0441\u0438\u044f \u0441\u0442\u0430\u0442\u044c\u0438 <a href=\"https:\/\/github.com\/Lozkins\/mos\/blob\/master\/06_Traveling_in_Russia.ipynb\">\u0437\u0434\u0435\u0441\u044c<\/a><\/p>\n<h2>\u0421\u0445\u043e\u0436\u0438\u0435 \u043c\u0430\u0442\u0435\u0440\u0438\u0430\u043b\u044b<\/h2>\n<ul>\n<li>\n<p><a href=\"https:\/\/habr.com\/ru\/articles\/745300\/\">\u041f\u0440\u043e\u0433\u0443\u043b\u043a\u0430 \u043f\u043e \u043c\u043e\u0441\u0442\u0430\u043c \u041a\u0451\u043d\u0438\u0433\u0441\u0431\u0435\u0440\u0433\u0430<\/a><\/p>\n<\/li>\n<li>\n<p><a href=\"https:\/\/habr.com\/ru\/articles\/772012\/\">\u041c\u043e\u0434\u0435\u043b\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435 \u0440\u0430\u0437\u043c\u0435\u0449\u0435\u043d\u0438\u044f \u0445\u0430\u0431\u043e\u0432 \u0432 \u0441\u0435\u0442\u0438<\/a><\/p>\n<\/li>\n<li>\n<p><a href=\"https:\/\/habr.com\/ru\/articles\/765116\/\">\u0424\u0438\u0447\u0438 \u043b\u0438\u043d\u0435\u0439\u043d\u043e\u0433\u043e \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f<\/a><\/p>\n<\/li>\n<\/ul>\n<\/div>\n<\/div>\n<\/div>\n<p><!----><!----><\/div>\n<p><!----><!----><br \/> \u0441\u0441\u044b\u043b\u043a\u0430 \u043d\u0430 \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b \u0441\u0442\u0430\u0442\u044c\u0438 <a href=\"https:\/\/habr.com\/ru\/articles\/778782\/\"> https:\/\/habr.com\/ru\/articles\/778782\/<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<div><!--[--><!--]--><\/div>\n<div id=\"post-content-body\">\n<div>\n<div class=\"article-formatted-body article-formatted-body article-formatted-body_version-2\">\n<div xmlns=\"http:\/\/www.w3.org\/1999\/xhtml\">\n<figure class=\"\"><\/figure>\n<p>\u0421 \u0432\u0430\u043c\u0438 \u0410\u043b\u0435\u043a\u0441\u0435\u0439 \u041b\u043e\u0436\u043a\u0438\u043d\u0441, \u044d\u043a\u0441\u043f\u0435\u0440\u0442 \u043f\u043e \u0430\u043d\u0430\u043b\u0438\u0437\u0443 \u0434\u0430\u043d\u043d\u044b\u0445 \u0438 \u043c\u0430\u0448\u0438\u043d\u043d\u043e\u043c\u0443 \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u044e \u0432 \u041f\u0413\u041a \u0414\u0438\u0434\u0436\u0438\u0442\u0430\u043b. \u041c\u044b \u0440\u0430\u0437\u0440\u0430\u0431\u0430\u0442\u044b\u0432\u0430\u0435\u043c \u0446\u0438\u0444\u0440\u043e\u0432\u044b\u0435 \u043f\u0440\u043e\u0434\u0443\u043a\u0442\u044b \u0434\u043b\u044f \u043b\u043e\u0433\u0438\u0441\u0442\u0438\u0447\u0435\u0441\u043a\u043e\u0439 \u043e\u0442\u0440\u0430\u0441\u043b\u0438, \u0432 \u043f\u0435\u0440\u0432\u0443\u044e \u043e\u0447\u0435\u0440\u0435\u0434\u044c, \u0434\u043b\u044f \u0436\/\u0434 \u043f\u0435\u0440\u0435\u0432\u043e\u0437\u043e\u043a.<\/p>\n<p>\u0412 \u043a\u0443\u043b\u0443\u0430\u0440\u0430\u0445 \u043c\u043e\u0441\u043a\u043e\u0432\u0441\u043a\u043e\u0433\u043e \u043e\u0444\u0438\u0441\u0430 \u041f\u0413\u041a \u043c\u044b \u043e\u0431\u0441\u0443\u0436\u0434\u0430\u0435\u043c \u0438 \u043d\u0435\u0440\u0430\u0431\u043e\u0447\u0438\u0435 \u0442\u0435\u043c\u044b. \u0422\u043e\u043f\u043e\u0432\u0443\u044e \u0441\u0442\u0440\u043e\u0447\u043a\u0443 \u0432 \u0442\u0435\u043c\u0430\u0445 \u043d\u0435\u0444\u043e\u0440\u043c\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u043e\u0431\u0449\u0435\u043d\u0438\u044f \u0437\u0430\u043d\u0438\u043c\u0430\u0435\u0442 \u043e\u0442\u043f\u0443\u0441\u043a. \u041c\u044b \u0440\u0435\u0448\u0438\u043b\u0438 \u0440\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0435\u0442\u044c \u0437\u0430\u0434\u0430\u0447\u0443 \u043f\u043b\u0430\u043d\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f \u043e\u0442\u043f\u0443\u0441\u043a\u0430, \u043a\u0430\u043a \u0437\u0430\u0434\u0430\u0447\u0443 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u0438 \u043c\u0430\u0440\u0448\u0440\u0443\u0442\u0430 \u043f\u043e \u0432\u044b\u0431\u0440\u0430\u043d\u043d\u044b\u043c \u0434\u043e\u0441\u0442\u043e\u043f\u0440\u0438\u043c\u0435\u0447\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044f\u043c. \u0414\u043b\u044f \u044d\u0442\u043e\u0433\u043e \u0432\u043e\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043b\u0438\u0441\u044c \u043a\u043b\u0430\u0441\u0441\u0438\u0447\u0435\u0441\u043a\u043e\u0439 \u043f\u043e\u0441\u0442\u0430\u043d\u043e\u0432\u043a\u043e\u0439 \u0437\u0430\u0434\u0430\u0447\u0438 \u043a\u043e\u043c\u043c\u0438\u0432\u043e\u044f\u0436\u0435\u0440\u0430.<\/p>\n<p>\u041c\u043e\u0434\u0435\u043b\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435 \u043c\u0430\u0440\u0448\u0440\u0443\u0442\u0430 \u0432 \u0432\u0438\u0434\u0435 \u0437\u0430\u0434\u0430\u0447\u0438 \u043a\u043e\u043c\u043c\u0438\u0432\u043e\u044f\u0436\u0435\u0440\u0430 \u043f\u043e\u0437\u0432\u043e\u043b\u0438\u0442 \u043f\u043e\u0441\u0442\u0440\u043e\u0438\u0442\u044c \u043c\u0430\u0440\u0448\u0440\u0443\u0442 \u043f\u043e \u0432\u0441\u0435\u043c \u0437\u0430\u043f\u043b\u0430\u043d\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u043c \u043b\u043e\u043a\u0430\u0446\u0438\u044f\u043c \u0431\u0435\u0437 \u043f\u043e\u0432\u0442\u043e\u0440\u0435\u043d\u0438\u0439 \u0441 \u0437\u0430\u0434\u0430\u043d\u043d\u044b\u043c \u043a\u0440\u0438\u0442\u0435\u0440\u0438\u0435\u043c \u043a\u0430\u0447\u0435\u0441\u0442\u0432\u0430 (\u0432\u0440\u0435\u043c\u044f, \u0441\u0442\u043e\u0438\u043c\u043e\u0441\u0442\u044c). \u0420\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u043f\u043e\u0434\u0445\u043e\u0434\u043e\u0432 \u043a \u0440\u0435\u0448\u0435\u043d\u0438\u044e \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u043e\u043d\u043d\u043e\u0439 \u0437\u0430\u0434\u0430\u0447\u0438 (TSP) \u0441 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u0435\u043c \u043f\u0430\u043a\u0435\u0442\u0430 ORTools.<\/p>\n<h2>\u041e \u0437\u0430\u0434\u0430\u0447\u0435 \u043a\u043e\u043c\u043c\u0438\u0432\u043e\u044f\u0436\u0435\u0440\u0430 (TSP)<\/h2>\n<p>\u0414\u043e\u0441\u0442\u0430\u0432\u043a\u0430 \u0440\u0430\u0437\u043d\u044b\u0445 \u0442\u043e\u0432\u0430\u0440\u043e\u0432 \u043e\u0447\u0435\u043d\u044c \u043f\u043e\u043f\u0443\u043b\u044f\u0440\u043d\u0430\u044f \u0443\u0441\u043b\u0443\u0433\u0430 \u0441\u0435\u0433\u043e\u0434\u043d\u044f. \u0427\u0442\u043e\u0431\u044b \u0441\u043d\u0438\u0437\u0438\u0442\u044c \u0441\u0435\u0431\u0435\u0441\u0442\u043e\u0438\u043c\u043e\u0441\u0442\u044c \u0438 \u0446\u0435\u043d\u0443 \u043d\u0430 \u0443\u0441\u043b\u0443\u0433\u0438 \u0434\u043b\u044f \u043f\u043e\u0442\u0440\u0435\u0431\u0438\u0442\u0435\u043b\u044f, \u0437\u0430\u043a\u0430\u0437\u044b \u043e\u0431\u044a\u0435\u0434\u0438\u043d\u044f\u044e\u0442 \u0438 \u0434\u043e\u0441\u0442\u0430\u0432\u043b\u044f\u044e\u0442\u0441\u044f \u043e\u0434\u043d\u0438\u043c \u043a\u0443\u0440\u044c\u0435\u0440\u043e\u043c. \u0417\u0434\u0435\u0441\u044c \u043f\u043e\u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0442\u0430\u043a \u043d\u0430\u0437\u044b\u0432\u0430\u0435\u043c\u044b\u0439 \u044d\u0444\u0444\u0435\u043a\u0442 \u043c\u0430\u0441\u0448\u0442\u0430\u0431\u0430, \u043a\u043e\u0433\u0434\u0430 \u0441\u0435\u0431\u0435\u0441\u0442\u043e\u0438\u043c\u043e\u0441\u0442\u044c \u0434\u043e\u0441\u0442\u0430\u0432\u043a\u0438 \u0435\u0434\u0438\u043d\u0438\u0446\u044b \u0437\u0430\u043a\u0430\u0437\u0430 \u0441\u043d\u0438\u0436\u0430\u0435\u0442\u0441\u044f \u0441 \u0443\u0432\u0435\u043b\u0438\u0447\u0435\u043d\u0438\u0435\u043c \u0438\u0445 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0430.<\/p>\n<p>\u041f\u0440\u0438 \u0440\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0435\u043d\u0438\u0438 \u043e\u0434\u043d\u043e\u0433\u043e \u043a\u0443\u0440\u044c\u0435\u0440\u0430 \u0438 \u043f\u0443\u043b\u0430 \u0437\u0430\u043a\u0430\u0437\u043e\u0432, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043e\u043d \u0434\u043e\u043b\u0436\u0435\u043d \u0434\u043e\u0441\u0442\u0430\u0432\u0438\u0442\u044c, \u0432\u043e\u0437\u043d\u0438\u043a\u0430\u0435\u0442 \u043a\u043b\u0430\u0441\u0441\u0438\u0447\u0435\u0441\u043a\u0430\u044f \u0437\u0430\u0434\u0430\u0447\u0430 \u043a\u043e\u043c\u043c\u0438\u0432\u043e\u044f\u0436\u0435\u0440\u0430. \u0412 \u0431\u043e\u043b\u0435\u0435 \u0441\u043b\u043e\u0436\u043d\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435, \u043a\u043e\u0433\u0434\u0430 \u0443 \u043d\u0430\u0441 \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u043a\u0443\u0440\u044c\u0435\u0440\u043e\u0432, \u0437\u0430\u0434\u0430\u0447\u0430 \u043a\u043e\u043c\u043c\u0438\u0432\u043e\u044f\u0436\u0435\u0440\u0430 \u044d\u0432\u043e\u043b\u044e\u0446\u0438\u043e\u043d\u0438\u0440\u0443\u0435\u0442 \u0432 <a href=\"https:\/\/en.wikipedia.org\/wiki\/Vehicle_routing_problem\">vehicle routing problem<\/a>, \u043d\u043e \u044d\u0442\u043e \u0443\u0436\u0435 \u0434\u0440\u0443\u0433\u0430\u044f \u0438\u0441\u0442\u043e\u0440\u0438\u044f.<\/p>\n<p>\u0417\u0434\u0435\u0441\u044c \u0440\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u0437\u0430\u0434\u0430\u0447\u0438 \u043a\u043e\u043c\u043c\u0438\u0432\u043e\u044f\u0436\u0435\u0440\u0430 \u0434\u043b\u044f \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u044f \u0442\u0443\u0440\u0438\u0441\u0442\u0438\u0447\u0435\u0441\u043a\u043e\u0433\u043e \u043c\u0430\u0440\u0448\u0440\u0443\u0442\u0430 \u043d\u0430 \u043f\u0440\u0438\u043c\u0435\u0440\u0435 \u043b\u043e\u043a\u0430\u0446\u0438\u0439 \u043d\u0430 \u0442\u0435\u0440\u0440\u0438\u0442\u043e\u0440\u0438\u0438 \u0420\u043e\u0441\u0441\u0438\u0438. \u0422\u0440\u0435\u0431\u043e\u0432\u0430\u043d\u0438\u044f \u043a \u043c\u0430\u0440\u0448\u0440\u0443\u0442\u0443 \u043c\u043e\u0433\u0443\u0442 \u0431\u044b\u0442\u044c \u0440\u0430\u0437\u043d\u044b\u043c\u0438, \u0440\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u043d\u0430\u0438\u0431\u043e\u043b\u0435\u0435 \u043f\u043e\u043f\u0443\u043b\u044f\u0440\u043d\u044b\u0435: \u0441\u0430\u043c\u044b\u0439 \u0431\u044b\u0441\u0442\u0440\u044b\u0439 \u0438\u043b\u0438 \u0441\u0430\u043c\u044b\u0439 \u0434\u0435\u0448\u0435\u0432\u044b\u0439.<\/p>\n<h2>\u0422\u0443\u0440\u0438\u0441\u0442\u0438\u0447\u0435\u0441\u043a\u0438\u0435 \u043b\u043e\u043a\u0430\u0446\u0438\u0438: \u0434\u0430\u043d\u043d\u044b\u0435<\/h2>\n<p>\u041a\u0443\u0434\u0430 \u043c\u044b \u0445\u043e\u0442\u0438\u043c \u043f\u043e\u0435\u0445\u0430\u0442\u044c? \u0421\u043e\u0431\u0435\u0440\u0435\u043c \u043f\u043e\u0436\u0435\u043b\u0430\u043d\u0438\u044f \u0432 \u0441\u043f\u0438\u0441\u043e\u043a. \u0414\u0430\u0440\u044c\u044f \u0412\u0430\u0441\u0438\u043b\u044c\u0435\u0432\u0430 (\u043a\u043e\u043e\u0440\u0434\u0438\u043d\u0430\u0442\u043e\u0440 \u0443\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u0438\u044f \u0430\u043d\u0430\u043b\u0438\u0437\u0430 \u0434\u0430\u043d\u043d\u044b\u0445 \u0438 \u043c\u0430\u0448\u0438\u043d\u043d\u043e\u0433\u043e \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u044f)\u043f\u043e\u0434\u0433\u043e\u0442\u043e\u0432\u0438\u043b\u0430 \u0441\u0432\u043e\u0439 \u0432\u0430\u0440\u0438\u0430\u043d\u0442 \u0442\u0430\u043a\u043e\u0433\u043e \u0441\u043f\u0438\u0441\u043a\u0430, \u0441 \u043a\u043e\u0442\u043e\u0440\u044b\u043c \u043c\u043e\u0436\u043d\u043e \u043e\u0437\u043d\u0430\u043a\u043e\u043c\u0438\u0442\u044c\u0441\u044f <a href=\"https:\/\/github.com\/Lozkins\/mos\/blob\/master\/data\/06_tsp_coord.csv\">\u0437\u0434\u0435\u0441\u044c<\/a>, \u043e\u0442\u0434\u0435\u043b\u044c\u043d\u043e\u0435 \u0441\u043f\u0430\u0441\u0438\u0431\u043e \u0435\u0439 \u0437\u0430 \u044d\u0442\u043e! \u041f\u043e\u043c\u0438\u043c\u043e \u043b\u043e\u043a\u0430\u0446\u0438\u0439 \u043f\u043e\u0442\u0440\u0435\u0431\u0443\u044e\u0442\u0441\u044f \u0440\u0435\u0431\u0440\u0430 &#8212; \u0441\u0432\u044f\u0437\u044c \u043c\u0435\u0436\u0434\u0443 \u043b\u043e\u043a\u0430\u0446\u0438\u044f\u043c\u0438.<\/p>\n<figure class=\"\">\n<div><figcaption>\u0420\u0435\u043a\u043e\u043c\u0435\u043d\u0434\u0443\u0435\u043c\u044b\u0435 \u043b\u043e\u043a\u0430\u0446\u0438\u0438 \u043a \u043f\u043e\u0441\u0435\u0449\u0435\u043d\u0438\u044e<\/figcaption><\/div>\n<\/figure>\n<p>\u0420\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u043d\u0435\u043f\u043e\u043b\u043d\u044b\u0439 \u0433\u0440\u0430\u0444 (\u0432\u043e\u0437\u043c\u043e\u0436\u043d\u044b \u043d\u0435 \u0432\u0441\u0435 \u0441\u043e\u0435\u0434\u0438\u043d\u0435\u043d\u0438\u044f \u043c\u0435\u0436\u0434\u0443 \u0433\u043e\u0440\u043e\u0434\u0430\u043c\u0438, \u0430 \u043d\u0430\u0438\u0431\u043e\u043b\u0435\u0435 \u0440\u0430\u0446\u0438\u043e\u043d\u0430\u043b\u044c\u043d\u044b\u0435 \u0440\u0435\u0431\u0440\u0430). \u0413\u0435\u043e\u0433\u0440\u0430\u0444\u0438\u044f \u043f\u0440\u0435\u0434\u043b\u0430\u0433\u0430\u0435\u043c\u044b\u0445 \u043c\u0435\u0441\u0442 \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u043e\u0431\u0448\u0438\u0440\u043d\u0430\u044f, \u0438 \u0432\u0440\u0435\u043c\u044f \u0441\u043b\u0435\u0434\u043e\u0432\u0430\u043d\u0438\u044f \u0436\/\u0434 \u0438\u043b\u0438 \u0430\u0432\u0442\u043e \u0442\u0440\u0430\u043d\u0441\u043f\u043e\u0440\u0442\u043e\u043c \u043c\u043e\u0436\u0435\u0442 \u0437\u0430\u043d\u0438\u043c\u0430\u0442\u044c \u0440\u0430\u0431\u043e\u0447\u0443\u044e \u043d\u0435\u0434\u0435\u043b\u044e, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u0441\u0434\u0435\u043b\u0430\u043b\u0438 \u0430\u043a\u0446\u0435\u043d\u0442 \u043d\u0430 \u0430\u0432\u0438\u0430\u043f\u0435\u0440\u0435\u0432\u043e\u0437\u043a\u0438. \u0415\u0441\u043b\u0438 \u0445\u043e\u0442\u0438\u0442\u0435 \u043d\u0430\u0441\u044b\u0442\u0438\u0442\u044c \u043f\u043e\u0435\u0437\u0434\u043a\u0443 \u0436\/\u0434 \u0430\u043d\u0442\u0443\u0440\u0430\u0436\u0435\u043c, \u0442\u043e \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u043d\u0430\u043f\u043e\u043b\u043d\u0438\u0442\u044c \u0432\u0445\u043e\u0434\u043d\u044b\u0435 \u0434\u0430\u043d\u043d\u044b\u0435 \u0442\u0430\u0440\u0438\u0444\u0430\u043c\u0438 \u0438 \u0432\u0440\u0435\u043c\u0435\u043d\u0435\u043c \u0432 \u0445\u043e\u0434\u0443 \u0434\u043b\u044f \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u0443\u044e\u0449\u0438\u0445 \u0440\u0435\u0431\u0435\u0440. \u041c\u043e\u0434\u0435\u043b\u044c \u043c\u043e\u0436\u043d\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u0438 \u0434\u043b\u044f \u0433\u0440\u0443\u0437\u043e\u043f\u0435\u0440\u0435\u0432\u043e\u0437\u043e\u043a \u043f\u043e \u0436\u0435\u043b\u0435\u0437\u043d\u043e\u0439 \u0434\u043e\u0440\u043e\u0433\u0435 \u0432 \u0442\u043e\u043c \u0447\u0438\u0441\u043b\u0435. \u0421 \u0433\u0440\u0430\u0444\u043e\u043c \u0434\u043e\u043f\u0443\u0441\u0442\u0438\u043c\u044b\u0445 \u043f\u0435\u0440\u0435\u043c\u0435\u0449\u0435\u043d\u0438\u0439 \u043c\u043e\u0436\u043d\u043e \u043e\u0437\u043d\u0430\u043a\u043e\u043c\u0438\u0442\u044c\u0441\u044f <a href=\"https:\/\/github.com\/Lozkins\/mos\/blob\/master\/data\/06_tsp_dist.csv\">\u0437\u0434\u0435\u0441\u044c<\/a>.<\/p>\n<figure class=\"\">\n<div><figcaption>\u0420\u0435\u0431\u0440\u0430 \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u0435\u043c\u043e\u0433\u043e \u0433\u0440\u0430\u0444\u0430<\/figcaption><\/div>\n<\/figure>\n<h2>\u0422\u0435\u0445\u043d\u0438\u0447\u0435\u0441\u043a\u0438\u0439 \u0441\u0442\u044d\u043a<\/h2>\n<p>\u041f\u0440\u0435\u0436\u0434\u0435 \u0447\u0435\u043c \u043f\u0435\u0440\u0435\u0445\u043e\u0434\u0438\u0442\u044c \u043a \u0442\u0435\u0445\u043d\u0438\u0447\u0435\u0441\u043a\u043e\u0439 \u0447\u0430\u0441\u0442\u0438, \u043e\u0431\u0441\u0443\u0434\u0438\u043c \u0438\u043d\u0441\u0442\u0440\u0443\u043c\u0435\u043d\u0442\u044b \u0438 \u043f\u043e\u0434\u0445\u043e\u0434. \u041c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u0438\u0439 \u0430\u043f\u043f\u0430\u0440\u0430\u0442 \u0434\u043b\u044f \u043c\u043e\u0434\u0435\u043b\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f \u0437\u0430\u0434\u0430\u0447\u0438 &#8212; \u0446\u0435\u043b\u043e\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u043e\u0435 \u043b\u0438\u043d\u0435\u0439\u043d\u043e\u0435 \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435 (ILP), \u043e\u0442\u043d\u043e\u0441\u0438\u0442\u0441\u044f \u043a \u0442\u043e\u0447\u043d\u044b\u043c \u043c\u0435\u0442\u043e\u0434\u0430\u043c. \u041f\u043e\u0441\u0442\u0430\u043d\u043e\u0432\u043a\u0430 \u0432 ILP \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u043f\u0440\u0438\u043c\u0435\u043d\u0438\u0442\u044c \u0443\u0436\u0435 \u0433\u043e\u0442\u043e\u0432\u044b\u0435 \u043f\u0430\u043a\u0435\u0442\u044b (\u0441\u043e\u043b\u0432\u0435\u0440\u044b) \u0434\u043b\u044f \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u043e\u043d\u043d\u043e\u0439 \u0437\u0430\u0434\u0430\u0447\u0438 \u0438 \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c \u0442\u043e\u0447\u043d\u043e\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u043d\u0430 \u0432\u044b\u0445\u043e\u0434\u0435.<\/p>\n<p>\u0421\u043e\u043b\u0432\u0435\u0440\u044b \u043c\u043e\u0436\u043d\u043e \u0440\u0430\u0437\u0434\u0435\u043b\u0438\u0442\u044c \u043d\u0430 \u0431\u0435\u0441\u043f\u043b\u0430\u0442\u043d\u044b\u0435 open-source \u0441\u043e\u043b\u0432\u0435\u0440\u044b (cbc, scip, highs, glpk \u0438 \u0434\u0440.) \u0438 \u043a\u043e\u043c\u043c\u0435\u0440\u0447\u0435\u0441\u043a\u0438\u0435 (gurobi, copt, cplex, optverse \u0438 \u0434\u0440.). \u0422\u0430\u043a \u043a\u0430\u043a \u0441\u043e\u043b\u0432\u0435\u0440\u044b \u043f\u0440\u0438\u043c\u0435\u043d\u044f\u044e\u0442\u0441\u044f \u0442\u043e\u043b\u044c\u043a\u043e \u0434\u043b\u044f \u043c\u043e\u0434\u0435\u043b\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f \u0438 \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u0437\u0430\u0434\u0430\u0447, \u0442\u043e \u0441\u043f\u0435\u043a\u0442\u0440 \u043e\u0442\u043b\u0438\u0447\u0438\u0439 \u0443 \u043d\u0438\u0445 \u043d\u0435 \u0431\u043e\u043b\u044c\u0448\u043e\u0439: API \u0438 \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c. \u0412\u043e\u043f\u0440\u043e\u0441 API \u0440\u0435\u0448\u0430\u0435\u0442\u0441\u044f \u0441\u0442\u043e\u0440\u043e\u043d\u043d\u0438\u043c\u0438 \u043e\u0431\u0435\u0440\u0442\u043a\u0430\u043c\u0438 \u043d\u0430\u0434 \u0441\u043e\u043b\u0432\u0435\u0440\u0430\u043c\u0438, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u044e\u0442 \u043c\u043e\u0434\u0435\u043b\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0438 \u043f\u043e\u0434\u043a\u043b\u044e\u0447\u0430\u0442\u044c \u0440\u0430\u0437\u043b\u0438\u0447\u043d\u044b\u0435 \u0441\u043e\u043b\u0432\u0435\u0440\u044b \u0434\u043b\u044f \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u0437\u0430\u0434\u0430\u0447 (\u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, PuLP, Pyomo, ORTools, FeLooPy, GAMS \u0438 \u0434\u0440.). \u041a\u0430\u043a \u0441\u043b\u0435\u0434\u0441\u0442\u0432\u0438\u0435, \u043a\u043e\u043c\u043c\u0435\u0440\u0447\u0435\u0441\u043a\u0438\u0435 \u0441\u043e\u043b\u0432\u0435\u0440\u044b &#171;\u043f\u043e\u0447\u0442\u0438 \u0432\u0435\u0437\u0434\u0435&#187; \u043f\u0440\u0435\u0432\u043e\u0441\u0445\u043e\u0434\u044f\u0442 \u043f\u043e \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438 open-source, \u0431\u043e\u043b\u044c\u0448\u0435 \u0444\u0430\u043a\u0442\u043e\u0432 <a href=\"https:\/\/plato.asu.edu\/ftp\/milp.html\">\u0437\u0434\u0435\u0441\u044c<\/a>.<\/p>\n<p>\u0417\u0430\u0444\u0438\u043a\u0441\u0438\u0440\u0443\u0435\u043c \u0441\u0442\u044d\u043a. \u0420\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044e \u043c\u043e\u0434\u0435\u043b\u0438 \u0441\u0434\u0435\u043b\u0430\u0435\u043c \u043d\u0430 python, \u0441\u0440\u0435\u0434\u0430 \u0434\u043b\u044f \u043c\u043e\u0434\u0435\u043b\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f <a href=\"https:\/\/developers.google.com\/optimization?hl=en\">ORTools<\/a>, \u0441\u043e\u043b\u0432\u0435\u0440 open-source cp-sat (ORTools), \u0432\u0438\u0437\u0443\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044e \u0431\u0443\u0434\u0435\u043c \u043f\u0440\u043e\u0432\u043e\u0434\u0438\u0442\u044c \u0432 plotly, \u043d\u0435\u043c\u043d\u043e\u0433\u043e \u043f\u043e\u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u043c pandas \u0438 networkx.<\/p>\n<p>\u041f\u043e \u043f\u043e\u0432\u043e\u0434\u0443 \u0441\u043e\u043b\u0432\u0435\u0440\u0430, cp-sat \u043d\u0435 \u0441\u043e\u0432\u0441\u0435\u043c \u0440\u0435\u0448\u0430\u0442\u0435\u043b\u044c \u0437\u0430\u0434\u0430\u0447 \u0446\u0435\u043b\u043e\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u043e\u0433\u043e \u043b\u0438\u043d\u0435\u0439\u043d\u043e\u0433\u043e \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f, \u043d\u043e \u0432 \u0442\u043e\u043c \u0447\u0438\u0441\u043b\u0435 \u043f\u043e\u043a\u0440\u044b\u0432\u0430\u0435\u0442 \u044d\u0442\u043e\u0442 \u043a\u043b\u0430\u0441\u0441 \u0437\u0430\u0434\u0430\u0447. \u0414\u0435\u0442\u0430\u043b\u044c\u043d\u043e \u0432 \u0441\u043f\u0435\u0446\u0438\u0444\u0438\u043a\u0443 \u043d\u0435 \u0431\u0443\u0434\u0435\u043c \u0443\u0445\u043e\u0434\u0438\u0442\u044c (\u043a\u043b\u044e\u0447\u0435\u0432\u044b\u0435 \u0441\u043b\u043e\u0432\u0430 \u0434\u043b\u044f \u0442\u0435\u0445 \u043a\u0442\u043e \u0445\u043e\u0447\u0435\u0442: constraint programming, boolean satisfability). \u041a\u0440\u043e\u043c\u0435 \u0442\u043e\u0433\u043e, ORTools \u0438\u043c\u0435\u0435\u0442 \u043e\u0442\u0434\u0435\u043b\u044c\u043d\u044b\u0439 \u043d\u0430\u0431\u043e\u0440 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u0432 \u0434\u043b\u044f \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u0437\u0430\u0434\u0430\u0447\u0438 vehicle routing problem, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u0432 \u0447\u0430\u0441\u0442\u043d\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u044d\u043a\u0432\u0438\u0432\u0430\u043b\u0435\u043d\u0442\u043d\u0430 \u0437\u0430\u0434\u0430\u0447\u0435 TSP. \u0412\u043e\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u043c\u0441\u044f \u044d\u0442\u0438\u043c\u0438 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430\u043c\u0438 \u0434\u043b\u044f \u0432\u0430\u043b\u0438\u0434\u0430\u0446\u0438\u0438 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u0430 \u043c\u043e\u0434\u0435\u043b\u0438 ILP.<\/p>\n<h2>\u041c\u043e\u0434\u0435\u043b\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435<\/h2>\n<p>\u0412\u043e\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u043c\u0441\u044f \u0441\u0438\u043c\u043c\u0435\u0442\u0440\u0438\u0447\u043d\u043e\u0441\u0442\u044c\u044e \u043c\u0430\u0442\u0440\u0438\u0446\u044b \u043f\u0435\u0440\u0435\u0445\u043e\u0434\u043e\u0432 \u043c\u0435\u0436\u0434\u0443 \u0443\u0437\u043b\u0430\u043c\u0438 \u0438 \u0441\u0444\u043e\u0440\u043c\u0443\u043b\u0438\u0440\u0443\u0435\u043c \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u0438\u0441\u0442\u0438\u0447\u043d\u0443\u044e \u043c\u043e\u0434\u0435\u043b\u044c ILP \u0437\u0430\u0434\u0430\u0447\u0438 \u043f\u043b\u0430\u043d\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f \u043c\u0430\u0440\u0448\u0440\u0443\u0442\u0430 \u043d\u0430 \u0443\u0441\u043b\u043e\u0432\u0438\u044f\u0445 TSP.  \u0412\u0432\u0435\u0434\u0435\u043c \u043e\u0431\u043e\u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f, \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f \u0438 \u0446\u0435\u043b\u0435\u0432\u0443\u044e \u0444\u0443\u043d\u043a\u0446\u0438\u044e:<\/p>\n<p> &#8212; \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e \u0443\u0437\u043b\u043e\u0432 \u0441\u0435\u0442\u0438;<\/p>\n<p> &#8212; \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0435\/\u0437\u0430\u0442\u0440\u0430\u0442\u044b\/\u0432\u0440\u0435\u043c\u044f \u0434\u0432\u0438\u0436\u0435\u043d\u0438\u044f \u043f\u043e \u0440\u0435\u0431\u0440\u0443 ;<\/p>\n<p> &#8212; \u0431\u0438\u043d\u0430\u0440\u043d\u0430\u044f \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u0430\u044f, \u0438\u043d\u0434\u0438\u043a\u0430\u0442\u043e\u0440 \u0432\u044b\u0431\u043e\u0440\u0430 \u0440\u0435\u0431\u0440\u0430 \u0432 \u043c\u0430\u0440\u0448\u0440\u0443\u0442 (=1 \u0435\u0441\u043b\u0438 \u0440\u0435\u0431\u0440\u043e \u0432 \u043c\u0430\u0440\u0448\u0440\u0443\u0442\u0435, 0 &#8212; \u0432 \u043f\u0440\u043e\u0442\u0438\u0432\u043d\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435);<\/p>\n<p>\u041d\u0430\u0447\u043d\u0435\u043c \u0440\u0430\u0437\u0431\u043e\u0440 \u043c\u043e\u0434\u0435\u043b\u0438 \u0441 \u0446\u0435\u043b\u0435\u0432\u043e\u0439 \u0444\u0443\u043d\u043a\u0446\u0438\u0438 &#8212; \u0442\u0440\u0430\u0434\u0438\u0446\u0438\u043e\u043d\u043d\u043e \u044d\u0442\u043e \u043c\u0438\u043d\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u044f \u0434\u043b\u0438\u043d\u044b \u043c\u0430\u0440\u0448\u0440\u0443\u0442\u0430, \u043d\u043e \u043a\u0430\u043a \u0432\u0430\u0440\u0438\u0430\u0446\u0438\u0438 \u043c\u043e\u0433\u0443\u0442 \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u0442\u044c\u0441\u044f \u043c\u0438\u043d\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u044f \u0437\u0430\u0442\u0440\u0430\u0442 \u0438\u043b\u0438 \u043c\u0438\u043d\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u044f \u0432\u0440\u0435\u043c\u0435\u043d\u0438 \u0432 \u043f\u0443\u0442\u0438, \u0434\u0440\u0443\u0433\u0438\u0435 \u0432\u0430\u0440\u0438\u0430\u043d\u0442\u044b \u0442\u043e\u0436\u0435 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u044b. \u041e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0435 (1) \u043e\u0431\u044f\u0437\u044b\u0432\u0430\u0435\u0442 \u043c\u043e\u0434\u0435\u043b\u044c \u043e\u0440\u0433\u0430\u043d\u0438\u0437\u043e\u0432\u0430\u0442\u044c \u043e\u0434\u0438\u043d \u0432\u0445\u043e\u0434 \u0438 \u043e\u0434\u0438\u043d \u0432\u044b\u0445\u043e\u0434. \u0414\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u043f\u043e\u0434\u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430  \u0441\u043e\u0437\u0434\u0430\u0435\u043c \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f \u0442\u0438\u043f\u0430 (2), \u043e\u043d\u0438 \u043e\u0431\u0435\u0441\u043f\u0435\u0447\u0438\u0432\u0430\u044e\u0442 \u0441\u043e\u0437\u0434\u0430\u043d\u0438\u0435 \u0441\u0432\u044f\u0437\u043d\u043e\u0433\u043e \u043c\u0430\u0440\u0448\u0440\u0443\u0442\u0430. \u041e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0435 \u0441\u0438\u043c\u043c\u0435\u0442\u0440\u0438\u0438 (3), \u043d\u0435\u0432\u0430\u0436\u043d\u043e, \u0432 \u043a\u0430\u043a\u043e\u043c \u043d\u0430\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u0438\u0438 \u0438\u0434\u0435\u043c \u043f\u043e \u0440\u0435\u0431\u0440\u0443, \u0432\u0430\u0436\u043d\u043e \u0447\u0442\u043e \u0438\u0434\u0435\u043c (\u043c\u0430\u0442\u0440\u0438\u0446\u0430 \u043f\u0435\u0440\u0435\u0445\u043e\u0434\u043e\u0432 \u0441\u0438\u043c\u043c\u0435\u0442\u0440\u0438\u0447\u043d\u0430\u044f). \u041e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f (4) &#8212; \u0431\u0438\u043d\u0430\u0440\u043d\u043e\u0441\u0442\u044c \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0445.<\/p>\n<p>\u041a\u043e\u043c\u043c\u0435\u043d\u0442\u0430\u0440\u0438\u0438 \u043a \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f\u043c. \u041e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f \u0442\u0438\u043f\u0430 (3) \u0441\u043e\u043a\u0440\u0430\u0442\u044f\u0442\u0441\u044f \u043d\u0430 presolve \u044d\u0442\u0430\u043f\u0435 \u0441\u043e\u043b\u0432\u0435\u0440\u0430. \u041c\u043e\u0436\u043d\u043e \u0441\u0444\u043e\u0440\u043c\u0443\u043b\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u043c\u043e\u0434\u0435\u043b\u044c \u0431\u0435\u0437 \u044d\u0442\u043e\u0433\u043e \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f, \u043d\u043e \u0437\u0430\u043f\u0438\u0441\u044c \u043c\u043e\u0434\u0435\u043b\u0438 \u0431\u0443\u0434\u0435\u0442 \u043d\u0435\u043c\u043d\u043e\u0433\u043e \u0441\u043b\u043e\u0436\u043d\u0435\u0435. \u041a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0439 \u0442\u0438\u043f\u0430 (2) \u0440\u0430\u0441\u0442\u0435\u0442 \u044d\u043a\u0441\u043f\u043e\u043d\u0435\u043d\u0446\u0438\u0430\u043b\u044c\u043d\u043e \u0432 \u0437\u0430\u0432\u0438\u0441\u0438\u043c\u043e\u0441\u0442\u0438 \u043e\u0442 , \u0447\u0442\u043e \u0432\u044b\u0433\u043b\u044f\u0434\u0438\u0442 \u043d\u0435 \u043e\u0447\u0435\u043d\u044c \u043f\u0440\u0430\u043a\u0442\u0438\u0447\u043d\u043e. \u0421 \u044d\u0442\u0438\u043c \u043f\u043e\u0431\u043e\u0440\u0435\u043c\u0441\u044f \u0434\u0430\u043b\u0435\u0435.<\/p>\n<h2>Python \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f \u043c\u043e\u0434\u0435\u043b\u0438<\/h2>\n<p>\u041f\u043e\u0441\u0442\u0440\u043e\u0438\u043c \u043c\u043e\u0434\u0435\u043b\u044c \u0431\u0435\u0437 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f (2), \u043f\u043e\u0441\u043c\u043e\u0442\u0440\u0438\u043c, \u0447\u0442\u043e \u043e\u0437\u043d\u0430\u0447\u0430\u0435\u0442 \u0441\u0432\u044f\u0437\u043d\u043e\u0441\u0442\u044c \u043c\u0430\u0440\u0448\u0440\u0443\u0442\u0430 \u043d\u0430 \u043f\u0440\u0430\u043a\u0442\u0438\u043a\u0435. \u0412 \u043a\u0430\u0447\u0435\u0441\u0442\u0432\u0435 \u0446\u0435\u043b\u0435\u0432\u043e\u0439 \u0444\u0443\u043d\u043a\u0446\u0438\u0438 \u0431\u0443\u0434\u0435\u043c \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u043c\u0438\u043d\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u044e \u0437\u0430\u0442\u0440\u0430\u0442 \u043d\u0430 \u0442\u0440\u0430\u043d\u0441\u0444\u0435\u0440 \u043c\u0435\u0436\u0434\u0443 \u043b\u043e\u043a\u0430\u0446\u0438\u044f\u043c\u0438.<\/p>\n<details class=\"spoiler\">\n<summary>\u0420\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f \u0443\u043f\u0440\u043e\u0449\u0435\u043d\u043d\u043e\u0439 \u0432\u0435\u0440\u0441\u0438\u0438 \u043c\u043e\u0434\u0435\u043b\u0438 \u0431\u0435\u0437 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0439 \u0442\u0438\u043f\u0430 (2)<\/summary>\n<div class=\"spoiler__content\">\n<pre><code class=\"python\"># \u0423\u043f\u0440\u043e\u0449\u0435\u043d\u043d\u0430\u044f \u0432\u0435\u0440\u0441\u0438\u044f \u043c\u043e\u0434\u0435\u043b\u0438 \u0431\u0435\u0437 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0439 \u0442\u0438\u043f\u0430 (2) from ortools.sat.python import cp_model import pandas as pd import numpy as np  # \u0421\u0447\u0438\u0442\u0430\u0435\u043c \u0432\u0445\u043e\u0434\u043d\u044b\u0435 \u0434\u0430\u043d\u043d\u044b\u0435 df_dist = df_cab = pd.read_csv(\"https:\/\/raw.githubusercontent.com\/Lozkins\/mos\/master\/data\/06_tsp_dist.csv\", sep=\";\", encoding=\"cp1251\") df_location = df_cab = pd.read_csv(\"https:\/\/raw.githubusercontent.com\/Lozkins\/mos\/master\/data\/06_tsp_coord.csv\", sep=\";\", encoding=\"cp1251\")  obj_type = \"cost\"  # \u0422\u0438\u043f \u0446\u0435\u043b\u0435\u0432\u043e\u0439 \u0444\u0443\u043d\u043a\u0446\u0438\u0438. \u0414\u043e\u043f\u0443\u0441\u0442\u0438\u043c\u044b\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f [\"cost\", \"travel_time\"]  m = cp_model.CpModel()  # \u0418\u043d\u0438\u0446\u0438\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0445 df_dist[\"var_id\"] = np.ogrid[:df_dist.shape[0]] df_dist[\"var\"] = df_dist[\"var_id\"].apply(lambda x: m.NewBoolVar(f\"x_{x}\"))  # \u0421\u043e\u0437\u0434\u0430\u0435\u043c \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f \u0442\u0438\u043f\u0430 (1) dct_constr_1 = df_dist.groupby(\"to\")[\"var\"].sum().to_dict() for from_node, var_sum in dct_constr_1.items():   m.Add(var_sum == 2)  # \u0421\u043e\u0437\u0434\u0430\u0435\u043c \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f \u0442\u0438\u043f\u0430 (3) dct_constr_3 = df_dist.set_index([\"from\", \"to\"]).to_dict()[\"var\"] for (from_node,  to_node), var_ in dct_constr_3.items():   m.Add(var_ == dct_constr_3[to_node, from_node])  m.Minimize(sum(df_dist[obj_type] * df_dist[\"var\"]))  # \u0418\u043d\u0438\u0446\u0438\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f solver solver = cp_model.CpSolver() solver.parameters.log_search_progress = True  # \u0420\u0435\u0448\u0435\u043d\u0438\u0435 \u0437\u0430\u0434\u0430\u0447\u0438 status = solver.Solve(m)  # \u041f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u043c \u0441\u0442\u0430\u0442\u0443\u0441 if status == cp_model.OPTIMAL:   print(\"-\" * 40)   gap_val = abs((solver.ObjectiveValue() - solver.BestObjectiveBound()) \/ max(1, solver.ObjectiveValue()))   # \u0418\u0437\u0432\u043b\u0435\u043a\u0430\u0435\u043c \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442   df_dist[\"sol\"] = df_dist[\"var\"].apply(lambda x: solver.Value(x))   df_dist_opt = df_dist[df_dist[\"sol\"] > 0]    print(f\"-- Found solution {solver.ObjectiveValue()}\")   print(f\"-- GAP: {round(gap_val, 2)}%\")   print(f\"-- Solved in {solver.WallTime()} sec.\")   print(f\"-- Costs {df_dist_opt['cost'].sum() \/ 2} rub\")   print(f\"-- Duration {df_dist_opt['travel_time'].sum() \/ 2} h\") <\/code><\/pre>\n<\/div>\n<\/details>\n<details class=\"spoiler\">\n<summary>\u0424\u0443\u043d\u043a\u0446\u0438\u044f \u0432\u0438\u0437\u0443\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u0432 plotly<\/summary>\n<div class=\"spoiler__content\">\n<pre><code class=\"python\"># \u041d\u0430\u043d\u0435\u0441\u0435\u043d\u0438\u0435 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u0430 \u043d\u0430 \u043a\u0430\u0440\u0442\u0443 import plotly.graph_objects as go  def plot_route(df_graph: pd.DataFrame):   # \u041d\u0430\u0447\u0430\u043b\u043e \u0438 \u043e\u043a\u043e\u043d\u0447\u0430\u043d\u0438\u0435 \u043c\u0430\u0440\u0448\u0440\u0443\u0442\u0430 \u0432 \u041c\u0421\u041a   df_location[\"color\"] = np.where(df_location[\"id\"] == 0, \"red\", \"blue\")   df_location[\"size\"] = np.where(df_location[\"id\"] == 0, 14, 10)   df_location['text'] = df_location[\"id\"].astype(str) + \", \" + df_location[\"name\"]    # \u0414\u043e\u0431\u0430\u0432\u043b\u044f\u0435\u043c \u043a\u043e\u043e\u0440\u0434\u0438\u043d\u0430\u0442\u044b \u0438 \u043d\u0430\u0438\u043c\u0435\u043d\u043e\u0432\u0430\u043d\u0438\u0435 \u0442\u043e\u0447\u0435\u043a \u043e\u0442\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u0438\u044f \u0438 \u043f\u0440\u0438\u0431\u044b\u0442\u0438\u044f   df_loc_from = df_location.copy()   df_loc_from.columns = [col + \"_from\" for col in df_loc_from.columns]   df_loc_to = df_location.copy()   df_loc_to.columns = [col + \"_to\" for col in df_loc_to.columns]    df_travel_map = df_graph.merge(df_loc_from, how=\"left\", left_on=\"from\",                               right_on=\"id_from\")   df_travel_map = df_travel_map.merge(df_loc_to, how=\"left\", left_on=\"to\",                               right_on=\"id_to\")    # \u041d\u0430\u043d\u043e\u0441\u0438\u043c \u0432\u0435\u0440\u0448\u0438\u043d\u044b   fig = go.Figure(data=go.Scattergeo(           lon = df_location['lon'],           lat = df_location['lat'],           text = df_location['text'],           mode = 'markers',           name = \"\u041b\u043e\u043a\u0430\u0446\u0438\u0438\",           marker = dict(               size = df_location[\"size\"],               opacity = 0.8,               color = df_location[\"color\"],               ),           ))    # \u041d\u0430\u043d\u043e\u0441\u0438\u043c \u0440\u0435\u0431\u0440\u0430   for row in df_travel_map.itertuples():     fig.add_trace(             go.Scattergeo(                 lon = [row.lon_from, row.lon_to],                 lat = [row.lat_from, row.lat_to],                 mode = 'lines',                 line = dict(width = 1,color = 'blue'),                 opacity = 0.8,                 name=row.name_from + \" - \" + row.name_to             ),         )    fig.update_layout(           title = 'Travel route in Russia &lt;br>',           geo = dict(               showland = True,               landcolor = \"rgb(250, 250, 250)\",               subunitcolor = \"rgb(217, 217, 217)\",               countrycolor = \"rgb(217, 217, 217)\",               countrywidth = 0.5,               subunitwidth = 0.5           ),       )    fig.show() <\/code><\/pre>\n<\/div>\n<\/details>\n<p>\u0421 \u0446\u0435\u043b\u0435\u0432\u043e\u0439 \u0444\u0443\u043d\u043a\u0446\u0438\u0435\u0439 \u043c\u0438\u043d\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u0438 \u0437\u0430\u0442\u0440\u0430\u0442 \u043f\u043e\u043b\u0443\u0447\u0438\u043b\u0438 \u043e\u043f\u0442\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u0437\u0430\u0434\u0430\u0447\u0438 \u0441 \u043e\u0431\u0449\u0438\u043c\u0438 \u0437\u0430\u0442\u0440\u0430\u0442\u0430\u043c\u0438 93 876 \u0440\u0443\u0431 (115.05 \u0447\u0430\u0441\u043e\u0432). \u041f\u0430\u0440\u0430\u043c\u0435\u0442\u0440 <code>obj_type<\/code> \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u043f\u0435\u0440\u0435\u043a\u043b\u044e\u0447\u0438\u0442\u044c \u0446\u0435\u043b\u0435\u0432\u0443\u044e \u0444\u0443\u043d\u043a\u0446\u0438\u044e \u043d\u0430 \u043c\u0438\u043d\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u044e \u0432\u0440\u0435\u043c\u0435\u043d\u0438 \u0432 \u043f\u0443\u0442\u0438, \u0442\u043e\u0433\u0434\u0430 \u043e\u043f\u0442\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u0431\u0443\u0434\u0435\u0442 70.9 \u0447\u0430\u0441\u043e\u0432 (131 493 \u0440\u0443\u0431). \u041d\u0430\u043d\u0435\u0441\u0435\u043c \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 \u043d\u0430 \u043a\u0430\u0440\u0442\u0443 \u0434\u043b\u044f \u0446\u0435\u043b\u0435\u0432\u043e\u0439 \u0444\u0443\u043d\u043a\u0446\u0438\u0438 \u043c\u0438\u043d\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u0438 \u0437\u0430\u0442\u0440\u0430\u0442.<\/p>\n<figure class=\"\">\n<div><figcaption>\u041f\u0435\u0440\u0432\u0430\u044f \u043f\u043e\u043f\u044b\u0442\u043a\u0430 \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u0437\u0430\u0434\u0430\u0447\u0438: \u041d\u0435\u0441\u0432\u044f\u0437\u043d\u044b\u0439 \u043f\u0443\u0442\u044c<\/figcaption><\/div>\n<\/figure>\n<p>\u041d\u0435 \u0442\u0430\u043a\u043e\u0439 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 <\/p>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[],"tags":[],"class_list":["post-362180","post","type-post","status-publish","format-standard","hentry"],"_links":{"self":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/362180","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=362180"}],"version-history":[{"count":0,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/362180\/revisions"}],"wp:attachment":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=362180"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=362180"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=362180"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}