演讲 | 运筹学专家叶荫宇：在物流、零售与金融行业，优化算法如何改变决策方式？

2017-07-05 机器之心之心整理

参与：杜夏德

运筹学的历史比 AI 和机器学习更悠久，但 AI 与机器学习又为它提供了一种机会，很多顶层的东西都是要靠优化，不管是学习还是刚才讲到的决策问题，都要有 OR (运筹学)的结合。

作为优化算法的基础，运筹学在第二次世界大战期间因英美两国配置资源的需求而发展起来。近些年，随着数据量大幅度攀升等科技环境的变化，运筹学得以快速发展，并广泛应用于零售、金融、物流等行业。正如运筹学顶级专家叶荫宇所说，运筹学的历史比 AI 和机器学习更悠久，但 AI 与机器学习又为它提供了一种机会，很多顶层的东西都是要靠优化，不管是学习还是刚才讲到的决策问题，都要有 OR (运筹学)的结合。从叶荫宇以《优化算法的思想及应用》为题的一次演讲中，我们可以了解到运筹学如何应用于物流选址及路径优化、库存管理、投资组合优化。以下是经过编辑整理而成的演讲内容：

叶荫宇，是斯坦福大学李国鼎工程讲座教授（K. T. Li Chair Professor），优化领域基石算法之一——内点算法的奠基人之一，他曾获得美国运筹与管理学会冯·诺依曼理论奖，也是迄今为止唯一获得此奖的华人学者。目前，叶荫宇担任优化软件公司MOSEK科技顾问委员会主席、杉数科技的首席科学顾问。

1982 年，我刚到美国读书，AI 非常热，但那时候就要搞所谓的专家系统AI 空间，学的语言是Lisp，数据也不多，很多东西没法总结，AI 就慢慢冷下去了。我比较喜欢数学，就开始了运筹学的研究。运筹学是一种研究优化的学问，就是研究如何在实际生活中，把事情做到极值，找到最优解，而不是简单找一个可行的方案。

数学家欧拉说过，Nothing at all takes place in the Universe in which some rule of maximum or minimumdoes not appear（笔者译：宇宙中，没有最大值或最小值的事物是不存在的）。这种理论是基于自然形成的，也是在所谓的一个平衡，也是能量函数到了极值。那时候还没有计算机，数学不接地气，无法落到实地，无法真正应用到人们生活中，产生一些影响。于是数学家们就开始寻求落地的方案。也有一些其他的紧迫因素促使运筹学的诞生，二战时，两军交战，需要研究盟军配置，其中包括一些博弈问题。

1947 年，美国数学家George Dantzig 提出线性优化的单纯形法，是优化中最经典的算法，具有里程碑意义。之后运用到经济学中后，运筹学得到快速发展，特别是计算机的高速发展，以前遇到结构问题，可能要1小时，现在可能不到1秒就可以解出来，这里面有硬件的控制，也有算法的提高。运筹学的历史比AI 和机器学习要老，但是AI 和机器学习又提供了一种机会，很多顶层的东西都是要靠优化，不管是学习还是刚才讲到的决策问题，都要有OR(运筹学)的结合。

整体来说，所谓优化，是满足一定的约束条件下，使某一个函数最大。怎么把一个问题变成这个优化问题，就需要建模。一般是从建模到求解，再到决策，这就需要一套算法来求解。

在这个里面，把实际问题变成数学问题，变成优化问题，然后来求解。什么叫大数据，有很多不同的解释。而数据大到一定程度后，就可以量化了，量化以后，我们可以用数学的方程、公式来描述它，然后变成一个量化的决策问题。

1982 年我去美国时 AI 很火，后来沉寂了，现在又红起来。但是优化一直都在那里，各行各业都需要它，在这点上，它像统计、数学。在大数据时代的商务决策中，要用到计算机、信息学，包括机器学习，数据搜集，然后我们要通过机器学习做一些规律性分析，然后就是建模、决策。这里面需要有一些量化、需求管理、规律性分析，我觉得机器学习确实做的好。但是在决策中有一些很传统的优化模型和运筹学的模型。

举几个简单的例子，为什么有些决策模型并不需要深刻的理解就可以得出来。

一、物流选址及路径优化

比如说选址问题，寻求一个区域内最优的仓库，成本最少，每个库建在什么地方，这里面要权衡很多问题，一次建设费多少，服务区域有多大，如果区域大了，运输成本就高了，这里就是数学规划的问题。那么怎么选才好？以前，我把它写成一个整数规划，然后去算，有些算法，几个月都算不出解来，但是客户有很多需求都是有时限的。现在把它看成是一张网络，就要把这个点放在上面，进行随时的调配，重新选址，这个时候我的算法就非常的快，然后就会有很多的近似算法。这里面的算法，选址的问题，我们在与客户合作的过程中有很多这样的问题。

另一个问题更复杂一点，选一个仓库提供一个区域服务，叫hub 的选址。有些物品不是从仓库发到某一个顾客上，而是要经过中转站，再到顾客上。那么这个中转站怎么选才好。通常我们把选址的问题，叫作战略性的决策，一旦选了以后，几年都不会变。决策也分为战略决策，战术决策、operation 决策，而我这里谈的是operation 决策，我现在要送货，送到这么多的点上，如何把货都送出去，然后回到出发的地点，最终要使整个距离最小，这叫「旅行商问题」，也是很经典的确定性问题。

在实际中，也叫车辆调度问题。当然现实问题比这更复杂，因为可能有一辆车不能跑了，几千上万辆车，每辆车跑哪些地点，哪些区域，又怎么选址，还要考虑取货和同时送货，取货必须要保证某一个时间点或者时间窗口。这是运筹学比较擅长的问题，要实时低解决这些问题。

比如我现在有5 辆车，要服务这个区域。首先建立一个服务区的概念，怎么把这个大的区域分成50 分点，每一个区域选择一个分点，这叫「区域选择」。在分这个区域的时候，我要知道每个区域的工作量都是多少，尽量分的均匀，要不然一个区域很大，跑两天跑不完，一个小区域半天就跑完了。我的一个学生在和杉数在一起研究，怎么把区域所有的工作量都分得一样，每个给的这个点就是车的出发点，可以很快的划分出来，在作一些路线规划。

这张图里面有50 辆车，需要找路径，这是一个实际问题。每一条街道都要跑，我在划分这个区域的时候，每个区域里街道的总长度是基本上相似的。在跑这个区域的时候，怎么跑到最大，把所有的街道都跑一趟，这就是路径问题，这是地图公司需要考虑的。

大家肯定用过GPS，其中有两个核心技术，一个是卫星定位，经度纬度定位以后。剩下所有的地理信息位置，都是搜集过来的，但是街道的地理数据不断在变，所以每次都要把街道的信息更新都要重新搜集进来，派一辆车把每个街道跑一遍。这个时候要把城市的街道都跑一遍的话，不可能跑一辆车，可能需要50 辆车。那么怎么划分这个车辆的区域，以前是用邮政编码来分，由于城市区域的改变，有些邮政编码覆盖的区域大好几倍，这样分就不合理，所以要根据瞬时情况进行分析。如何判断有效，比如原来要用75 辆车现在60 辆就够了，原来用2天时间现在一天半就够了，这个技术，诺基亚在全世界26 个国家使用。我原来认为我刨出来最后的路程最短，后来又提出一个要求，在排路径的时候，尽量向右转。因为左转所要花的时间，比向右转高出5 到10 倍，最后我们用运筹学的办法把这个解决了。

再举一个路径优化的问题，大家都在搞所谓的无人仓，有一些小车搬运载有货物的托盘到空闲工作台，然后小车搬运托盘从工作台回到仓库空储位，这叫回库，然后小车搬运空托盘从工作台到托盘回收处，叫回收，这里面都是一些货柜，怎么拖起来怎么用，就需要路径规划和协调。

在国内，研究机器人，研究的比较多的是提高每个机器人自身的能力，做的非常好。但是在很多问题上，缺少通盘调配和安排。单个机器人能力很强，但是在一个团队中时就不一定了。我们比较缺乏统筹的软件决策系统。我们很注重个人能力的提高，但是期缺乏一种集体的统筹的决策开发。每个机器人都在瞎跑，这样肯定不行，无人车也是。很多公司都在考虑无人车的技术多强，但是其实最主要的问题是什么，反而是无人车之间的协调、调配和统一指挥。

比如说这是工作台，某一个区域的货来了以后，要进行分担，这里面有很多问题，比如路径问题。从设计上来说，是设计成单行线还是双程线，如果设置单行线，跑的 距离要长，碰撞的可能性就少一些，这里面都可以通过优化来解决。比如杉数与京东618 活动的物流仓统筹调配合作，其中的算法也都是算出来的。这里面是三配，机器人怎么配到货柜，怎么收检这个站。目前的方法是用机器人用托盘拖这个货柜，把整个的货柜拖到旁边的这个台上，然后又把这个拿下来，再把托盘送回去。首先是机器人，把整个的货柜拖起来，可能那个货柜员就检一个东西下来。那么为什么货柜不动，让货柜员坐在机器身上然后去检货呢？因为这样货柜可以装

的更高了，空间利用率更高了。而且人坐在这个机器上，不仅可以前后移动，还可以升降货柜，放的更高，运行过程中形成三位的仓库而不是平面的仓库，这样 我们就可以计算出来，货的密度增加多少，仓库的利用率可以增加多少。在中国，人力相对比较便宜，但是房子非常贵，这样就能更加节省成本，但是整个也是靠产品运输来优化问题进行求解。

工业界总是觉得我们需要深度学习、机器学习，需要把预测的精度再提高1%，却忽略了测不准的这个定理，精度到一定程度就不可能再提高了。所以在测不准的情况下，在决策上是不是可以做点工作，在知道测不准，可能有不同状况出现的情况下，决策是不是可以调整一下。比如说，可以保证我在期望值省时一些，但是我保证永远不会破产，防备那些恶性大事件发生。所以这些模型在OR 应用到很多的。比如说今天给到这个送货员的送货任务有10 单，我们做了一个辅助工具PonyPlus ，可以帮助送货员如果选择送货路径。

二、库存管理

这里面最典型的是库存问题，就是典型的知道你测不准，我怎么能够把局测做到最好，把库存做到最好。以前早的时候还没有深度学习，比如你是小零售商，你进货进 多少，进一个星期的货，但是不知道这个星期有多少，多的有多的损失，少的有少的损失。所以这个时候运筹学就有一套方法来处理这个问题。

比如你是小零售商，一个星期要进多少货，进多了，有多的损失，进少了，有少的损失。

这个时候运筹学就有一套方法来处理这个问题。最近，美联航因为机票卖多了，有人上了飞机后被拖下去。这是典型的不确定环境下的决策问题，飞机上座位是固定的300 个，你事先只卖300 张票，不会卖多，来的人都可以登记，问题是总有5%到10%的人，因为各种各样的原因是不会来的。所以航空公司一般都会多卖一点。最好的情况是不来的人数正好是我多卖的人数。但是这个人数永远是测不准的，也就出现了美联航的这个问题。

这类问题也出现在很多电商中。通常周转率在29 天的，那么现在降16.5%，库存的金额大家也都知道零售商最怕的就是库存周转率太低，买了人家的东西自己又卖不出去，库存金额降19.2%，现货率提升了，GMV 上升1.9%，而周转天数下降到24.4 天。就是说我们主要是降低了这部分人力，在不损失这两个标准的情况下。

还有一个办法根据某一个电商的特点，叫闪购，出一份货卖一个星期就不卖了，此时电商把那个星期的预测，需要备多少货就决定下来。我们采取两阶段的策略，首先 我有一个总的估量，但是我发货的时候是发三天的货，通过第一天的销量我再决定追不追货，本来一周的需求量是100 件，我实际送到前沿仓库的是60 件，我是否需要把这40 件补上去就看第一天的销量，第一天的销量对后续的预测度更高。

杉数的一个产品经理设计了一个叫StockGo 的智能库存决策系统。我们觉得应该给每一个中小电商，至少提供一个可能的工具，观察库存的这个周转，帮助他决策，这里面有很多的功能，比如说对目前库存状态的量化评估，对高精度的销量预测，高精度的补货策略，供应链管理的智能化转型，这里面包括很多机器学习和深度学习的工具，对你的库存状态进行评估，精确到每一个SKU，还有补货策略，以及个性化的全云端的解决方案，也可以直接把数据传送到杉数，然后帮你进行诊脉。

总的目的是把这些OR 的东西应用到经济中。很多 ERP（企业资源应用系统）的公司用了这个系统后，通常周转率会提高到50%，资金及人力成本降低，电商自动化库存能力也都提高，这样一个小工具，能够为广大的小电商服务。你也可以自己调整，但是至少给了你一个可能性。

三、投资组合优化

我最近还研究一些投资组合，也就是防范风险。

美国有一位经济学家Harry M.Markowitz，他有一个著名的理论叫现代投资前沿理论。他把投资组合的问题写成一个二代规划，其目标函数不是线性函数，而是二次函数，所有的约束也都是线性的，如何最 快的解这个问题解？这个时候我们就有很多的问题，那么这个模型中为什么出现了二次函数？在统计中，二次的X 的平方通常描述的是变化量，通常需要波动不太 大，这就是简单的这个二次函数，实际上要解的也就是二次规划，常见的软件Barra、Axioma、ITG、Mosek。现在，华尔街搞风险控制的都是用二次模型，用的求解器也就使用的 Mosek 。那么在交易过程当中，你的算法你的求解器比别人家快一些，我个人认为高频交易的竞赛也就是算法速度的竞赛。我知道国内就有用到过这样的模型，自己解需要 解 10 秒钟的时间。从 10 秒到 0.04 秒，这里面有算法的模型。FICO（ FICO 信用分是由美国个人消费信用评估公司开发出的一种个人信用评级法）也是二次规划的问题，很多很多大数据公司，越来越重视优化。美国最早的大数据公司就是产 生 FICO 的一家公司，国内是叫征信打分，最早的是一家公司把个人所有的信息收集起来给这个人的信誉打一个分。到美国租房要担保，首先就是看这个FICO 分。

这个公司后来做的很好，大家都用他的 FICO 。包括在网上查一查这个征信也都要交钱，这是美国很早的大数据公司，收集很多公司对每个人也都有打分。

运通公司是一个纯信用卡公司，实际上是一个担保公司。我总跟人家讲运通公司是合法的高利贷公司，利率确实比较高。那么他的核心技术就是防范风险，希望你消费但又希望你不要还钱而且希望你还钱不要还得太快，但是又不希望你永远不还。运通公司有一个专门的团队从事相关工作。

我当时团队帮运通公司搞了一个怎么追债软件，很多是基于算法的。国内公司做这种AI 软件的非常热。中国的文化也比较适合。

为什么？因为在中国，数据公开是比较自由的，像美国大公司数据绝对不会给你的，所以我觉得这种公开自由为AI 开辟了很多前途。

但是中国公司在发展过程中忽略了算法的力量，他们通常是以问题为根本，找了一些参考资料，在开源软件中找一个算法进行试一试。这是要花非常大的这个功夫，确实是要耐得住寂寞，但是要用人家的开源软件，人家不给源代码，就永远会被牵着鼻子走。我知道其实他们很需要线性规划或者说其他的运营规划。但是你要买别家公司的，出于安全考虑也不太妥当。现在有很多公司比如CPLEX，Mosek，还有些大学，不光是做实际应用，也培养自己的算法开发，这样就比较有核心技术了。真正的成为技术公司而不是咨询公司。所以投资要耐得住寂寞，要有核心的技术。

未来，AI、深度学习和机器学习提供了很多的支撑，模型规模也飞速增长，需要超大规模的优化算法。以前我认为就要搞出个万能的算法，解所有的线性规划都要解得快，但是我后来反观看AI 和人的思维并非是通用的，他是非常定制的，我可以什么方法对某一类方法用的好就用那个方法，不是追求某一个统一的算法，或者类别法。反而是比较定制化的，用中国化来讲比较实用主义一些。不一定追求理论上的完美，有一个统一的算法，所以这点上，我觉得反过来，AI 对运筹学会有很大的促进，什么问题需要什么样的算法，本身需要学习的过程。

还有一个问题，我们以前比较重视凸划，但是大量的问题是非凸规划。现在需要考虑集群化，软硬件结合，如何利用GPU 实现并行运算，包括应用在智慧供应链、智能金融、健康管理等领域。比如挂号系统，有很多很多的问题能不能采取更好的方法，这个方法在OR 中叫排序。

总的来说，我一直在研究运筹学和优化。从1982 年到现在，大半辈子看到学术研究的起伏变化。我原来比较重视理论，很多问题都是写文章，证明一些东西，也小有成就，但是人到年纪大的时候会觉得最大的利益还是对一般人生活产生一些影响。不光是有一定的学术造诣，把自己的学术成果转化成技术，对人的基本生活产生影响，这才是OR 的本质，OR 是一个接地气的科学，是一个落地的科学，怎么落地，需要经过我们的试验，像深度学习、机器学习这些技术也确实对物流业产生一些影响。我希望通过我们的努力，促使中国的企业，能从一个比较粗狂的形式进一步拓展为依赖于大数据、国际技术来进行决策的环境里面。

本文为机器之心整理，转载请联系本公众号获得授权。

From:

https://mp.weixin.qq.com/s/_Bo6NYLrF-yGOwXIDNi0OA?ptlang=2052&source&ADUIN=406806983&ADSESSION

=1499472611&ADTAG=CLIENT.QQ.5521_.0&ADPUBNO=26675