V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
tivizi
V2EX  ›  程序员

脑洞车辆分配算法

  •  
  •   tivizi ·
    tivizi · 2020-07-27 16:18:31 +08:00 · 838 次点击
    这是一个创建于 1340 天前的主题,其中的信息可能已经有所发展或是发生改变。
    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
        1
    tivizi  
    OP
       2020-07-27 16:20:20 +08:00
    主题排名太靠后了。。。
    yuruizhe
        2
    yuruizhe  
       2020-07-27 22:02:35 +08:00   ❤️ 1
    不考虑空车返程时间的话,总运量 200*3+500*4+300*5=5900(小时人)
    每批可以运送 50*5+30*10+10*10+1*10=660(人)
    运输总耗时 5900/660=8.9 小时

    不过“每量车使用时间相差不超过 5 小时”是啥意思?
    tivizi
        3
    tivizi  
    OP
       2020-07-28 07:26:23 +08:00 via iPhone
    @yuruizhe 谢谢🙏

    这个 5 小时是指:因为车辆可以复用,但不能一直复用某些车,而停用某些车,要保证每辆车用的时间都差不多,最多不能超过这个值
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   5850 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 29ms · UTC 02:00 · PVG 10:00 · LAX 19:00 · JFK 22:00
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.