Добрый день, уважаемые форумчане
встала вот такая задача, есть таблица точек(заказов) которые нужно обслужить, со своим временем приемки, для каждой точки известно расстояние от склада до нее и до всех других
нужно составить такой маршрут который был бы кратчайшим, и в то же время удовлетворял условиям доставки для каждой точки

попробовал сделать с помощью перебора всех перестановок, но он приемлим если точек <12, потом выяснилось что их может быть около 100

есть ли какие-либо готовые решения для данной задачи?
или какой алгоритм не слишком сложный?

это тебе теорию графов изучать надо

в школе информатику прогуливал?

wiki:%C7%E0%E4%E0%F7%E0_%EA%EE%EC%EC%E8%E2%EE%FF%E6%B8%F0%E0

(3) на счет коммивояжера я в курсе, вопрос в том каким методом ее проще реализовать в 1с, и чтобы еще условия отгрузки соблюдались

(4) купить специализированный софт. который учитывает дорожный граф, окна доставки и т.п.

(4) реализуй методом функции, на вход которой будешь подавать начальную и конечную точки а на выходе получать оптимальный маршрут

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

говорил мне 1986-й, что я их еще буду вспоминать как умных... а я не верил...

Если точек штук сто, тогда методом перебора будешь считать мильёен лет :)

(5) спасибо, но это надо самим сделать
(9) дада

http://www.dmtsoft.ru/bn/358/as/oneaticleshablon

http://av-mag.ru/referat/traveling-salesman-problem.htm

http://www.cyberforum.ru/delphi/thread574388.html

(10) ну тогда тебе к математикам надо обращаться, а не к тупым и жадным 1С-никам. Если у тебя маршруты более или менее регулярны, то будет у тебя в определенный район 1 основной маршрут и 2 или 3 дополнительных, а для форс-мажоров логист будет уже ручками планировать и раскидывать РН по маршрутным листам.

http://forum.vingrad.ru/forum/topic-317907.html

aleks-id сспасибо, посмотрю

(0)
Короче.

Варианты:
Купить спец. софт. Антор-Логистика, БиТ:Управление Логистикой.
Все они внутригородские, достаточно навороченные.

Написать самим, в виде отдельного сервиса.
На 1С-бы не советовал -  медленно.

На WPF у нас, криворуких, заняло это полтора месяца.
Маршрут из ста точек (пять опорных) рассчитывается за три секунды на десктопной машине.

(16) спасибой не отмажешься. а вот статьей в http://www.kb.mista.ru/ запросто

(17) кластерный анализ районирования делаете?

(17) а сколько человек занималось?  каким методом?

проходили мы в Вузе такой предмет - "Дискретная математика".
Отличный препод и отличный учебник нашего препода Рыбина - http://www.ozon.ru/context/detail/id/4122627/

Помнится, там решались такие задачи на графе.

(20) а у вас контора занимается логистикой?

(22) не совсем логистикой, поставкой систем мониторинга

(23) а как называется контора? Не пиара ради, токмо обойти стороной...

Сто точек - это точно не один маршрут...
Поэтому алгоритм такой - вначале сто точек разбиваются на кластеры -- по числу маршрутов (машин, курьеров...) - можно использовать стандартную кластеризацию 1С
Потом внутри каждого кластера решаете задачу комивояжера - самый простой способ - т.н. "жадный алгоритм" - дает вполне удовлетворительный результат

(23) =) про генетические алгоритмы - вы на щелчок, естественно, ничего не сделаете. Задача, подобная вашей, если мне память не изменяет, на генетическом алгоритме, описана в труде профессора Комарцовой из МГТУ. Если ошибаюсь, тогда из этих же сборников, просто не она автор, а кто-то из ее аспирантов. Ну почему то отложилось что у Комарцовой я про это читал :)

(25) кластеризация проведена уже, надо внутри кластера провести оптимизацию

(19)
Неееет. o_O

(20)
Один человек на обсчеты.
Другой - на интерфейсную часть.

Метод - A*

Дольше всего делалась интерфейсная часть.

https://dl.dropbox.com/u/11083106/map.PNG

Вот так вот выглядит.

(28) ааа, у тебя задача чуть другая. У ТС, имхо, задачка немного другого класса.

Если ТС собрался в 1С решать VRPwTM, то - попутного ветра в горбатую спину. ))))

(0)
А вообще, если на входе:
1. Некоторое число машин.
2. Некоторые точки с временными окнами.

То смотрите в сторону решений от Антор. На коленке такие вещи не делаются.

(30) спасибо за напутствие))

самому интересно стало как такие задачи решать
опыта мало пока, может научусь чему

ДЕЛОВАЯ КАРТА - транспортная логистика, бизнес-технологии

я автоматизировал с помощью этой программы

http://www.ingit.ru/businessmap/?SID=uf0nzj89mn4x&RND=dsnu1hum9b32&M=2

(33)
Мутные они, эти парни из ингита.

Продажи им не нужны.