Задача коммивояжера

В приведенной постановке выбор оптимального варианта объезда решается методами задачи коммивояжера, например методом ветвей и границ. Алгоритм ее решения описывается ниже. [c.227]

Вначале выскажем некоторые соображения по поводу алгоритма решения данной задачи. Как было указано выше, выбор оптимального варианта объезда относится к так называемой задаче коммивояжера. При выборе оптимальной схемы необходимо руководствоваться тем, что из исходного положения штабелер должен пройти по кратчайшему, с точки зрения эксплуатационных затрат, маршруту, который лишь однажды пересекает обслуживаемую ячейку, и после объезда всех ячеек вернуться в исходное положение. [c.266]

В итоге получаем множество, содержащее один цикл, т. е. замкнутый маршрут, стоимость которого равна нижней границе оценки этого подмножества. Этот вариант является оптимальным. Описанный процесс разбиения приведен на рис. 5.9, б в виде дерева, а на рис. 5.9, а показан оптимальный маршрут объезда 01437852 0. Применение описанной методики планирования работы штабелеров обеспечивает увеличение их производительности на 8—10%. Укажем, что описанный метод решения задачи коммивояжера является достаточно универсальным и его можно успешно использовать при планировании перемещения кранов на контейнерных площадках. В-работе [2] приведен числовой пример решения задачи адресования контейнеров при сортировке. [c.270]

Множество деревьев графа называют лесом. Задачи выделения эйлеровых и гамильтоновых циклов и покрывающих деревьев связаны с задачами о лабиринте, коммивояжере и с построением путей минимальной стоимости. [c.205]

С задачей определения гамильтоновых циклов и кратчайших расстояний тесно связана задача о коммивояжере, суть которой в следующем имеется N городов (вершин графа) и заданы расстояния между городами. Коммивояжер находится в городе Х. Ему необходимо посетить только по одному разу все остальные N—1 городов. и вернуться в Хи чтобы общее пройденное расстояние было минимальным. [c.207]

О, если 1 = ah, i ф и предположим, что последовательность команд образует замкнутый контур (начинается н заканчивается командой а )- Тогда наша задача совпадает с классической задачей о коммивояжере [c.304]

В математическом плане рассматриваемая задача относится к классу задач целочисленного или дискретного программирования, характерная особенность которых заключается в конечности множества допустимых вариантов решения задачи, на котором проводится оптимизация. Классическим примером задачи целочисленного программирования является так называемая "задача о коммивояжере" ([4], с. 39). Данная задача состоит в следующем. [c.506]

Существуют различные варианты задачи о коммивояжере, различающиеся правилом назначения "цены" маршрута, а также видом маршрута (замкнутый или разомкнутый). В простейшем варианте"цена" перехода из одного пункта в другой фиксирована и не зависит от маршрута движения. Например, расстояния между пунктами постоянны и не зависят от порядка их посещения. Такую задачу называют задачей с постоянной метрикой. Более сложным вариантом является задача с переменной метрикой, когда "цена" перехода из пункта в пункт зависит от маршрута движения на предыдущем этапе. Например, плата за проезд может уменьшаться по мере того, как коммивояжер оставляет часть товара на предыдущих остановках. Определяемый маршрут является по постановке задачи замкнутым, если коммивояжер должен возвратиться в исходный пункт начала движения, и незамкнутым, если требование возвращения в исходный пункт не ставится. [c.507]

При остановке алгоритма в случае, если допустимому решению соответствует значение целевой функции iopt (X)—полученное решение оптимально, в противном случае допустимого решения не существует. Метод ветвей и границ особенно эффективен для решения комбинаторных задач, в частности задачи коммивояжера. [c.314]

Ддя решения задачи коммивояжера в настоящее время разработаны как точные, так и приближенные методы. Приближенные методы разра-батьшаются для задач с большой размерностью (когда порядок матрицы в задаче коммивояжера примерно 40—100). К подобным методам относятся метод движения в ближайший городи метод оптимизации существуют и другие приближенные методы [185-190]. Метод движения в ближайший город подменяет полный перебор щ маршрутов частичным перебором щ маршрутов а именно, начиная с каждого из Пх номеров, осуществляется выбор (/2i — 1) наименьших по стоимости чисел jj последовательно в маршруте, а последнее число замыкает маршрут. В результате получается локально-оптимальный маршрут, близкий по стоимости к оптимальному [191]. Методом /--оптимизации тоже можно получить лишь локальный экстремум сущность метода зжлючается в совершении всевозможных замен г коммуникаций С/у в уже имеющемся маршруте. Пржтически используется оптимизация при г = 3 4 [192. [c.254]

N — общее количество прямоугольников Тэ — время экспонирования одного прямоугольника. Начиная с некоторого прямоугольника Ра необходимо обойти все прямоугольники Р, Р2,...,Ры таким образом, чтобы. чремя работы микрофотонаборной установки Т было минимально. Подобная задача в теории графов называется задачей коммивояжера, но в данном случае время перехода из состояния / в / не пропорционально расстоянию между прямоугольниками Рг и Р/, поэтому необходимо модифицировать соответствующие алгоритмы. [c.222]

Для минимизации времени работы микрофотонаборной установки применяются алгоритмы приближенного решения задачи коммивояжера последовательного или итерационного типа. [c.222]

Использованный для выбора оптимальной схемы объезда один из методов решения задачи коммивояжера метод Литтла основан на разбиении множества из S (0) вариантов на два непересекающихся подмножества с последующим вычислением оценок для каждого из них. Затем подмножество с минимальной оценкой вновь разбивается на два подмножества и вычисляются их оценки. Таким образом, на каждом шаге итерационного процесса выбирается подмножество с минимальной оценкой из всех полученных ранее. [c.267]

Нетрудно видеть, что задача выбора оптимального марщрута разведения ББ структурно тождественна задаче о коммивояжере, чем и объясняются терминологическиезаимствования, о которых упоминалось выше маршрут разведения, обход целей ступенью разведения и др.). При этом в данном случае мы имеем дело с задачей о коммивояжере с незамкнутым маршрутом и с переменной метрикой. Последнее обстоятельство определяется тем, что затраты топлива ступени разведения прн переходе от одной цели к другой зависят не только от расстояния между этими целями на земной поверхности, но и от предыстории движения. В частности, уменьшение массы ступени разведения по мере отделения ББ повышает эффективность расходования топлива СР на сообщение ей заданного приращения скорости при переходе к последующей цели вследствие увеличения кажущегося ускорения СР при той же тяге ДУ. С другой стороны, уменьшение скоростных баллистических производных по мере движения СР по траектории приводит к увеличению потребных приращений скорости при переходе СР на последующие цели, что вызывает соответствующее увеличение потребного расхода топлива по сравнению с предыдущими этапами разведения. Хотя данные факторы частично уравновешивают друг друга, полной взаимной их компенсации не происходит. Переменность метрики означает, что "цена" каждого участка маршрута разведения при переходе от одной точки цели к другой не может быть установлена заранее и включена в постановку оптимизационной задачи, а должна определяться непосредственно в ходе ее решения. [c.507]

Энциклопедия по машиностроению XXL

Оборудование, материаловедение, механика и ...