Задача размещения с ограничениями на мощности

Главная страница библиотеки   Задача размещения с ограничениями на мощности

Оптимизационные алгоритмы

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

Первые приближенные алгоритмы были опробованы в 1963 году [1, 2] и представляли собой примитивные эвристики, основанные на процедурах типа "добавить - удалить" предприятия. Варианты этих "жадных" алгоритмов тестировались в [1, 2, 3]. Естественным продолжением идеи жадных алгоритмов является процедура замены типа "один закрыть - другой открыть", которая в дополнении с жадными эвристиками составила первый работоспособный алгоритм для данной задачи [3, 4]. Наиболее широко этот алгоритм применяется в методе ветвей и границ, когда требуется быстро построить допустимое решение задачи на заданной части допустимой области [6].  Дальнейшим развитием идеи жадных алгоритмов является разработка их вероятностных аналогов, так называемых GRASP-адгоритмов  (Greedy Randomized Adaptive Search Procedure [7, 8]) и на их основе алгоритмов типа "муравьиной колонии" [9, 10].

Процедуры "добавить - удалить - заменить" можно рассматривать как способ формирования окрестности заданного решения. С этой точки зрения вышеупомянутые алгоритмы представляют собой локальный спуск с остановкой в точке локального оптимума. Понятно, что такой локальный оптимум не обязан быть глобальным и, вообще говоря, может быть сильно удален от него. Оценки уклонения локального оптимума от глобального можно найти в [11, 12]. Современные методы локального поиска (Поиск с запретами, Имитация отжига, Генетические алгоритмы) еще только разрабатываются для данной задачи. Первые варианты таких алгоритмов демонстрируют высокую эффективность, и их разработка является одним из перспективных направлений в данной области.

Принципиально другим типом эвристик для данной задачи являются Лагранжевы релаксации. Существует много вариантов построения таких релаксаций, сравнение которых подробно описано в [13]. С вычислительной точки зрения наиболее эффективной является релаксация первой группы ограничений, которая требует удовлетворения потребностей всех потребителей. На основе этой релаксации разработаны точные методы [14, 15, 16, 17] и приближенные алгоритмы [18, 19, 20]. К сожалению, точные методы позволяют решать задачи только небольшой размерности: 50 предприятий, 200 потребителей. Как правило эти задачи имеют значительный разрыв двойственности, и методы их решения еще далеки от совершенства.

Литература

1. Kuehn A.A., Hambarger M.J. A heuristic procedure for locating warehouses. Management Science. v9 (1963), pp 643-666.

2. Feldman E., Lehrer F.A., Ray T.L. Warehouse locations under continuous economies of scale. Management Science. v12 (1966), pp 670-684.

3. Khumawala B.M. An efficient heuristic procedure for the capacitated warehouse location problem. Naval Research Logistics Quarterly. v21 (1974), N4, pp 609-623.

4. Jacobson S.K. Heuristics for the capacitated plant location model. European Journal of Operational Research. v12 (1983), pp 253-261.

5. Domschke W., Drexl A. ADD-heuristics' starting procedures for capacitaded plant location models. European Journal of Operational Research. v21 (1985), pp 47-53.

6. Akins U., Khumawala M. An efficient branch and bound algorithm for the capacitated warehouse location problem. Management Science v23 (1977), pp 585-594.

7. Гончаров Е.Н., Кочетов Ю.А. Поведение вероятностных жадных алгоритмов для многостадийной задачи размещения. Дискретный анализ и исследование операций. Сер.2, т6 (1999), №1, с.12-32.

8. Feo T.A. Greedy Randomized Adaptive Search Procedures. Journal of Global Optimization. v6 (1995), pp 109-133.

9. Александров Д.А. Алгоритм муравьиной колонии для задачи о минимальном покрытии. Труды XI международной Байкальской школы-семинара Методы оптимизации и их приложения. Иркутск, т3 (1998), с.17-20.

10. http://iridia.ulb.ac.be/dorigo/ACO/ACO.html

11. Korupolu M., Plaxton C., Rajaraman R. Analisys of a local search heuristic for fasility location problem Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms. 1998, pp 1-10.

12. Chudak F.A., Williamson D.P. Improved approximation algorithm for capacitated facility location problem. IPCO'99, LNCS. v1610 (1999), pp 99-113.

13. Cornuejols G., Sridharan R., Thizy J.M. A comparison of heuristics and relaxations for the capacitated plant location problem. European Journal of Operational Research. v50 (1991), pp 280-297.

14. Geoffrion M., McBride R. A direct dual method for the mixed plant location problem with some side constraints. Mathematical Programming. v17 (1978),   N2, pp 40-47.

15. Nauss R.M. An improved algorithm for the capacitated facility location problem. Journal of Operational Research Society, v29 (1978) pp 1195-1202.

16. Christofides N., Beasley J.E. An algorithm for the capacitated warehouse location problem. European Journal of Operational Research. v12 (1983), pp 19-28.

17. Van Roy T.J. A cross decomposition algorithm for capacitated facility location. Operations Research. v34 (1986), pp 145-163.

18. Agar M.C., Salhi S. Lagrangear heuristics applied to a variety of large capacitated plant location problems. Journal of Operational Research Society, v49 (1998) pp 1072-1084.

19. Beasley J.E. Lagrangean heuristics for location problem. European Journal of Operational Research. v65 (1993), pp 383-399.

20. Кочетов Ю.А., Пащенко М.Г. Лагранжевы релаксации в задаче выбора оптимального состава системы технических средств. Управляемые системы, вып.31 (1993), с.26-39.

21. Пащенко М.Г. Лагранжевы эвристики для задачи размещения с ограничениями на мощности. Труды XI международной Байкальской школы-семинара Методы оптимизации и их приложения. Иркутск, т1 (1998), с.175-178.

Главная страница библиотеки   Задача размещения с ограничениями на мощности