集智
导语

当我们开车去往商场等人群众多的地方时,邻近的停车位总是很难找到,我们到底该怎么寻找停车位呢?是随便找个位置停车,然后走很长一段路到停车场出口?还是花点时间找找靠近出口车位,然后轻松地走到出口?最近,圣塔菲研究所研究员发表了一项研究,给出了一个简单而且最优的“谨慎停车策略”。

数学使我们明智:

解决停车问题

就像数学揭示了恒星的运动和自然的规律一样,它也可以揭示日常生活中更为平凡的现象。例如,物理学家Paul Krapivsky(波士顿大学)和Sidney Redner(圣塔菲研究所)就使用数学来回答了一个古老的问题:在停车场中,最好的停车点在哪?
论文题目:

Simple parking strategies

论文链接:
https://iopscience.iop.org/article/10.1088/1742-5468/ab3a2a
在这项研究中,物理学家们将现实中的停车场简化为理想的单排停车场,如图1所示,汽车从最右侧进入停车场,找到停车位后,司机要步行到最左侧的出口。如果司机一进入停车场就准备停车,那么司机下车后要走很长一段路程;反过来,如果司机进入停车场后一直向前开,积极寻找靠近出口的停车位,那么下车后的步行距离就很短了。但不巧的是,靠近出口的停车场往往很抢手,司机们很可能会空手而归,把时间浪费在往返巡航上。
那么司机该采用什么策略呢?研究者对三种策略进行了建模,分别是:温和、谨慎和乐观策略。
集智
图 1:简化的停车场(黑色方块代表汽车,圆圈代表空位,汽车从最右侧进入停车场,司机下车后从最左侧走出停车场)

三种简单的停车策略:

温和、谨慎、乐观

  • 温和策略:汽车进入停车场后,将找到的第一个空位作为目标。如图2a 所示,汽车(红色方块)将停在第一个黑色方块的左边。
  • 谨慎策略:当司机找到第一个空位后,如果该空位左边还有空位,就将车停在该空位的左边;如果该空位左边没有空位,就继续往前开到头,然后回退到最靠近出口的空位。如图2b所示,汽车停在了入口处第二个空位处。
  • 乐观策略:司机一直将车开到出口处,然后回退到离出口最近的空位。如果回退到入口处还没有发现空位,则重复该过程,直到找到最靠近出口的停车位为止。如图2c所示,汽车停在了离出口最近的空位处。
采用温和策略的司机没有把时间浪费在找车位上,一旦有空位,他们就会停车,但是他们往往会错失出口处的空车位;而那些采用乐观策略的司机们就像赌徒一般,他们总是想在出口处找到空位,在不断的寻找中会浪费时间;采用谨慎策略的司机们则采用折中的办法,他们会驶过第一个可用车位,打赌停车场至少还有一个其他的空位。
那么在这三种策略中,哪种策略花费的时间最少呢?

集智

图 2:三种策略的示意图(红色方块代表新进入的汽车)

谨慎策略最终胜出:

驾驶员花费时间最少

研究者对温和策略进行了建模,在建模过程中观察到,温和策略似乎和微观动力学有某种联系。这一现象似乎告诉我们,自然界的万物有着千丝万缕的联系,而发现这一联系的有力工具就是奇妙的数学。
此外,对于乐观策略和谨慎策略,研究者使用了微分方程进行建模。为了更加简单的表述这一过程,研究者将这两种策略的时间代价进行了图形化,如图3所示。当停车场情况如图3a上半部分所示时,谨慎策略不需要回退,而乐观策略却需要一段回退的时间,因此谨慎策略花费的时间更少;当停车场情况如图3a下半部分所示时,停车场没有空位,两种策略都需要不断的回退寻找车位,花费的时间基本相同。
综合来看,谨慎策略花费的时间最少,乐观策略紧随其后,而温和策略则最差,因为它往往会在远离出口的地方停车,从而导致步行到出口的时间过长。

集智

图 3 (a)谨慎策略和(b)乐观策略的时间代价示意图

往期研究:淋雨时间

(步行时间)最短策略

关于停车场最佳停车位问题,在往期的一篇报道中(《抢车位中的机器学习与统计物理),中国学者傅渥成给出了一些有趣的见解。在该文章中,最优停车问题定义如下:假设你驾驶汽车开到一条单行道上,你准备去马路尽头的健身房。下雨了,你准备在路边停车,有些车位被占了,而有些车位空着,你应该用怎样的策略才可以尽可能少淋雨。傅渥成认为,下雨时,大家都想着不要淋雨,于是大家尽可能占据距离健身房最近的车。根据 Pauli 不相容原理(每个车位只能停一辆车),可以得到汽车的分布满足 Fermi 分布,通过建立一个 Logistic 将回归模型,就可以求解该 Fermi 分布的参数。

抢车位中的机器学习与统计物理 | 傅渥成

理论和现实的差距:

我们要考虑更多

简化的停车问题牺牲了许多实际的用途,从而换取数学的解答。例如,简化的停车问题没有考虑汽车之间的竞争,而且假设在每种情况下,所有汽车都遵循统一的策略。这些假设都是不切实际的,未来的研究一定要考虑更多现实的问题。尽管如此,这对于像 Render 这样的物理学家来说,这仍然是一种生活的乐趣。

作者:鄢鹏高

审校:刘培源

编辑:张爽

推荐阅读

元胞自动机揭示交通瘫痪成因:车多路窄惹的祸

Nature | 自动驾驶调度算法有望将出租车数量减少一半

抢车位中的机器学习与统计物理 | 傅渥成

加入集智,一起复杂!


集智

集智俱乐部QQ群|877391004

商务合作及投稿转载|swarma@swarma.org

搜索公众号:集智俱乐部

加入“没有围墙的研究所”

集智

让苹果砸得更猛烈些吧!

原文始发于微信公众号(集智俱乐部):集智