作者gawi (lala)
看板CSSE
標題[問題]多個車子routing 的最佳路徑
時間Mon Feb 25 00:42:11 2008
不知道有沒有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
1F：推 oohay:Lozovanu的文章,可能沒直接相關,你找來讀讀看 02/25 05:35
2F：→ gawi:非常感謝你，我看看~~ 02/25 12:53
3F：推 yoco315:運輸規劃上面很多這種問題，基本上NP 02/25 17:13
4F：→ yoco315:所以都是找近似解 :Q 那你就有一狗票方法可以用了 02/25 17:13
5F：→ yoco315:這種考慮 time window 的最短路徑問題 02/25 17:13
6F：→ yoco315:大學念運輸的時候還蠻常遇到，找運輸的paper還比較多資料 02/25 17:14
7F：→ gawi:這跟time window 不一樣吧? time window有限制時間要到達某點 02/25 18:38
8F：→ gawi:我上面的問題只已知某車的出發時間和從哪裡要到哪而已 02/25 18:39
9F：→ gawi:另外有沒有paper 可以參考 謝謝 :p 02/25 18:40
10F：推 oohay:不見得互斥,time window可能是一種方法 02/25 18:54
11F：推 yoco315:你v2v3定了,對v1就是time window.. 02/25 23:00
12F：→ gawi:感謝樓上的網友，總算有一點清楚了 02/26 00:48