Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Only_HED
4 / 4 / 0
Регистрация: 28.05.2009
Сообщений: 29
#1

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

14.07.2009, 17:03. Просмотров 892. Ответов 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

...


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

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

Может стоить использовать Алгоритм флойда ?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
TanT
эволюционирую потихоньку
 Аватар для TanT
464 / 462 / 43
Регистрация: 30.06.2009
Сообщений: 1,399
14.07.2009, 17:20     Коммивояжёр - или оптимизация пути. #2
какая скорость движения машин и начальные координаты? сколько клиентов можно по пути подобрать? в общем таксуют у нас нынше на чём? Ока или Лиазы
Only_HED
4 / 4 / 0
Регистрация: 28.05.2009
Сообщений: 29
14.07.2009, 17:23  [ТС]     Коммивояжёр - или оптимизация пути. #3
скорость движения машин и начальные координаты
Пускай скорость v = 1 начальные координаты (0,0)


сколько клиентов можно по пути подобрать?
3
TanT
эволюционирую потихоньку
 Аватар для TanT
464 / 462 / 43
Регистрация: 30.06.2009
Сообщений: 1,399
14.07.2009, 18:04     Коммивояжёр - или оптимизация пути. #4
(0,0) для всех машин? и время в пути для клиента должно быть минимально? и совсем забыл как у нас двигаются машины? то есть перемещение из точки (1,1) в точку (3,1) происходит за 3 единицы времени или square(4+1)

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

и ещё клиентов можно раньше подбирать или машина должна простаивать?
Only_HED
4 / 4 / 0
Регистрация: 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 секунд
клиентов можно раньше подбирать или машина должна простаивать?
Желательно нагружать равномерно, но учитывая и расстояние (цену пути).
TanT
эволюционирую потихоньку
 Аватар для TanT
464 / 462 / 43
Регистрация: 30.06.2009
Сообщений: 1,399
15.07.2009, 12:13     Коммивояжёр - или оптимизация пути. #6
клиентов можно раньше подбирать или машина должна простаивать?
Желательно нагружать равномерно, но учитывая и расстояние (цену пути).
я не совсем об этом спрашивал, насколько важно и зачем в условии присутствует "Время подбора клиента T3"? что означает этот параметр?

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

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

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

P.S. Я это для чего пишу. Чётко сформулированная задача - это уже половина решения. А в код перевести это и кодер сможет.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
16.07.2009, 21:14     Коммивояжёр - или оптимизация пути.
Еще ссылки по теме:

Оптимизация функции C++
C++ Оптимизация. Что быстрее работает: cout или printf
Циклы и их оптимизация C++
C++ Оптимизация программы
оптимизация C++

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

Или воспользуйтесь поиском по форуму:
TanT
эволюционирую потихоньку
 Аватар для TanT
464 / 462 / 43
Регистрация: 30.06.2009
Сообщений: 1,399
16.07.2009, 21:14     Коммивояжёр - или оптимизация пути. #9
черновой вариант. данные берёт из файла clients.txt, данные ввиде : time x_begin y_begin x_end y_end
Вложения
Тип файла: txt Taxi.txt (3.9 Кб, 38 просмотров)
Yandex
Объявления
16.07.2009, 21:14     Коммивояжёр - или оптимизация пути.
Ответ Создать тему
Опции темы

Текущее время: 05:30. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru