Задача о коммивояжере, но со следующими изменениями:
- Измерение расстояния время в пути
- Не только края иметь веса - поэтому не только поездка в город занимает время, но также посещение города требует времени (проще всего добавить время пребывания в городе к каждому входящему краю)
- Есть награда присваивается каждому городу . Когда вы посещаете город, вы получаете его награду.
- Существует максимальный период времени, в течение которого города можно посетить (например, с 1 по 17 июня). Таким образом, максимальная сумма расстояние (в данном случае время ) ограничено .
- Момент посещения города может быть ограничен (например, y вы можете посетить Чика go только 4 июня .)
- Некоторые из городов могут быть помечены как обязательно . Вы должны посетить все обязательные города и любое количество необязательных городов (например, необходимо посетить Лас-Вегас )
- Конечный город может отличаться от начального, но должен быть (например, начальная точка должна быть в Вашингтоне, а конечная точка - в Лос-Анджелесе ). Итак, маршрут может быть нециклическим c.
Цель в этом случае - не минимизировать расстояние (время) путешествия, а максимизировать общую награду и соблюдение всех ограничений (общее время, момент посещения, обязательные города).
Я работаю над этим, но не хочу изобретать велосипед.
- Имеет ли описанная выше проблема какое-либо конкретное c имя ? (Например, Да, это проблема XYZ )
- Или это случай какого-либо известного типа проблем (например, да, , который относится к задачам оптимизации XYZ )
На данный момент я знаю только, что это связано с:
- проблемой коммивояжера,
- проблемой удовлетворения ограничений,
- (целочисленное) линейное программирование,
- Проблема маршрутизации транспортного средства с временным окном
Спасибо за ваши ответы и любую помощь. Просто изображение для лучшего понимания (случай 4 городов)