作者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