2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

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

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

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



Начать новую тему Ответить на тему
 
 построить маршрут
Сообщение02.04.2013, 21:32 


25/02/10
5
есть энное количество точек с координатами Х, У
есть ср. скорость движения, есть ограничение на продолжительность маршрута
задача построить маршруты прохождения через точки так чтобы:
1. необходимо пройти все точки
2. каждый маршрут начинается с коорд.00
3. маршрут не может быть дольше предельного значения
4. маршрутов - минимум
5. общая продолжительность - минимальна
и еще в каждой точке задано время выполнения задания.
задача такая: есть точки доставки, необходимо минимальным количеством курьеров обойти все точки, чтобы курьеры не перерабатывали 8 часов (480 минут в задаче).
задача №1 сократить до мин. кол-во курьеров (выданных зарплат)

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

 Профиль  
                  
 
 Re: построить маршрут
Сообщение02.04.2013, 22:41 
Аватара пользователя


14/02/10
4956
Очевидно Теория графов

 Профиль  
                  
 
 Re: построить маршрут
Сообщение03.04.2013, 00:39 


17/10/08

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

При большом количестве потребуется более эффективное моделирование – в описанной постановке задача, скорее всего, «труднорешаема» – приближенные алгоритмы будут давать плохое решение. Уж так у нас повелось: по книжкам можно научиться создавать комбинаторный ужас вместо реальных моделей.

 Профиль  
                  
 
 Re: построить маршрут
Сообщение03.04.2013, 00:50 


07/03/11
690
Задача реальная или учебная? Рекомендую полный перебор (по кол-ву курьеров)! Фиксированное время выполнения задания значительно сужает поиск (на раннем этапе помогает отбросить ложные пути).

 Профиль  
                  
 
 Re: построить маршрут
Сообщение03.04.2013, 07:56 
Заслуженный участник


22/11/10
1183
Это таки один из вариантов задачи коммивояжера. Есть специализированный сайт VRP.

 Профиль  
                  
 
 Re: построить маршрут
Сообщение03.04.2013, 08:38 


25/02/10
5
задача реальная, только точек много
ручной перебор занимает очень много времени...хотелось хоть немного автоматизировать процесс...
перебрала много литературы, но нигде не могу найти хоть на что-то похожий алгоритм...
Уж так у нас повелось: по книжкам можно научиться создавать комбинаторный ужас вместо реальных моделей. Это точно...
ведь задача не сократить длину маршрута(надо что бы курьер работал 8 часов), а минимизировать количество курьеров...то есть самих маршрутов...
так что транспортной задачей ничего не сделать, а задача коммивояжера, в том варианте (классическом), тоже не удовлетворяет всем требованиям, она находит обход всех точек, а мне надо разбить их на несколько маршрутов...
Благодарю всех кто старался подсказать, может все же найду вариант

 Профиль  
                  
 
 Re: построить маршрут
Сообщение03.04.2013, 14:51 
Заслуженный участник
Аватара пользователя


06/04/10
3152
sup в сообщении #705082 писал(а):
Это таки один из вариантов задачи коммивояжера.

Осложнён дважды.
1/ На выходе - разбиение множества вершин на минимальное число зон.
2/ Маршруты по зонам не закольцованы.

 Профиль  
                  
 
 Re: построить маршрут
Сообщение03.04.2013, 15:41 
Заслуженный участник


22/11/10
1183
nikvic в сообщении #705205 писал(а):
Осложнён дважды.
1/ На выходе - разбиение множества вершин на минимальное число зон.
2/ Маршруты по зонам не закольцованы.

Это все и есть вариации на тему. Если бы не ограничение на величину каждого маршрута, то все свелось бы к чистой задаче коммивояжера (с помощью фиктивных вершин и/или асимметричой TSP).
Коль скоро решение ищется вручную (!), то можно попробовать такой подход хотя бы в качестве начального приближения. А уж задачу коммивояжера решать с помощью приближения Хелда-Карпа.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 8 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group