Задача по транспортной логистике

[квит]

Приглашаю интеллектуалов размять мозги

Как бы вы решали задачу? - можно накидывать мысли, полу- и четверть мысли, намётки, намёки и размышления на тему

Транспортная компания развозит грузы (в пределах города и окрестностей)
Имеется транспортный парк - N машин
Каждый день имеется M заказов
Каждый заказ характеризуется адресом (его можно перевести в координаты - х,у - долгота/широта), временной рамкой (от и до - время, в которое заказ должен быть доставлен заказчику), и массой груза (как вариант - объем груза)
Имеется склад, откуда каждое ТС должно начинать маршрут и там же его заканчивать

Задача - сформировать маршруты доставки грузов

Критерии
1. Минимальный суммарный путь по всем транспортным средствам
2. Минимальное кол-во ТС (как сформулировал заказчик - минимумом машин вывезти максимум грузов)

Ограничения
1. каждый заказ должен попасть в свою временную рамку
2. планируемая загрузка каждого ТС не должна превышать его фактическую грузоподъемность

там есть еще всякого рода мелкие нюансы, но в базовом варианте будем считать такую постановку задачи

[квит]

простейший вариант - задача коммивояжера - одно ТС, без учета временных рамок и грузоподъемности

для нее известны алгоритмы, находящие решение с приемлемой скоростью

http://ru.wikipedia.org/wiki/%D0%97%...91%D1%80%D0%B0

Задача коммивояжёра (англ. Travelling salesman problem, сокращённо TSP) — одна из самых известных задач комбинаторной оптимизации, заключающаяся в отыскании самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город. В условиях задачи указываются критерий выгодности маршрута (кратчайший, самый дешёвый, совокупный критерий и тому подобное) и соответствующие матрицы расстояний, стоимости и тому подобного. Как правило, указывается, что маршрут должен проходить через каждый город только один раз — в таком случае выбор осуществляется среди гамильтоновых циклов.

методы полного перебора вариантов не работают

Оптимизационная постановка задачи относится к классу NP-трудных задач, впрочем как и большинство её частных случаев. Версия «decision problem» (то есть такая, в которой ставится вопрос существует ли маршрут не длиннее, чем заданное значение k) относится к классу NP-полных задач. Задача коммивояжёра относится к числу трансвычислительных: уже при относительно небольшом числе городов (66 и более) она не может быть решена методом перебора вариантов никакими теоретически мыслимыми компьютерами за время, меньшее нескольких миллиардов лет.

[Samirat]

ну... наверное зависит от охвата территории и точек выгрузки (доставки) в сегментах этой территории.

вариант использования субподрядчиков на доставке исключен?

[квит]

Сообщение от Samirat

ну... наверное зависит от охвата территории и точек выгрузки (доставки) в сегментах этой территории.

компания имеет представительства/филиалы в нескольких городах, разных по размеру - поэтому нужен общий алгоритм

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

например, может быть 2 заказа в одном поселке, потом пилить 10 км в другой поселок еще с двумя заказами, а между ними окно в 1,5 часа)

вариант использования субподрядчиков на доставке исключен?

субподряд используют, да

но еще есть свой парк машин, загрузку которого хотят оптимизировать

[Samirat]

Сообщение от квит

компания имеет представительства/филиалы в нескольких городах, разных по размеру - поэтому нужен общий алгоритм

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

например, может быть 2 заказа в одном поселке, потом пилить 10 км в другой поселок еще с двумя заказами, а между ними окно в 1,5 часа)

Такой вопрос: компания чисто транспортирует или полный цикл, включая хранение товара?
и еще: филиалы - чисто офис и площадка для автопарка?

субподряд используют, да

но еще есть свой парк машин, загрузку которого хотят оптимизировать

загрузку а/м или расходы на доставку?

[квит]

Сообщение от Samirat

Такой вопрос: компания чисто транспортирует или полный цикл, включая хранение товара?
и еще: филиалы - чисто офис и площадка для автопарка?

где как - есть и только транспортировка, есть и хранение

по филиалам - такой же ответ, есть чисто офис (в небольших городах), есть офис+склад, есть даже (для родственной организации) офис+склад+производство

загрузку а/м или расходы на доставку?

и то, и то

Критерии
1. Минимальный суммарный путь по всем транспортным средствам
2. Минимальное кол-во ТС (как сформулировал заказчик - минимумом машин вывезти максимум грузов)

1 - расходы на доставку
2 - загрузка

[Afa]

построй маршруты. для начала все. сортируй по длине. выкидывай пересекающиеся точки. дальше просто выборка. слегка оптимальная.
проще говоря, обменяй память на время.

[квит]

Сообщение от Afa

построй маршруты. для начала все.

все возможные? невозможно. (проклятие размерности)

[квит]

http://ru.wikipedia.org/wiki/%D0%9F%...81%D1%82%D0%B8

Проклятие размерности (ПР) — термин, используемый в отношении ряда свойств многомерных пространств и комбинаторных задач. В первую очередь это касается экспоненциального роста необходимых экспериментальных данных в зависимости от размерности пространства при решении задач вероятностно-статистического распознавания образов, машинного обучения, классификации и дискриминантного анализа. Также это касается экспоненциального роста числа вариантов в комбинаторных задачах в зависимости от размера исходных данных, что приводит к соответствующему росту сложности переборных алгоритмов. «Проклятие» действует и на непрерывные оптимизационные методы в силу усложнения многомерной целевой функции. В более широком смысле термин применяется по отношению ко всем «неудобным» или необычным свойствам многомерных пространств и к трудностям их исследования. В комбинаторике чаще имеют в виду не размерность пространства, а размер исходных данных. В частности, в задачах теории Рамсея было бы точнее говорить о ’’’проклятии размера’’’ исходных данных даже в случае задач минимальной размерности — числа параметров, определяющих задачу. Впервые термин ввел Ричард Беллман применительно к общей задаче динамического программирования[1][2]. Это выражение продолжает употребляется в работах по технической кибернетике, машинному обучению и анализу сложных систем, в том числе, в заголовках[3].

в этой задаче даже не экспоненциальный, а факториальный рост

[Afa]

Сообщение от квит

все возможные? невозможно. (проклятие размерности)

та фиг. длиннее дневного маршрута уже не надо.
отсекай лишние веточки. как дипблю каспарова чихвостил - вот так жеж