В настоящее время я делаю игру в Unity, где мне нужно иметь возможность создавать маршруты для транспортных средств. Единственные ограничения, которые у меня действительно есть:
- Каждое здание города должно быть посещено транспортным средством один раз
- Все транспортные средства отправляются из одного места
- Рабочая нагрузка должна быть распределена (ie, каждое транспортное средство должно посещать некоторые здания, не обязательно должно быть абсолютно одинаковым)
Я знаю, что эта проблема, по сути, является VRP, который является NP-сложным Однако я не слишком беспокоюсь о поиске оптимального решения, так как игрок будет контролировать ручную или автоматическую генерацию маршрута c для каждого транспортного средства. Было просто интересно, сталкивался ли кто-нибудь еще с этой проблемой, особенно в Unity, и как к ней можно подойти. Я знаю, что мне нужно использовать структуру данных для ручной маршрутизации, которую также можно использовать для генерации маршрута.