tag:blogger.com,1999:blog-77748414728873404642011-11-28T03:49:53.352+04:00//Ильнарhttp://www.blogger.com/profile/13010418728196605247noreply@blogger.comBlogger41100tag:blogger.com,1999:blog-7774841472887340464.post-46262301434139158882008-02-02T20:36:00.000+03:002008-02-16T02:57:42.724+03:00За последнее время реализовал и протестировал алгоритм параллельного решения задачи коммивояжера. Алгоритм построен на основе метода Литтла с улучшенными функциями определения нижней оценки набора решений и порядок выбора дуги. В ходе просмотра дерева решния по методу Литтла алгоритм ответвляет подзадачи и передает их параллельным решателям. Параллельные решатели и список подзадач для решения Ильнарhttp://www.blogger.com/profile/13010418728196605247noreply@blogger.com0tag:blogger.com,1999:blog-7774841472887340464.post-37952352343599333232007-03-01T19:25:00.000+03:002007-04-24T14:30:26.136+04:00Непонятки с CVRP. Следуя постановке задачи CVRP (http://neo.lcc.uma.es/radi-aeb/WebVRP//Problem_Descriptions/CVRPDesc.html), целевая функция задачи состоит в минимизации количества используемых транспортных средств (ТС) и суммарного растояния проезда: "Objective: The objective is to minimize the vehicle fleet and the sum of travel time, and the total demand of commodities for each route may not Ильнарhttp://www.blogger.com/profile/13010418728196605247noreply@blogger.com0tag:blogger.com,1999:blog-7774841472887340464.post-8341792470192577982007-01-17T15:26:00.000+03:002007-01-18T13:17:03.881+03:00Коварный p43. (Именно так остается думать)Задача сама по себе малой размерности - 43 пункта. Однако несколько часов работы метода Литтла не находят решение, включая метод с модификациями.Рассмотрев данные, углядел, что p43 получена из задачи размерности 22 пункта путем дублирования некоторых пунктов 2, 3, а то и 4 раза. Между такими клонами пунктов нулевая стоимость, а стоимость до других пунктовИльнарhttp://www.blogger.com/profile/13010418728196605247noreply@blogger.com0tag:blogger.com,1999:blog-7774841472887340464.post-91583150979606053022007-01-17T12:42:00.000+03:002007-04-24T14:31:51.914+04:00Получил результаты тестовых вычислений одного своего алгоритма точного решения задачи коммивояжера. Алгоритм основывается на методе Литтла, модификации подвержены функция определения нижней оценки набора решений и порядок выбора дуги. Теоретические обоснования корректности модификации функции нижней границы и выбора дуги оформлены в виде статьи. Статья опубликована.Результаты тестов на случайных Ильнарhttp://www.blogger.com/profile/13010418728196605247noreply@blogger.com1