Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

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

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

14.07.2009, 17:03. Просмотров 916. Ответов 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
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
14.07.2009, 17:03
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Коммивояжёр - или оптимизация пути. (C++):

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

Нахождение кратчайшего пути по матрице, или передвижение привидений в игре Пакмен - C++
Подскажите пожалуйста как правильно реализовать? Имеются координаты x,y пакмана и приведения. Я использую такой алгоритм: void...

Нужен алгоритм поиска пути в этом лабиринте (будь то волновой алгоритм или алгоритм правой/левой руки ) - C++
#include "stdafx.h" #include <iostream> #include <conio.h> using namespace std; void lab () { int s1 = 0; int s2 =...

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

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

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

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


сколько клиентов можно по пути подобрать?
3
0
TanT
эволюционирую потихоньку
466 / 464 / 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). в общем движение по рёбрам треугольника или по его диагонали

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

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

Т.е. нужно учитывать не только расстояние от высадки клиента к следующему, но и время во сколько забрать клиента.
0
TanT
эволюционирую потихоньку
466 / 464 / 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. Я это для чего пишу. Чётко сформулированная задача - это уже половина решения. А в код перевести это и кодер сможет.
0
TanT
эволюционирую потихоньку
466 / 464 / 43
Регистрация: 30.06.2009
Сообщений: 1,399
16.07.2009, 21:14 #9
черновой вариант. данные берёт из файла clients.txt, данные ввиде : time x_begin y_begin x_end y_end
0
Вложения
Тип файла: txt Taxi.txt (3.9 Кб, 38 просмотров)
16.07.2009, 21:14
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
16.07.2009, 21:14
Привет! Вот еще темы с ответами:

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

Оптимизация запросов или как обрабатывать пачками? - SQL Server
В данный момент есть прототип системы. но он страдает тем что у нас есть какой либо запрос который вернёт нам кучу параметров. Далее во...

Оптимизация или построение графиков ремонтов оборудования - Delphi БД
Доброй ночи! Помомогите пожалуйста. Есть у кого исходники Delphi по оптимизации или построению графиков ремонтов оборудования?

Оператор case или альтернативные пути - Delphi
Все никак не могу придумать как оформить: Type сезон=(зима,весна,лето,осень); ...


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

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

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