利潤最大化算法：解決方法/方法？（高級NP-Complete）

這個很難，所有的幫助真的很感謝！利潤最大化算法：解決方法/方法？（高級NP-Complete）

我知道這是一個NP完全，因此不能在多項式時間內解決，但尋找分析的幫助下，什麼類型的NP完全問題它減少了，它提醒你類似的問題，等等。

故事如下。我擁有與n卡車的冰淇淋卡車業務。有米停止在哪裏我交付。每個位置m _i已有p _i人在等我。買完冰淇淋後，大家都離開了。 p _i隨着時間的推移，越來越多的人排隊購買冰淇淋。

我怎樣才能找出下一輛卡車的位置，以便在任何特定的日子裏獲得最大的利潤？

事情要記住：

兩卡車停在相似的時間同一地點將只能獲得利潤一次，即在人離開後，一個卡車到達
卡車需要時間從一個地方到另一個
p _我隨時間增加每站，但有些站增加的比別人快，即一些地方是附近商場（位置，位置，位置）

我試圖減少這一個多機調度問題，旅遊銷售人員的問題，ILP等，但主要的問題是，p _我在每個位置（即TSP中的距離或調度問題中的作業長度）不斷增加。

在此先感謝！

來源

2011-12-07 Jason

p_i如何改變？每一個都是恆定的增長率（與時間成線性關係）？ –

Jason，在你的描述中缺少一些東西，因爲就像你說的那樣，它看起來像人們會永遠等待交付，所以當你把你的卡車送到交貨站時並不重要。該模型必須包含一個參數，該參數描述人們在離開前等待冰淇淋的時間等等;還有多少冰淇淋車可以容納的問題。否則就有一個小問題：你只有一輛卡車，晚上一晚通過車站，每個人都在等待一整天（TRAVELLING SALESMAN）。 –

這可能會更好地在cstheory.stackexchange.com – phs

聽起來像是Assignment Problem.的一個變種因此，您可能沒有考慮過的一種方法是Auction Algorithm（它具有可以輕鬆並行化的優點）或Hungarian algorithm。

我意識到您的問題存在併發症（總是存在！），但拍賣算法非常靈活。您的卡車和客戶之間可能有相當複雜的成本功能。您還可以調整算法，讓多輛卡車爲容量受限的多個客戶提供服務。

來源

2011-12-28 00:11:30

利潤最大化算法：解決方法/方法？ （高級NP-Complete）

回答

相關問題

利潤最大化算法：解決方法/方法？（高級NP-Complete）