Аннотация:
В классических метрических задачах размещения стоимость обслуживания клиента предприятием пропорциональна длине кратчайшего пути между ними (другими словами, предприятие обслуживает клиента по кратчайшему маршруту). В данной статье исследуются обобщения этих задач, в которых маршрут обслуживающей бригады проходит через удалённый склад, содержащий блоки или модули, требующие замены. В этом случае суммарная длина пути до клиента, вообще говоря, уже не будет кратчайшей и задача перестаёт быть метрической. Показано, что известные в литературе алгоритмы для нахождения приближённых решений классических метрических задач переносятся на рассматриваемые обобщения с сохранением установленных для них оценок точности.
Библ. 12.
УДК:519.854
Статья поступила: 07.12.2006 Переработанный вариант: 14.05.2007