沒有容量和成本矩陣的多輛車

Question

我正在嘗試使用兩輛屬於同一類型的車輛在同一位置開始創建一輛VRP。我希望解決方案能夠以最具成本效益的方式爲問題中的每輛車創建一條路線。我使用GraphHopper來計算每個服務位置之間的道路距離和時間，並創建包含該信息的運輸成本矩陣。

我的問題是，所有的服務都放在一個路線，第二輛車從未使用過。在輸出中，我可以看到問題包含兩輛車，但解決方案只顯示一輛車的一條路線。

如果我設置了車輛的容量和服務的尺寸，我可以使用兩種車輛。我明白，如果我沒有說明他們，他們會被忽略，但會導致所有的服務使用同一輛車？

我錯過了什麼嗎？

如果需要，我可以發佈代碼示例。

謝謝！

Answer 1

沒有容量限制，使用單個車輛（如果滿足三角不等式，這是道路距離）將始終是最優的。換句話說，沒有容量限制的VRP = TSP。

想一下這樣：假設你有兩條路線，一條在城市A（在返回車廠之前）結束，另一條在城市B（離開車廠之後）開始。現在想象一下，從A到倉庫，從倉庫到B，從A到B添加一條腿，從而刪除這條腿。通過三角形不等式，c_AB < = c_A，倉庫+ C_depot，B，所以新解決方案比舊的。