Том 14, серия 1, номер 3, 2007 г., Стр. 3-12

УДК 519.854
А. А. Агеев
Метрические задачи размещения c не кратчайшими маршрутами обслуживания

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

Агеев А. А. ¹
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
е-mail: ageev@math.nsc.ru

Статья поступила 7 декабря 2006 г.
Исправленный вариант — 14 мая 2007 г.