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卡车 - 每天左右130次停止 - 基本上是车轮上的旅行推销员问题。
ORION的承诺是明确的:每位司机每年每节省一英里，UPS就能节省3000万美元。求解旅行商问题所需的数学，即使是近似的，也很清楚。但是，在试图将这种数学方法应用到实际的配送和司机世界中去时，UPS的管理人员需要了解，交通不仅与交通的交叉路口和时区有关，也与人及其施加的独特限制有关。正如杰夫·温特斯(Jeff Winters)对我说的那样，“从表面上看，想出一条优化的路线并交给驾驶员应该是非常容易的，然后你就完成了。”我们原以为这需要一年的时间。”那是十年前的事了。
当司机停止面包车时，他“有九秒钟选择一个包裹并离开那里。”
一方面，人类是非理性的，容易养成习惯。当这些习惯被打破时，有趣的事情就会发生。例如，在明尼苏达州的I-35大桥倒塌后，过江的游客数量毫不奇怪地下降了;但研究人员大卫·莱文森(David Levinson)指出，即使在大桥修复后，交通流量也再也没有接近之前的水平。加州大学的Akshay Vij和Joan Walker在一篇题为《你可以引导旅行者到公交站，但你不能让他们乘车》的论文中指出，习惯可能会特别麻烦人们规划固定的旅行路线，比如公共汽车。“传统的旅行需求模型假设，个人知道他们可以选择的所有选择，”该论文写道，“而有意识的选择是基于感知成本和收益之间的权衡做出的。”但事实并非如此。
人们也是情感的，事实证明了一个不快乐的卡车司机可能会有麻烦。现代路线模型包括卡车司机是否幸福或没有 - 他可能不了解自己。例如，拒绝被命名为“预测分析”的一家主要货运公司在驾驶员涉及崩溃的风险更大时确实“预测分析”。公司不仅有关于卡车如何被驱动 - 超速，难以制动的事件，快速车道变化 - 但在驾驶员的生活中。“我们实际上建立了模型中的一些可能是出于不满的指标，”一名员工熟悉该计划。
这可能是司机实得工资的变化，可能是家庭成员去世或离婚等生活事件，也可能是像司机早上上班时间突然改变这样微妙的事情。该分析考虑了公司工程师能想到的一切，然后梳理出哪些因素似乎与事故风险相关。危险最高的司机会被标记。然后有程序到位，以确保驱动程序的经理将与标记的驱动程序对话。
换句话说，当你不得不考虑推销员的幸福时，旅行推销员的问题就变得相当复杂了。你不仅要知道他什么时候不开心，还要知道你的模型是否会让他不开心。普林斯顿大学运营研究和金融工程系城堡实验室(Castle Laboratory at Princeton University’s Department of Operations Research and Financial Engineering)主任沃伦·鲍威尔(Warren Powell)对从Netjets到Burlington Northern等运输公司进行了优化。他回忆说，在黄色货运公司，“我们和司机一起做事情，他们说，你就是不能那样做。”有工会规则，有行业惯例。拖拉机可以储存在任何地方，人们喜欢晚上回家。“我说我们需要一份包含2000条规则的文件。卡车是简单的;司机很复杂。”
在UPS，一个程序可以想出一条很棒的路线，但如果它违反了，比如说，卡车司机工会的规定，它就毫无价值。例如，需要为司机的休息和午餐设置时间窗口。虽然拍摄感言的司机我看到在UPS在猎户座的描述主要是积极的,有趣的是,公司和工会之间的最新合同包括一项条款,没有司机将“排放完全基于信息收到GPS或任何继任者系统。”
不过，鲍威尔在考虑人类在算法中的作用方面最大的发现是，人类可以做得更好。“我会去黄色部门，我们试图解决这些重大的确定性问题。我们一点关系都没有。我会坐在那里，看着调度中心，想，他们是怎么做到的?”这时他注意到:他们不会试图一次性解决整个星期的日程安排。他们是分着做的。他说:“我们人类解决问题的方式很有趣，但没人能说清楚。”运筹学研究人员只是把它称为“启发式方法”。
这种与生俱来的人类能力在桑提利女儿的班上也起了作用。五年级的学生大概猜对了。詹姆斯·麦格雷戈和托马斯·奥默罗德请注意，“旅行推销员问题的任务可能发生在任何情况下，在任何情况下，在任何情况下都是对感知系统进行的自然的平行。”奇怪的是，使用这种启发式方法，他们注意到，实验中的受试者“非常擅长找到最佳旅游”。在其他实验中，当受试者被显示出最佳旅行的图像时，他们被认为比次优秀更令人愉悦。
现代路线模型包括卡车司机是否幸福或没有 - 他可能不了解自己。
当然，即使是人类也不愿意理解其他人的行为。鲍威尔给我看了一个范例图，他有时会给一屋子的卡车运输业高管看。“我有一堆东西要去拿。60英里外有个司机。我只要把他干掉，就完事了。我还有另一个司机，他一旦卸货，就会在大约30英里外，大约下午三点左右就会到。”你会选择确定的东西吗，即使它会消耗更多的里程?或者你会冒险去短途旅行，因为它可能会晚点到达?当他要求大家举手表决哪个选择更好时，人们的回答通常是褒奖不一。“司机B帮我节省了里程。但他还没有到达，如果他没有呢？他说，声音降成了阴谋的耳语。不同的人会有不同的回答。他们会说，‘我认识那个司机，他会成功的。’欢迎来到现实世界的决策过程。”
最终，最好的方法结果是建立人们已经在做的事情。当鲍威尔十年前与施耐德卡车咨询的时候，好奇地，他没有模仿一些施耐德的Über高效的理想化愿景。他基本上是施耐德的建模是．“我们的目标不是得到最好的解决方案，”施耐德的长期运营研究专家Ted Gifford说。“我们的目标是尝试模拟现实世界规划者真正在做的事情。”当我向吉福德建议，他试图从数学上理解现实世界时，他表示同意，但补充道:“‘理解’这个词太强烈了——我们很高兴能得到积极的结果。”
对UPS来说，量化人类行为也是关键。UPS的温特斯说:“在旧的商业规则中，我们要求司机对他们跟随路线的程度负责。”UPS代表的是路线。他说，更糟糕的是，司机在没有得到指导的情况下，会因为错误和延误或“破坏路线”而受到惩罚——“辅导和咨询”。他说，这是一个“愚蠢的规则”，是公司最初只提供地面递送服务的遗留思想。“正确的做法是，”温特斯说，“只利用空中工作来建立航线，然后考虑成本高昂的地面区域，这样就不必再回到那个区域。”它颠覆了一个商业问题。”
T.因此，传输优化是困难的，理解如何实现它可能更困难。桑提利告诉我:“教数学分析团队最困难的事情之一，就是分辨可行的解决方案和可执行的解决方案之间的区别。可行意味着它满足所有的数学约束。但可实施的是人类可以执行的东西。”
但优化已经成功地走了很长的路。建模已经变得更加复杂，鲍威尔在他的一生工作中概述了这一发展，一本书叫做近似动态规划:解决维数的诅咒．“你去看数学文学，那都是些玩具题。大约20年之后，我才走到白板前说，你知道吗，我可以把问题写下来。”地图绘制得到了显著改善。几十年前，UPS购买的地图服务让人们打电话给企业，问他们是否真的在UPS提供的数据所显示的位置。早期的GPS地图也有缺陷。UPS首席科学家Ranga Nuggehalli表示:“当我们在早期得到一些糟糕的结果时，我们不知道这是因为算法太差了，还是我们的数据太差了。”是后者。
此后，跟踪所需的数据采集技术已经开发出来。UPS的“配送信息采集设备”(DIAD)是一款棕色的手持电脑，你肯定会在上面签名，它创建了一个数据体系结构，支持他们的优化策略。
最终的结果是缓慢但稳定的改善。鲍威尔和桑提利指出了他们自己的成功故事。鲍威尔说，黄色货运公司过去有大约700条“终点站”，这些终点站是货物转运到终端客户手中的分拣终端。鲍威尔开发了一种模型，传达了一种有违直觉的信息:有了这么多终端，卡车要到达客户那里需要走得更远。他说，如今，Yellow Freight拥有400条终点站。“这是正确的数字，”他说。至于UPS，桑提利注意到宾夕法尼亚州葛底斯堡的一名司机。现在每天的行驶里程减少了近25英里，从原来的150多英里减少到126英里——但停车次数不变。
我们在移动物体方面变得越来越聪明。但不那么明显的是，我们正在掌握如何为交通工具中的人元素建模。就像我们开始了解算法一样，算法也开始了解我们。
汤姆·范德比尔特的文章涉及设计、技术、科学和文化等领域。他最近的一本书是纽约时报畅销书交通:我们为什么要这样开车(以及这说明了我们什么)．
