Проблема с краном-штабелером
В комбинаторной оптимизации задача о кране-штабелере является задачей оптимизации, тесно связанной с задачей коммивояжера . Его входные данные представляют собой набор упорядоченных пар точек в метрическом пространстве , и цель состоит в том, чтобы соединить эти точки в цикл минимальной общей длины, включающий все пары, ориентированные согласованно друг с другом. Он моделирует задачи планирования забора и доставки отдельных партий груза краном- штабелером , строительным краном или (при перевозке ) грузовым автомобилем в упрощенной форме без ограничений по срокам этих доставок. [ 1 ] Он был введен Фредериксоном, Хехтом и Кимом (1978) с эквивалентной формулировкой в терминах смешанных графов с направленными ребрами, моделирующими входные пары, и ненаправленными ребрами, моделирующими их расстояния. Фредериксон и др. приписывают его формулировку личному сообщению Дэниела Дж. Розенкранца. [ 2 ]
Задачу о коммивояжере-штабелере можно рассматривать как обобщение задачи о коммивояжере в метрических пространствах: любой пример задачи о коммивояжере можно преобразовать в пример задачи о коммивояжере-штабелере, имея пару за каждое очко в экземпляре коммивояжера. С другой стороны, задачу о кране-штабелере можно рассматривать как частный случай асимметричной задачи о коммивояжере, где точками асимметричной задачи о коммивояжере являются пары экземпляров крана-штабелера, а расстояние от одной пары до другой берется как расстояние от пункта доставки первой пары, через пункт его выдачи, до пункта доставки второй пары. Поскольку она обобщает задачу коммивояжера, она унаследовала ту же вычислительную сложность : она NP-трудна и, по крайней мере, так же сложна для аппроксимации. [ 2 ]
Алгоритм аппроксимации, основанный на алгоритме Кристофидеса для задачи коммивояжера, может аппроксимировать решение задачи крана-штабелера с точностью до коэффициента аппроксимации 9/5. [ 2 ]
Задача проектирования обратной стороны рисунка вышивки для минимизации общего количества используемых ниток тесно связана с задачей крана-штабелера, но позволяет каждой из пар точек (концам видимых стежков на лицевой стороне вышивки) шаблон) для обхода в любом направлении, вместо того, чтобы требовать прохождения всех пар в одном и том же направлении. Она NP-трудна благодаря тому же преобразованию, что и задача коммивояжера, и может быть аппроксимирована с точностью до коэффициента аппроксимации 2. [ 3 ] Другой вариант задачи о кране-штабелере, называемый задачей «дозвона до машины» , требует минимального маршрута, по которому транспортное средство может выполнять сбор и доставку грузов, в то же время позволяя ему удерживать некоторое количество k > 1 грузов в любой точке своего пути. маршрут. [ 4 ]
Ссылки
[ редактировать ]- ^ Срур, Ф.Дж. (2010), Рассекающая перевозка: исследование структуры, информации и контроля в перевозочных операциях , ERIM Ph.D. Серия «Исследования в области менеджмента», том. EPS-2010-186-LIS, Научно-исследовательский институт менеджмента Эразма, hdl : 1765/18231
- ^ Jump up to: а б с Фредериксон, Грег Н.; Хехт, Мэтью С.; Ким, Чул Э. (1978), «Алгоритмы аппроксимации для некоторых задач маршрутизации», SIAM Journal on Computing , 7 (2): 178–193, doi : 10.1137/0207017 , MR 0489787 ; ранее объявлено на 17-м ежегодном симпозиуме по основам информатики, 1976 г.
- ^ Аркин, Эстер М .; Харт, Джордж; Ким, Джундон; Костицына Ирина; Митчелл, Джозеф С.Б .; Сабхнани, Гиришкумар; Скиена, Стивен (2008 г.), «Проблема вышивки», Материалы 20-й ежегодной канадской конференции по вычислительной геометрии, Монреаль, Канада, 13–15 августа 2008 г.
- ^ Чарикар, Моисей ; Рагхавачари, Баладжи (1998), «Проблема дозвона с конечной пропускной способностью», 39-й ежегодный симпозиум по основам информатики, FOCS '98, 8–11 ноября 1998 г., Пало-Альто, Калифорния, США , Компьютерное общество IEEE, стр. 458–467, дои : 10.1109/SFCS.1998.743496