车辆载人交通调度模型最优化

markfang2050

AB两地相距1000公里，甲开车，时速40公里/小时；乙丙丁。。。等99人步行，时速5公里/小时。甲一次只能搭一人。问，怎么安排行程在最短时间100人都到达终点？计算出最短时间。（甲需要多次往返。假设只有甲会开车，不考虑车掉头，换乘，故障，加油等所耗时间。）

aimisiyou

逆向递推过程，最后的结果是甲开车载上一人追上前面98人且同时达到终点。假设甲离开98人反向去接一人时距终点距离为x,则此时最后一人距离终点为x+（1+5/40）*((x/5)*40-x)/2=4.9375x……

kastin

不管是步行还是车载，所有人都必须通过那个100公里路程，，而车在返程途中是空载，因此不能出现有人到达目的地白白浪费时间等其他人，也就是说，利用好返程空档，那就能提高运输效率。

假设车先载一人行 `x` 公里后，放下该人，让其继续步行，然后车再返程接下一个，那么车返回接人的时间没有白白浪费（因为前一个人也在行走而非等候）。接到下一个后继续将其运送 `x` 公里后恰好追上前面步行的那人，将其放下，二人同时步行。然后继续返程接送第三人……如此下去直到接送最后一人，恰好在终点处刚好追上前面九十八人。这就是最短的时间方案。

那么一个来回花费时间为 `x/40+(40-5)x/((40+5)40)=2x/45`，一共98个来回再加最后一段追及 `x` 公里的距离，因此有 `98\times 2x/45\times 5+x=100`，得 `x=180/41\approx 4.39`，共花费时间 `T=98\times 2x/45+x/40=1577x/360=1577/82\approx 19.232 \mathrm h `

markfang2050

kastin 发表于 2019-3-25 15:04
不管是步行还是车载，所有人都必须通过那个100公里路程，，而车在返程途中是空载，因此不能出现有人到达目 ...

大哥！1000/40=25小时。光车走就需要25小时了，你这样居然算出来比车走还快？对吗？

风云剑

他方法是对的，只是把1000看成100了。

markfang2050

kastin 发表于 2019-3-25 15:04
不管是步行还是车载，所有人都必须通过那个100公里路程，，而车在返程途中是空载，因此不能出现有人到达目 ...

此处有个问题：为何98个来回是最优？99个来回呢？

markfang2050

理解了

markfang2050

风云剑 发表于 2019-3-25 16:16
他方法是对的，只是把1000看成100了。

x/40 +(40-5)x/((40+5)40)=2x/45.这里的(40-5)x/((40+5)40)含义：第二人与车返回相遇时间：x-(x/40)*5=5*t2+40*t2=>t2=35*x/(40*45)

98次为何最优如何证明？

markfang2050

x/40+(40−5)x/((40+5)40)=2x/45此关系式多余；

kastin

markfang2050 发表于 2019-3-25 17:14
理解了

自己看时间-位移图吧（为了清晰起见，上图只显示了最开始的一部分结果）：

时间-位移

其中下面的黑线为未乘坐车的人群的运动轨迹图，上面绿线为乘过车的人群的运动轨迹图，绿点和红点的大小分别代表人群的数量。蓝色折线为车的运动路线，分别在两波人群间来回，两波人群都在步行。