транспортная задача

[svirma]

Подскажите, пожалуйста, в каком направлении нужно "копать", чтобы решить данную задачу?
( как тут записать задачу линейного программирования?)
просто, как я понимаю, тут не совсем чистая транспортная задача

1) на складе 215 коробок;
2) имеется 5 магазинов, потребность в доставке в каждом магазине своя (задана 55,40,30,50,15,25)
и в сумме равна 215;
3) имеется грузовичек с максимальной вместимостью 96 коробок;
4) известны все расстояния между магазинами, магазинами и складом;


(Расстояния до: [ склада; 1; 2; 3; 4; 5; 6 магазины])

склад [ 0; 10,5; 17,9; 9,2; 21,6; 15,5; 7,3.]

--------------------------------------------------------------------------------
1 магазин [10,5; 0; 14,5; 10,0; 21,9; 16,7; 3,9.]

--------------------------------------------------------------------------------
2 магазин [17,9; 14,5; 0; 23,3; 8,8; 7,3; 16,8.]

--------------------------------------------------------------------------------
3 магазин [9,2; 10,0; 23,3; 0; 29,1; 23,1; 6,5.]

--------------------------------------------------------------------------------
4 магазин [21,6; 21,9; 8,8; 29,1; 0; 6,2; 23,2.]

--------------------------------------------------------------------------------
5 магазин [15,5; 16,7; 7,3; 23,1; 6,2; 0; 17,5.]

--------------------------------------------------------------------------------
6 магазин [7,3; 3,9; 16,8; 6,5; 23,2; 17,5; 0.]





определить маршрут с минимизацией суммарного пробега.

[_Ivana]

Я бы сначала написал программку и решил прямым перебором с ограничением по вместимости грузовика.
ЗЫ в реальной жизни подобная идеальная логистика разбивается в прах регулярностью структуры пробок и загруженности транспортных потоков в зависимости от времени суток.

[svirma]

ну,просто перебором это понятно..
может все-таки имеются какие-то более оптимальные методы..

[_Ivana]

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

[Sender]

А в магазинах можно организовывать временные склады?

[svirma]

нет.

[sup]

Это разновидность задачи коммивояжера. Можно гуглить Capacitated Vehicle Routing Problem.
Есть спец. сайты
http://neo.lcc.uma.es/radi-aeb/WebVRP (старый)
http://neo.lcc.uma.es/vrp
Общая формулировка Вашей задачи как задачи ЛП требует экспоненциального количества ограничений (для обеспечения корректности маршрута). Такая постановка уже давно была организована. Для малых размеров (как у Вас) можно найти и точное решение.
Вот например обзор, в котором есть ссылка на Кристофидеса и Ко.

The Vehicle Routing Problem: An overview
of exact and approximate algorithms
Gilbert Laporte

Но для такого "сверхмалого" размера как у Вас, наверное проще всего полный перебор.

[Sender]

Кое-где она называется One-Commodity Pickup and Delivery Problem (1-PDP), например, здесь.

[svirma]

Спасибо большое, разобрался..

[_Ivana]

Мои знакомые работают в фирме, которая, помимо всего прочего, занимается транспортной логистикой и развозит товар по сети розничных точек. Так они выбирали между двумя вариантами - либо заказ каждому магазину запечатывается в одну палету и за недостачу отвечает кладовщик (который аккуратный и ответственный), либо все грузится валом и за недостачу отвечает экспедитор (которых много и не такие ответственные). К чему это я? В рамках этих вариантов следующий частный случай сабжевой задачи будет иметь разные решения: есть 3 магазина, между ними по 1 км, каждому надо по 10 коробок, склад за 10 км, вместимость газели 16 коробок (4*2*2 :) ).