Как подойти к «проблеме коммивояжера» с изменением стоимости каждый раз, когда продавец приезжает в новый город - PullRequest
Новая
       53

Как подойти к «проблеме коммивояжера» с изменением стоимости каждый раз, когда продавец приезжает в новый город

0 голосов
/ 22 декабря 2019

Скажем, вместо нахождения кратчайшего пути мы должны максимизировать прибыль за год для продавца при следующих ограничениях.

  1. Продавец может ездить в другой город только по выходным, все будни недели он будет продавать в одном и том же городе
  2. Продавец имеет ограниченное количество топлива, поэтому он может посещать только городакоторые находятся в радиусе 300 (или любой другой постоянной) мили
  3. Каждый раз, когда продавец едет в другой город, он получает новые цены для каждого города за свой инвентарь, основанный на спросе и предложении в каждом городе. Для простоты можно предположить, что у вас есть цены для каждого города на каждую неделю, заранее решенные. то есть у вас есть матрица Nx52, где N - количество городов. Чем больше цена, тем больше будет прибыль.

Для дальнейшего упрощения можно предположить, что график ( G ) будет содержать N узлов и каждого узлабудет указывать на все города в радиусе 300 миль. 

class GraphNode:
    def __init__(self, locID, prices, close_locations)
        self.locID = locID
        self.prices = prices #List of prices in 52 weeks
        self.close_locations = close_locations #List of locations in 300 mile radius

Как решить эту проблему. Я не мог найти никаких ресурсов, чтобы начать решать эту проблему. Вот вопрос подобного рода, но это насколько я мог найти сходство: Как называется этот особый случай коммивояжера с динамическими издержками?

...