[问题] 最佳分配的问题 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

继续阅读