共享汽车如何拼车

KeyTo9_Fans

我模仿zYr的拼单问题：https://bbs.emath.ac.cn/thread-15698-1-1.html

出了一道拼车问题：

----------

现在已经出了共享单车，我认为共享汽车也很快要推出了。

我们先假设$N$个人只有$1$辆共享汽车的简单情形。

这$N$个人有些会开车，有些不会，（考虑到第二问太难，第二问假设所有人都会开车）

但可以肯定的是，至少有$1$个人会开车。

现在这$N$个人和这辆（可以容纳$N$个人）的车都散落在地图的各处，

每个人都有一个起点和一个终点。

为了简单起见，我们使用“天圆地方”的假说，

也就是说，他们所在的城市是一个正方形的大草原，

没有任何障碍，车可以往任何方向开。

假设他们的步行速度是汽车的$1/10$，上下车是一瞬间的事儿。

问题一：如何使用这辆车，才能在最短时间内使得所有人从起点到达终点？

问题二：假设起点、终点、车辆都是随机地均匀地分布在这个城市里，问最佳策略下所用时间的期望值是多少？

zYr

我们不妨加一个限制条件
我们以这些人的上车顺序为这些人的编号1-N
设N个人中至少有两个人是会开车的，且第1号和第N号必须会开车
我们计算前N-1个人的用时总和
起始的时候第1号在车上
结束的时候第N号在车上（作为下一个迭代的第1号）

--------------------------
补充：计算时间和的时候应当计算加权时间 越早上车的人的权重越大

zYr

说句题外话 我觉得这个点评功能不好用

KeyTo9_Fans

楼主的问题还需要做些假设：

$1$、正方形的边长是$15$千米。

$2$、步行的速度是$1.5$米每秒。

$3$、开车的速度是$15$米每秒。

才能得到准确的答案。

#####

于是当$N=1$时，示意图如下：



通过编程可以求解问题二的近似答案，程序运行结果表明：

$1$、使用蒙特卡罗方法（$50$亿个样本），得到问题二的答案是$4138.79$秒。

$2$、如果没有车，那么问题二的答案是$2000/3*(2+\sqrt(2)+5*\ln(1+\sqrt(2)))\approx 5214.05$秒。

$3$、这辆车为我们节省了大约$1075.26$秒的时间，也就是大约$20.6224%$的时间。

$4$、我们有$45.2215%$的概率会用上这辆车，有$54.7785%$的概率直接步行到终点。

zYr

KeyTo9_Fans 发表于 2019-1-20 13:48
楼主的问题还需要做些假设：

$1$、正方形的边长是$1$千米。

我觉得这是一个调度问题 而且是实时连续调度
求出每一时刻最有效的调度策略 可以为行业发展提供理论支撑
而算个期望并没有什么用

说到这 我觉得这个问题可以用强化学习求个近似解了
将地图、乘客、车构成一个系统 随机生成适当数量的乘客
将某时刻系统状态作为神经网络输入 网络输出每个乘客该时刻的运动方向
计算每个乘客从起点到终点的加权时间 乘客下车时给予网络奖励 奖励的多少与该乘客的加权时间负相关

zeroieme

我觉得城市拼车更合理的假设是网格线路，移动距离按边长的整数倍n算。