[問題] 最佳分配的問題 jimshsu PTT批踢踢實業坊

作者: jimshsu (jims) 2013-12-30 00:58:05

最近遇到一個分類貨物的問題,
貨物n件, 每件配重不同,
貨車每台上限k公斤,
需要一次配送出門
求最少輛發車數的貨物分配法
請問這類問題是否有何種演算法或方式可以解?
謝謝!!

作者: yoco315 (眠月) 2013-02-09 03:48:00

這種問題用 GA 作弊最好了 QQ

作者: s89162504 (阿本) 0000-00-00 00:00:00

貨物有要照順序上車嗎?

作者: jimshsu (jims) 0000-00-00 00:00:00

沒有~~單純以最少發車輛的分配為考量

作者: tkcn (say) 0000-00-00 00:00:00

multiple knapsack problem抱歉，沒看清楚。沒注意到想求的東西不一樣。

作者: johnlinvc (阿翔) 0000-00-00 00:00:00

min-max flow

作者: DJWS (...) 0000-00-00 00:00:00

vechicle routing problem 論文和書籍都非常多是個大問題臺灣的話工業管理/物流運籌方面的科系有在研究這個問題

作者: adzen (忍仁) 0000-00-00 00:00:00

僅分配貨物到貨車上，不考慮貨車移動成本的話是multiple knapsack problem沒錯但實際運用會考慮移動成本所以應是 VRP。（俺曾經試著解 VRPTW 過orz

繼續閱讀