УДК 518.0
Б.А. Бигеев,
к.т.н., Днепропетровский национальный университет им. О.Гончара
Компьютерная реализация задачи о коммивояжере
В статье представлены математическая постановка и компьютерная реализация известной экономической задачи о коммивояжере. Разработан оригинальный алгоритм решения задачи, обеспечивающий получение оптимального маршрута с минимальными экономическими затратами.
The article gives the mathematical definition and computer realization of a well-known economic task about a commercial traveler. The unique algorithm of coving the problem that provides the fully satisfactory rout with minimum economic costs.
Ключевые слова: задача о коммивояжере, маршрут, алгоритм, экономические затраты.
Введение. В статье представлена задача о коммивояжере – бродячем торговце, который покинул город (которому мы присваиваем имя «С»), объехав еще N городов и вернулся снова в город с именем «С». В его распоряжении есть дороги, соединяющие эти города. Он должен выбрать свой маршрут – порядок посещения городов так, чтобы путь, который ему надлежит пройти, был минимальным. Основное условие этой задачи состоит в том, что в каждом городе коммивояжер может побывать только 1 раз – это условие будем называть условием (a). Естественно, что расстояние между двумя городами – функция f(xi, xj) – определено. Добавление города с именем «С» расширяет сферу практического применения в экономике задачи о коммивояжере.
Функция f(xi, xj) может означать не только расстояние, но и, например, время, издержки в пути; да и сам коммивояжер может быть некоторым транспортным средством, развозящем товары по N пунктам доставки.
Математическая постановка задачи.
Длина l пути S определяется формулой
. (1)
а) Сумма в выражении (1) распространена по всем индексам i, j, удовлетворяет условию (a).
б) Путь из пункта i в пункт j может не совпадать по затратам пути из пункта j в пункт i. Это значит, что
. (2)
Эта задача не удовлетворяет принципу оптимальности Беллмана и не может решаться методами динамического программирования. Но функция f(xi, xj) и функция пути l(x1,…,xN) в этой задаче определены на конечном множестве точек, следовательно задача сводится к перебору всех возможных маршрутов и проблема носит чисто вычислительный характер. Однако именно вычислительные трудности здесь огромны: число возможных маршрутов между N пунктами доставки равно N!.
Техническая постановки задачи
1. Имеется N пунктов доставки, куда следует завести заданные объемы грузов.
2. Имеется «Матрица расстояний» между пунктами доставки.
3. Имеется «Матрица весов» для каждого пути, отражающая характер дорог, их пропускную способность и загруженность.
4. Расходы на преодоление пути между пунктами i и j вычисляются по формуле:
(3)
где Gij – вес транспортного средства с грузом, соответствующим участку пути между пунктами i и j.
lij – длина пути между пунктами i и j.
vij – весовой коэффициент участка пути между пунктами i и j.
kz – коэффициент затрат, отражающий расход топлива на единицу пути и амортизационные отчисления транспортного средства.
Найти оптимальный порядок обхода пунктов доставки, чтобы затраты на доставку были минимальными.
На данном этапе разработки компьютерной реализации число пунктов доставки ограничено , N £ 9.
Результаты.
Задача о коммивояжере принципиально состоит из двух вычислительных процессов.
Первый процесс это генерация перестановок (возможных маршрутов) из N элементов по N. Количество таких перестановок, как уже было сказано, составляет N!.
Второй процесс это вычисление затрат на преодолении текущего маршрута.
Процедура генерации перестановок относится к числу исключительно сложных программистских задач. Нами разработаны два алгоритма генерации перестановок. В первом алгоритме члены натурального ряда от 1 до N! преобразуются в соответствующие перестановки. Второй алгоритм построен на использовании рекуррентного вызова процедур. Это означает, что при генерации перестановок процедура N раз вызывает сама себя. И каждый такой вызов дожжен не начинать процесс заново, а продолжить предыдущее. Оба алгоритма характеризуются высоким уровнем программирования.
Мы установили, что генератор по первому алгоритму дает выигрыш при использовании устаревших компьютеров с малой оперативной памятью. На современной технике второй алгоритм дает 40-ка процентный выигрыш во времени. Следует также подчеркнуть, что каждый из алгоритмов обладает исключительной производительностью: 9! перестановок (362880) он генерирует на современном компьютере за 5 – 6 секунд. Текст одной из процедур приведен ниже.
Sub Perestanovki()
' Перебор всех перестановок из n элементов по n
' достигается путем преобразования натурального ряда
' чисел от 1 до n! в перестановки
Dim n As Integer
Dim a As String
Dim p(10), po(10), pf(10) As Long
' p(n) - целевой массив
' pо(n) - контрольный массив
n = Cells(1, 1).Value
Application.ScreenUpdating = False
' первичные присвоения
J = 1
For i = 1 To n
J = J * i
pf(i) = J ' накопление факториалов от 1 до n
Next i
k = J
Cells(5, 1) = J
m = 1
For i = 1 To k ' цикл от 1 до n!
For J = 1 To n
po(J) = J ' числа от 1 до n
Next J
ii = i
For J = n - 1 To 2 Step -1
' элемент натурального ряда делится в цикле
' последовательно на (n-1)!, (n-2)!,..., 2!,
' чтобы получить первые n-2 индекса
kk = pf(J)
L = Int((2 * (ii - 1) + 1) / (2 * kk)) + 1
ii = ii - kk * (L - 1)
jk = n - J
If jk > 1 Then
t = 0
For LL = 1 To n
If po(LL) > 0 Then
t = t + 1
If t = L Then
L = LL
Exit For
End If
End If
Next LL
End If
p(jk) = L
po(L) = 0
Next J
' получение двух последних индексов
m = 3 - m ' m принимает значения 1,2,1,2,...
ji = m
For J = 1 To n
ij = po(J)
If ij > 0 Then
p(n + 1 - ji) = ij
ji = 3 - ji
End If
Next J
' свертка массива p(n) для компактно печати
a = ""
For J = 1 To n
a = a & Trim(Str(p(J)))
Next J
Next i
End Sub
Программа, реализующая расчет затрат на преодолении маршрута зависит от экранной реализации процесса вычислений, от размещения исходных данных. Вот примерный вид листа Excel с данными к задаче.
Процедуру расчета затрат мы также написали в двух вариантах. В первом варианте использовано чтение данных из матриц расстояний и весов с помощью вычисляемых индексов. Во втором случае использован конечный автомат, таблица переходов которого содержит всю информации о ячейках матриц весов и расстояний. Процедуры эквивалентны. Кроме вычисления затрат на маршруте, процедура обеспечивает печать текущего маршрута, если он лучше предыдущих и индикацию процесса поиска решения. Два последних обстоятельства существенно замедляют работу программы: на обработку маршрута затрачивается времени в 30 – 40 раз больше, чем на генерацию перестановки (маршрута). Поэтому имеется возможность отказаться от индикации.
Выводы:
· разработаны два оригинальных алгоритма генерации перестановок из N элементов по N, производительность которых составляет примерно 80000 перестановок в секунду;
· разработана техническая схема задачи о коммивояжере. При этом учтены длины и класс дорог, изменение веса груза в процессе его развозки по пунктам, а также норму затрат транспортного средства. Все это реализовано в виде программного модуля расчета затрат;
· программа автоматически настраивается на количество пунктов доставки по объему исходных таблиц (в рамках ограничений от 1 до 9);
· программа может использоваться не только для доставки грузов на пункты доставки, но и сбор грузов от производителей (например, для объезда молочных ферм), если грузы доставки брать со знаком минус;
· обеспечена наглядность представления результатов расчета;
· использован индикатор работы программы, что особенно важно при длительных расчетах
Список использованных источников:
1. Моисеев Н.Н., Иванилов Ю.П., Столярова Е.М. Методы оптимизации. - М.: «Наука», Главная редакция физико-математической литературы, 1978. - 352 с.
2. Романовский И.В. Алгоритмы решения экстремальных задач. – М.: Главная редакция физико-математической литературы изд-ва «Наука», 1977.
3. Гавурин М.К. Лекции по методам вычислений. – М.: Главная редакция физико-математической литературы изд-ва «Наука», 1971.
4. Кузин Л.Т. Основы кибернетики: В 2-х т. Т.2. Основы кибернетических моделей: Учеб. пособие для вузов. - Энергия, 1979. - 584 с.
5. Марюта А.Н., Смирнов С.А. Эвристический системный анализ экономики: Монография. - Днепропетровск: Наука и образование, 2004. - 294 с.
Стаття надійшла до редакції 11.11.2009 р.