Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.80/5: Рейтинг темы: голосов - 5, средняя оценка - 4.80
4 / 4 / 2
Регистрация: 28.05.2009
Сообщений: 29
1

Коммивояжёр - или оптимизация пути.

14.07.2009, 17:03. Просмотров 1037. Ответов 8
Метки нет (Все метки)

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

К примеру у нас n машин и m заказов.

машина1
координаты машины Xi1j1
машина2
координаты машины Xi2j2
...


клиент 1
координаты подбора клиента Pi1j1 (pick)
координаты высадки клиента Di1j1 (drop)
Время подбора клиента T1

клиент 2
координаты подбора клиента Pi2j2 (pick)
координаты высадки клиента Di2j2 (drop)
Время подбора клиента T2

клиент 3

координаты подбора клиента Pi3j3 (pick)
координаты высадки клиента Di3j3 (drop)
Время подбора клиента T3

...


Варианты подбора по пути клиентов также учитывается, если он находиться в области выгодного подбора и дальнейшей высадки (т.е. небольшое отклонение от курса).

При появлении нового клиента, пересмотр уже готовых маршрутов.

Может стоить использовать Алгоритм флойда ?
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
14.07.2009, 17:03
Ответы с готовыми решениями:

Оптимизация. Что быстрее работает: cout или printf
Что быстрее работает: cout или printf ????????? Добавлено через 32 минуты ЕЩе вот что: Как...

Коммивояжёр, метод поиска в глубину
Всем привет. Собственно, тема говорит сама за себя. И ведь задачка-то не самая сложная, но что-то...

Типы оптимизация: черная оптимизация, серая оптимизация и белая оптимизация
Много много лет назад, на заре становления профессии "оптимизатора" в какой то умной книжке был...

Оптимизация или контекстная
Доброй ночи! Я, дилетант в этом деле и рассматриваю различные способы получения прибыли с сайта...

8
эволюционирую потихоньку
468 / 466 / 91
Регистрация: 30.06.2009
Сообщений: 1,401
14.07.2009, 17:20 2
какая скорость движения машин и начальные координаты? сколько клиентов можно по пути подобрать? в общем таксуют у нас нынше на чём? Ока или Лиазы
0
4 / 4 / 2
Регистрация: 28.05.2009
Сообщений: 29
14.07.2009, 17:23  [ТС] 3
скорость движения машин и начальные координаты
Пускай скорость v = 1 начальные координаты (0,0)


сколько клиентов можно по пути подобрать?
3
0
эволюционирую потихоньку
468 / 466 / 91
Регистрация: 30.06.2009
Сообщений: 1,401
14.07.2009, 18:04 4
(0,0) для всех машин? и время в пути для клиента должно быть минимально? и совсем забыл как у нас двигаются машины? то есть перемещение из точки (1,1) в точку (3,1) происходит за 3 единицы времени или square(4+1)

Добавлено через 13 минут 41 секунду
пардон, перемещение (1,1) в (3,2). в общем движение по рёбрам треугольника или по его диагонали

и ещё клиентов можно раньше подбирать или машина должна простаивать?
0
4 / 4 / 2
Регистрация: 28.05.2009
Сообщений: 29
15.07.2009, 11:08  [ТС] 5
(0,0) для всех машин?
Вначале Да!

время в пути для клиента должно быть минимально?
Желательно, но Варианты подбора по пути клиентов немного может время увеличить

перемещение (1,1) в (3,2)
L = sqrt((1-3)^2 - (1-2)^2)) - его диагональ

Добавлено через 23 минуты 37 секунд
клиентов можно раньше подбирать или машина должна простаивать?
Желательно нагружать равномерно, но учитывая и расстояние (цену пути).
0
эволюционирую потихоньку
468 / 466 / 91
Регистрация: 30.06.2009
Сообщений: 1,401
15.07.2009, 12:13 6
клиентов можно раньше подбирать или машина должна простаивать?
Желательно нагружать равномерно, но учитывая и расстояние (цену пути).
я не совсем об этом спрашивал, насколько важно и зачем в условии присутствует "Время подбора клиента T3"? что означает этот параметр?

задача мне кажется интересной, но пока алгоритм как-то не складывается, именно из-за не поняток со временем. если клиентов надо подбирать в определённое время, то тут несколько меняется расстановка приоритетов.
0
4 / 4 / 2
Регистрация: 28.05.2009
Сообщений: 29
15.07.2009, 12:21  [ТС] 7
зачем в условии присутствует "Время подбора клиента T3"?
Это когда я заказываю поездку на определенное время.

Т.е. нужно учитывать не только расстояние от высадки клиента к следующему, но и время во сколько забрать клиента.
0
эволюционирую потихоньку
468 / 466 / 91
Регистрация: 30.06.2009
Сообщений: 1,401
15.07.2009, 17:35 8
В общем, фиксирую как я понял.
Начальные координаты машин (0,0). движение до клиента по прямой, соединяющей координаты подбора клиента Pi1j1 и координаты высадки клиента Di1j1, со скоростью 1.
Клиентов у которых есть параметр - Время подбора клиента T1 нужно подбирать в строго оговоренное время, ни раньше ни позже. Клиентов у которых этот параметр отсутсвует можно подбирать когда угодно.
Максимальная загрузка машины - 3 клиента. Время в пути не оговаривается, то есть можно возить довольно долго (хотя тут можно ввести ограничитель скажем не больше чем длительность поездки на 1,5 длины пути от Pi1j1 до Di1j1, так же надо продумать ограничение на "небольшие" отклонения от маршрута для подбора второго клиента)
Оптимальность проложения маршрутов как самособой разумеется.

Правильно понял?

P.S. Я это для чего пишу. Чётко сформулированная задача - это уже половина решения. А в код перевести это и кодер сможет.
0
эволюционирую потихоньку
468 / 466 / 91
Регистрация: 30.06.2009
Сообщений: 1,401
16.07.2009, 21:14 9
черновой вариант. данные берёт из файла clients.txt, данные ввиде : time x_begin y_begin x_end y_end
0
Вложения
Тип файла: txt Taxi.txt (3.9 Кб, 39 просмотров)
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
16.07.2009, 21:14

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

Оптимизация запросов или их количества
Ситуация такая : Есть таблицы refers и games Есть сайт с лотерей типа угадай число и результат ...

Оптимизация или контекстная реклама?
Здравствуйте, дорогие специалисты! У нас сайт марки женской одежды и белья нестандартных размеров....

Оптимизация JEditorPane или что-то другое
Заметил, что JEditorPane не справляется с большим объемом текста. Если в нем много текста начинает...

Оптимизация ОЗУ - польза или вред?
Всем привет! Вчера столкнулся с такой ситуацией. Пришлось обрабатывать большое количество...


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

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

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