脑洞车辆分配算法

[tivizi]

1. 有目的地d1, d2, d3
2. 有学生1000人，200人去 d1, 500人去 d2, 300人去 d3，去的 d1 需要3小时，去 d2 需要4小时，去 d3 需要5小时
3. 有50 人校车 5辆，30 人校车 10辆，10 人校车 10辆，载 1 人摩托车 10辆（这些车速度一致，不用考虑，只考虑用车时间）
4. 车辆可以复用，但每量车使用时间相差不超过 5 小时
5. 最快把学生运送到目的地

怎么安排这些车拉同学去目的地最佳？

最终根据这些前提推广为算法。即目的地数量可变，但每个目的地都有确定的用车时间，去每个目的地的人数可变，各种车的数量可变。

我正在想怎样分配最佳，大家也一起想想。

[tivizi]

主题排名太靠后了。。。

[yuruizhe]

不考虑空车返程时间的话，总运量 200*3+500*4+300*5=5900(小时人)
每批可以运送 50*5+30*10+10*10+1*10=660(人)
运输总耗时 5900/660=8.9 小时

不过“每量车使用时间相差不超过 5 小时”是啥意思？

[tivizi]

@yuruizhe 谢谢🙏

这个 5 小时是指：因为车辆可以复用，但不能一直复用某些车，而停用某些车，要保证每辆车用的时间都差不多，最多不能超过这个值