Это сложно, поэтому вся помощь очень ценится!
Я знаю, что это NP-Complete и, следовательно, не может быть решена за полиномиальное время, но ищу помощь в анализе, какой тип NP-Complete проблемы этосводится к аналогичным проблемам, о которых напоминает вам, и т. д.
История выглядит следующим образом.Я владею бизнесом по производству мороженого с n грузовиками. m остановок, где я делаю поставки.Каждое местоположение m i имеет p i людей, ожидающих меня.После покупки мороженого все уходят. p i увеличивается с течением времени, когда все больше людей выстраиваются в очередь за мороженым.
Как определить, куда следует отправлять грузовики, чтобы максимизировать мою прибыльв любой конкретный день?
Что следует иметь в виду:
- Два грузовика, которые останавливаются в одном и том же месте в одно и то же время, будут получать прибыль только один раз, т.е. люди уходят после одногогрузовик прибывает
- Грузовикам требуется время, чтобы добраться из одного места в другое
- p i увеличивается со временем на каждой остановке, но некоторые остановки увеличиваютсябыстрее, чем другие, т. е. некоторые местоположения находятся рядом с торговыми центрами (местоположение, местоположение, местоположение)
Я пытался свести это к проблеме планирования нескольких машин, проблеме с коммивояжером, ILP и т. д., но основнойпроблема в том, что p i в каждом месте (т. е. расстояние в TSP или длина задания в задаче планирования) постоянно увеличивается.
Заранее спасибо!