BusyMan1. Распределять заказы по маршрутам
...
3. Автоматическое распределение заказов по маршрутам на основе адреса доставкиЗадача множества комивояжеров. Имеет высокую вычислительную сложность. Когда-то давно-давно приходилось ее решать в рамках самописки (делал автоматизированную диспетчерскую для службы линейных радиомехаников предприятия, занимающегося ремонтом бытовой радиоапаратуры). Задача решается совмещением одновременно нескольких приемов вычислительной комбинаторики. Задача оказалась настолько сложной и интересной, что на базе этого алгоритма можно было дисертацию написать. :) Если есть интерес, как сделать своими руками, пишите на мыло.

BusyMan GaryaЕсли есть интерес, как сделать своими руками, пишите на мыло.
ОН скрыт :(Да нет, не скрыт. Просто защищен от спама....

BusyManКакие же недостатки в участочном подходе? (При делении города на сектора)Перед тем, как я взялся за решение задачи "множества комивояжеров" для диспетчерской, линейные радиомеханики тоже были закреплены за районами с фиксированными границами. В результате флюктуаций повышенного/пониженного спроса на услуги радиомехаников в различные моменты времени могло случиться так, что в одном районе механик перегружен, а в соседнем - мается от безделья.

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

Для того, чтобы изначально радиомеханики были привязаны примерно к одному району (но НЕ с фиксированными границами!), траектория их перемещения привязывалась к фиктивной точке в центре этого района. Наряды на текущий день линейные радиомеханики получали с утра в диспетчерской, после обслуживания последнего заказа имели право напрямую двинуть домой (что обычно и делали). Начальные условия для работы алгоритма еще ДО того, как принят хотя бы один заказ предполагали наличие начальной фиктивной траектории перемещения для каждого радиомеханика, состоящей из трех точек и двух отрезков: диспетчерская -> центр обслуживаемого радиомехаником района -> место проживания радиомеханика. Таких траекторий было столько же, сколько радиомехаников. Затем, по мере поступления заказов, в имеющиеся траектории включались новые заказы. При включении в траекторию запускался оптимизационный алгоритм, учитывающий текущую загрузку радиомехаников, повторные вызовы, модель телевизора/приемника/магнитофона и первичные признаки неисправности (по ним оценивается время ремонта и набор запчасти, которые необходимо взять на вызов). Время на перемещение вычислялосьс учетом метода перемещения - некоторые топали пешком, некоторые общественным транспортом, некоторые разъезжали на собственных автомобилях (им компенсировали расходы на содержание автомобиля), некоторым выдавали служебный автомобиль. После формирования всех траекторий фиктивная точка, обозначающая центр обслуживаемого радиомехаником района, из реальной траектории выбрасывалась - потому она и фиктивная, что служила лишь целям примерной группировки заказов изо дня в день в одном районе. Но при флюктуациях повышенного спроса на услуги из определенного района (например, при перебоях с электричеством, приводившим к сильным всплескам питающего напряжения, могла возникнуть флюктуация спроса на услуги по ремонту аппаратуры) оптимизационный алгоритм сам перераспределял в данный район еще одного-двух-трех радиомехаников таким образом, что они как бы на время "расширяли" границы своих соседних районов в сторону района с повышенной флюктуацией.

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

Сразу после того, как системе стал известен адрес, характер неисправности, что именно вышло из строя, и повторный ли это вызов, запускается расчет возможных вариантов включения поступившего заказа во "временнЫе полосы", шириной в 1 час, на которые разбит рабочий день радиомехаников, начиная от "сейчас", продолжая постепенно в будущее и заканчивая месяцем (заявки принимались только на месяц вперед). В процессе расчета у диспетчера высвечиваются временные полосы, по которым уже произведен расчет, с указанием возможности включения заказа в эту полосу. Если включение заказа в полосу приводило к недопустимому смещению во времени ранее принятых заказов (более чем на час), либо если для обслуживания заказов требовалась превысить рабочий день какого-либо радиомеханика более 8 часов, временнАя полоса считалась недоступной, в противном случае - доступной. Гляда на экран монитора, диспетчер согласовывал время прихода радиомеханика с клиентом и фиксировал в системе, в какой из доступных временнЫх полос ожидается приход радиомеханика, сообщал номер заказа и вешал трубку. Система фиксировала один из произведенных ею предварительных расчетов как окончательный, после чего ждали следующего звонка...

Были и проблемы (не очень существенные), связанные с возможностью поступления в диспетчерскую сразу нескольких звонков одновременно (всего было 4 оператора). Пока один диспетчер глядит на экран монитора и видит свободную временнУю полосу, другой диспетчер ее может занять и она окажется не свободной, когда первый диспетчер тоже захочет в нее же включить свой заказ. Но каких-то серьезных неудобств это не доставляло, поскольку происходило не так часто. Появлялось просто сообщение о том, что временнАя полоса только что занята другим заказом, и нужно было выбрать другую.

PS. Эх, молодость... :)
1988 год, г. Таллинн.
СМ-1420, TSX-Plus, Pascal, вместо СУБД низкоуровневые операции с файлами... :)