W.UPS高级项目经理Hen Bob Santilli于2009年邀请他女儿的五年级课程，他努力与他以谋生为生的究竟描述。最终，他决定展示他工作的那种旅游优化问题，并用它的乐趣和复杂的方式给他们留下深刻的印象。挑战是在典型的郊区 - 差事行程中选择六个不同的停止中最有效的路线。该类设计了各自的路线，然后开始挑选它们。但是一个女孩认为经过了效率的问题。“她说，我的妈妈永远不会去商店买来易腐的东西 - 她没有利用易腐的词，我做了 - 并在整个工作中留在车里，”Santilli告诉我。
她的评论反映了关于在几乎所有现代交通系统的表面下面的数学的基本真相，从自行车 - 股票重新平衡航空公司机组安排去杂货店送货服务。对交通问题的简化模型进行建模会带来一系列挑战（这些挑战可能非常重要）。但现实世界的建模往往是真正的挑战所在，因为现实世界中存在着诸如融化的冰淇淋和人类特有的行为等约束。数学家、运筹学专家和企业高管开始对连接现代世界的交通网络进行数学化和优化，他们正在重新发现我们最人性化的一些怪癖和能力。他们发现他们的工作就是发现世界，也就是改变世界。
T.桑提利向女儿班上提出的问题被称为“旅行推销员问题”。解决这一问题的算法是交通运输业中最重要和最常用的算法之一。一般来说，旅行推销员的问题是这样的:给定一份站点列表，对于一个推销员来说，最省时的方式是什么?例如，1962年宝洁公司(Procter and Gamble)的一则广告向读者提出了这样一个挑战:帮助艾美奖(emmy award)电视节目的联合主演“图迪和马尔登”(Toody and Muldoon)汽车54，你在哪里？，设计一次横跨美国大陆的33个城市的旅行。“你应该为他们规划一条从一个地点到另一个地点的路线，”指示说，“这将使从伊利诺伊州芝加哥返回伊利诺伊州芝加哥的总里程最短。”
数学家声称奖项，富豪10,000美元。但比赛组织者只能核实他的解决方案是那些提交的解决方案，而不是这是最短的可能的路线。这是因为通过单独计算每条路线来解决33个城市的问题需要28万亿年——能源部的12.9万核超级计算机Roadrunner(世界上速度最快的集群之一)。正是因为这个原因，威廉·j·库克在他的书中在《追逐旅行推销员》中，称旅行推销员问题是“关于复杂性本质和人类知识可能局限性的更大争论的焦点”。它的定义特征是复杂性的扩展速度。6个城市的旅行只有720条可能的路径，而根据库克的快速计算，20个城市的旅行有超过100万亿的可能路径。
建模现实世界，与熔化冰淇淋和特质人类行为一样，通常是真正的挑战谎言。
有一些旅行推销员问题的答案。库克自己制作了一个iPhone应用程序这将破解100个城市，使用宽松的线性规划和其他算法技术。每隔几年左右，配备了复杂硬件和编程方法的团队就会提高标准。例如，2006年，库克带领的团队进行了一次85,900个城市的最佳旅行。当然，考虑到上面提到的计算约束，它并不包括单独检查每条路由。“把纽约和洛杉矶之间的所有公路旅行都列出来是没有希望的，”他说。相反，几乎所有的计算都用来证明没有比他的团队发现的更短的旅程了。从本质上说，有一个答案，但没有一个解决方案。库克写道:“所谓解决方案，我们指的是一个算法，这是一个循序渐进的方法，无论我们现在举什么例子，它都能产生最佳的旅游效果。”
而这个解决方案可能永远不会出现。旅行推销员问题是一个正在进行的问题的核心-这问题在计算机科学：是否P.=NP.．总结了麻省理工学院的新闻办公室的钝优雅，“粗略地说，P.是一组相对容易的问题，NP.是一组非常难的问题，如果它们相等，那么大量看起来非常难的计算机科学问题实际上相对容易。”克莱数学研究所悬赏100万美元奖励一个像母船一样盘旋在车54挑战与挑战：证明这一点P.做或不等于NP.．
到目前为止，我们应该清楚，我们谈论的不仅仅是销售人员的路线需求，因为即使是最精明的地区代表，也不会考虑通过电话走访9万个遥远的城镇。但是“旅行推销员问题”和它的知识兄弟们远非理论;事实上，它们是我们交通网络中看不见的核心。每当你想要去某个地方，或者你想要得到某样东西时，很有可能就在那一刻，有人在思考如何让这个过程更有效率。我们都是旅行推销员。
一种像Bob Santilli这样的职位，负责优化，在UPS并不总是存在。过去的日子比较简单。直到20世纪80年代初，UPS的司机们还只有一个简单的目标:在一天结束前将所有包裹送到卡车上。那是“地面”的日子。桑提利指出:“我们唯一拥有的是对商业司机的时间敏感性。UPS运营研究主管杰夫•温特斯(Jeff Winters)表示:“所有问题都是需要解决的、可扩展的问题。”这是必须的。桑提利(UPS称其棕色运送货车为“轿车”)说:“我们每天都为司机提供单独的载货图。”在纸上。路线是用图钉在地图上标出的。 At the end of the day, everything was filed, and the process began again.
但是，在1982年，世界发生了变化:“次日空运”被引入。突然间，时间“提交”的种类越来越多;包裹必须在上午10:30之前送到一个地址，下午1:30之前送到另一个地址，中午之前送到另一个地址。还有新的包裹取货时间限制。它不再只是一个最优路由问题，而是一个最优调度问题。UPS怀疑的一件事是，它做的事情不是最优的。你可以想象在这些墙里没有比这更大的罪孽了。甚至货车内部也受到一种路由算法的约束;下次您收到一个包时，寻找三个字母的字母代码，比如“RDL”。这意味着“后门向左”，所以司机需要采取尽可能少的步骤来定位包裹。 In one typical aside, Santilli told me that when a driver stops the van, he “has nine seconds to select a package and get out of there.” His tone suggested he was talking about a member of a bomb disposal unit.
1986年，UPS购买的RoadNet是一家物流公司，为啤酒经销商等商家创造了最佳路线。只有一个问题：Roadnet的司机在每天左右的速度甚至左右的驾驶员，甚至是相同的路线。因此，UPS开始被称为项目orion（onroad综合优化和导航），这一项目跨越多年的项目以及数百万美元，其算法努力刚刚开始在近58,000卡车的船队中脱颖而出。在orion的核心是旅行的推销员问题。每辆UPS卡车 - 每天左右的停留 - 基本上是一个在车轮上的旅行推销员问题。
ORION的承诺是明确的:每位司机每年每节省一英里，UPS就能节省3000万美元。求解旅行商问题所需的数学，即使是近似的，也很清楚。但是，在试图将这种数学方法应用到实际的配送和司机世界中去时，UPS的管理人员需要了解，交通不仅与交通的交叉路口和时区有关，也与人及其施加的独特限制有关。正如杰夫·温特斯(Jeff Winters)对我说的那样，“从表面上看，想出一条优化的路线并交给驾驶员应该是非常容易的，然后你就完成了。”我们原以为这需要一年的时间。”那是十年前的事了。
当驾驶员停止面包车时，他“有九秒钟选择一个包裹并离开那里。”
一方面，人类是非理性的，容易养成习惯。当这些习惯被打断时，有趣的事情就会发生。例如，在明尼苏达州I-35大桥倒塌后，过河的游客数量下降，这并不令人惊讶；但研究人员大卫·莱文森指出，即使在大桥修复之后，交通水平也再也没有接近之前的水平。在加利福尼亚大学的Akshay Vij和Joan Walker的一篇论文中提到，“人们可以安排固定的出行路线，比如公交车，这一点特别麻烦，”你可以把旅行者带到公共汽车站，但不能让他们骑车。“传统的旅游需求模型假设个人知道他们可以选择的全部替代方案，”论文写道，“并根据感知成本和收益之间的权衡做出有意识的选择。”但事实并非如此。
人们也是情绪化的，事实证明了一个不开心的卡车司机可能会有麻烦。现代路线模型包括卡车司机是否幸福或没有 - 他可能不知道自己。例如，拒绝被命名的一个主要货运公司在司机陷入碰撞的风险更大的风险时，“预测性分析”。公司不仅有关卡车如何驱动 - 超速，难以制动的事件，快速车道的变化 - 但在驾驶员的生命中。“我们实际上建立了模型中的许多指标，这些指标可能是不满的代理人，”一名员工熟悉该计划。
这可能是司机实得工资的变化，可能是家庭成员去世或离婚等生活事件，也可能是像司机早上上班时间突然改变这样微妙的事情。该分析考虑了公司工程师能想到的一切，然后梳理出哪些因素似乎与事故风险相关。危险最高的司机会被标记。然后有程序到位，以确保驱动程序的经理将与标记的驱动程序对话。
换句话说，当你不得不考虑推销员的幸福感时，旅行推销员的问题变得更加复杂。而且，你不仅要知道他什么时候不开心，还要知道你的模特是否会让他不开心。普林斯顿大学运营研究和金融工程系Castle实验室主任沃伦·鲍威尔（Warren Powell）优化了从Netjets到伯灵顿北部的运输公司。他回忆说，在Yellow货运公司，“我们和司机一起做事，他们说，你不能那样做。”有工会规则，有行业惯例。拖拉机可以存放在任何地方，人们喜欢晚上回家。“我说我们需要一份2000条规则的文件。卡车很简单，司机很复杂。”
在UPS，一个程序可以想出一条很好的路线，但是如果它违反了，比如说，卡车司机工会的规则，它就一文不值了。例如，需要为司机休息和午餐设置时间窗口。虽然我在UPS看到的司机的推荐信在很大程度上对ORION的描述是正面的，但有趣的是，该公司与工会之间的最新合同包含一项条款，即任何司机都不会“仅根据从GPS或任何后续系统收到的信息而被解雇”
鲍威尔在考虑人类在算法中的作用的最大启示，是人类可以更好地做到这一点。“我会下降到黄色，我们正试图解决这些大确定性问题。我们甚至没有关闭。我会坐下来看看调度中心并思考，他们是如何做到的？“那是他注意到的时候：他们不想一下子解决整个星期的日程安排。他们正在分头做这件事。“我们人类有很有趣的方式来解决没有人能够表达的问题，”他说。运营研究人们只是平底船，称之为“启发式方法”。
这种与生俱来的人类能力在桑提利女儿的班上也起了作用。五年级的学生大概猜对了。詹姆斯·麦格雷戈和托马斯·奥默罗德笔记，“旅行推销员问题的任务可能发生在任何情况下，在任何情况下，在任何情况下都是平行的。”奇怪的是，使用这种启发式方法，他们注意到，实验中的受试者“非常善于找到最佳旅行”。在其他实验中，当受试者被显示出最佳旅游的图像时，他们被认为比次最优巡回赛更令人愉悦。
现代路线模型包括卡车司机是否幸福或没有 - 他可能不知道自己。
当然，即使是人类的诽谤也会了解其他人的行为。鲍威尔向我展示了一个样本图，他有时会给一名宽敞的卡车运输管理员。“我有一个必须被拿起的负担。我有一个60英里的司机。我所要做的就是派他，它已经完成了。我有另一个司机，一旦他卸载，就会在距离Midawternoon周围大约30英里外。“你肯定的是，即使它消耗了更多英里？或者您是否在较短的旅行中冒险，这可能会在以后进入？当他要求一个选择更好的手的表演时，响应通常混合。“司机B救了我数英里。但他还没有到达，如果他没有呢？他说，他的声音降低到一种阴谋的低语。“不同的人会有不同的回答。他们会说，‘我认识那个司机，他会成功的。’欢迎来到现实世界的决策。”
最终，最好的方法结果是建立人们已经在做的事情。当鲍威尔十年前与施耐德卡车咨询的时候，好奇地，他没有模仿一些施耐德的Über高效的理想化视力。他基本上被建模了施耐德是．“我们的目标不是得到最好的解决方案，”施耐德的长期运营研究专家Ted Gifford说。“我们的目标是尝试模拟现实世界规划者真正在做的事情。”当我向吉福德建议，他试图从数学上理解现实世界时，他表示同意，但补充道:“‘理解’这个词太强烈了——我们很高兴能得到积极的结果。”
同样，在UPS，以定量的方式考虑人类行为也是关键。“在旧的商业规则中，”UPS的Winters说，“我们要求司机对他们跟踪追踪的程度负责”——UPS代表路线。他说，更糟糕的是，司机们虽然没有得到指导，但却因为错误和延误或“破坏踪迹”而受到惩罚——“指导和建议”。他说，这是一条“愚蠢的规则”，是公司作为地面交付服务的起源遗留下来的传统思想的遗留物。“正确的做法是，”温特斯说，“只需空中作业就可以修建路线，然后再看看昂贵的地面区域，这样就不必再返回该区域。这就彻底解决了一个商业问题。”
T.然后，Ransport优化，很难，并且了解如何实现它可能更加困难。“教授数学分析组的最困难的事情之一”Santilli告诉我“是可行解决方案和可实现的解决方案之间的区别。可行只是意味着它符合所有数学限制。但可实现的是人类可以实现的东西。“
但优化已经成功地走了很长的路。建模已经变得更加复杂，鲍威尔在他的一生工作中概述了这一发展，一本书叫做近似动态规划：解决维数灾难．“你去看数学文学，那都是些玩具题。大约20年之后，我才走到白板前说，你知道吗，我可以把问题写下来。”地图绘制得到了显著改善。几十年前，UPS购买的地图服务让人们打电话给企业，问他们是否真的在UPS提供的数据所显示的位置。早期的GPS地图也有缺陷。UPS首席科学家Ranga Nuggehalli表示:“当我们在早期得到一些糟糕的结果时，我们不知道这是因为算法太差了，还是我们的数据太差了。”是后者。
已经开发出跟踪所需的数据采集。UPS的“交付信息采集设备”或DIAD，毫无疑问签名的棕色手持电脑签名，创建了一个支持其优化策略的数据架构。
最终结果一直是缓慢而稳定的改善之一。鲍威尔和圣诞老人指向自己的成功案例。黄色货运曾经有大约700“线的线条，”鲍威尔说，这是排序终端，货物被转移到其最终客户。Powell开发了一种拨出违反直觉信息的型号：卡车的旅行进入更远，以便使用这么多的终端向客户提供。今天，他说，黄色货运有400条线条。“那是正确的数字，”他说。至于UPS，Santilli注意到葛底斯堡的驾驶员，PA。现在每天开车近25英里，从超过150英里的原始路线到126英里 - 与相同数量的停靠点。
我们在移动物体方面变得越来越聪明。但不那么明显的是，我们正在掌握如何为交通工具中的人元素建模。就像我们开始了解算法一样，算法也开始了解我们。
汤姆·范德比尔特写的是设计、技术、科学和文化等方面的文章。他最近的一本书是纽约时报畅销书交通：我们为什么这样开车（以及它对我们的影响）．
