PTT數位生活區 / CSSE (電腦科學及軟體工程)

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

看板CSSE (電腦科學及軟體工程)作者 (lala)時間17年前 (2008/02/25 00:42), 編輯推噓4(4推 0噓 8→)
留言12則, 3人參與, 最新討論串1/1
不知道有沒有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
推
02/25 05:35, , 1F
Lozovanu的文章,可能沒直接相關,你找來讀讀看
02/25 05:35, 1F
→
02/25 12:53, , 2F
非常感謝你，我看看~~
02/25 12:53, 2F
推
02/25 17:13, , 3F
運輸規劃上面很多這種問題，基本上NP
02/25 17:13, 3F
→
02/25 17:13, , 4F
所以都是找近似解 :Q 那你就有一狗票方法可以用了
02/25 17:13, 4F
→
02/25 17:13, , 5F
這種考慮 time window 的最短路徑問題
02/25 17:13, 5F
→
02/25 17:14, , 6F
大學念運輸的時候還蠻常遇到，找運輸的paper還比較多資料
02/25 17:14, 6F
→
02/25 18:38, , 7F
這跟time window 不一樣吧? time window有限制時間要到達某點
02/25 18:38, 7F
→
02/25 18:39, , 8F
我上面的問題只已知某車的出發時間和從哪裡要到哪而已
02/25 18:39, 8F
→
02/25 18:40, , 9F
另外有沒有paper 可以參考 謝謝 :p
02/25 18:40, 9F
推
02/25 18:54, , 10F
不見得互斥,time window可能是一種方法
02/25 18:54, 10F
推
02/25 23:00, , 11F
你v2v3定了,對v1就是time window..
02/25 23:00, 11F
→
02/26 00:48, , 12F
感謝樓上的網友，總算有一點清楚了
02/26 00:48, 12F
‣ 更多 gawi 的文章
文章代碼(AID): #17mPvaDV (CSSE)
CSSE 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 gawi 的文章
文章代碼(AID): #17mPvaDV (CSSE)