Помощь в написании студенческих работ
Антистрессовый сервис

Разработка и исследование алгоритмов муравьиной колонии для решения задач оптимального размещения предприятий

Диссертация: Разработка и исследование алгоритмов муравьиной колонии для решения задач оптимального размещения предприятий
ДиссертацияПомощь в написанииУзнать стоимостьмоей работы

Значительное внимание в диссертации уделяется простейшей задаче размещения и задаче о р-медиане на минимум. Для их решения разработаны алгоритмы муравьиной колонии, основанные на искусственном муравье, представляющем собой вероятностую модификацию жадного алгоритма спуска. Доказаны некоторые асимптотические свойства предложенных алгоритмов. В работе также рассматривается задача размещения… Читать ещё >

Разработка и исследование алгоритмов муравьиной колонии для решения задач оптимального размещения предприятий (реферат, курсовая, диплом, контрольная)

Содержание

  • Глава 1. Постановки задач и методы решения
    • 1. 1. Постановки задач
    • 1. 2. Вычислительная сложность и методы решения
    • 1. 3. Алгоритмы муравьиной колонии
  • Глава 2. Алгоритмы муравьиной колонии для задач оптимального размещения предприятий
    • 2. 1. Алгоритмы муравьиной колонии для задачи ор-медиане
    • 2. 2. Алгоритмы муравьиной колонии для простейшей задачи размещения
    • 2. 3. Алгоритм муравьиной колонии для задачи с ограничениями на мощности производства
    • 2. 4. Локальный поиск в алгоритмах муравьиной колонии
  • Глава 3. Теоретические вопросы сходимости алгоритмов муравьиной колонии
    • 3. 1. Известные результаты о сходимости алгоритмов
    • 3. 2. Асимптотические свойства алгоритмов муравьиной колонии для задачи о р-медиане
    • 3. 3. Простейшая задача размещения
    • 3. 4. Алгоритм муравьиной колонии и локальный поиск
  • Глава 4. Результаты вычислительного эксперимента
    • 4. 1. Простейшая задача размещения
    • 4. 2. Задача о р-медиане
    • 4. 3. Задача размещения предприятий с ограничениями на мощности производства

В современных условиях для успешного развития производства и сферы услуг необходимо решать достаточно широкий спектр задач опти-# мального размещения (предприятий, их филиалов, сервисных центров, складов и т. п.). Во многих случаях подобные проекты требуют значительных затрат и имеют большое число возможных вариантов решений. Вследствие этого выбор наилучшей альтернативы с позиций опыта и интуиции является весьма затруднительным. Поэтому для решения таких задач используются модели исследования операций и оптимизации, а также методы системного анализа.

Указанные задачи могут быть описаны в терминах дискретных задач оптимального размещения, в которых при определенных условиях необходимо наилучшим образом расположить предприятия и назначить им потребителей для обслуживания. Под обслуживанием часто понимается транспортировка продукции от пунктов производства к пунктам потребления. В аналогичных терминах также могут быть сформулированы многие другие прикладные задачи, возникающие при проектировании печатных плат, электрических и компьютерных сетей, в стандартизации и других областях.

Задачи оптимального размещения и методы их решения образуют важное направление в дискретной оптимизации. Тематика исследований по данным задачам достаточно разнообразна и включает разработку и исследование точных и приближенных алгоритмов их решения, изучение структуры и вычислительной сложности задач, выделение полиномиально разрешимых случаев, построение семейств «трудных» задач для определенных классов алгоритмов [1,2,4,6,7,11,12,15,17−26,28,31,32,3739,49,57,59,62,70,94,95,110, ИЗ, 120].

В данной области существуют классические задачи, к которым можно отнести простейшую задачу размещения и задачу о р-медиане. Указанные задачи допускают многочисленные обобщения и представляют большой практический интерес. Именно поэтому им посвящено значительное число работ [2,6,38,41,45,66,70,90,96]. Кроме того, ведутся исследования задач размещения предприятий с ограничениями на мощности производства [43,52,104,113]. Можно также отметить работы по многопродуктовым [4] и многоуровневым [12,17,51] задачам размещения.

Актуальность исследования дискретных задач размещения связана с iVP-трудностью многих таких проблем. Вопросы сложности задач размещения производственно-транспортного типа и сводимости к ним известных задач рассматриваются, например, в [1,16, 27, 35, 70]. Задача о р-медиане, простейшая задача размещения, задача размещения предприятий с ограничением на мощности производства также являются ЛГР-трудными. Поэтому значительное внимание уделяется разработке алгоритмов решения указанных задач размещения и исследованию их эффективности.

Вычислительная сложность, а также большая размерность задач размещения предприятий, как правило, не позволяют находить оптимальное решение за приемлемое время. В связи с этим особое значение приобрела разработка методов получения приближенных решений. В последние годы активно развиваются алгоритмы, основанные на процедуре локального поиска [34,88,93,103]. Значительный интерес проявляется к алгоритмам, идеи которых заимствованы у живой природы или физических процессов. К таким методам можно отнести генетические алгоритмы, алгоритм имитации отжига, нейронные сети, а также алгоритмы муравьиной колонии [3,8,19,33,50,65,72,89,93,97,101,102].

Алгоритмы муравьиной колонии принадлежат к классу эвристических вероятностных алгоритмов. Идея данного подхода появилась в результате исследования поведения живых муравьев [77], умеющих находить кратчайший путь от муравейника до источника пищи. Оказалось, что муравей при движении выделяет вещество, называемое феромоном, которое остается за ним на земле в виде следа. След из феромона используется другими членами колонии при поиске источника пищи, причем вероятность выбора пути возрастает с увеличением на нем концентрации феромона. Так как через некоторое время на кратчайшем пути оказывается наибольший уровень феромона, то выбор именно этого маршрута становится наиболее вероятным.

Центральной идеей любого алгоритма муравьиной колонии является накопление и использование статистической информации, которую собирают искусственные муравьи. При этом каждый искусственный муравей или агент представляет собой рандомизированный жадный алгоритм. На каждой итерации алгоритма муравьиной колонии определенное число агентов собирают информацию о решениях, которая обрабатывается и используется каждым из них в дальнейшем. Таким образом, алгоритм муравьиной колонии моделирует поведение нескольких муравьев.

Ранее алгоритмы муравьиной колонии применялись для решения задачи коммивояжера [64,67,73−78,80,116−118], квадратичной задачи о назначениях [81,82,106−108], задачи календарного планирования [68], задач раскроя и упаковки [8,50] и ряда других комбинаторных задач [60,63,72], зарекомендовав себя как эффективный инструмент решения задач оптимизации. Однако, этот подход для решения задач оптимального размещения предприятий практически не применялся.

Целью диссертации является разработка алгоритмов муравьиной колонии для решения задач оптимального размещения предприятий, их теоретическое и экспериментальное исследование.

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

Диссертация состоит из введения, четырех глав, заключения и списка литературы.

Основные результаты диссертации заключаются в следующем.

1. Разработаны алгоритмы муравьиной колонии для решения задачи о р-медиане на минимум, простейшей задачи размещения и задачи размещения с ограничениями на мощности производства. Построены гибридные алгоритмы муравьиной колонии, использующие процедуру локального поиска.

2. Доказано, что в предложенных алгоритмах муравьиной колонии ф для задачи о р-медиане при определенных ограничениях на коэффициент испарения феромона текущий рекорд стремится к оптимальному значению целевой функции. Показано также, что для одного из алгоритмов муравьиной колонии вероятность получения оптимального решения алгоритмом искусственного муравья стремится к единице.

3. Показано, что применение процедуры локального поиска не ухудшает свойств асимптотической сходимости исследуемых алгоритмов муравьиной колонии для задачи о р-медиане на минимум. Для одного из таких гибридных алгоритмов доказано, что при некоторых условиях число шагов алгоритма локального поиска до локального оптимума стремится к нулю.

4. Выполнена реализация предложенных алгоритмов муравьиной колонии, проведено их экспериментальное сравнение на различных сериях тестовых задач. Установлено, что гибридные алгоритмы с процедурой локального поиска более эффективны по качеству получаемых решений.

Полученные в диссертации результаты позволяют сделать вывод о перспективности дальнейшей разработки и применения алгоритмов муравьиной колонии к задачам оптимального размещения предприятий.

Заключение

.

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

Показать весь текст

Список литературы

  1. А.А. О сложности задач минимизации полиномов от булевых переменных // Управляемые системы. — Новосибирск, 1983. — Вып. 23. — С. 3−19.
  2. А.А. Точные и приближенные алгоритмы для задач размещения: обзор последних достижений // Материалы конференции. Новосибирск: Изд-во ИМ СО РАН, 1998. — С. 4−10.
  3. Д.А. Алгоритм муравьиной колонии для задачи о минимальном покрытии // Труды XI междунар. Байкальской школы-семинара «Методы оптимизации и их приложения», Т. З, Иркутск, 1998. — С. 17−20.
  4. А.Е., Колоколов А. А., Коробкова З. В. Дискретные задачи производственно-транспортного типа. Новосибирск: Наука, 1978. — 160 с.
  5. B.JI. Эффективный алгоритм для задачи размещения производства с вполне уравновешенной матрицей // Дискретный анализ и исследование операций, Серия 1, 1998, том 5, N1. — С. 20−31.
  6. Береснев B. JL, Гимади Э. Х., Дементьев В. Т. Экстремальные задачи стандартизации. Новосибирск, 1978. — 333 с.
  7. В.П. Методы погружения в задачах оптимизации. — Новосибирск: Наука, 1977. 161 с.
  8. А.Ф., Аглиуллин М. Н. Алгоритм муравьиной колонии для задач двухмерной упаковки: результаты вычислительного эксперимента // Труды XIII Байкальской международной школы-семинара, Иркутск, Байкал, 2005. Т.1. — С. 429−434.
  9. JI.K., Трубин В. А. О некоторых классах задач размещения деревьев на цепи // Кибернетика, 1991, N2. С. 76−79.
  10. Э.Х. Задачи стандартизации с данными произвольного знака и связными, квазивыпуклыми и почти квазивыпуклыми матрицами // Управляемые системы, Новосибирск, 1987. Вып. 27. С. 3−11.
  11. Э.Х. Обоснование априорных оценок качества приблио/сен-ного решения задачи стандартизации // Управляемые системы. -Новосибирск, 1987. Вып.27. — С. 12−27.
  12. Е.Н. Метод ветвей и границ для простейшей двухуровневой задачи размещения предприятий // Дискретный анализ и исследование операций, Серия 2, 1998, том 5, N1. С. 19−39.
  13. Е.Н., Кочетов Ю. А. Вероятностный жадный алгоритм с ветвлением для многостадийной задачи размещения // Труды XI междунар. Байкальской школы-семинара «Методы потимиза-ции и их приложения», Иркутск, Байкал, 1998. С. 121−124.
  14. JI.E., Кочетов Ю. А. Вероятностная эвристика для двухуровневой задачи размещения If Труды XI междунар. Байкальской школы-семинара «Методы потимизации и их приложения», Иркутск, Байкал, 1998. С. 249−252.
  15. В.П. Полиномиальность в простейшей задаче размещения. // Препринт ЦЭМИ АН СССР. М.: 1987. 64 с.
  16. М., Джонсон Д. Вычислительные машины и трудпорешае-мые задачи./ Пер. с англ. М.: Мир. — 1982. — 416 с.
  17. В.Т., Ерзин А. И., Ларин P.M., Шамардин Ю. В. Задачи оптимизации иерархических структур. ~ Изд-во НГУ, Новосибирск, 1996. 167 с.
  18. В.А., Ковалев М. М., Кравцов М. К. Многогранники, графы, оптимизация. М.: Наука, 1981. — 344с.
  19. А.В. Генетический алгоритм для задачи о минимальном покрытии // Материалы конф. Новосибирск: Изд-во ИМ СО РАН, 1998. — С. 21−24.
  20. И.И., Мазуров В. Д., Астафьев Н. Н. Несобственные задачи линейного выпуклого программирования. М.: Наука, 1983. — 336с.
  21. И.А., Леванова Т. В. Анализ градиентных алгоритмов решения задачи о р-медиане на основе крутизны целевой функции II Матер, междунар. конф. «Дискретный анализ и исследование операций». Новосибирск, 2000. С. 167.
  22. Заблоцкая О.А. L-разбиение многогранника стандартизации // Моделирование и оптимизация систем сложной структуры: Меж-вуз. сб. научн. труд./ Омск: ОмГУ, 1987. С. 151−154.
  23. Г. Г. О минимаксной и минисуммной задачах размещения на плоскости с запрещенными областями // Труды XIII Байкальской международной школы-семинара «Методы потимизации и их приложения», Иркутск, Байкал, 2005. Т.1. — С. 455−460.
  24. Л.А., Китриноу Е., Колоколов Задача оптимального размещения центров телекоммуникаций в регионе // Труды XI Байкальской международной школы-семинара «Методы оптимизации и их приложения», Иркутск, Байкал, 2005. Т.1. — С. 469−476.
  25. В.П. Оценка точности алгоритма жадного спуска для задачи минимизации супермодулярной функции // Дискретный анализ и исследование операций. Серия 1. — 1998. — Т.5. — N4. — С. 45−60.
  26. В.П., Леванова Т. В. Анализ градиентного алгоритма минимизации супермодулярной функции на матроиде // Труды XI междунар. Байкальской школы-семинара «Методы потимизации и их приложения», 1998. Т.1. — С. 143−146.
  27. М. Карп. Сводимость комбинаторных проблем // Кибернетический сборник, 12, М.: Мир, 1975. С.16−38.
  28. М.М. Дискретная оптимизация (целочисленное программирование). Минск: БГУ, 1977. — 192 с.
  29. А.А. Выпуклые множества с альтернирующим L-разбиением // Моделирование и оптимизация систем сложной структуры: Межвуз. сб. научн. труд./ ОмГУ. Омск, 1987. -С. 144−150.
  30. А.А. Применение регулярных разбиений в целочисленном программировании // Изв. вузов. Математика, 1993, N 12. С. 11−30.
  31. А.А. Регулярные разбиения и отсечения в целочисленном программировании. // Сиб. журнал исслед. операций. Новосибирск. — 1994. — Т.1, N 2. — С.18−39.
  32. А.А., Леванова Т. В. Алгоритмы декомпозиции и перебора L-классов для решения некоторых задач размещения. // Вестник Омского ун-та. Омск: ОмГУ, 1996. — N 1. -С.21−23.
  33. Ю.А. Вероятностные методы локального поиска для задач дискретной оптимизации // Дискретная математика и ее приложения: Сборник лекций молодежных научных школ по дискретной математике и ее приложениям. М.: МГУ, 2001. — С. 84−117.
  34. Ю.А., Младенович Н., Хансен П. Локальный поиск в комбинаторной оптимизации: достижения и перспективы j j Материалы конф. «Проблемы оптимизации и экономические приложения». Омск: Изд-во Наследие. Диалог Сибирь, 2003. — С. 43−47.
  35. Кук С. А. Сложность процедур вывода теорем/ Кибернетический сборник, 12, М., Мир, 1975, с.5−15.
  36. Г. С. Выбор эффективной системы зависимых признаков // Вычислительные системы, 1965, вып. 19. С. 21−34.
  37. Т.В. Решение некоторых задач размещения на информационно-вычислительной сети // Информ. технологии и радиосети (ИНФОРАДИО'96): Междунар. науч. -практ. конф. Новосибирск: Изд-во ИМ СО РАН, 1998. — С. 44−47.
  38. Т.В. Двойственный жадный алгоритм для задачи о р-медиане и ее обобщений // Препринт 98−4. Омск: Омский госуниверситет, 1998. 13 с.
  39. Т.В. Алгоритмы решения одной задачи размещения на основе декомпозиции и перебора L-классов // В сб. докладов Междунар. конф. «Распределенные системы: оптимизация и приложения в экономике и науках об окружающей среде», 2000. С. 146— 149.
  40. Т.В., Лореш М. А. Алгоритм муравьиной колонии для задачи о р-медиане // Информационный бюллетень Ассоциации математического программирования. № 10. Научное издание. Екатеринбург: УрО РАН, 2003. С. 172−173.
  41. Т.В., Лореш М. А. Алгоритмы муравьиной колонии и имитации отжига для задачи о р-медиане // Автоматика и телемеханика, N 3, 2004. С. 80−88.
  42. Т.В., Лореш М. А. Алгоритм муравьиной колонии и имитации отоюига для простейшей задачи размещения // Материалы конференции «Дискретный анализ и исследование операций», Новосибирск, 2002. С. 235.
  43. Т.В., Лореш М. А. Алгоритм муравьиной колонии для задачи размещения предприятий с ограничениями на мощности производства // Материалы конференции «Дискретный анализ и исследование операций», Новосибирск, 2004. С. 189.
  44. Т.В., Лореш М. А. О сходимости одного алгоритма муравьиной колонии для задачи о р-медиане // Труды XIII Байкальской международной школы-семинара «Методы оптимизации и их приложения», Иркутск, Байкал, 2005. Т.1. — С. 535−541.
  45. М.А. Некоторые метаэвристики для задачи о р-медиане II Материалы Всероссийской научной молодежной конференции «Под знаком «Сигма», Омск, 2003. С. 11−12.
  46. М.А. Алгоритмы муравьиной колонии для простейшей задачи размещения: Препринт. Омск, ОмГУ, 2006. — 19 с.
  47. Л.С. Оптимизация больших систем. М.: Наука, 1975. -432 с.
  48. Мину М. Математическое программирование. Теория и алгоритмы. М.: Наука., 1990. — 488 с.
  49. Э.А. Обзор и перспективы развития комбинаторных методов решения задач раскроя и упаковки // Материалы российский конференции «Дискретный анализ и исследование операций». Новосибирск, 2002. — С. 80−87.
  50. М.Г. Нижние оценки для целевой функции в динамической задаче выбора оптимального состава двухуровневой системы технических средств // Дискретный анализ и исследование операций, Серия 2, 1997, Т.4, N1. -С. 40−53.
  51. М.Г. Лагранэюевы эвристики для задачи размещения с ограничениями на мощности // Труды XI международной Байкальской школы-семинара «Методы оптимизации и их приложения», Иркутск, Байкал, 1998. Т.1. — С. 175−178.
  52. И.В. Математические модели и методы решения задач дискретной оптимизации. Киев: Наук, дум., 1988. — 472 с.
  53. А. Теория линейного и целочисленного программирования./ Пер. с англ. В 2-х т. М.: Мир, 1991. — 702 с.
  54. В.Р. Математические методы регионального программирования. М.: Наука, 1989. — 304 с.
  55. Ху Т. С. Целочисленное программирование и потоки в сетях./ Пер. с англ. М., Мир, 1974. 519 с.
  56. В.Н. Качественные вопросы целочисленного программирования. М.: Физматлит, 1995. — 190 с.
  57. D., Ни Т.С. Optimal Linear Ordering // SIAM Jornal on Applied Mathematics. 1973. — V.25, N.3. — P.403−423.
  58. Ageev A.A., Sviridenko M.I. Approximation Algorithms for some Problems with cardinalyty-type contraints // Труды XI международной Байкальской школы-семинара «Методы оптимизации и их приложения», Иркутск, Байкал, 1998. С. 107−110.
  59. Ant Colony Optimization / Dorigo M., Stutzle Т., MIT Press, 2004.
  60. Badr A., Fahmy A. A proof of convergence for Ant algorithms // Information Sciences, 160, 2004. P. 267−279.
  61. Beasley J.E. An algorithm for solving large capacitated warehouse location problems // Europ. J. of Oper. Res. 1988. — 33. — P.314−325.
  62. Bonabeau E., Dorigo M., Theraulaz G. From Natural to Artificial Swarm Intelligence // Oxford University Press, 1999.
  63. Bullnheimer В., Hartl R.F., Strauss C. A New Rank Based Version of the Ant System: A Computational Study // Central European Journal for Operations Research 7(1), 1999. P. 25−38.
  64. Chvatal V. A greedy heuristic for the set-covering problem // Math. Oper. Res. 1979. — 4, N8. — P. 789−810.
  65. Chudak F.A. Improved approximation algorithms for uncapacitated facility location // IPC06 Proceedings, 1998.
  66. Colorny A., Dorigo M., Maniezzo V. Distributed optimization by ant colonies //In Proceedings of the First European Conference on Artificial Life, Elsevier, 1992. P. 134−142.
  67. Colorny A., Dorigo M., Maniezzo V., Trubian M. Ant system for job-shopscheduling // Belgian Journal of Operations Research, Statistics and Computer Science (JORBEL), 34, 1994. R 39−53,
  68. Cornuejols G., Fisher M.L. and Nemhauser G.L. Location of bank accounts to optimize float: An analytic study of exact and approximate algorithms // Management Science. 1977. — V. 23. — P. 789−810.
  69. Discrete Location Theory / Ed. by Pitu B. Mirchamdani and Richard L. Franscis, 1990, by John Wiley & Sons, Inc.
  70. Dorigo M. Optimization, Learning and Natural Algorithms // PhD thesis, Dipartimento di Electronica, Politecnico di Milano, IT, 1992 (in Italian).
  71. Dorigo M., Di Caro G., Gambardella L.M. Ant Algorithms for Discrete Optimization // Artificial Life, 1999. V.5(2). — P.137−172.
  72. Dorigo M., Gambardella L.M. Ant-Q: A reinforcement learning approach to the traveling salesman problem //In Proceedings of the Twelfth International Conference on Machine Learning, ML-95, Palo-Alto, 1995. P. 252−260.
  73. Dorigo M., Gambardella L.M. A study of some properties of Ant-Q //In Proceedings of PPSN-IV, Fourth International Conference on Parallel Problem Solving From Nature, Berlin: Springer-Verlag, 1996. P. 656−665.
  74. Dorigo M., Gambardella L.M. Ant colonies for the traveling salesman problem // BioSystems, 43, 1997. P. 73−81.
  75. Dorigo M., Gambardella L.M. Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem // IEEE Transactions on Evolutionary Computation, 1(1), 1997. P. 53−66.
  76. Dorigo M., Maniezzo V., Colorny A. Ant System: An Autocatalytic Optimizing Process // Report No. TR-91−016. Milan: Politecnico di Milano, 1991.
  77. Dorigo M., Maniezzo V., Colorny A. The ant system: Optimization by ' a colony of cooperating agents // IEEE Transactions on Systems, Man, and Cybernetics-Part B, 26(1), 1996. P. 29−41.
  78. Eremeev A.V. A Genetic Algorithm with a Non-Binary Representation for the Set Covering Problem. In Proceedings of OR'98, Springer-Verlag, 1999. P. 175−181.
  79. Gambardella L.M., Dorigo M. Solving symmetric and asymmetric TSPs by ant colonies //In Proceedings of the IEEE Conference on Evolutionary Computation, ICEC96, IEEE Press, 1996. P. 622−627.
  80. Gambardella L.M., Taillard E. D., Dorigo M. Ant colonies for the QAP // Technical Report 4−97, IDSIA, Lugano, Switzerland, 1997.
  81. Gambardella L.M., Taillard E. D., Dorigo M. Ant colonies for the QAP // Journal of the Operational Research Society (JORS), 50(2), 1999. -P. 167−176.
  82. Guha S., Khuller S. Greedy strikes back: improved facility location algorithms // The Ninth Annual ACM-SIAM Symposium on discrete algorithms (SODA), 1998. P. 649−654.
  83. Gutjahr W.J. A Converging ACO Algorithms for Stochastic Combinatorial Optimization // Proc. SAGA 2003, Springer LNCS 2827, 2003. P. 10−25.
  84. Gutjahr W.J. ACO algorithms with guaranteed convergence to the optimal solution // Information Processing Letters, 82(3), 2002, P. 145−153.
  85. Gutjahr W.J. A graph-based Ant System and its convergence // Future Generation Computer Systems. 2000. — 16. — P. 873−888.
  86. Hajek B. Cooling schedules for optimal annealing // Math, of OR, 13, 1988. P. 311−329.
  87. Hansen P., Mladenovic N. An introduction to variable neighborhood search // S. Voss (eds.), Metaheuristics: Advances and Trends in Local Search Paradigms for Optimization, Kluwer Academic Publishers, Dorchester, 1998.
  88. A.Hertz, E. Taillard, Dominique de Werra Local search in combinatorial optimization // John Wiley &- Sons, Inc., New York, 1997. 512 p.
  89. D.S. Hochbaum Heurustics for the fixed cost median problem // Math. Progr. 1982. — 22. — P. 148−162.
  90. Kariv 0., Hakimi L. An algorithmic approach to network location problems. II: The p-medians // SIAM J. Appl. Math. Vol 37, No.3, 1979. P.539−560.
  91. Kernighan B.W., Lin S. An efficient heuristic procedure for partitioning graphs // Bell System Technical Journal. 1970. — V.49. — P. 291−307.
  92. Kochetov Y., Alekseeva E., Levanova Т., Loresh M. Large neighborhood local search for the p-median problem // Yugoslav Journal of Operations Research, 15, N1, 2005. P. 53−63.
  93. Kolokolov A.A. On the L-structure of the integer linear programming problems //Proceedings of the 16th IFIP-TC7 Conference on System Modelling and Optimization. Compiegne. France, 1993. P. 756−760.
  94. Kolokolov A.A. Decomposition Algorithms for Solving of some Production-Transportation Problems // Triennal Symposium on
  95. Transportation Analysis II. Preprints. Vol. 1. Capri, Italy, 1994. -P. 179−183.
  96. Krarup J., Pruzan P.M. The simple plant location problem: survay and synthesis //European J. Oper. Res. 1983. V.12, N1. P. 36−81.
  97. M. Laguna, F. Glover Bandwing Packing: A tabu Search Approach // Managment Science. Vol. 39, No.4, April 1993, P. 492−500.
  98. Lawler E.L. The Quadratic Assignment Problem // Management Science, 1963. V.9. — P. 586−599.
  99. Lin J. -H., Vitter J.S., Approximation algorithms for geometric median problems // Inform. Process. Lett. 44 (1992), no.5. P. 245−249.
  100. Lin S. Computer solutions of the traveling salesman problem // Bell System Journal, 1965. V.44. — P. 2245−2269.51 999. P.76.
  101. Levanova T.V., Loresh M.A. Ant colony and simulated annealing algorithms for the p-median problem // Proceedings of The Second International Workshop «Discrete Optimization Methods in Production and Logistics», Omsk-Irkutsk, 2004. P. 70−74.
  102. Levanova T.V., Loresh M.A., Nikitin A.G. Some local search algorithms for uncapacitated facility location problem // Proc. of XXXIII annual conference «AIRO 2002», L’Aquila, 10−13 September, 2002. P. 170.
  103. Local search in Combinatorial optimization / Edited by E. Aarts and J.K.Lenstra, 1997, John Wiley and Sons Ltd.
  104. Loresh M.A., Levanova T.V. The Ant Colony algorithm for the Capacitated Plant Location Problem // EWGLA XV Meeting, Saarbriicken, September 5−8, 2004. P. 39−40.
  105. Love R.F., Wong J.Y. On Solving a One-Dimensional Space Allocation Problem with Integer Programming // INFOR. V.12, N2. — R 139 143.
  106. Maniezzo V. Exact and approximate nondeterministic tree-search procedures for the quadratic assignment problem // Technical Report CSR 98−1, C. L. In Scienze dell’Informazione, University di Bologna, sede di Cesena, Italy, 1998.
  107. Maniezzo V., Colorni A. The ant system applied to the quadratic assignment problem // IEEE Trans. Knowledge and Data Engineering, 1999
  108. Maniezzo V., Colorni A., Dorigo M. The ant system applied to the quadratic assignment problem // Technical Report IRIDIA/94−28, Universite Libre de Bruxelles, Belgium, 1994.
  109. Neumann F., Witt C. Runtime Analisys of a Simple Ant Colony Optimization Algorithm // Technical Report, Reihe CI 200/06, SFB 531, Universitat Dortmund, 2006.
  110. Picard J.C., Queranne M. On the One-Dimensional Space Allocation Problem // Oper. Res. 1981. — Vol. 29. — P. 371−391.
  111. Reeves C.R. Genetic Algorithms for the Operations Researcher // INFORMS J. on Computing. 1997. — Vol. 9, N 3. — P. 231−250.
  112. Resende M.G.C., Werneck R.F. On the implementation of a swap-based local search procedure for the p-median problem // Proceedings of the Fifth Workshop on Algorithm Engineering and Experiments, SIAM, 2003. P. 119−127.
  113. Sridharan R. Invited Review. The capacitated plant location problem // Europ. J. of Operational Research 87, 1995. P. 203−213.
  114. Sttitzle Т., Dorigo M. A Short Convergence Proof for a Class of ACO Algorithms // IEEE Transactions on Evolutionary Computation, 2002, 6(4). -P. 358−365.
  115. Stutzle Т., Hoos H.H. MAX-MIN Ant System // Future Generation Computer Systems. 2000. — 16. — P. 889−914.
  116. Stutzle Т., Hoos H.H. Improvements on the Ant System: Introducing the MAX-MIN Ant System //In R.F. Albrecht G.D. Smith, N.C. Steele, editor, Artificial Neural Networks and Genetic Algorithms. Springer-Verlag, Wien, New York, 1998. P. 245−249.
  117. Yagiura M., Ibaraki Т., Glover F. An ejection chain approach for generalized assignment problem /j INFORMS Journal on computing, 16, 2004. P. 133−151.120. http://www.math.nsc.ru/AP/benchmarks/index.hnml
Заполнить форму текущей работой

Сессия? Спокойно!