11.05.2014, 21:43 | #1 |
Администратор
Регистрация: 18.02.2010
Сообщений: 17,004
|
Задача по транспортной логистике
Приглашаю интеллектуалов размять мозги
Как бы вы решали задачу? - можно накидывать мысли, полу- и четверть мысли, намётки, намёки и размышления на тему Транспортная компания развозит грузы (в пределах города и окрестностей) Имеется транспортный парк - N машин Каждый день имеется M заказов Каждый заказ характеризуется адресом (его можно перевести в координаты - х,у - долгота/широта), временной рамкой (от и до - время, в которое заказ должен быть доставлен заказчику), и массой груза (как вариант - объем груза) Имеется склад, откуда каждое ТС должно начинать маршрут и там же его заканчивать Задача - сформировать маршруты доставки грузов Критерии 1. Минимальный суммарный путь по всем транспортным средствам 2. Минимальное кол-во ТС (как сформулировал заказчик - минимумом машин вывезти максимум грузов) Ограничения 1. каждый заказ должен попасть в свою временную рамку 2. планируемая загрузка каждого ТС не должна превышать его фактическую грузоподъемность там есть еще всякого рода мелкие нюансы, но в базовом варианте будем считать такую постановку задачи
__________________
Да здравствует то благодаря чему мы несмотря ни на что!!! Последний раз редактировалось квит; 11.05.2014 в 21:53. |
11.05.2014, 21:52 | #2 | ||
Администратор
Регистрация: 18.02.2010
Сообщений: 17,004
|
простейший вариант - задача коммивояжера - одно ТС, без учета временных рамок и грузоподъемности
для нее известны алгоритмы, находящие решение с приемлемой скоростью http://ru.wikipedia.org/wiki/%D0%97%...91%D1%80%D0%B0 Цитата:
Цитата:
__________________
Да здравствует то благодаря чему мы несмотря ни на что!!! |
||
11.05.2014, 21:54 | #3 |
Старожил
Регистрация: 01.05.2006
Сообщений: 15,108
|
ну... наверное зависит от охвата территории и точек выгрузки (доставки) в сегментах этой территории.
вариант использования субподрядчиков на доставке исключен? |
11.05.2014, 22:04 | #4 | ||
Администратор
Регистрация: 18.02.2010
Сообщений: 17,004
|
Цитата:
(хотя конечно, размер нас. пункта будет иметь значение - в большом городе высокая плотность заказов - в пригородах меньше например, может быть 2 заказа в одном поселке, потом пилить 10 км в другой поселок еще с двумя заказами, а между ними окно в 1,5 часа) Цитата:
но еще есть свой парк машин, загрузку которого хотят оптимизировать
__________________
Да здравствует то благодаря чему мы несмотря ни на что!!! |
||
11.05.2014, 22:10 | #5 | ||
Старожил
Регистрация: 01.05.2006
Сообщений: 15,108
|
Цитата:
и еще: филиалы - чисто офис и площадка для автопарка? Цитата:
|
||
11.05.2014, 22:15 | #6 | |||
Администратор
Регистрация: 18.02.2010
Сообщений: 17,004
|
Цитата:
по филиалам - такой же ответ, есть чисто офис (в небольших городах), есть офис+склад, есть даже (для родственной организации) офис+склад+производство Цитата:
Цитата:
2 - загрузка
__________________
Да здравствует то благодаря чему мы несмотря ни на что!!! |
|||
11.05.2014, 22:55 | #7 |
Шволочь. И провокатор.
Регистрация: 12.02.2006
Сообщений: 31,206
|
построй маршруты. для начала все. сортируй по длине. выкидывай пересекающиеся точки. дальше просто выборка. слегка оптимальная.
проще говоря, обменяй память на время.
__________________
... Survivors will be shot again. |
11.05.2014, 22:58 | #8 |
Администратор
Регистрация: 18.02.2010
Сообщений: 17,004
|
все возможные? невозможно. (проклятие размерности)
__________________
Да здравствует то благодаря чему мы несмотря ни на что!!! |
11.05.2014, 23:00 | #9 | |
Администратор
Регистрация: 18.02.2010
Сообщений: 17,004
|
http://ru.wikipedia.org/wiki/%D0%9F%...81%D1%82%D0%B8
Цитата:
__________________
Да здравствует то благодаря чему мы несмотря ни на что!!! |
|
11.05.2014, 23:05 | #10 |
Шволочь. И провокатор.
Регистрация: 12.02.2006
Сообщений: 31,206
|
та фиг. длиннее дневного маршрута уже не надо.
отсекай лишние веточки. как дипблю каспарова чихвостил - вот так жеж
__________________
... Survivors will be shot again. |