Архив форума

Здравствуйте Ирина.
Сейчас на рынке очень много решений по GPS мониторингу, но есть 1 но, все они реализованы на закрытых платформах или вообще в WEB интерфейсах на сайтах разработчиков. Предложения заманчивы в первую очередь дешевизной предложения, но на практике получается что бесплатный сыр, только в мышеловке, т.к  доработать необходимые отчеты и настроить передачу данных в корпоративную учетную систему представляется мало возможностей, это могут только сами разработчики, и вы попадаете на большие сроки и вот тут уже на внушительные суммы, вот и весь фокус.
По мониторингу работы автопарка могу порекомендовать ITOB: Центр мониторинга http://itob.ru/solutions/itob_moncenter/  
Система очень гибкая и можно настроить практически любые отчеты в  короткий срок, т.к реализовано на платформе 1С: Предприятие 8, коды открыты и если есть собственные программисты, можно забыть о разработчике и дополнительных инвестициях.  

Или вопрос про применение системы на складе?

GPS только отслеживает перемещения объектов (машин, людей), которое можно отразить как на карте, так и охарактеризовать цифрами - сколько проехал, маршрут, примерный рассчет бензины.
 
Но это скорее контролирующий элемент, вначале нужно все грамотно распланировать, а потом уже отслеживать.
 
Ездил недавно к знакомому, так они на работе сейчас разрабатывают очень интересный комплекс по рассчету развоза продукции по 150 точкам как собственным транспортом, так и наемным. При этом закладываются множество ограничений. В итоге при попытки решить задачу перебором уткнулись в производительность, поэтому сейчас берут уроки по высшей математики и изучают генетические алгоритмы.
 
Если интересно могу свести т.к. они готовят коммерческий продукт.

Процитировано сообщение: Сизов Евгений от 26.11.2008 :: 15:27:54:

 
По словам знакомого анализ российского рынка показал, что за 20 т.$ ни одна из представленных систем не решает эту задачу полно, в основном простые методы конечного перебора с большим процентом погрешности.

Процитировано сообщение: Сизов Евгений от 26.11.2008 :: 18:14:01:

 
На сколько я понял, решение от nova-it выполняет планирование не самым оптимальным способом.
 
Изначально задача ставилась так, что имеем разнообразный собственный парк (стоимость одного километра разная, как и скорость, объем, вес и т.д.) и есть наемный транспорт. Теперь нужно рассчитать самый выгодный вариант, причем не обязательно использовать только собственный парк, или обязательно в один район отправлять только одну машину, или обязательно заполнять машины под завязку или заставлять проехать как можно больше точек. Нужно просто зная все доступные способы, тарифы и ограничения предложить самый ДЕШЕВЫЙ вариант с соблюдением всех сроков. Т.е. критерий прозрачный - снизить стоимость доставки не нарушая других требований.  
 
Такие рассчеты занимают очень много времени, поэтому для оптимизации применяются или симплекс метод, или генетический алгоритм.
 
Плюс есть такие мелочи, как не только доставка, но и забор груза и т.п.
 
Большинство текущий решений оптимизируют или время (чем быстрее тем лучше) или расстояние (чем короче тем лучше), да и то по простому алгоритму - берем весь парк машин и начинаем последовательно заполнять их заказами. Если не удалось уложиться в рамки доставки, то заказ переноситься в другую машину.

Процитировано сообщение: Соломатин Владимир от 27.11.2008 :: 14:36:37:

 
Ну вот, люди применяют
 
Если задать достаточно жесткие условия, то результат может быть разным, но скорее всего он будет равноправным, если это позволяют условия. Плюс его можно комбинировать/проверять с другими методами

Нашел вот статью про генетические алгоритмы в задаче коммивояжера.
http://www.mnogosmenka.ru/drugoe/genetitiskie.htm
Главное чтобы потом заказчику не объясняли если что не так пойдет - мол гены, хромосомы, мутация..........как в том анекдоте

Процитировано сообщение: Соломатин Владимир от 28.11.2008 :: 08:42:39:

 
Ну у заказчика всегда есть выбор - или использовать простые не всегда эффективные алгоритмы, или довериться нелинейным алгоритмам для получения лучшего результата.
 
Например, Солво тоже пошло по этому пути:
http://www.solvo.ru/press/pub/319/

Нашел онлайн игрушку для логиста:
 
http://www.lalena.com/ai/tsp/Tsp.aspx
 
достаточно занимательно смотреть как система пытается найти оптимальный путь наугад расставленным точкам

Процитировано сообщение: Рубанов Сергей от 28.11.2008 :: 15:35:10:

 
Да уж, оч занимательная штучка!
Мне было интересно смотреть как выбирается маршрут если точки стоят примерно по диагоналям.

Действительно, болезнью генетических алгоритмов является недетерминированность результата при неизменных входных данных, что может привезти заказчика, мягко говоря, в недоумение  .  
У себя в программе www.packer3d.ru мы решили эту проблему введя множество коэффициентов, которые используются геномом алгоритма при оценке "удачности" оптимизации локального шага и созднния выборки предметов для следующего. Таким образом, если не менять параметры задачи, то каждый раз расчет будет выдавать одно и то же решение.  
 
По умолчанию выставлены усредненные коэффициенты, полученные на основе опыта предыдущих успешных расчетов. Всего около 50 коэффициентов.  
 
Причем пользователь сам может "подкручивать" геном под свою специфику погрузочных работ, редактируя эти коэффициенты. Самые понятные из них вынесены в интерфейс программы, остальные доступны в XML файле. При запуске расчета оптимальной загрузки система зачитывает эти коэффициенты и использует их.  
 
При определенном навыке получается улучшить качество загрузки, на 3-10%, хотя и сложновато. Представьте себе настройку сложного механизма с 50 регулировками.  
 
Желающие могут поиграться с генетическим алгоритмом.  
Скачать демо программы здесь http://www.packer3d.ru/ver3/p3d-demo-setup.exe.
Коэффициенты доступные из GUI в разделе "Параметры алгоритма"/"Правила", остальные в файле каталог_программы\format\ru\0.xml

Юрий, очень интересно !  
Задача коммивояжера, это, как всем известно,  NP-полная задача, т.е. для нахождения ТОЧНОГО решения требуется полный перебор.  Вы утверждаете, что обладаете вычислительными мощностями для обхода графа в 300 вершин, т.е. просчета 300! вариантов ?  
Или вы смогли найти алгоритмическое ТОЧНОЕ решение ?  

Прошу прощения, это не Ильюх Валерий, а Бобрышев Юрий. Валера наш сотрудник и я зашёл с его logina и компа. В остальном всё верно и никаких мистификаций.

Процитировано сообщение: Якимович Андрей от 27.01.2009 :: 17:02:41:

 
Это еще актуально?

Отчего ж не понять? Очень даже хорошо понимаю разницу между точным и приближённым решением: точное решение оптимизационной задачи - это когда лучше - ну никак! Собственно, это один из критериев проверки.  
Что касаемо Института Клэя и премии, то конечно я об этом знаю. Но! Все имеющиеся на данный момент алгоритмы точного решения ЗК так или иначе включают в себя процедуры, для которых невозможно доказать их полиномиальность даже при условии их быстрой сходимости. Таковы, например, процедуры оценки снизу. Есть некоторые другие эффективные итеративные процедуры о которых можно сказать то же самое.  
Поэтому премия до сих пор и не востребована.  
И потом, за решение фундаментальной проблемы дискретной математики всего 1 млн. долл.? Это жадность.

Процитировано сообщение: Бобрышев Юрий   от 27.01.2009 :: 18:03:09:

 
Ну это как в том анекдоте когда на вопрос «Раскольников, зачем Вы убили старушку всего за 20 копеек?» тот ответил – «А пять бабушек это уже рубль!»  
Если решить одну задачу - то оставшиеся 6 - думаю уже не проблема  

Андрей!
На самом деле критерий проверки прост:
берёте какую-нибудь свою задачу, присылаете нам исходные данные, мы решаем и Вы сравниваете решение со своим.
Чего проще?
Если сделать так раз 100, то ответ нарисуется сам собой.
А МГУ, конечно, аргумент.
 

Скажите пжл тупенькому, в каких таких практических задачах возникает хотя бы 200 точек?

Цитата:
 
1. Если решать ЗК на несимметричном графе, например дорожном, то лобовое сведение несимметричного графа к симметричному удваивает количество вершин. Т.е. нужно объехать сто адресов, а решать удобно задачу с 200-ми точками. Такие "масштабные" проблемы иногда возникают у инкассаторов.
2. Если отвлечься от чисто складских и транспортных вопросов, то, например, задачи пробивки отверстий печатных плат - до нескольких тысяч вершин
3. Всякие хитрые задачи вроде бы небольшого размера, не решаюшиеся лобовым перебором, которые при сведении к ЗК увеличивают размер задачи в разы
и прочая, прочая, прочая...

Цитата:

Конечно! Категоричность терминологии уместна при рекламе шампуня или туалетной бумаги. В нашем же деле уместны оговорки и всяческие уточнения. И практические и терминологические.
...  
И моё предложение совместно что-нибудь посчитать не встретило отклика...  
Пойду на другую ветку, попугаю там народ точными (оптимальными!) решениями!  

Цитата:
 
Да куда уж скромнее...
Только правду.
Но у меня складывается впечатление, что Вы не верите в возможность получить точное решение (точное не в смысле полиномиальности алгоритма, а в смысле оптимальности) ЗК никаким способом, кроме как перебором?  
Все имеющиеся в настоящее время алгоритмы получения точного решения ЗК можно с некоторыми оговорками назвать разновидностями метода ветвей-и-границ. Вопрос только в том, какой подход, или идеологию закладывают авторы при отсечении неверных путей. И таких различных подходов очень, очень мало.  

В простейшем случае задачу о нахождении гамильтонова цикла можно свести к 2^n(имеется ввиду точный алгоритм). Поэтому вариантов будет 2^300. Но полностью с вами согласен, Андрей. Это удивительно =))) По идее машина будет считать это хозяйство 2^300 = 2*(10^90). Т.е. примерно 2^82 секунд. Думаю конец света случится раньше =))))

Я не скептик, напрасно вы, я очень позитивный оптимист   Другие люди в нашей области просто не выживают.  
 
Когда 8 лет назад мы взялись за задачу оптимизации плана загрузки транспорта, нам ученые люди пальчиком крутили у виска и доказывали, что задача не решается.  
 
Когда через 2 года , в 2003 годы мы получили первые успешные решения и выпустили packer3d v1.0 у нас так же как у вас горели глаза и мы были абсолютно уверены, что мы перевернем мир    
 
Но мир устоял, как ни странно   В первой версии (которая до сих пор еще работает бесплатно под видом on-line сервиса на сайте www.old.packer3d.ru)  можно было выставить только ограничения по грузу: тоннаж, зафисксировать высоту, и запрет на установку на коробку сверху. И все. Как оказалось в реальной жизни, довольно редко встречаются погрузки такого простого типа. Обычно надо учитывать множество дополнительных условий и ограничений.  
 
Поэтому потребовалось добавлять функционал: хрупкость, уровни, ряды, нагрузки по осям, группировки, загрузка с разных сторон, порядок загрузки, дозагрузка, паллетирование, затаривание и т.д. и т.п. Полный функционал в картинках на текущий момент можно посмотреть здесь http://www.packer3d.ru/program/features. Ну и геном несколько раз переписывали по-ходу. Вот этим и занимаемся последние 5 лет.  
 
Поэтому оптимизм - это здорово, но настраивайтесь на работу, работу, работу ........
Форум "Общие вопросы задач оптимизации" готов http://www.packer3d.ru/forum/11. Приглашаем всех, кому интересна эта тема.