根據其容量分配總線到路線

我在面向路線分配總線時遇到問題。我有四輛巴士和四條路線。根據其容量分配總線到路線

總線容量是每輛公共汽車的座位數量。路線容量是路線每個停靠點上的人數。路線實際上是多個站點的組合。

單個測試情況的一個例子是：

BUS CAPACITY   ROUTE CAPACITY 
BUS 1 44 Seats  Route 1 30 Peoples 
BUS 2 63 Seats  Route 2 50 Peoples 
BUS 3 14 Seats  Route 3 40 Peoples 
BUS 4 17 Seats  Route 4 17 Peoples

有很多的試驗例針對此問題的多種組合。路線和巴士的數量總是相等的。

我正在尋找一種算法，幫助解決這個問題的最佳。

來源

2017-06-03 Talha Malik

您的問題顯示路線1四次？你試圖優化什麼成本或優點功能？你有什麼試圖解決你的問題？ –

我通過尋找最近的公共汽車和路線之間的差異，然後指定最近的巴士路線，但它沒有幫助，需要任何其他解決方案是有道理的 –

嘗試

https://en.wikipedia.org/wiki/K-nearest_neighbors_algorithm

或

https://en.wikipedia.org/wiki/Euclidean_distance

方法基本上你正在尋找最佳匹配。

通俗地說，你可能想要做的是找到一條公交車的最佳匹配路線，其中最佳匹配定義爲公交線路的容量最佳，即busCapacity - routeCapacity爲最低正數。

一旦你找到這樣的匹配，他們將從問題世界中消除。

然後對剩餘的世界重複這一點。

最終產品是一切都匹配。

但是準備意想不到的： -

您可能會用盡所有可能的組合和左小容量和大容量的路由。在這種情況下，您可以查找routeCapacity - busCapacity之間的差異，作爲最佳匹配。

這是這樣，你給的人的數量知道他們不能服務是最小的。

來源

2017-06-03 20:56:30 bhantol

當我告訴多個測試案例這意味着給定的例子可以有各種這並不意味着我必須從多個測試用例中選擇最佳匹配。你提到的算法對於這樣的問題是有好處的，但是在我正在研究的那個上，我必須找到最適合個人測試用例的方式，比如說給定的一個我必須找到最佳匹配。如果你發現對這樣的問題有任何想法，那意味着很多我。對不起，任何誤導。 –

我建議你描述一下沒有用的測試用例，但更重要的是你試圖解決這個問題。因爲在你的問題中，你基本上要求'我在分配公共汽車到路線時遇到問題'。我提出的算法是一般性地解決這個問題。我們大多數人都非常注重代碼，所以我們可以幫助完善或修復一些代碼。請不要擔心誤導。 – bhantol

我還沒有爲此編寫代碼，因爲我在製作邏輯時卡住的很糟糕，我所嘗試的實際上是減去容量，然後找到最近的距離，以便我可以將總線分配給路線，但是我不滿足於此解決方案，需要任何其他方式來做到這一點。我已經看了你的建議算法教程，其中組織問題已經解決。可能你對這個問題很熟悉，我不認爲它可以幫助我。事實上，我沒有得到關於我的問題的歐幾里德方程。如果您可以將給定的數據設置爲等式，以便我能理解它。 –

你實際上並沒有說這裏有什麼最佳方法，這可能會改變最佳解決方案，但我會傾向於對路線和巴士進行排序，然後將最大的巴士分配給最多的路線等待的人數，等待次數最多的路線中次最大的公共汽車，等等。

如果一條路線被分配了一條公共汽車，但沒有足夠的座位給路線上的人，但在這項任務中，所有擁有更多座位的公共汽車都會被分配到更多人的路線等一等，所以給一輛更大的公共汽車，至少可以讓沒有座位的其他人也能享受到。

匹配人民和公共汽車的一個更復雜的方式看https://en.wikipedia.org/wiki/Assignment_problem

的最佳定義是如何改變的事情的一個例子是，如果你不關心的人惱火的數目，但對於路由的數量人們沒有座位。在這種情況下，如果你有2,3,5,9人在等候的路線和可以搭載1,2,4,8人的公共汽車，那麼將它們分配爲2人-2座位，3人-4座位，5人8座，9人1座，8人無座位而不是4人，但所有這8人只有一條路線。

來源

2017-06-04 05:29:23 mcdowella

根據其容量分配總線到路線

回答

相關問題