Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.67/18: Рейтинг темы: голосов - 18, средняя оценка - 4.67
m_feel
5 / 5 / 0
Регистрация: 12.12.2009
Сообщений: 6
#1

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

12.12.2009, 22:44. Просмотров 3182. Ответов 11
Метки нет (Все метки)

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

Хотел бы узнать, как называется класс этих задач? Траспортная задача здесь не подойдет, т к в ней нужно единовременно распределить перевозки.
1
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.12.2009, 22:44
Ответы с готовыми решениями:

Оптимальный алгоритм сортировки
Камрады! Есть функция/процедура f(m,n), которая получает 2 номера и...

Перебор цифр и оптимальный алгоритм
Всем, добрый день. Есть набор цифр от 1 до 5. В числе может быть от 1 до 15...

Оптимальный поиск элемента в массиве
Столкнулся с проблемой поиска оптимального алгоритма нахождения индекса нужного...

Оптимальный язык Web-программирования
Профессионалы в Web-программировании, Выскажите свое мнение по поводу выбора...

Оптимальный алгоритм распределения образа на N машин
Задача. Надо доставить образ VM на N(20) машин по сети. Хотелось бы придумать...

11
TanT
эволюционирую потихоньку
467 / 465 / 91
Регистрация: 30.06.2009
Сообщений: 1,399
13.12.2009, 06:52 #2
а у вас разве не так?
это всё из серии транспортных задач, задач о коммивояжёре.

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

помоему обычная транспортная задача.
1
m_feel
5 / 5 / 0
Регистрация: 12.12.2009
Сообщений: 6
13.12.2009, 13:43  [ТС] #3
полный перебор не пойдет
товар на складах заканчивается и может быть надо заезжать на 2 и более складов
1
darkAngel
Технофашист
218 / 201 / 11
Регистрация: 11.03.2009
Сообщений: 883
13.12.2009, 16:47 #4
ВОзможно свести её к классу "задач о назначениях" на минимум (метод Эгервари).


строим матрицу. i столбец - склады, j - магазины.
Составим матрицу. Коэффициентs будут представлять затраты времени/км от каждого склада, до каждого магазина.
1
m_feel
5 / 5 / 0
Регистрация: 12.12.2009
Сообщений: 6
14.12.2009, 12:59  [ТС] #5
Это похоже на транспортную задачу с методом с-з угла.
А как быть, если надо заехать на несколько складов?
1
darkAngel
Технофашист
218 / 201 / 11
Регистрация: 11.03.2009
Сообщений: 883
14.12.2009, 14:19 #6
НУ ищем самые ближайщие склады к этому складу (в который заедет машина) и ищем ближайщие склады до магазина. ПОтом сравниваем и выбираем оптимальный склад (т.е. он должен быть максимально близок и к магазину и к 1 складу одновременно)

Добавлено через 7 минут
хотя если складов придётся объехать много, то мой совет будет мало эффективен.
У меня складывается мнение, что это np-неразрешимая задача. Т.е. оптимального алгоритма нет, возможен лишь полный перебор.
1
TanT
эволюционирую потихоньку
467 / 465 / 91
Регистрация: 30.06.2009
Сообщений: 1,399
14.12.2009, 19:54 #7
Цитата Сообщение от darkAngel Посмотреть сообщение
У меня складывается мнение, что это np-неразрешимая задача. Т.е. оптимального алгоритма нет, возможен лишь полный перебор.
или частичный
1
m_feel
5 / 5 / 0
Регистрация: 12.12.2009
Сообщений: 6
14.12.2009, 19:58  [ТС] #8
Мое решение задачи.
-Задан взвешенный неор граф(множеством вершин и множеством ребер), т е транспортная сеть.
-Вес ребра графа = стоимость/километраж проезда по этому ребру(дороге)
-Некоторые вершины помечены как склады с определенным количеством товара. (n)
-Некоторые вершины помечены как гаражи с машинами(машина имеет неограниченную грузоподъемность, т к перевозка за 1 поездку 100 единиц товара равноценна 10 поездкам по 10 ед товара) (m)

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

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

Вопросы:
1)можно ли в п1, 2 жадного решения обойтись без перебора?
2)Существует ли более оптимальный метод поиска точного решения?
1
darkAngel
Технофашист
218 / 201 / 11
Регистрация: 11.03.2009
Сообщений: 883
14.12.2009, 20:59 #9
2) Находим ближайший склад к найденному гаражу(тоже перебором), едем туда и закружаем минимум из (требуемый товар, товар на складе)
3)Если заказ выполнен, то возвращаемся назад по известному пути
Иначе ищем ближайший склад к текущему складу и едем туда......
Ездим по ближайшим складам, пока не выполним заказ.
возможна такая ситуация, что ближайщий склад к этому складу будет далеко, и выгодней поехать к дальнемоу сперва складу, рядом с которым будет ещё один склад.
0
m_feel
5 / 5 / 0
Регистрация: 12.12.2009
Сообщений: 6
14.12.2009, 22:02  [ТС] #10
darkAngel, ты имеешь в виду такую ситуацию?
(расстояние до ближайшего склада от гаража + расстояние от этого склада до ближайшего) > (расстояние до не самого ближайшего склада от гаража + расстояние от этого склада до ближайшего)

Если так, то такое может быть, на то он и жадный алгоритм, что не дает оптимального решения.
1
darkAngel
Технофашист
218 / 201 / 11
Регистрация: 11.03.2009
Сообщений: 883
15.12.2009, 01:19 #11
да это имею в виду.
Ну коли алгоритм не обязательно должен быть самым оптимальным, а хотя бы близок к оптимуму, то тогда пойдёт
0
m_feel
5 / 5 / 0
Регистрация: 12.12.2009
Сообщений: 6
15.12.2009, 10:26  [ТС] #12
Как можно оптимизировать этот частичный перебор?
0
15.12.2009, 10:26
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
15.12.2009, 10:26

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

Оптимальный алгоритм поиска на графике ⋂-образных областей
Подскажите, пожалуйста, оптимальный алгоритм поиска на графике ⋂-образных...

Найти методом потенциалов оптимальный путь от пункта 1 к пункту 9
Найти методом потенциалов оптимальный путь от пункта 1 к пункту 9(помогите...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
12
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru