Українською | English

НАЗАДГОЛОВНА


УДК 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(xixj) – определено. Добавление города с именем «С» расширяет сферу практического применения в экономике задачи о коммивояжере.

Функция f(xixj) может означать не только расстояние, но и, например, время, издержки в пути; да и сам коммивояжер может быть некоторым транспортным средством, развозящем товары по N пунктам доставки.

 

Математическая постановка задачи.

Длина l пути S определяется формулой

.                                                                                              (1)

а) Сумма в выражении (1) распространена по всем индексам i, j, удовлетворяет условию (a).

б) Путь из пункта i в пункт j может не совпадать по затратам пути из пункта j в пункт i. Это значит, что

 

.                           (2)

 

Эта задача не удовлетворяет принципу оптимальности Беллмана и не может решаться методами динамического программирования. Но функция f(xixj) и функция пути 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 р.

bigmir)net TOP 100

ТОВ "ДКС Центр"