Транспортная логистика. Нужна помощь по определении логики работы системы

MaximuS_G
Дата: 03.10.2011 22:17:20
Всем привет!
Собираюсь реализовать проектное решение в сфере транспортной логистики на базе системы Террасофт.
Система уже выбрана и куплена.
Сейчас нужно писать концепцию использования системы, что бы определить доработки. Проблема в том, что я вообще не разбираюсь в транспортной логистике. Взялся что бы научиться, и для заказчика поэтому стоимость реализации проекта минимальна.
Поэтому обращаюсь к гуру за советом и подсказкой :).

Определил основные задачи системы:
1. Расчет стоимости маршрута из пункта А в пункт Б.
2. Контроль за процессом перевозки.
3. Управленческий учет.

Мне кажется сейчас ключевым моментом является определение алгоритма, по которому система сможет предлагать несколько вариантов доставки из п.А в п.Б. То есть из п.А в п.Б напрямую через авиа, или через дополнительный пункт В машиной в зависимости от заданных критериев сравнения (затраты, сроки).
Поэтому разбиваю ее на подзадачи:
1.1. Определение точек/звеньев, через которые будет транспортироваться товар.
1.2. Определение видов затрат, по каждой из точек.

Вот пока такие мысли по поводу структуры таблиц для точек. Буду думать по алгоритму.
Точка в цепи Откуда Куда Тип транспорта
Киев Харгос Москва Железная дорога
Киев Москва Харгос Железная дорога
Харгос - Москва Авиа

То есть из такой таблицы, система может определить, что доставить в Москву из Харгоса можно через Киев, можно напрямую. Остается посчитать затраты каждой точке. Но вот с затратами по точкам еще не совсем ясна концепция.
Прошу подсказать, двигаюсь ли я в правильном направлении? Что почитать (только не книги, нет времени)? Что поклацать?
Заранее спасибо!
Garya
Дата: 03.10.2011 22:59:06
Транспортная задача - это классическая задача линейного программирования. Если нужно определить оптимальные маршруты, откуда куда и чем везти, то можно поднять и припомнить этот раздел математики. Однако, классическая транспортная задача рассматривает НЕ цепочные маршруты. Если нужно определиться, из каких источников в какие приемники наиболее оптимально осуществить одиночные доставки, то транспортная задача красиво справляется с такой постановкой. Однако, это задача распределения источников по приемникам, она не решает задачу оптимизации маршрута.

Если нужно решить задачу оптимизации комбинирования звеньев цепочки для цепочного маршрута, то в комбинаторике такая задача рассматривается как "задача коммивояжера". Данная задача занимается оптимизацией маршрута, но не решает задачу оптимизации распределения.

Смесь оптимизации распределения и оптимизации маршрутов - задача, в общем-то, не тривиальная. Она имеет высокую вычислительную сложность (множество вложенных друг в друга итераций) и обычно точное решение такой задачи на практике не ищут, а ищут приблизительное. Когда-то давно-дано мне приходилось заниматься решением подобной задачи для автоматизированной диспетчерской, когда необходимо было распределить множество линейных радиомехаников по множеству заказов с одновременной оптимизацией их маршрутов и с учетом, что одни из них передвигаются пешком + общественным транспортом, другие ездят на автомобилях. Применялся модификация алгоритма доктора Дейкстры для решения задачи коммивояжера (использующая метод ветвей и границ), которая была адаптирована еще и для решения задачи распределения. Описывать алгоритм здесь - несколько муторно, да и не уверен я, что Вы будете так глубоко нырять в комбинаторную математику.

Кроме того, есть некоторые сомнения непосредственно в самой постановке задачи. Вот в этой книжке описан пример, как более дорогая транспортировка мелкими партиями самолетом может оказаться более эффективной, нежели существенно более дешевая, но очень медленная транспортировка водным транспортом очень крупных партий. При увеличении расходов на транспорт резко сокращаются расходы на хранение, а кроме этого резко сокращаются сроки исполнения заказов, что делает такую схему работы более привлекательной для клиентов и приводит к увеличению общего объема заказов. В результате сокращаются многие другие переменные расходы. Хотя сумма транспортных расходов при этом может и существенно возрасти, общая сумма расходов на единицу продукции уменьшается. Достигается это многократным увеличением КПД потока создания ценности.

P.S. Я не уверен, что правильно понял вопрос.
MaximuS_G
Дата: 03.10.2011 23:41:13
Garya, спасибо большое что присоединились!
Мне кажется Вы совершенно правильно поняли мой вопрос. Могли бы Вы уточнить что означает распределение источников по приемникам (оптимизация распределения) и оптимизация маршрута?
Garya
Смесь оптимизации распределения и оптимизации маршрутов - задача, в общем-то, не тривиальная.

То-есть насколько я понял, лучше не разрабатывать этот механизм, а предоставить возможность менеджеру самостоятельно сформировать маршрут на основании опыта? И внести в систему все затраты по маршруту вручную?
Как Вы считаете, насколько данный механизм был бы желателен, если бы система планировалась потом продаваться как отраслевой продукт?
Garya
Вот в этой книжке описан пример, как более дорогая транспортировка мелкими партиями...

Очень интересно, но я так понимаю это Вы говорите, если компания пытается оптимизировать своих расходы на доставку товаров. В моей ситуации система будет предназначена для транспортной компании, основная деятельность которой для других осуществлять доставку товаров.

У меня сейчас вопрос в том, от чего отталкиваться при описании логики такой системы. Может быть у Вас какие мысли будут по этому поводу?
Заранее спасибо! Удачи! :)

PS. Как Ваш робот-пылесос? )
George Nordic
Дата: 04.10.2011 10:19:39
MaximuS_G, ой-ей-ей! :) Вы даже не представляете, во что ввязываетесь.

1. Строить задачу не просто учета, а планирования на CRM системе - это безумство.
2. В компании, для которой Вы будете писать решение, есть мультимодальные перевозки?
3. Генеральные партии грузов или сборники? Сколько складов консолидации?
4. Таможенные услуги есть? ВЭД?
5. Как осуществляется оптимизация загрузки транспортных средств?
6. Как рассчитываются тарифы? От чего зависят, как часто корректируются?
7. Есть собственный парк тс?
8. Много контрагентов? По каким критериям происходит выбор поставщика услуг?
9. Как происходит учет затрат? Что делать, если происходит превышение над запланнированными затратами?

Есть у Вас нет ответа хотя бы на один вопрос, и Вы не представляете себе, каким образом должна быть реализована функциональность хотя бы 1 пункта, то я не рекомендовал бы Вам браться за реализацию данной задачи. Есть вероятность писать ее несколько лет. А потом постоянно усовершенствовать, дополнять и переписывать. Впрочем, если хотите пересидеть кризис на клиенте - отличная идея. Будете обеспечены работой на долгие годы. Многие так делают. Для консалтиноговой компании подобный проект смертельно опасен.

С Уважением,
Георгий
IgorK
Дата: 04.10.2011 10:27:59
Насколько я понимаю, для того, чтобы система автоматически выбирала маршрут, тип транспорта и т.п. нужен граф транспортной сети со всеми узловыми точками. И причем отдельно для каждого вида транспорта - чтобы можно было сравнить маршруты по времени/стоимости.
Такой граф, фактически, есть векторная карта в любом формате - на ее основе и строят автоматические прокладчики маршрутов.
Например - http://www.ingit.ru/articles/index.php?id=4
Можно, конечно, самому вести такой граф, но трудоемкость ИМХО велика.
Программист 1с
Дата: 04.10.2011 11:13:31
George Nordic
MaximuS_G, ой-ей-ей! :) Вы даже не представляете, во что ввязываетесь.
+1
George Nordic
Дата: 04.10.2011 11:57:32
IgorK,

Да, Вы все правильно понимаете. Но еще необходимо разделять тактическую и оперативную. Вы говорите про тактическую - для нее я предлагаю ряд продуктов, такие как IBM iLog TM, Oracle Transportation Management или SNO (Strategic Network Optimization) или JDA TM. У кого стоит SAP, то к нему у самого SAP тоже есть модуль ТМ. Для Axapta - решения партнеров (АйТи Бокс). Если говорить про оперативную, которая считает оптимальные маршруты развозки товаров по городу с учетом пробок, порядки выгрузки машины (забивной склад), то на рынке есть CDC, Антор и ряд прочих предложений, в том числе и от отечественных разработчиков. Вполне достойных по качеству, кстати.

С Уважением,
Георгий
Garya
Дата: 04.10.2011 12:03:55
MaximuS_G
Могли бы Вы уточнить что означает распределение источников по приемникам (оптимизация распределения) и оптимизация маршрута?
Транспортная задача решает задачу оптимального распределения источников по приемникам. Имеется N возможных источников груза и M возможных приемников груза. Но при этом каждый маршрут от источника к приемнику является "однозвенным", то есть предполагается, что транспорт движется из одного источника в один приемник и не предполагается использовать идеологию "молоковоза", когда один транспорт должен объехать несколько пунктов по очереди.
Для отдельно взятого "молоковоза", если перечень пунктов, которые он должен объехать, уже за ним закреплен (то есть, если задача распределения пунктов по транспортам уже решена каким-либо способом) задача построения оптимальной последовательности объезда этих пунктов решается с помощью задачи коммивояжера.

Однако, задача оптимизации распределения пунктов по транспорту (в моем случае это были адреса заказчиков, которые нужно было распределить по линейным радиомеханикам) одновременно с задачей оптимизации маршрута отдельного транспорта (в моем случае оптимизации маршрута движания каждого отдельно взятого радиомеханика) при построении последовательности прохождения нескольких пунктов - такая задача "классического" решения не имеет, по крайней мере, я, когда его искал, мне его найти не удалось.

Мне пришлось изучить примерно дюжину методов решения задачи коммивояжера при нахождении решения, близкого к оптимальному. Я решал одновременно несколько оптимизационных задач одновременно, и если бы они решались методом "тупого перебора вариантов", время их решения. заняло бы несколько суток. А решение, может быть принят заказ на данный час в данном районе и если может, то за каким конкретно радиомехаником его нужно закрепить, нужно было принимать буквально "на лету" (пока клиент висит на телефоне). При этом нужно было попутно соблюсти совокупность специфических ограничений. В частности, если это повторный заказ, то он должен быть жестко закреплен за тем же радиомехаником, который его обслуживал в прошлый раз. И еще, по возможности каждый радиомеханик должен обслуживать примерно свой район города, чтобы в случае повторных заказов или не-повторных заказов, но от одних и тех же клиентов на них по возможности выходил один и тот же специалист, который уже знаком с проблемами конкретного аппарата. При этом, однако, если в двух соседних районах сложилась такая ситуация, что в одном районе заказов очень мало, а в другом их перебор, нужно привлечь радиомеханика соседнего района на обслуживание заказов соседнего района ближе к границе со своим районом.

У Дейкстры я нашел специфический алгоритм незамкнутого решения задачи коммивояжера, который в своей работе помимо использования метода ветвей и границ разделял точки, которые необходимо объехать/обойти на "окончательно включенные" в конкретный граф, "временно включенные" и "пока еще не включенные". Именно эта особенность и позволила решать весь комплекс оптимизационных задач одновременно. Для того, чтобы привязать траекторию движения конкретного радиомеханика к конкретному району города, я изначально включал точку в центре района, закрепленного за радиомеханиками, в граф каждого радиомеханика в качестве "виртуальной исходной точки" и "виртуальной конечной точки" для каждой полосы времени длительностью в 2 часа в середине рабочего дня. Для полосы времени в начале рабочего дня в качестве "исходной точки" (не виртуальной) обозначалась сама диспетчерская, в которой линейные радиомеханики каждое утро получали наряды, а в качестве "виртуальной конечной точки" - центр района каждого радиомеханика. Для последних 2 часов "виртуальной исходной точкой" обозначался центр района, а конечной точкой (не виртуальной) - место проживания радиомеханика. Таким образом, на протяжении рабочего дня заказы распределялись таким образом, что радиомеханики обслуживали их по утрам "по дороге из диспетчерской в свой район", к концу рабочего дня "по дороге из своего района домой", а в середине рабочего дня перемещаясь "вокруг центра своего района".

Далее в граф каждого радиомеханика включаются точки, требующие обязательного присутсвия на данном заказе данного радиомеханика (например, связанные с повторным ремонтом бытовой радиоаппаратуры), которые помечались как "окончательно включенные в граф". Далее каждый из пока еще не включенных заказов пытался включиться по очереди в ребра всех уже имеющихся графов таким образом, чтобы среднее время на перемещение всех радиомехаников было наименьшим (с учетом средней скорости перемещения разных радиомехаников, часть из которых перемещалась на автомобилях, а часть передвигались пешком). При этом должно было не нарушиться граничное условие - с запланированного времени на ремонт время движения по всему графу не должно превысить двух часов (ширины временной полосы, в которой работает оптимизационный алгоритм). Включение точки в ребро графа происходит очень просто - направленный отрезок от точки A к точке B разрывается и между ними включается точка C, после чего оценивается среднее время по всем графам. Для поиска локального оптимума каждая точка по очереди ключаяется во все ребра всех графов. После того как определен граф и ребро графа, включение в который конкретной точки наиболее оптимально, точка закрепляется за этим графом (она остается "временно включенной" в данный граф). Далее происходит включение следующей пока еще не включенной точки в ребра графов - опять же исходя из этих же оптимизационных критериев и ограничений на время движения по каждому графу не более 2 часов. Каждая включенная точка получает статус "временно включенной". Если включение какой-либо в какой-либо граф наиболее оптимально с точки зрения минимизации среднего времени перемещения по графам, но приводит к нарушению граничного условия (по двум часам перемещения по данному графу), то такая точка временно фиксируется в данном графе, а все ранее "временно включенные" точки по очереди исключаются из него до тех пор, пока не будет выявлена точка, которую наиболее оптимально исключить из данного графа, чтобы не нарушились граничные условия. В итоге исключена из данного графа может быть как текущая точка, так и та, которая ранее в него была включена.

Если после пробегания исключаемой точкой по всему набору графов выясняется, что такая точка не может быть включена ни в один из графов без нарушения граничных условий, алгоритм генерит ошибку, которая сигнализирует о факте "переполнения" данной временной полосы. Диспетчер, который в этот момент пытался включить некий заказ в эту полосу (шириной в 2 часа), получив сообщение об ошибке, сообщал клиенту, что на данный диапазон времени все диспетчеры заняты и предлагал выбрать другой.

После отработки оптимизационного алгоритма из маршрутов исключались начальные и конечные "виртуальные точки". Оценка граничных условий происходила, разумеется, без отрезков, концами которых являлись "виртуальные точки".

Ну вот, описал алгоритм во всех подробностях. Может быть, кому-нибудь пригодится... :) К слову сказать, для его корректной работы пришлось получать допуск у КГБ-шников к детальной карте города Таллинна (22 листа формата А0) и вколачивать эту карту в базу данных. :) Сейчас подобные задачи решают GPS-навигаторы на полном автомате, причем учитывают дорожные знаки.

MaximuS_G
То-есть насколько я понял, лучше не разрабатывать этот механизм, а предоставить возможность менеджеру самостоятельно сформировать маршрут на основании опыта? И внести в систему все затраты по маршруту вручную?
Затрудняюсь ответить. Не знаю, что лучше, каждый решает сам. Тут, видимо, нужно смотреть, какой опыт у этих самых менеджеров. Если я еду по незнакомой местности, то, скорее всего, GPS-навигатор предложит более оптимальный маршрут, нежели я высосу из пальца. А вот ежели я уже хорошо знаю дорогу, все нюансы и нюансики, то GPS-навигатор очень часто выдает менее оптимальное решение. Ему, например, может быть невдомек, что поворот налево на нерегулируемом перекрестке с плотным движением может сильно задержать из-за того, что нужно пропускать транспорт в обе стороны и лучше проехать чуть более длинным путем, но без подобных задержек.

MaximuS_G
PS. Как Ваш робот-пылесос? )
Фурычит, куда ж он денется... :)
George Nordic
Дата: 04.10.2011 14:16:39
Garya
Ну вот, описал алгоритм во всех подробностях. Может быть, кому-нибудь пригодится... :)
Да, Спасибо большое - с большой буквы. Действительно, изящное решение, немного только его перестроить, с учетом дополнительных факторов в соответствии с требованиями заказчика. Вот что значит старая школа ;-)

С Уважением,
Георгий
s_ustinov
Дата: 04.10.2011 14:25:25
MaximuS_G
Собираюсь реализовать проектное решение в сфере транспортной логистики на базе системы Террасофт.

Сейчас нужно писать концепцию использования системы, что бы определить доработки. Проблема в том, что я вообще не разбираюсь в транспортной логистике. Взялся что бы научиться, и для заказчика поэтому стоимость реализации проекта минимальна.

Самый неоднозначный момент )))))))
MaximuS_G
Определил основные задачи системы:
1. Расчет стоимости маршрута из пункта А в пункт Б.
2. Контроль за процессом перевозки.
3. Управленческий учет.

Мне кажется сейчас ключевым моментом является определение алгоритма, по которому система сможет предлагать несколько вариантов доставки из п.А в п.Б. То есть из п.А в п.Б напрямую через авиа, или через дополнительный пункт В машиной в зависимости от заданных критериев сравнения (затраты, сроки).
........
Но вот с затратами по точкам еще не совсем ясна концепция.
Прошу подсказать, двигаюсь ли я в правильном направлении? Что почитать (только не книги, нет времени)? Что поклацать?
Заранее спасибо!

Мне кажется, вы ушли совсем не туда...
для начала вам надо "писать концепцию использования системы", а не пытаться решать задачи оптимизации. Возможно, в результате выяснится, что алгоритмы оптимизации и не нужны ))))

и еще одно замечание - а что вы подразумеваете под управленческим учетом?