|
|
|
Задача к коммивояжеров
|
|||
|---|---|---|---|
|
#18+
Задача к коммивояжеров Условия На множестве из n + 1 города строится к замкнутых маршрутов по следующим правилам 1. Один из городов называемых базой, входит во все маршруты 2. каждый из городов, исключая базу, входит ровно в один маршрут 3. суммарная длина всех маршрутов минимальна Методы решения 1. Сначала решается ЗК для всех городов, а потом подбирается наилучшее разделение результата для k коммивояжёров. 2. Сначала множество городов разбивается на k групп, а затем ЗК решается для каждой из них Подробно методы излагаются здесь http://www.marigostra.ru/materials/ktsp-tsu-2008.pdf Вопрос, как адаптировать предлагаемые решения при условии Ограниченного Времени работы коммивояжеров Собственные соображения : В первом из предложенных вариантов можно делить маршрут исходя не из равномерного распределения количества городов между к коммивояжерами, а из времени работы каждого коммивояжера, НО данный вариант возможен только при условии, что общее время работы меньше суммарного времени работы к коммивояжеров, т.е. все города будут пройдены за выделенное время, а это далеко не факт Во втором варианте действуем по предложенному варианту, затем накладываем временное ограничение на к - ый полученный маршрут и отрезаем города, не вошедшие в маршрут по времени. Затем города, не вошедшие маршрут, перераспределяем между остальными группами маршрутов по предложенным выше вариантам . - Собственно вызывает вопрос вообще правильность предложенного варианта, смущает обрывание маршрута просто повремени и в целом предложенный вариант почему включать в маршрут первые n городов, а не последние и т.д. Буду благодарен за любые идеи и ссылки. Спасибо ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.10.2012, 23:31 |
|
||
|
Задача к коммивояжеров
|
|||
|---|---|---|---|
|
#18+
1 База должны иметь к*2 дорог к сосденим городам. Для каждого комивояжера разный маршрут приезда и возврата. 2. Считать рекурсивно, одни ход считать от точки отъезда , следующий от точки возврата, пока маршрут не замкнется. 3 Расчет для всех комивояжеров должен производиться паралельно( по очереди). 4. Внутри цикла ходов , первым должен ходить( выбирать вариант куда поехать) , тот комивояжер у которого меньше вариантов для выбора. 5. В случае наступания на занятый город, откатывать последний ход ( возможно даже несколько ходов до хода в котором был занят этот город) у всех комивояжеров и искать алтернативные маршруты , начиная с того кто наступил на чужой город. приблизительно так. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 08.10.2012, 00:09 |
|
||
|
Задача к коммивояжеров
|
|||
|---|---|---|---|
|
#18+
6. Может возникнуть необходимость менять между комивояжерами вторую половину маршрутов( замыкать маршрут на соседа , а соседский на себя). Для быстрого разрешения пересечения маршрутов 2 комивояжеров, на последних ходах работы алгоритма. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 08.10.2012, 01:05 |
|
||
|
Задача к коммивояжеров
|
|||
|---|---|---|---|
|
#18+
ДохтаР, Вы хотя бы сами поняли, что написали ... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 08.10.2012, 02:11 |
|
||
|
Задача к коммивояжеров
|
|||
|---|---|---|---|
|
#18+
rus_bug, Если бы не понимал , не писал бы . Просчитывается к *2 маршрутов от базы к краям по критерию сумарной длины. Потом маршруты попарно замыкаются ( п 6) друг на друга. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 08.10.2012, 11:13 |
|
||
|
Задача к коммивояжеров
|
|||
|---|---|---|---|
|
#18+
rus_bug, Я бы не пытался так жёстко сводить задачу к задаче коммивояжёра (по сути, к случаю k=1). И что значит - "ограниченное время работы"? Что длина каждого из путей не должна превышать некий max? Некоторые мысли вслух: Пусть у нас есть некоторое решение. 1) База - вершина степени не меньше k, иначе задача не решается. 2) Каждый город может быть достигнут из базы по пути не длиннее max/2. 3) Вообще, может оказаться полезно приписать каждой вершине минимальное расстояние до базы. 4) Если у нас маршрут, то на подграфе, образованном входящими в него вершинами, его можно модифицировать как и в случае обычной задачи коммивояжёра. 5) Дугой маршрута назовём его фрагмент от базы до базы, не включающий базу кроме как в конечных точках. 6) Если у нас есть две дуги, принадлежащие разным маршрутам, то, если у некоторой пары рёбер перекрёстно соединены концы, при некоторых условиях их возможно "перемкнуть": получить две других дуги. 7) Предположительно, операции 4) и 6) позволяют достаточно сильно модифицировать решение, чтобы можно было применить метод имитации отжига. Однако для этого желательно, чтобы степень вершины базы была не меньше 2k. 8) Поскольку частный случай k=1, max=100500 есть NP-полная задача, без дополнительных предположений о значениях k и max не стоит надеяться решить задачу аналитически, в любом случае. 9) В принципе, вместо имитации отжига можно попробовать модифицировать муравьиный алгоритм . В этом случае, по идее, легко сформулировать ограничение по длине пути (пройдя max, муравей дохнет), но над тем, как потребовать k непересекающихся маршрутов, надо думать. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 08.10.2012, 11:45 |
|
||
|
Задача к коммивояжеров
|
|||
|---|---|---|---|
|
#18+
Abstraction, Я когда вчера вечером размышлял о возможных вариантах решения, думал о некотором угасающем весовом коэфициенте для маршрута в каждой вершине графа. автор Чем выше концентрация феромона на тропе, тем больше муравьев будет по ней двигаться. Со вре менем феромон испаряется, что позволяет мура вьям адаптировать свое поведение под изменения внешней среды. Распределение феромона по про странству передвижения муравьев является свое го рода динамически изменяемой глобальной па мятью муравейника Для временного отсечения псевдо-тупиковых маршрутов методом имитации отжига. Для предотвращения попадания комивояжоров на маршрут , где недавно произошло наступание на грабли ( в тупик ). По мере уменьшения весовго коэфицента конфигурация других маршрутов должна достаточно сильно поменяется , И этот ранее тупиковый маршрут можно попробовать использовать повторно. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 08.10.2012, 13:15 |
|
||
|
Задача к коммивояжеров
|
|||
|---|---|---|---|
|
#18+
rus_bugДохтаР, Вы хотя бы сами поняли, что написали ... Вы находитесь в позиции просящего. Вам специалисты помогают бесплатно. Поэтому менторский тон здесь совершенно неуместен. Не забывайте об этом. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 08.10.2012, 13:29 |
|
||
|
Задача к коммивояжеров
|
|||
|---|---|---|---|
|
#18+
если это развозка товара,то надо учитывать грузоподъемность + если планирование на 1 день , то 1 водитель не сможет обслужить более 8-10 точек( разгрузка + оформление документов) + иногда надо учитывать время работы точки + если развозка по области, то через некоторые населенные пункты проезжать придется многократно ( из А в Б,Д,Е только через С) + иногда лучше проехать лишнего по хорошей дороге, чем сэкономить км и ехать по плохой ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 09.10.2012, 14:11 |
|
||
|
|
start [/forum/topic.php?fid=16&fpage=64&tid=1342104]: |
0ms |
get settings: |
7ms |
get forum list: |
10ms |
check forum access: |
2ms |
check topic access: |
2ms |
track hit: |
63ms |
get topic data: |
8ms |
get forum data: |
2ms |
get page messages: |
50ms |
get tp. blocked users: |
1ms |
| others: | 245ms |
| total: | 390ms |
| 0 / 0 |
