Мне нужно реализовать алгоритм планирования для оценщиков имущества, чтобы они посещали несколько (как правило, <10) сайтов в день и проводили некоторое переменное количество времени, выполняя работу. Если бы это было просто вопросом выполнения работы в любое время дня и определения близкого к оптимальному маршрута и расчета времени работы + времени в пути, чтобы увидеть, возможно ли это в день оценщика, это было бы простым использованием TSP , Мы используем OSRM сервер. </p>
Большая разница в том, что некоторые задания должны быть запущены либо в AM, либо в PM, и, кроме того, некоторые задания должны начинаться в определенное время.
В настоящее время я просто использую грубую силу и матрицу времени прохождения от OSRM. С каждой комбинацией я резервирую фиксированное время, перебираю комбинации сайтов и ищу наиболее оптимальное с точки зрения времени прохождения решение. Код отклонит любые новые добавляемые задания, если они превысят рабочее время оценщика. Работает нормально до 10 рабочих мест.
Теперь, с добавлением возможных срабатываний клавиш (для доступа к собственности) и выпадений клавиш, количество остановок легко превысит 10, а грубая сила займет слишком много времени.
В другом посте аналогичная проблема была названа проблемой маршрутизации транспортных средств с временными окнами. (http://en.wikipedia.org/wiki/Vehicle_routing_problem), хотя это не относится к фактическому времени, проведенному на месте.
Я все еще мог бы применить грубую силу, если бы просто рассматривал раскладки клавиш и выпуски как часть самой работы. Таким образом, любая работа с ключами будет просто маленьким треугольником времени вождения + рабочего времени, но сама по себе рассматривается как одна остановка. Я думаю, что было бы безопасно продолжать использовать грубую силу в этом случае, так как это задания, которые занимают некоторое время, наряду с временем вождения, поэтому фактическое количество заданий в день должно быть <= 10. Я полагаю, в краю - случаи, в которых может быть максимальное количество рабочих мест в день, и система просто будет искать другого оценщика. </p>
Пример:
JOB | Time | Duration | Constraint
A: | 9:00 AM | 45 mins. | None. Any time of the day. No key pickups. |
B | 10:00 AM | 30 mins. | Fixed appt of 10:30. Key pickup and drop-off time of 15 mins.
C | 11:00 AM | 60 mins. | Must be done in AM
etc for PM...
Должен ли я продолжать использовать метод грубой силы, рассматривая раскладки ключей как своего рода «спутниковую» группировку, а также просто называя это днем (для этого оценщика), когда задания (и, следовательно, возможные перестановки) превышают 10 ( что должно быть редко)?
Или существует какой-то алгоритм, в котором могут быть заданы временные диапазоны (для 9-12 часов утра, для фиксированных заданий, например, 10: 00-10: 00) и время выполнения заданий (50 минут) (при подборе ключей, возможно, 10 минут каждый) что определит довольно оптимальные маршруты на день?