Добрый утро. Помогите найти решение такой задачи. Наша компания устанавливает окна, и взаимодействие с клиентом начинается с приезда мастера по замерам. Сейчас графики приезда мастера формируются после накопления некоторого определенного логистами количества заявок, после чего выполняется его построение, то есть клиента ориентируют на точное время не в момент обращения, а через неск. дней (в зависимости от плотности). А хочется записывать клиентов в момент обращения на более точное время (с погрешностью час-два не больше), учитывая естественно что мастер не должен из одного конца города в другой как угорелый. Любое построение оптимального маршрута предполагает наличие нескольких адресов, которые надо оптимально расставить, в нашем случае всё немного по-другому. Может существуют какие-либо готовые решения? ну или близко подходящие.

задача коммивояжёра подойдёт?

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

(2) не понял. адресов ещё нет, но уже хочется оптимальный маршрут?

Поделите город на сектора,  каждому сектору свой временной (2х часовой например)  промежуток времени.  И расставляйте туда заявки.

доводилось как-то автоматизировать ресторан доставки. пытался чего-то думать про взвешенные графы, да ещё и с учётом периодических пробок... заглохло. вывод: не говори водителю, куда ехать ;)

(4) думала над этим, но тогда есть вероятность что никто не обратится из каких-то секторов, а из других обратятся слишком много. Сейчас думаю над тем, чтобы делить не на сектора а учитывать удалённость, типа если удаленность больше 100 км расстояние между этими заявками должно быть более 4-5 часов, чтобы когда будут обращения из более близких районов ставить их в этом промежутке

(6) Заполняй сектора с "середины",  если заполнился залезай в соседний.    В любом случае идеальный маршрут без дырок не получишь,  когда точки заранее не известны.

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

Отталкивались от загрузки базовых секторов, остальные график строился по потребности базовых.

с готовым решением никто не сталкивался? можно предложить свои услуги

Любая программа построения маршрутов доставки.
Например, тот же антор (правда, он дорогой до ужаса в вашем случае)

Несколько соображений:
1) Задача похожа на "переход к жесткому расписанию  при наборе групп". Там говорилось, что жесткое расписание дает плюс слушателей курсов минус заполняемость групп. Отсюда вывод: в критерий оптимальности нужно заложить уменьшение отвала клиентов за счет увеличения средней длины маршрута.
2) Нужно использовать статистику заявок по районам. Составить оптимальный маршрут в расчете на среднестатистический набор заявок. Далее, при поступлении каждой новой заявки, перестраивать маршрут, оставляя часть среднестатистических (прогнозных) заявок. И вот тут интересный вопрос: если есть уже сделанные заявки плюс статистика прошлых дней - как предсказать из каких районов будут заявки? Они, скорее всего, независимы, поэтому точнее всего будет просто сужать выборку по времени поступления заявок.
3) Вопрос: а сколько замерщиков?
4) Какой город? - Это нужно, чтобы размерность транспортного графа и возможность его получения и представления понять.

(11) любая программа построения маршрутов доставки предполагает (на сколько я понимаю), что точки изначально заданы. В моём случае точки возникают в течение времени и в случайно удаленных друг от друга участках

(12)
2) статистика есть, сейчас всю эту работу делают вручную логисты. Но в текущий момент построение графиков происходит после набора заявок
3) 4) города разные, количество замерщиков тоже разная и может изменяться

(13) нормальная программа построения маршрута позволяет фиксировать некоторые точки (в вашем случае - уже пройденые, либо "жестко договоренные"), и задавать временнЫе окна.

(12) а поможет ли статистика на малом количестве точек? а уж тем более - предсказание?

(0) "естественно что мастер не должен из одного конца города в другой как угорелый".
Или у вас один мастер на весь ваш зоопарк или нет "привязки" мастера к определенному "району".

"в текущий момент построение графиков происходит после набора заявок" // А как хочется - чтобы график обхода был независимо от набора заявок что ли?

(16) мастер не один, но привязки к районам нету.
(11) антор нам не поможет

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

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

(19) именно

(20) Понимаете что это удобство для клиентов, аукнется офигительным неудобством для вас?

(21)+ Когда например мастер вместо того чтобы точка 1 и рядом точка 3, после точки один не идет в соседний подъезд, а сначала едет через полгорода на точку 2 и потом назад к месту точки 3 (и 1 тоже).

(18) Вот и решение. Разбить свое хозяйство на районы обслуживания. Можно даже использовать место проживания мастера. До обеда мастер "дежурит" в районе А, после обеда - в районе Б. Размеры районов должны быть в рамках вашей нормы времени (от одного конца района до другого - час-два).
Не оболльщайтесь.
В системе, которая зависит от случайного обращения клиента ВСЕГДА будут периоды простоя. Их можно только уменьшить.
Ввели в эксплуатацию ЖК "Лоджии без окон" - ваши начи должны смекнуть: и объявы развесить на всех столбах и дежурного мастера туда направить.

(21) кстати да. это не должно усложнить жизнь операторам контактного центра)

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

(19) Так Я так и работал дежурным инженером :) Было временное окно на один район (до обеда) и кажому абоненту говрился диапазон из этого окна, когда к нему подойдет человек

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

(18) антор вам как раз поможет. там прекрасно фиксируются точки маршрута, и прекрасно делается пересчет.
Но дорогой, зараза.
Аналоги на гугл-апи или яндекс-апи видел, там такого нет...

Антор сказал, что не поможет

(24) ТЗ составьте и бюджет озвучьте. Еще нужна карта границ скоростей передвижения мастеров между адресами/райнами.

(28) что, анторовцы знают возможности программы хуже клиентов? :-)

(29)+ Т.е. нужны данные как быстро сможет мастер добраться из любого адреса к любому адресу.

(29) иэх. дорожный граф - это как раз и есть самое ценное в ГИСах...

(26) Количество замеров не снизится а равномерно распределится между всеми сотрудниками.

-утром звонок - точка 1 на 10утра
-в обед звонок - точка 2 на 12утра
-вечером звонок - точка 3 на 18дня,
потому что то точка 3 рядом с 1, а вторая на другом конце города

что делать в таком случае?

(31) а ты построй полный список "любых адресов" :-)

(33)+ Проблема будет только у отдельных замерщиков со связями/блатом среди диспетчеров - это не шутка, учитывайте.

(33) не обязательно. зависит от критерия оптимизации.
Если критерием будет пробег, то будут перекосы в одну сторону, если безусловное исполнение в узких окнах - мастера будут метаться по всему городу  с диким пробегом

(36) это будет.
Но в принципе, это и так решаемо, ручной подстановкой. Все равно оператор будет смотреть глазами, делать руками и говорить головой :-)

(35) Ну да долго только зачем?
Проводим натурные измерения/замеры скорости по текущим адресам, далее пары точек накладываются на карту и далее по графу по моему методу http://catalog.mista.ru/public/442306/ т.е. чтобы узнать время добирания между любыми точками используем промежуточные точки.

(37) Угу от критериев, но в среднем даже по минимальный пробег иногда у мастеров будут перекосы, что на большем интервале нивелируется.

(39) Ну так этот же метод используется и в гугломапах-яндекскартах. причем  сразу на графе дорожной сети.

(41) Он зараза самый быстрый ибо просчет заранее а потом только берем готовые рассчитанные маршруты из матрицы.

(29) могу предложить только наоборот: есть задача назначать время при обращении клиента. При этом при формировании графика после его наполнения он должен быть достаточно оптимальным. Жду варианты того, за какую цену готовы взяться + сроки реализации

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

Т.е. без знания маршрутов никак, а если знаем маршруты то задачка сводится к простейшему перебору вариантов между ключевыми точками с проверкой на укладываемся ли.

(43) что такое "достаточно оптимальным"? оптимальным по пробегу, оптимальны по времени, оптимальным по количеству задействованых мастеров?

И да, для моделирования - зависит ли от чего-то "время у клиента"?

(44)+ Надеюсь понятно что никак не смогу приехать в Волгодонск и замерить там маршруты перемещений между районами города и пригорода, причем разными способами :)

(47) - в (13) "города разные". Я предполагала что эти вещи карты должны какие-нибудь реализовать. Типа гугла

(45) по пробегу и количеству заявок

(47) https://yandex.ru/maps/11036/volgodonsk/?utm_source=geoblock_maps_chelyabinsk&ol=geo&ouri=ymapsbm1%3A%2F%2Fgeo%3Fll%3D42.19843%252C47.516545%26spn%3D0.001%252C0.001%26text%3D%25D0%25A0%25D0%25BE%25D1%2581%25D1%2581%25D0%25B8%25D1%258F%252C%2B%25D0%25A0%25D0%25BE%25D1%2581%25D1%2582%25D0%25BE%25D0%25B2%25D1%2581%25D0%25BA%25D0%25B0%25D1%258F%2B%25D0%25BE%25D0%25B1%25D0%25BB%25D0%25B0%25D1%2581%25D1%2582%25D1%258C%252C%2B%25D0%2592%25D0%25BE%25D0%25BB%25D0%25B3%25D0%25BE%25D0%25B4%25D0%25BE%25D0%25BD%25D1%2581%25D0%25BA&ll=42.166057%2C47.517153&z=13&rtext=47.520990%2C42.129665~47.531312%2C42.213358&rtt=auto

(48) Они тока между городами результат приемлимый выдают когда пробеги большие
Для одного города нужен учет пробок и способа перемещения

(49) по пробегу - это "суммарный пробег минимален, с учетом старта-финиша"?
а что значит "по количеству заявок"?
и какой вес каждого из критериев?

(50) Яндекс уже выдает время внутри городов по данным со своего навигатора и карт?

(53) по картам - да. есть даже коррекция на пробки.
но в любом случае, это штука ориентировочная.

(54) Хм надо будет попробовать, но без проверки в реале и хорошего запаса по времени не стал бы юзать.

(55)+ Да проверил по своим маршрутам частым, довольно точно причем с запасом говорит но без учета "диких пробок" от ДТП или еще чего.

(56)+ Т.е. выдает среднее значение, не учитывая время когда едем и часы пик.

(57) трехмерное планирование - это слишком круто...

(58) Ну хотя бы округленно по часам было бы еще лучше.

К примеру вот сейчас от работы до дома я могу доехать на авто за 25-35 минут легко. Но с 17:10 до 19:50 уже минимум час нужен, а если не повезет то и 2.

+(58) Хотя не удивлюсь, если яндексовцы сделают.
у ни ест же яндекс-пробки со статистикой-предсказанием...
Хотя и они не учитывают ливни, метеориты, загоревшиея пазики, приезды премьеров и прочих аналогичных...

(59)+ А яндекс пишет что 29 минут ))

(60) Ну ждемс ))

(57) я думаю нам среднее подойдёт

Garykom мне кажется я не поняла вашу идею

(63) Идея очень простая, платится некая сумма и получается результат, который тестируется. Потом при необходимости допиливается и в ответ остаток суммы. ))

(64+ Сумма потому что для скорости получения ответа в проге, придется предварительно запросить у яндекса и спарсить результаты по времени на маршруты между точками.
И далее это периодически обновлять чтобы смогли.

Есть вариант с разделением оплаты, часть исполнителю а часть яндексу за сервис https://tech.yandex.ru/maps/doc/tariffs/jsapi/index-docpage/

о каком размере оплаты исполнителю идёт речь?

бесплатной версии яндекс карт не хватит?

(67) Ограничения бесплатной лицензии https://tech.yandex.ru/maps/jsapi/ если в онлайне.

(66) Без ТЗ детального сложно прикинуть но от 10 до 25 т.р. за готовую систему с годовой поддержкой.
Сумма оценочная может у вас там 100+ мастеров и по всему югу РФ хотите кататься ))

(69) мелочишься?

(68)+ Да учтите что точность системы по оценке времени на поездки будет хуже на 20-50% чем через платную яндекс.
Со сути сдергиваем маршруты разные к себе и потом используя их пытаемся оценить время.

яндекс карты вроде в обычных формах не работают

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

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

(72) Работают прекрасно http://catalog.mista.ru/public/88304/

(74) никаких человекоресурсов.  СМС информирвоание с оговоркой  если Вы не сможете принять менеджера замера  позвоните по номеру ххххх   отмените замер.  и всё.  и полного обзвона нет

(76) Удачное и весьма удобное решение

(77) +можно дополнить автоответчиком с голосовым меню для отмены/назначения  другого времени замера из автопредложенных роботом

(76) мы сильно заинтересованы в том, чтобы не было отмены замера, поэтому так важно прямое взаимодействие с потенциальным клиентом

(75) "Отдельно хотелсь бы отметить, что обработка выложена здесь для ознакомления - лицензионное соглашение Яндекс.Карт не предусматривает применение API Яндекс.Карт на десктоп приложении. Если есть необходимость использовать данную обработку в коммерческих целях, Вам необходимо будет перевести ее в Управляемые формы, разместить на вебсервере 1C 8.2 и сделать доступной из сети Интернет."

вы там в скайпе отзовитесь

(81) Я бы отозвался но кроме вчерашнего спама "[28.07.2016 23:41:06] *** Пользователь Ирина Баранова хочет внести вас в свой список контактов Skype

Приветик)) )))) Ты такой приятный. Мне кажется получится приятное знакомство :) Добавляйся   http://kerecta.ru/lb1-d  ***"

Ничего нету ((

(80) Ну все логично, на декстопе низзя по лицухе, но можно сделать на УФ некий вебсайт и выложить в общий доступ, тогда типа не нарушает.

По факту авторизацию придется того или разрешить регаться для всех.

(79)Так об отмене речи не идёт идёт дополнительное оповещение сузающее рамки - что есть внимание к клиенту  чтобы он не торчал пол дня.  но если неприемлимо держите штат девочек