[問題] 最佳分配的問題

[jimshsu (jims)]

最近遇到一個分類貨物的問題,


貨物n件, 每件配重不同,
貨車每台上限k公斤,
需要一次配送出門
求最少輛發車數的貨物分配法

請問這類問題是否有何種演算法或方式可以解?

謝謝!!

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 36.225.77.220
推 s89162504:貨物有要照順序上車嗎?
→ jimshsu:沒有~~單純以最少發車輛的分配為考量
→ tkcn:multiple knapsack problem
→ tkcn:抱歉，沒看清楚。沒注意到想求的東西不一樣。
推 johnlinvc:min-max flow
推 DJWS:vechicle routing problem  論文和書籍都非常多  是個大問題
推 DJWS:臺灣的話  工業管理/物流運籌方面的科系有在研究這個問題
推 adzen:僅分配貨物到貨車上，不考慮貨車移動成本的話
→ adzen:是multiple knapsack problem沒錯 但實際運用會考慮移動成本
→ adzen:所以應是 VRP。  （俺曾經試著解 VRPTW 過orz
推 yoco315:這種問題用 GA 作弊最好了 QQ