算法与理论计算机2015arxiv.org
FedEx 问题
The FedEx Problem
进阶 · 约 30 分钟读完前置知识：几何中位数/设施选址、基础微积分、美国地理与人口分布
导读
这篇论文研究美国航空货运枢纽的最优选址问题：在全国人口分布下寻找使得到各地平均距离最小的地点。作者算出的最优点位于印第安纳州格林县附近（约39°N, 87°W），其到全国人口的平均距离约为795英里，优于孟菲斯的843英里；评论还指出该点与UPS路易斯维尔枢纽和FedEx后来在印第安纳波利斯的二级枢纽位置相近。
HN 关注点：一个纯地理优化算出的“理论最优点”，与FedEx/UPS实际选址所受的机场、天气、劳动力和监管等现实约束之间有多大差距。
HN 评论精选
这几条评论里：补充 2 亲历 2
亲历现实选址远不止平均距离，需同时满足机场、天气、停机坪、劳动力、监管、跑道等十余项约束，最终候选只剩孟菲斯、辛辛那提和堪萨斯城等少数地点。
是的，在FedEx，我们考虑过这个问题大约三秒钟，然后就注意到我们还需要：(1) 枢纽所在地有合适的现成机场；(2) 当地天气好，比如雪、雾、雨相对较少；(3) 有良好的停机坪空间，即飞机停放和维护、包裹分拣的地方；(4) 良好的劳动力供应，比如分拣中心所需人力；(5) 相对较低的生活成本以压低价格；(6) 友好的监管环境；(7) 候选机场不能太繁忙，比如不希望到达飞机长时间盘旋才能降落；(8) 机场侧风相对较少，且有不止一条跑道可在有风时备选；(9) 跑道海拔不能太高，以免限制最大起飞总重，比如排除丹佛；(10) 跑道端附近没有高山等高大障碍物；(11) 喷气燃料供应良好；(12) 有良好的公路接入，方便18轮卡车在卡车与飞机之间交换包裹，比如部分货物可卡车运到枢纽储存，再直接由飞机送往客户，支持晚上11点下单、次日上午10点前送达。所以大约只有三个候选地点：孟菲斯，以及我记得的辛辛那提和堪萨斯城。孟菲斯机场跑道旁有一些二战旧机库，FedEx可用于分拣中心、飞机维护和总部办公……
graycat查看英文原文
Yes, at FedEx, we considered that problem for about three seconds before we noticed that we also needed: (1) A suitable, existing airport at the hub location. (2) Good weather at the hub location, e.g., relatively little snow, fog, or rain. (3) Access to good ramp space, that is, where to park and service the airplanes and sort the packages. (4) Good labor supply, e.g., for the sort center. (5) Relatively low cost of living to keep down prices. (6) Friendly regulatory environment. (7) Candidate airport not too busy, e.g., don't want arriving planes to have to circle a long time before being able to land. (8) Airport with relatively little in cross winds and with more than one runway to pick from in case of winds. (9) Runway altitude not too high, e.g., not high enough to restrict maximum total gross take off weight, e.g., rule out Denver. (10) No tall obstacles, e.g., mountains, near the ends of the runways. (11) Good supplies of jet fuel. (12) Good access to roads for 18 wheel trucks for exchange of packages between trucks and planes, e.g., so that some parts could be trucked to the hub and stored there and shipped directly via the planes to customers that place orders, say, as late as 11 PM for delivery before 10 AM. So, there were about three candidate locations, Memphis and, as I recall, Cincinnati and Kansas City. The Memphis airport had some old WWII hangers next to the runway that FedEx could use for the sort center, aircraft maintenance, and HQ office space. Deal done -- it was Memphis. That's how the decision was really made. Uh, I was there at the time, wrote the first software for scheduling the fleet, had my office next to that of founder, COB, CEO F. Smith.
补充论文算出的最优点在印第安纳州格林县，平均到人距离优于孟菲斯，且靠近FedEx二级枢纽和UPS路易斯维尔枢纽。
文中埋没的重点：“我们发现最小值为(39°, 87°)，位于印第安纳州格林县，印第安纳波利斯西南约70英里。从该点到全国任何人的平均距离是795英里，而到孟菲斯的平均距离是843英里。有趣的是，随着FedEx成长，它建立了一些二级枢纽，其中之一就在印第安纳波利斯。此外，这个最优点距离UPS主要枢纽所在地路易斯维尔西北仅约85英里。”
iandanforth查看英文原文
Buried lead from the article: "We found the minimum to be (39◦, 87◦), a location in Greene County, Indiana, about 70 miles southwest of Indianapolis. From this point the average distance to any person in the country is 795 miles, while the average distance to Memphis is 843 miles. It is interesting to note that as FedEx has grown it has established some secondary hubs, one of them being in Indianapolis. Furthermore, the optimal location is only about 85 miles northwest of Louisville where UPS has established its main hub."
补充UPS路易斯维尔枢纽比孟菲斯更接近论文给出的最优点。
在图5中你会注意到，UPS的路易斯维尔枢纽比FedEx的孟菲斯枢纽更接近作者的最优“H点”。
ISL查看英文原文
In Figure 5, you'll note that the UPS Louisville hub is closer to the author's optimal "Point H" than the FedEx hub in Memphis.
亲历亲历者称实际排程精度惊人但依赖大量Excel和方程，最终可用Gecode写优化器。
我实际上曾在一家高级计划与排程（APS）公司工作，做过站点规划的POS。他们把时间安排得精细程度令人印象深刻；不那么令人印象深刻的是我不得不读的疯狂Excel工作簿，以及我必须在网络驱动器上铺开的所有方程。工作量相当大。但我能用Gecode（gecode.org）为它写一个优化器。
mcginleyr1查看英文原文
I actually was at an advanced planning and scheduling company and did a POS for station planning. The timings they have things down to are impressive. What's not is the insane excel books I had to read and all the equations I had to lay out that went across the network drive. It was quite a bit of work. But I was able to write an optimizer for it using Gecode (gecode.org)
相关资源
从这篇论文所有 HN 讨论帖的全部评论里整理出来的链接。
历次讨论
- 2015Hacker News 讨论帖229 分 · 98 评
同领域还值得读
哲学家为何应关注计算复杂性
Why Philosophers Should Care About Computational Complexity (2011)
Scott Aaronson 的这篇长文论证计算复杂性理论（如 P vs NP、停机问题的复杂度视角）对哲学问题（如知识的本质、中文房间、水槽论证等）具有实质意义，而不仅是技术细…
算法与理论计算机2015 · 552 分 · 120 评进阶 · 约 90 分钟编辑精选通信的数学理论
A Mathematical Theory of Communication
是香农1948年的《通信的数学理论》，为通信建立数学框架：把信息量定义为不确定性或自由度（信息熵），并讨论信源编码、信道容量与可靠传输。
算法与理论计算机2020 · 495 分 · 91 评进阶 · 约 120 分钟编辑精选物理、拓扑、逻辑与计算：罗塞塔石碑
Physics, Topology, Logic and Computation: A Rosetta Stone (2009)
用范畴论充当“罗塞塔石碑”，试图在量子物理、拓扑、逻辑与计算四个领域之间建立统一的结构性类比：物理中的量子过程、拓扑中的配边、逻辑中的证明和计算中的程序，都可被视为某类范畴中的态…
算法与理论计算机2009 · 390 分 · 55 评 · 引用 13专业 · 约 180 分钟编辑精选一种快速、极小内存的一致性哈希算法
A Fast, Minimal Memory, Consistent Hash Algorithm
论文给出一种快速、省内存的一致哈希方案，目标是在桶数量变化时保持较小的键迁移成本，同时降低计算和内存开销。
算法与理论计算机2014 · 327 分 · 57 评 · 引用 4进阶 · 约 25 分钟编辑精选第五个 Busy Beaver 值的确定
Determination of the fifth Busy Beaver value
宣布确定了第五个 Busy Beaver 值 BB(5)：即 5 状态图灵机中停机前运行步数最多的机器（Champion）在 47,176,870 步后停机。
算法与理论计算机2025 · 288 分 · 116 评 · 引用 1专业 · 约 75 分钟编辑精选