[問題]多個車子routing 的最佳路徑

[gawi (lala)]

        不知道有沒有paper 是有關這種問題的
        我找了好久 還是沒有找到適合的

        問題如下

        給定一個網路圖
        例如說有  3台車子 V1,V2,V3 在網路的點上
        已知 V2 在時間0時，要從 B點走到A點 (B->C->E->D->A)
             V3 在時間1時，要從 D點走到A點 (D->B->E->D->A)

        則V1在時間2時，要從 F點走到A點
        怎麼走 才是最佳?


        V1走最短路徑可能不是最佳的路徑
        也就是說V1要走最不塞車的路徑就是


        謝謝各位囉?


--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 140.112.194.109
推 oohay:Lozovanu的文章,可能沒直接相關,你找來讀讀看
→ gawi:非常感謝你，我看看~~
推 yoco315:運輸規劃上面很多這種問題，基本上NP
→ yoco315:所以都是找近似解 :Q 那你就有一狗票方法可以用了
→ yoco315:這種考慮 time window 的最短路徑問題
→ yoco315:大學念運輸的時候還蠻常遇到，找運輸的paper還比較多資料
→ gawi:這跟time window 不一樣吧? time window有限制時間要到達某點
→ gawi:我上面的問題只已知某車的出發時間和從哪裡要到哪而已
→ gawi:另外有沒有paper 可以參考 謝謝 :p
推 oohay:不見得互斥,time window可能是一種方法
推 yoco315:你v2v3定了,對v1就是time window..
→ gawi:感謝樓上的網友，總算有一點清楚了