Расчет оптимальных маршрутов по карте

Цена договорная • наличный расчёт, безналичный расчёт, электронные деньги
14 мая 2018, 14:07 • 9 откликов • 64 просмотра
На вход есть:



1) ~500 точек (GPS-координаты магазинов в одном городе)

2) частота посещений каждой точки (каждый день, ВТ-ЧТ, ПН-СР-ПТ, раз в неделю, раз в 2 недели, раз в 4 недели - любой, но фиксированный день недели);

3) GPS-координаты стартовой и финальной точки, либо информация об их отсутствии

4) перечень выходных дней




Требуется дать сбалансированные маршруты посещений на каждый день на следующие 4 недели которые:

- посещают все точки согласно заданной частоте

- относительно равномерно распределены по дням

- начинаются и заканчиваются в заданной точке

- относительно оптимальны по суммарному километражу

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

получение расстояний предлагаем делать через
https://developers.google.com/maps/documentation/d...

Пример данных - во вложении, формат файла:
- ID точки;
- lat;
- lon;
- частота посещений;

Формат частоты посещений:
1 - один раз за все 4 недели, в любой день;
2 - один раз в две недели: любой но фиксированный день недели, например ПН первой и третьей недели, или ВТ второй и четвертой недели;
4 - один раз в неделю: любой но фиксированный день недели, например каждый ПН;
8 - 2 раза в неделю - ВТ, ЧТ;
12 - 3 раза в неделю - ПН, СР, ПТ;
20 - каждый день;

Для теста считаем что:
- рабочие дни с ПН по ПТ, СБ+ВС - выходные;
- дополнительных выходных нет;
- фиксированной точки старта и финиша нет.

Требуется предоставить:
- ежедневный маршрут на 28 календарных (20 рабочих дней) покрывающий заданные точки согласно указанной частоте оптимальный по расстоянию и сбалансированный по дням;
- километраж маршрута на каждый день согласно данным google maps

необходимо учитывать, что расстояние от точки А до точки Б на машине может отличаться от расстояния от точки Б до точки А




Файлы