j**********i
发帖数: 3758 | 1 我以前做过匹配问题，失败了，当时想的太大太好，价格下不下来，而且算法
复杂性不能承受。匹配问题是为了解决18-65岁上下班/上下学的问题。
年纪再大一些的人建议使用电动车。
现在条件可以限制一下，以后再扩。
给定地铁停靠站半径为5公里的圆盘的匹配问题。
这样，就可以把顾客的要求分类，在同一类里进行匹配，计算量就小的多。
matching problem 的第一个应用是给定一个request pool（一个区域）。
每一个request 的结构是这样的（ID（姓名），出发点，目的地，要求用车的时间范围）
也就是说，头天晚上，有一大堆人打电话或发Email到调度中心要车。那么调度中心
就必须在第二天早上前把匹配信息发给司机。比如
Mr A，Mr B，Mr C，Mr D，Mr E，Mr F 都要到地铁站PP，这些人居住接近都在地铁站
5公里半径内，都要在8：00-8：05分出发。计算机把这些人挑出来，给司机J，J就在早
上花10分钟时间把这些人准时 8：15分送到地铁站PP就不用管了。
同时，我们也知道Mr O，Mr P，Mr Q，Mr R，Mr S，Mr T会在8：35分在地铁站
LL下车出站。消息已经给了司机Y，司机Y就在9：00把这些人送到各自的公司。
这就是匹配问题。匹配的pool很大，估计一个城市所有的pool里的数量会有
20000-40000人。目的是要让这些人能够舒适准时到达公司。都是短途的运送。
最容易的匹配问题是一辆车搭载一个人，总能满足要求，但是价格下不下来。
如果一辆车一次运最多6个人，每人出2美元，这是容易被接受的，而且很可能还能
从公交那里得到补贴。每人掏1.5美元。这就相当有商业价值了。
一般能搭载3人的出租车也可以使用，复杂性小一点。但是我们的问题是pool里的
数据多而且不一致，就不可能完全达到6人标准。
人数少能保证效率，人数多能保证价格，就是在细微的变化里平衡。
因为各人居住的都很分散，要一个接一个pick up，需要一点时间。时间限制
整个应该在15-20分内完成。
这就是一个完整的算法问题了。
由于顾客的需求产生的request pool是常常变动的，有人会取消固定出行，也有人
会突然加入出行，这就需要从新计算和调整，目的是保证整体出车质量和个体出
车效率。
首先，我们考虑的是能减少算法的复杂性，如果算的很快，动态路游都可以使用
这个算法。有些固定模式可以加以保存和利用。
我觉得归并算法比较好。假设有N个客户，先给每个客户一辆车。因为目的地是一
个（地铁站），一遍扫描以后，就可以形成小一些的一系列组合（分类），每个
组合里的人的出发时间是比较接近的。我们要计算好完成这些工作的每辆车的时间，
及返回时间。
一般上班时间都在7：30am到9：30am。我们需要保证大多数顾客整个上班过程
在45-50分钟之间。这就在两头需要压缩到各15分钟的条件限制。在地铁上给15分钟。
但是这是粗略的框架。实际上还有进站等车和出站时间。我们依据的是地铁标准时间，
而且确信地铁准时。这不完全可能，所以要有灵活的应变。在出站口的小巴/出租车数量
要多一些。上面分类的时间片是以地铁到站时间加上顾客进地铁时间向前推为小巴到达
地铁站时间，这是一个严格的时间要求。
也就是说，在7：30am到9：30am有多少趟地铁班次，就有最少多少班小巴出行，
当然，小巴数量不限。
目前，在亚特兰大地铁是10分钟一辆，以后可能增加到6分钟一辆。这不要紧。要紧的
是小巴的分类。只有按时间分类以后，才可能归并需求。
######目前#######
我们可以假设一个地铁停靠点附近每天早上有300个需求，按12个时间片分成
12类。每个平均25个顾客，多的时候会有70-100个顾客。这就需要30辆这样的小巴
在随时待命。如果有20个地铁站，就需要1000辆左右小巴。乘以二应该有2000辆车
准备。这是可以负担的。需要的是优化小巴的路径和pick up 次序以保证时间。
在价格上是能得到保证的。300个需求产生的费用是50-100元次小巴出行，产生的费用
是250美元到500美元，平均每人花1-2美元，出租车司机得到8美元到16美元。这个还有
不小调整余地。关键是调度合适以后价格是对的，只是数量有点问题。
如果我们能保证每个司机在早晨和晚上各挣到20美元，余下的时间都有解决办法。
因为亚特兰大的司机的收入依靠两个来源：机场旅店，和周末的酒吧。这些司机在早晨
很少能在地铁线接到客人，这对司机来说是额外收入。我们只要能保证司机平时收入在
100美元就可以完成拟合。
在不增加地铁线路的条件下，我估计增益将会是有限的，因为增益将完全来之调度和
线路优化。我们改变的小巴的频率，能够获得的是固定线路动态的需求。当然，我们
也可以细致地分析这种结果。 |
j**********i
发帖数: 3758 | 2 我们换一个角度去分析亚特兰大的公交系统。
亚特兰大的公交系统完全是以美国式的居住条件环境设计的，而且目前完全是以
地铁站为重心的公交体系。地铁强调准点，公家大巴也强调准点和地铁衔接。这
是非常好的做法。
但是缺点是地铁线路过长。公交停靠站之间过远。公交班次太少，只有在上下班
高峰期间才有半个小时一班车。误了班次，就要完蛋，走路太不可行。
即使能够准点衔接上，上班回家耗费时间过长。一般都要在半个小时到一个小时
之间，有的要在一个小时以上。这种交通是没有效率的。
不要说是对于穷人，对于刚到美国的学生都是一种折磨。头一个学期，经常回家
以后倒头就睡，经常晚上到家时已经9：00，累得要死，什么都不能干。后来观察
到黑人和其他穷人，也是这种状态。
对比南京这里，单位社区面积相对小，几步路就到了公交车站，基本上绝大多数
公交车是6分钟一班，随到随上，不用赶车。当然，这是城市小的原因。但是，这
里更重要的是城市效率。
美国的公交大巴都十分安全结实，可是如果没有效率，空载太多，再安全结实也
是摆设。亚特兰大的地铁班车显然比公交大巴频繁。如果完全不增加地铁线路的
条件下，只改动公交线路要求显著增益将会十分困难。
强调准点是西方的哲学，但是人尤其是穷人不是那么守时的，要是都有严格的纪
律观念和有条理，可能还不会那么穷。同时，日常生活里还有各种突然时间导致延迟。
公交线路的设定也不是没有研究的。我想这一方面的工作可能是可靠的。
缺点在于，顾客流量变少的时候，完全维持原状，就亏了许多。当然，无端增加
小巴去提高频率，在美国要增加工人工资和小巴投入，这一点，亚特兰大公交系
统的管理人员也不一定愿意。
为什么造成这种尴尬的境地呢？公交地铁线路太少，不可能用于“主干线”交通。
许多线路必须走长距离，为了给穷人提供机会。但是这种长距离交通时间太长，效
率太低。太长距离的穿行，对于没有那种要求的人是无用的。同时，公家车也和地
铁一样存在一个重要的“半径”问题。即使是穷人，也不愿意长途步行到公交车站
去等10分钟车。这在冬天和雨天尤为难受。那么逼迫更多人去买2000-3000美元的
二手车。最终既减少了公交车的客流量，有堵塞了公路交通。
结论是美国的城市过大，交通站点衔接出了毛病，导致人们涌向私家车市场，导致
燃油消耗过度，导致交通堵塞。出的问题就是那个伟大的“半径”问题。住的分散，
行走到站点路程就长，以公交停靠站点为圆点的在有限体力容许的行走半径里的人
群数量就少。公交车的流量少到就可以计算出来了。需要的是提高这个有效半径的
长度和乘车办事的方便程度。
我估计，加密公路不太现实。电动车到更现实一点，但是电动车有无法长距离交通。
除非电动车开到地铁站能自动返回，而人下了地铁，多数情况下又需要有另外一辆
电动车等在那里。增加混合动力车，也会造成交通堵塞。现在的主干道几乎都已经
堵上了。
在大城市里增加长距离交通是为了给固定居住的人们提供更多的工作机会。
但是用出租车把顾客拖到公家车站上去，有点奢侈。顶多把顾客拖到地铁站上去。
所以，我想还是增加地铁站合适。顶多是把地铁站的有效半径扩一扩。在居民区扩
到5公里，在商业区扩到3公里，这样可能好一些。穷一点的居民区可以加多加密短
途高频公交小巴的使用。富裕一点的居民区，可以使用动态进入小区的小巴。有30
个站点以上并有环线的地铁，就可以覆盖800到一千平方公里，这是一个很大的数，
至少可以覆盖亚特兰大60%的市内面积。
当然，这还要取决于地铁速度很高。这不算增加太多能源。
黑人小孩很羡慕南京的交通。这不难，只要公交车站里家里300米以内，公家车频繁
到6分钟一班就可以做到了（尽管这要算乘客密度）。但是，我怀疑还是有人会不愿
意走路，南京这里的人有了钱，也不愿意多走路了。南京这里的汽车保有量在10年
里暴涨了5倍以上。
所以，我还是长期看好地铁。或者按照女王的说法：火车。
最后还是可能需要动态调度车辆。
只要能稳住出行的总燃料消耗，效率能提高多少就可以调高多少。
也即使：约束条件是总燃料消耗。关于这一点，不知道美国出租车使用燃气以后会有
多少弹性。我试过带自行车上公家，这不现实。电动车也一样不现实。
最头痛的是那个半径，半径小效率高，半径大，头痛。 |
j**********i
发帖数: 3758 | 3 shopping好解决，弄个有锁的箱子，让人deliver就行了。
实在不行，每个星期买一次。或者小的7eleven开到社区。
那么，万一美国人选择让那种没有太大动力的电动车普及，让家庭主妇
和老年人使用，会不会改变城市结构？会的。
但是地铁在亚特兰大仍然需要增加一条环线。
因为长距离的交通任然有必要，而且对于一些人仍然需要。
这样也可以约束燃料消耗。 |
j**********i
发帖数: 3758 | 4 http://en.wikipedia.org/wiki/Assignment_problem
这个东西有点象。我还没做到那步。
我有一个半径的约束条件，有一个价格的约束条件。
有一个时间的约束条件。时间和半径是有很强关联的。
价格也有关系，因为载客人数多，价格就可以下来，用的车也可以小一点。
但是复杂性主要是和那个半径关联太大。
半径究竟是多大才合适是问题的关键。这个半径现在肯定是可以扩展到
要比人的自然步行感觉承受的距离要大，但是究竟是多大才合适？
连地产商都撑长了脖子要看。
这个要保密，要不然都不交钱了。
我笨，还不行吗？
这个半径也不大，因为一到小路上去，车速就低，和自行车差不远。
关键是地点不一样，就很难办。
美国人都不愿意走路。这要看实际上的路况了。而且要看建筑分布。
半径要是小于一公里，意义就不是太大了。
jpost的结论是美国主干道之间的距离太大，可能应该在600米到1公里之间为好。
也就是说，一个街区的大小要在一平方公里以内好一点，这样，出租车可以开进去，
而且没有交通安全隐患。太多人住在一个大院里不好办。这是美国的一个大麻烦了。
参照“我们家的那条街”的距离。
http://www.mitbbs.com/pc/pccon.php?id=11729&nid=241033
我不知道美国的煤炭还能支撑多久，公开的资料也是每年几亿吨。这是一个不小
的数据，尽管美国的能源储备是世界第一的。但是目前仍然处于贴补状态。
对于长期考虑，这似乎逼迫美国必须改善交通体系。但是也许改动不是想象的那么大。
在局部地区改动可能就行了。因为对于交通能源优化的最大推动是来至城市布局和
地铁。也许仔细考虑过的改进要比盲动好的多。但是目前看不到实质性的危机。
但是人们也不喜欢交钱。 |
j**********i
发帖数: 3758 | 5 这个半径里面学问太大，北方的城市和南方的城市，这个半径都会不一样。 |
j**********i
发帖数: 3758 | 6 考察中国的地铁线路设计，所有的亏负都亏在这个半径上。
这是在有巴黎，伦敦，柏林，莫斯科，东京以后的设计产品。
都失误了。这个不怪我，反正有人背。
看看南京的地铁交通，我就知道北京和上海都没有利用双层地铁。
这是极不应该的。 |
j**********i
发帖数: 3758 | 7 http://baike.baidu.com/view/73673.htm
这是上海的规划，我家里还有80年代上海的地图，当时上海
因为缺钢铁，不要说是浦东，连个过苏州河的桥都没几座，
苏州河以北许多地区都无法开发。现在偷到了一堆钢铁，就拼命用。
中共中央还吹嘘给老百姓改革的红利，这种红利都是
澳大利亚的红利，有什么可吹嘘的呢？澳大利亚能撑中国几百年？
上海的地铁无论如何都没有太多效率，投入这么大，又有哪来
缘自自己的贡献呢？
上海的改革成果，还没有老百姓以前骑自行车的成果大。
我倒是建议长春的地铁就完全停下来，想一想怎么办。不要学其他地方。
中国不是所有地方都可以玩弄政治白捞钱的。但是不见得要玩弄政治
就过得好。
过度的货币发行，将导致无法控制的困境。在目前的情况下，继续在中国
给大城市增加投入，未来无论怎样增加地铁都无法保证平衡。
但是在中国，每一个大城市的过度投入，都和政治有千丝万缕的联系。
从陈希同，到陈良宇（所谓上海帮的替死狗），到薄熙来，几乎每一个有
影响的执政官都可以给当地带来巨大的收入。但是，即使是薄熙来，他
应该想一想，重庆人的道德水准是否足以带来回报？ |
j**********i
发帖数: 3758 | 8 “我们必须知道，我们必将知道”。希尔伯特讲这句话的时候，
我们还相信他的这种精神。可是对于许多给中国开空头支票
的政治家，尤其是那些躲在背后，利用政治的小人物,这句话
就一点也不能讲。不提醒一下，以后就用的精光，都去喝西北风。
科学的最后是真理，而真理却不可能被小人物利用。
我不相信中国可以持续30年，每年投入10亿吨的煤炭。也绝对看轻
人民网和中央电视台的吹嘘。即使中国立刻破产，这些“媒体人”
都会有新的“热情和专注”。也会有新的主人。 |
