Ключевые технологии для общего случая упомянуты тут (см. раздел "Часть 4. MVRP и пробки"). Более подробно мы обязательно расскажем, но это достаточно большая тема. Stay tuned :)
А еще в некоторых простых случаях можно решать задачу на основе алгоритмов из этой статьи. Приведу пару примеров.
Допустим, у вас есть заказ из точки A в точку B (обозначу его ). С помощью k-d-дерева можно решать задачу эффективного поиска "близких" заказов. Заказы и считаем близкими, если расстояние между и не превосходит , а расстояние между и не превосходит . Тогда, если всего в системе заказов, то можно пройтись по всем заказам, и для каждого из них за найти соседей по точке A в окрестности , и потом из найденных отобрать соседей по точке B в окрестности . Таким образом, для каждого заказа получим небольшое количество ближайших соседей, из которых можно составлять комбинации.
Можно назначать заказы не только на свободных исполнителей, но и на занятых, меняя им маршрут "на лету". В этом случае нужно учесть не только позицию исполнителя, но и точки его маршрута. С помощью k-d-дерева можно искать в каком-то смысле "близкие" маршруты (например, похоже на то, как я выше описал). А ещё прелесть в том, что с точки зрения Венгерского алгоритма назначение одного заказа можно делать как на свободных, так и на занятых исполнителей, при условии что правильно подобраны веса рёбер.
Спасибо за комментарий. Как я упомянул в конце статьи, у нас достаточно много алгоритмов, и здесь я не претендовал на полное и всеобъемлющее их описание. В частности, алгоритмы объединения заказов я не затронул совсем - это тема для отдельного большого рассказа.
Обычно такая "некомпактность" возникает из-за дополнительных ограничений при объединении заказов в один маршрут. Например: два заказа нужно доставить в один район, но один заказ ожидается днём, а другой — вечером. В этом случае доставить их подряд не получится, хотя точки их получения находятся близко друг к другу.
В этой я описал только алгоритмы поиска и назначения исполнителей. Алгоритмы объединения заказов — это отдельная большая тема.
Ключевые технологии для общего случая упомянуты тут (см. раздел "Часть 4. MVRP и пробки"). Более подробно мы обязательно расскажем, но это достаточно большая тема. Stay tuned :)
А еще в некоторых простых случаях можно решать задачу на основе алгоритмов из этой статьи. Приведу пару примеров.
Допустим, у вас есть заказ из точки A в точку B (обозначу его
). С помощью k-d-дерева можно решать задачу эффективного поиска "близких" заказов. Заказы 
и 
считаем близкими, если расстояние между 
и 
не превосходит 
, а расстояние между 
и 
не превосходит 
. Тогда, если всего в системе 
заказов, то можно пройтись по всем заказам, и для каждого из них за 
найти соседей по точке A в окрестности 
, и потом из найденных отобрать соседей по точке B в окрестности 
. Таким образом, для каждого заказа получим небольшое количество ближайших соседей, из которых можно составлять комбинации.
Можно назначать заказы не только на свободных исполнителей, но и на занятых, меняя им маршрут "на лету". В этом случае нужно учесть не только позицию исполнителя, но и точки его маршрута. С помощью k-d-дерева можно искать в каком-то смысле "близкие" маршруты (например, похоже на то, как я выше описал). А ещё прелесть в том, что с точки зрения Венгерского алгоритма назначение одного заказа можно делать как на свободных, так и на занятых исполнителей, при условии что правильно подобраны веса рёбер.
Спасибо за комментарий. Как я упомянул в конце статьи, у нас достаточно много алгоритмов, и здесь я не претендовал на полное и всеобъемлющее их описание. В частности, алгоритмы объединения заказов я не затронул совсем - это тема для отдельного большого рассказа.
Обычно такая "некомпактность" возникает из-за дополнительных ограничений при объединении заказов в один маршрут. Например: два заказа нужно доставить в один район, но один заказ ожидается днём, а другой — вечером. В этом случае доставить их подряд не получится, хотя точки их получения находятся близко друг к другу.
В этой я описал только алгоритмы поиска и назначения исполнителей. Алгоритмы объединения заказов — это отдельная большая тема.