Триангуляция в логистике что это
Триангуляция в логистике что это
ИДЕЯ ФРАХТА (idea of freight)
примерная величина фрахта, обычно соответствующая рыночной фрахтовой ставке, которая используется в качестве ориентира при фрахтовании судов.
ИЗВЕЩЕНИЕ ОБ ОТГРУЗКЕ (notice of shipment)
документ, подтверждающий отгрузку импортного груза из порта на станцию назначения или выдачу такого груза получателю на месте; составляется портом и включает в себя дату отгрузки, номера накладной и вагона, вес брутто, количество мест.
ИНКАССО (collection)
вид банковской операции по передаче денежных средств от одних клиентов другим, от плательщиков получателям.
ИНТЕРМОДАЛЬНЫЕ ПЕРЕВОЗКИ (intermodal transport) см. Смешанный транспорт.
ИНФОРМАЦИОННЫЙ ПОТОК (Information flow)
Совокупность циркулирующих в логистической системе, а также между логистической системой и внешней средой сообщений, необходимых для управления и контроля над логистическими операциями.
КАНЦЕЛИНГ (cancelling)
предусмотренный договором морской перевозки предельный календарный срок прибытия зафрахтованного судна в порт отправления и его готовности во всех отношениях к погрузке. Если судно не прибыло к дате К., фрахтователь вправе отказаться от приемки судна под погрузку и канцелироватъ (cancel), то есть расторгнуть чартер. Исключениями могут явиться: задержки, происшедшие по вине самого фрахтователя; случай аварии и форс-мажорные обстоятельства.
KAPАНТИННЫЙ НАДЗОР (quarantine regulations)
комплекс санитарно-охранных мероприятий по предотвращению завоза в страну из-за границы эпидемических заболеваний и сельскохозяйственных вредителей и болезней. К.н. осуществляется путем карантинного досмотра транспортных средств и грузов, прибывающих в страну. Импортные грузы растительного и животного происхождения должны иметь ветеринарные и санитарные свидетельства, выдаваемые органами К.н. страны-экспортера.
КАРГОПЛАН (cargo plan, stowage plan)
план размещения груза на морском или речном судне с целью наиболее рационального использования грузовых помещений. При составлении К. должны учитываться физико-химические и транспортные свойства грузов, возможность их совместной перевозки, последовательность выгрузки в промежуточных портах, правила перевозки и хранения, масса, объем груза, а также необходимость сохранения судном мореходных качеств. От качества составления К. в значительной степени зависит организация грузовых операций в портах погрузки и выгрузки судна, а, следовательно, и продолжительность его стояночного времени. К. составляется представителями порта и судовой администрации и утверждается капитаном судна.
КАРГОТРАСЕР (cargo tracer)
документ, составляемый брокером; отражает недостатки и излишки груза. Копии К. брокер посылает во все порты выгрузки, судовладельцу и капитану судна. В портах выгрузки брокеры проверяют данные, указанные в К., и одну подписанную ими копию посылают отправителю К.
КЛАРИРОВАНИЕ (clearance)
оформление всех формальностей и операций, необходимых для получения разрешения на вход судна в порт и выход из него (оформление документов, связанных с выполнением таможенных, санитарных и других формальностей, уплатой портовых сборов и т.д.).
КЛАСС СУДНА (class of vessel)
свидетельство о соответствии технических характеристик судна требованиям классификационного общества. К.с. присваивается на определенный срок.
КОМИССИЯ (commission)
вознаграждение брокеру или агенту в линейном судоходстве, которое устанавливается в виде определенного процента от фрахта.
КОММЕРЧЕСКАЯ ЛОГИСТИКА (Business logistics)
имеет дело не только с управлением материальным потоком, но и с обеспечением механизма разработки задач и стратегий, в рамках которых может осуществляться деятельность по распределению.
КОММЕРЧЕСКИЙ АКТ (carrier’s statement, statement of damage)
документ, составляемый перевозчиком или его представителем в удостоверение факта недостачи, повреждения или порчи груза при его выдаче грузополучателю в пункте назначения. К.а. фиксирует причины несохранности груза, размер и характер ущерба; имеет большое значение при ликвидации убытков страховщиком. К.а. служит основанием для предъявления получателем груза претензии о возмещение перевозчиком убытков. Отметка о составлении К.а. делается на оборотной стороне транспортной накладной.
КОНВЕНЦИОНАЛЬНЫЙ ГРУЗ (conventional cargo, break-bulk cargo)
генеральный груз, который загружается/выгружается на/из судно(а) обычным способом (т.е. не в контейнерах, не на трейлерах и т.п.) и соответственно поименованный в коносаменте.
КОНТЕЙНЕР С ОБЪЕДИНЕННЫМИ ГРУЗАМИ (consolidated containerload, CCL)
контейнер, который загружен грузами разных отправителей юга разных получателей.
КОНТЕЙНЕРИЗАЦИЯ (containerization)
метод доставки товаров в контейнерах, позволяющий вовлекать в транспортно-технологическую систему морской, речной, воздушный, железнодорожный и автомобильный транспорт. Бурное развитие К. привело к необходимости стандартизации крупнотоннажных контейнеров и выработке требований к их конструкции, которые регламентируются «Международной конвенцией по безопасным контейнерам». Основные преимущества К.: доставка грузов «от двери до двери» без промежуточной перегрузки, малый риск повреждения грузов, более быстрая доставка грузов, экономия рабочей силы и складских помещений.
КОНТЕЙНЕРНАЯ ПЛОМБА (container seal)
пломба, которая используется вместе с замком для опломбирования контейнера. К.п. обычно имеет номер или код, что зафиксировано в соответствующих документах.
КОНТРАКТНАЯ СТАВКА (contract rate)
в морском судоходстве льготная фрахтовая ставка, применяемая в отношении перевозимых грузов фирмы, которая заключила ограничительный договор с судовладельцем.
КОНТРСТАЛИЯ (demurrage)
время простоя судна в порту под грузовыми операциями сверх обусловленного договором морской перевозки сталийного времени. За К. фрахтователь оплачивает перевозчику демередж.
КРУГОВОЙ РЕЙС (round voyage, round trip)
рейс между двумя или несколькими портами, при котором судно возвращается в первоначальный порт отправления.
Триангуляция местоположения мобильного телефона базовыми станциями
Существует распространенное заблуждение о том, что географическое местоположение любого GSM-телефона можно с достаточно большой точностью определить при помощи триангуляции по трем базовым станциям. Описывают это обычно так: допустим, если можно стандартными средствами определить расстояние от базовой станции до телефона, то по расстояниям от трех базовых станций можно получить точные координаты аппарата, а по расстоянию от двух базовых станций — две точки, в одной из которых и будет находиться искомый телефон. Как правило, народная молва наделяет криминальные элементы или правоохранительные органы способностью при помощи подобной технологии находить нужных им людей.
Часть этого утверждения — сущая правда. Стандартными средствами иногда можно определить расстояние от телефона до одной базовой станции. Именно этим, наверно, и объясняется живучесть убеждения в том, что триангуляция возможна. На самом деле это не так.
Прежде чем начинать детальный разбор дела о триангуляции, стоит сделать существенную оговорку. Необходимо провести четкую границу между заблуждением о том, что базовые станции любой GSM-сети всегда триангулируют местоположение указанного телефона (вариант — всех телефонов в зоне покрытия) и возможностью обнаружения местоположения телефона другими средствами в рамках отдельно взятой сети.
Услуги, привязанные к местоположению
Для предоставления услуг, привязанных к местоположению абонента (location-based services, LBS), существует множество способов, опирающихся на наличие дополнительного программного и аппаратного обеспечения на всех базовых станциях конкретной сети, а иногда еще и в SIM-карте/телефоне абонента. Пример таких услуг: показать абоненту карту города и его место на ней, сообщить адрес ближайшего ресторана или магазина, сообщить о местоположении другого абонента, проложить маршрут в заданную точку.
Для ряда применений достаточно приблизительно знать какую-то одну базовую станцию, в зоне покрытия которой находится абонент. Это можно сделать в любой сети GSM. Результат: круг радиусом до 32 км с центром в месте установки какой-то базовой станции. В городских условиях радиус можно сократить, так как зоны покрытия базовых станций обычно невелики. Стоит упомянуть, что информация о «текущей» базовой станции обновляется при каждом звонке/SMS или же где-то раз в час, поэтому для повышения точности обнаружения абоненту непосредственно перед «замером» присылают SMS или же побуждают самого абонента послать SMS с запросом вида «где я/где ближайший ресторан/гостиница/метро/. ».
Этот результат можно улучшить при помощи метода, называемого «time of arrival». Требуется модернизация всех базовых станций сети. Результат: круг радиусом 100-500 метров с центром в месте установки базовой станции. Применение еще более совершенных методов (их описание может быть найдено в сети по ключевым словам «angle of arrival», «uplink time difference of arrival», «GPS», «assisted GPS») позволяет еще больше сократить радиус круга или перенести его центр в реальное местоположение абонента.
Наличие любой более-менее сложной системы обнаружения местоположения абонентов в сети оператора определить очень легко — оператор будет продавать соответствующие услуги, никто не будет инвестировать в создание необходимой инфраструктуры просто так. Нередко достаточно беглого просмотра рекламных материалов услуги, для того чтобы определить тип используемой оператором технологии, просто на основании данных о точности обнаружения.
На этом экскурс в технологии определения местоположения абонента можно считать завершенным и возвращаться к оригинальной теме:
Триангуляция
Начнем с аналогии. Рассмотрим такое утверждение: «при помощи утилиты ping можно определить время прохождения TCP-пакетов от одного компьютера до другого, а значит и оценить расстояние между ними. Тогда по расстояниям от трех компьютеров, зная их координаты, можно получить координаты искомого компьютера».
Выглядит неправдоподобно? А что, если мы возьмем четыре компьютера, соединим их сетевыми кабелями друг с другом непосредственно, без использования промежуточных сетей, причем провода проложим строго по прямой? Сможем ли мы в таком случае определить координаты центрального компьютера, зная координаты периферийных и пользуясь только ping-ом? Сможем. Означает ли это, что подобный способ можно будет использовать всегда? Безусловно, нет. Во-первых, провода редко соединяют два компьютера непосредственно и строго по прямой, во-вторых, мы, как правило, не знаем точных координат «опорных» компьютеров и т.п. Продолжить этот список будет несложно.
Телефон в режиме ожидания
Базовые станции регулярно передают сигналы в эфир, чтобы телефоны могли понимать, находятся ли они в зоне покрытия. Телефоны же, напротив, большую часть времени ничего не передают, только принимают, с целью экономии заряда батарей. Это легко проверить на практике, положив телефон рядом с компьютерными аудиоколонками и наблюдая за наводимыми телефоном возмущениями либо купив простейший брелок-детектор GSM-сигналов. Отсюда следует, что определить местоположение обычного GSM-телефона в обычной GSM-сети в произвольный момент времени нельзя просто потому, что телефон молчит и никому «не сообщает», где он и куда его несут.
Да, периодически телефон уведомляет сеть о том, в каком месте он находится, чтобы упростить доставку входящих звонков. Происходит это:
При этом телефон сообщает сети только о том, какую базовую станцию он «слышит» лучше всего, без всяких подробностей вроде уровня сигнала и т.п. Базовые станции не следят за тем, какие телефоны находятся в зоне их покрытия, это бессмысленно и технически неосуществимо. Соответственно, у мобильной сети большую часть времени есть лишь весьма приблизительные сведения о том, где сейчас обитает телефон. Может ли при этом стандартная мобильная сеть заниматься измерением расстояния до телефона, не выводя его из режима ожидания?
Во-первых, непонятно, от какой базовой станции измерять — со времени последнего обновления информации о местоположении телефон могли унести на значительное расстояние. Во-вторых, непонятно, что и как измерять. Базовая станция — не радиолокатор, и если телефон «молчит», то для нее он не существует.
Итак, в режиме ожидания стандартный телефон в стандартной сети GSM полностью невидим для мобильной сети и не может быть ею «триангулирован».
Сам телефон при этом находится в более выигрышном положении. Дело в том, что каждая базовая станция транслирует в эфир информацию о своих «соседях», указывая частоты, на которых работают ближайшие базовые станции той же сети. Телефон в режиме ожидания постоянно измеряет уровень сигнала (но не затухание) от каждой из «соседних» базовых и при необходимости выбирает в качестве дежурной базовой станции ту, сигнал от которой «лучше слышно». Если телефон обладает какими-то сведениями о том, где (по каким координатам) расположены базовые станции, то он может попытаться вычислить зону, в которой области гипотетического покрытия всех «соседних» базовых пересекаются. Где-то в пределах этой области и будет находиться телефон. Чем точнее телефон знает (или оценивает) границы зон покрытия, тем точнее будет работать такой метод. По имеющейся информации, именно так работает приложение Google Latitude. Если же данных о местонахождении базовых станций нет, то и у телефона не будет никакой возможности «триангулировать» свое положение.
Телефон в активном режиме
В активном режиме телефон посылает сигналы какой-то одной базовой станции и принимает от нее ответные сигналы.
У всех на слуху тот факт, что сети GSM могут работать на частотах 900, 1800 и (реже) 1900 mHz. На самом деле речь идет о диапазонах частот:890-960, 1710-1880 и 1850-1990 mHz соответственно.
Каждая базовая станция вещает только на одной определенной частоте из этого диапазона. Соседние базовые станции, независимо от того, какому оператору они принадлежат, всегда конфигурируются так, чтобы создавать друг другу минимум помех. В частности, соседние базовые станции никогда не будут работать на одной и той же частоте.
Базовая станция в процессе обслуживания разговора выполняет контролирующие и регулирующие функции. Она занимается расчетом величин так называемого временного сдвига (timing advance) и передает их телефону. Телефон использует их, чтобы корректировать ход своего таймера так, чтобы у него и у базовой станции «часы» шли синхронно и посланные телефоном сигналы достигали базовую станцию в пределах отведенного телефону «окна вещания». Чтобы правильно рассчитать временной сдвиг, базовая станция измеряет время прохождения сигнала от себя до телефона, но ей абсолютно не важно, сколько раз по пути следования сигнал отразился от зданий и прочих препятствий. Базовая станция также оценивает уровень сигнала от телефона и степень его затухания и выдает телефону рекомендации по необходимой мощности передачи.
Телефон в процессе разговора тоже имеет информацию о временном сдвиге, уровне сигнала от базовой станции и мощности своего передатчика. Получается, что и базовая станция, и телефон могут, в принципе, как-то оценить расстояние друг до друга по пути следования радиосигнала, но они никак не могут учесть все возможные преломления и отклонения. Точность измерения расстояния по временному сдвигу составляет примерно 500 м.
Выводы
Если не вести речь про какого-то конкретного оператора, а говорить о GSM как о технологии вообще, то можно утверждать, что:
Алгоритм триангуляции Делоне методом заметающей прямой
Доброго времени суток!
В этой статье я подробно опишу алгоритм, который у меня получился в результате использования идеи «заметающей прямой» для построения триангуляции Делоне на плоскости. В нем есть несколько идей, которые я нигде не встречал, когда читал статьи про триангуляцию.
Возможно, кто-то тоже найдет их необычными. Я постараюсь сделать все в лучших традициях и включить в рассказ следующие вещи: описание используемых структур данных, описание шагов алгоритма, доказательство корректности, временные оценки, а также сравнение с итеративным алгоритмом, использующим kD-дерево.
Определения и постановка задачи
Триангуляция
Говорят, что на множестве точек на плоскости задана триангуляция, если некоторые пары точек соединены ребром, любая конечная грань в получившемся графе образует треугольник, ребра не пересекаются, и граф максимален по количеству ребер.
Триангуляция Делоне
Триангуляцией Делоне называется такая триангуляция, в которой для любого треугольника верно, что внутри описанной около него окружности не находится точек из исходного множества.
Замечание: для заданного множества точек, в котором никакие 4 точки не находятся на одной окружности, существует ровно одна триангуляция Делоне.
Условие Делоне
Пусть на множестве точек задана триангуляция. Будем говорить, что некоторое подмножество точек удовлетворяет условию Делоне, если триангуляция, ограниченная на это подмножество, является триангуляцией Делоне для него.
Критерий для триангуляции Делоне
Выполнение условия Делоне для всех точек, образующих четырехугольник в триангуляции, эквивалентно тому, что данная триангуляция является триангуляцией Делоне.
Замечание: для невыпуклых четырехугольников условие Делоне всегда выполнено, а для выпуклых четырехугольников (вершины которого не лежат на одной окружности) существует ровно 2 возможные триангуляции (одна из которых является триангуляцией Делоне).
Задача заключается в том, чтобы для заданного множества точек построить триангуляцию Делоне.
Описание алгоритма
Видимые точки и видимые ребра
Пусть задана минимальная выпуклая оболочка (далее МВО) конечного множества точек (ребра, соединяющие некоторые из точек так, чтобы они образовывали многоугольник, содержащий все точки множества) и точка A, лежащая вне оболочки. Тогда точка плоскости называется видимой для точки А, если отрезок, соединяющий ее с точкой А, не пересекает МВО.
Ребро МВО называется видимым для точки А, если его концы видимы для А.
На следующей картинке красным помечены ребра, видимые для красной точки:
Замечание: контур триангуляции Делоне является МВО для точек, на которых построена.
Замечание 2: в алгоритме видимые для добавляемой точки А ребра образуют цепочку, то есть несколько подряд идущих ребер МВО
Хранение триангуляции в памяти
Есть некоторые стандартные способы, неплохо описанные в книге Скворцова [1]. Ввиду специфики алгоритма, я предложу свой вариант. Так как хочется проверять 4-угольники на условие Делоне, то рассмотрим их строение. Каждый 4-угольник в триангуляции представляет из себя 2 треугольника, имеющих общее ребро. У каждого ребра есть ровно 2 треугольника, прилегающих к нему. Таким образом, каждый четырехугольник в триангуляции порождается ребром и двумя вершинами, находящимися напротив ребра в прилегающих треугольниках.
Так как по ребру и двум вершинам восстанавливаются два треугольника и их смежность, то по всем таким структурам мы сможем восстановить триангуляцию. Соответственно предлагается хранить ребро с двумя вершинами в множестве и выполнять поиск по ребру (упорядоченной паре вершин).
Алгоритм
Идея заметающей прямой заключается в том, что все точки сортируются по одному направлению, а затем по очереди обрабатываются.
Проверка условия Делоне
Способы проверки четырехугольников на условие Делоне можно найти в той же книжке [1]. Подмечу лишь, что при выборе метода с тригонометрическими функциями оттуда при неаккуратной реализации могут получаться отрицательные значения синусов, есть смысл брать их по модулю.
Поиск видимых ребер
Осталось понять, как эффективно находить видимые ребра. Заметим, что предыдущая добавленная точка S находится в МВО на текущей итерации, так как имеет наибольшую координату 
, а также видима для текущей точки. Тогда, замечая, что концы видимых ребер образуют непрерывную цепочку видимых точек, мы можем идти от точки S в обе стороны по МВО и собирать ребра, пока они видимы (видимость ребра проверяется с помощью векторного произведения). Таким образом удобно хранить МВО как двусвязный список, на каждой итерации удаляя видимые ребра и добавляя 2 новых из рассматриваемой точки.
Визуализация работы алгоритма
Две красные точки — добавляемая и предыдущая. Красные ребра в каждый момент составляют стек рекурсии из шага (4):
Корректность алгоритма
Чтобы доказать корректность алгоритма, достаточно доказать сохранение инварианта в шагах (3) и (4).
Шаг (3)
После шага (3), очевидно, получится некоторая триангуляция текущего множества точек.
Шаг (4)
В процессе выполнения шага (4) все четырехугольники, не удовлетворяющие условию Делоне, находятся в стеке рекурсии (следует из описания), а значит, по окончании шага (4) все четырехугольники удовлетворяют условию Делоне, то есть действительно построена триангуляция Делоне. Тогда осталось доказать, что процесс в шаге (4) когда-нибудь закончится. Это следует из того, что все ребра, добавленные при перестроении, исходят из текущей рассматриваемой вершины (то есть на шаге 
их не больше, чем 
) и из того, что после добавления этих ребер мы не будем рассматривать четырехугольники, порожденные ими (см. предыдущее замечание), а значит, добавим не более одного раза.
Временная сложность
В среднем на равномерном, нормальном распределениях алгоритм работает довольно неплохо (результаты приведены ниже в табличке). Есть предположение, что время его работы составляет 
. В худшем случае имеет место оценка 
.
Давайте разберем время работы по частям и поймем, какая из них оказывает самое большое влияние на итоговое время:
Сортировка по направлению
Для сортировки будем использовать оценку .
Поиск видимых ребер
Для начала покажем, что время, суммарно затраченное на поиск видимых ребер, есть 
. Заметим, что на каждой итерации мы находим все видимые ребра и еще 2 (первые не видимые) за линейное время. В шаге (3) мы добавляем в МВО новые 2 ребра. Таким образом, всего в меняющейся на протяжении алгоритма МВО побывает не более 
ребер, значит, и различных видимых ребер будет не более . Еще мы найдем ребер, не являющихся видимыми. Таким образом, в общей сложности найдется не более 
ребер, что соответствует времени .
Построение новых треугольников
Суммарное время на построение треугольников из шага (3) с уже найденными видимыми ребрами, очевидно, .
Перестроение триангуляции
Осталось разобраться с шагом (4). Сначала заметим, что проверка условия Делоне и перестроение в случае его не выполнения являются довольно дорогими действиями (хоть и работают за 
). Только на проверку условия Делоне может уйти около 28 арифметических операций. Посмотрим на среднее количество перестроений в течение этого шага. Практические результаты на некоторых распределениях приведены ниже. По ним очень хочется сказать, что среднее количество перестроений растет с логарифмической скоростью, однако оставим это как лишь предположение.
Здесь еще хочется подметить, что от направления, вдоль которого производится сортировка, может сильно варьироваться среднее число перестроений на точку. Так на миллионе равномерно распределенных на длинном низком прямоугольнике с отношением сторон 100000:1 это число варьируется от 1.2 до 24 (эти значения достигаются при сортировке данных по горизонтали и вертикали соответственно). Поэтому я вижу смысл выбирать направление сортировки произвольным образом (в данном примере при произвольном выборе в среднем получалось около 2 перестроений) или выбрать его вручную, если данные заранее известны.
Таким образом, основное время работы программы обычно уходит на шаг (4). Если же он выполняется быстро, то есть смысл задуматься над ускорением сортировки.
Худший случай
В худшем случае на -ой итерации происходит рекурсивный вызов в шаге (4), то есть, суммируя по всем i, получаем асимптотику в худшем случае . Следующая картинка иллюстрирует красивый пример, на котором программа может работать долго (1100 перестроений в среднем при добавлении новой точки при входных данных в 10000 точек).
Сравнение с итеративным алгоритмом построения триангуляции Делоне с использованием kD-дерева
Описание итеративного алгоритма
Коротко опишу вышеуказанный алгоритм. При поступлении очередной точки мы с помощью kD-дерева (советую почитать про него где-нибудь, если вы не знаете) находим довольно близкий к ней уже построенный треугольник. Затем обходом в глубину ищем треугольник, в который попадает сама точка. Достраиваем ребра в вершины найденного треугольника и фактически выполняем шаг (4) из нашего алгоритма для новых четырехугольников. Так как точка может быть вне триангуляции, то для упрощения предлагается накрыть все точки большим треугольником (построить его заранее), это решит проблему.
Сходство алгоритмов
Различия алгоритмов
В итеративном алгоритме локализация точки (поиск нужного треугольника) происходит в среднем за 
, на вышеуказанных распределениях в среднем происходит 3 перестроения (как показано в [1]) при условии произвольного порядка подачи точек. Таким образом заметающая прямая выигрывает время у итеративного алгоритма в локализации, но проигрывает его в перестроениях (которые, напомню, довольно тяжелые). Ко всему прочему итеративный алгоритм работает в режиме онлайн, что также является его отличительной особенностью.
Заключение
Здесь я просто покажу некоторые интересные триангуляции, получившиеся в результате работы алгоритма.