Оптимальный план перевозок

Задана карта, на которой показана транспортная сеть, точки расположения складов с товаром и гаражи с транспортом. Алгоритм принимает от пользователя точку положения заказчика и заказ на доставку груза в некотором объеме(количестве). Построить оптимальный путь для автомобиля, который заедет на склад, возьмёт товар и привезёт в точку заказа.

Хотел бы узнать, как называется класс этих задач? Траспортная задача здесь не подойдет, т к в ней нужно единовременно распределить перевозки.

1

а у вас разве не так?
это всё из серии транспортных задач, задач о коммивояжёре.

хотя у вас тут вообще сложности не видно, если, как вы говорите,

Построить оптимальный путь для автомобиля, который заедет на склад, возьмёт товар и привезёт в точку заказа.

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

помоему обычная транспортная задача.

1

полный перебор не пойдет
товар на складах заканчивается и может быть надо заезжать на 2 и более складов

1

ВОзможно свести её к классу "задач о назначениях" на минимум (метод Эгервари).


строим матрицу. i столбец - склады, j - магазины.
Составим матрицу. Коэффициентs будут представлять затраты времени/км от каждого склада, до каждого магазина.

1

Это похоже на транспортную задачу с методом с-з угла.
А как быть, если надо заехать на несколько складов?

1

НУ ищем самые ближайщие склады к этому складу (в который заедет машина) и ищем ближайщие склады до магазина. ПОтом сравниваем и выбираем оптимальный склад (т.е. он должен быть максимально близок и к магазину и к 1 складу одновременно)

Добавлено через 7 минут
хотя если складов придётся объехать много, то мой совет будет мало эффективен.
У меня складывается мнение, что это np-неразрешимая задача. Т.е. оптимального алгоритма нет, возможен лишь полный перебор.

1

Сообщение от darkAngel У меня складывается мнение, что это np-неразрешимая задача. Т.е. оптимального алгоритма нет, возможен лишь полный перебор.

или частичный

1

Мое решение задачи.
-Задан взвешенный неор граф(множеством вершин и множеством ребер), т е транспортная сеть.
-Вес ребра графа = стоимость/километраж проезда по этому ребру(дороге)
-Некоторые вершины помечены как склады с определенным количеством товара. (n)
-Некоторые вершины помечены как гаражи с машинами(машина имеет неограниченную грузоподъемность, т к перевозка за 1 поездку 100 единиц товара равноценна 10 поездкам по 10 ед товара) (m)

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

Общий алгоритм:
1)найти кратчайшие пути до всех гаражей от заказчика.(всего m путей)
2)найти кратчайшие пути от каждого склада до каждого гаража( уже m*n путей)
3)найти кратчайшие пути от текущего склада до другого( всего m*m*n - те, где заказ выполнен)
.... до тех пор, пока все пути не будут с выполненными заказами или текущая стоимость проезда > текущей минимальной.

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

1

2) Находим ближайший склад к найденному гаражу(тоже перебором), едем туда и закружаем минимум из (требуемый товар, товар на складе) 3)Если заказ выполнен, то возвращаемся назад по известному пути Иначе ищем ближайший склад к текущему складу и едем туда...... Ездим по ближайшим складам, пока не выполним заказ.

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

0

darkAngel, ты имеешь в виду такую ситуацию?
(расстояние до ближайшего склада от гаража + расстояние от этого склада до ближайшего) > (расстояние до не самого ближайшего склада от гаража + расстояние от этого склада до ближайшего)

Если так, то такое может быть, на то он и жадный алгоритм, что не дает оптимального решения.

1

да это имею в виду.
Ну коли алгоритм не обязательно должен быть самым оптимальным, а хотя бы близок к оптимуму, то тогда пойдёт

0

Как можно оптимизировать этот частичный перебор?

0