作者：姜东晓、闵武国
一、序言
人类对世界的理解是主观而感性的，我们很自然地用习惯的思维方式去与这个真实的世界发生着关联。然而，在现代企业生产经营活动中，基于个体经验的主观性就不那么受欢迎了，它会导致复杂商业环境中的决策偏差，也会让决策者无法打开“善弈者谋势”的全局视野，反而陷入“不善弈者谋子”的局限。于是，一种科学的、数理的、客观的工具--运筹优化 (Operations Research and Optimization) 模型应运而生，我们用它来发掘和提炼隐藏在事物表象下的真实规律，以求将隐性知识转化为理性智慧，去提升复杂环境下的决策质量。
【优化算法为理性决策赋能】系列文章陆续从以下三个模型入手，为大家展现运筹思想如何在现代企业里帮助决策者完成理性思维的过程。本期为大家介绍选址应用的一种解决方案：图拓扑模型。
系列一：选址之图拓扑模型
系列二：规格推荐之需求预测及拆分模型
系列三：路径概况之路网匹配模型
二、扎根业务场景
想做出一个高效合理的运筹模型，第一步也是最关键的一步，尽可能准确地描述需要解决的问题，剖析各要素及其关联关系，这样才能在整个算法设计过程中有的放矢。
2.1 选址重要性
选址是围绕投放对象一系列决策的入口和起点，只有确认了某一小区可投放，才会有后续各类决策的产生，如规格预测、定价、广告投放、营收预测、竞品博弈等。所以选址决策的质量尤为重要，它的影响是长期的，会波及后续所有序贯决策。选址选的不好，定价和广告投放会无法达到预想的效果，后期做运营和推广也会颇为吃力，修正成本也非常高。
2.2 选址场景
投放柜机的选址可归纳为宏观和微观两个场景。两者的目标和侧重点不一样，前者的决策对象是柜机网，通过布局尽可能争取更大的柜机全网总收益；后者的决策对象是单点小区，通过点位的选择直接改善派件能效和用户取件体验，从而将小区潜在需求尽可能多的转化为实际使用，来获取更大的单点收益。
2.2.1 宏观选址
侧重在有限的投放资源约束下选出能带来最大边际收益的痛点小区。比如下图我们可以看到深圳市南山区已投放柜机（蓝色）和未投放柜机的备选小区（绿色）的分布。备选小区的数量也是相当庞大，宏观选址要做的是回答下面两个决策问题：
成百上千的备选小区中哪些应该被选择？
以南山全区域来看，这些柜机又为什么会被选择？
决策应该是基于已投放柜机网和备选小区网的整体融合做出的全局判断。然而，考虑到可行性和效率，目前实践中多采用基于经验的单点评分方式，即评价每一个备选小区的收益潜力，给予其中高潜力小区更多的被选优先级。但即便是这种简化的方式，依然需要运营人员对备选小区快递量、社区人口、租金、周边竞品等因素综合判断，既要顾及局部、眼前的收益，也要把握全局、长远的趋势，非常考验决策者的综合判断能力。
2.2.2 微观选址
另一方面，作为宏观选址后续的精细化决策之一，微观选址聚焦在小区内部，主要解决小区被选中后柜机具体摆放在哪个点位的问题。由小区俯瞰图可知，由于楼宇地理布局、路径铺设、人流量分布、用户取件习惯等的差异化，摆放点位不同导致对小区潜在需求转化为实际使用量的程度也不同。比如靠近小区门口的点位相比更深处的点位更能缩短快递员派件路径、为繁忙用户取件提供便利，就更容易带来潜在需求的转化。再比如消费能力强且布局集中的楼栋附近的点位，能让快递员在相同时间内完成更多派件、缩短小区全体用户平均取件时长，也就更容易带来潜在需求的转化。所以同样规格的一台柜机，放在小区内不同点位A和B，绩效都会不同，微观选址要做的是：
尽可能去选择小区潜在需求转化率大的优势点位，获得更多的收益。
目前这一决策过程依然是由运营人员根据经验综合判断决定的，决策质量可能会因为地域、时间、决策者或场景的不同而发生变化。如果我们能掌握到更优质的小区画像数据，就可以结合机器学习和运筹模型，将优质的决策过程提炼并迁移出来形成一种显性知识，提升后续所有相关决策的质量和速度。
2.3 决策难点
由于运筹模型的优势在于全盘规划，所以本期只介绍前一种宏观选址。这一过程其实是一项系统和缜密的复杂工程，局部、眼前、全局、长远，各角度考量缺一不可，靠人做出最优决策，往往需要花费很长时间。我们归纳了目前的难点：
决策极度依赖人的隐性知识，整个思维过程很难清晰地表述和有效地转移，缺乏解释性。比如运营人员用语言或文字描述的决策过程可能并不能充分反映他应对复杂环境时的思考过程。
现有决策过程“见树木不见森林”，非常的孤立，忽略了柜机网络中糅合交织的复杂关系，即使我们能让每个局部点都做到最优，依然不能等同于全局的最优。
决策精度不稳定、无标准，决策质量会因为地域、时间、决策者、场景和目标的不同而发生变化。比如用同样的方式去完成以收益最大化为目标和以扩大渗透率为目标的选址，决策结果会大相径庭。
不能在合理时间内求解大规模问题。比如小区数为7时，我们至少要判断128种选址布局的优劣，而当小区数增加到100时，布局方案的数量已经达到了京级（1E30）。但100在实际场景中依然是个特别小规模的问题。即便是深圳市南山区粤海街道办，都有接近300个小区，而整个上海市有37000+个小区，可以想象全部的解有多么惊人！
幸运的是面对这些困难，运筹规划这个智能工具都可以帮我们解决，运用它极大拓展了我们在选址决策上的能力。
三、拥抱智能技术
3.1 图拓扑模型
图拓扑模型非常适合来回答宏观选址中“某个区域备选小区中哪些应该被选择？” 和 “为什么被选择？”这两个问题。
这里的图（Graph）与图像（Image）或地图（Map）不同，它是数据结构和算法中一种强大的框架，用来表现所有可以用“节点”和“边”来定义的抽象结构或系统。将柜机网转化成节点和边的图拓扑，小区是节点，它是否被选中影响到了边的连接。比如下图中节点A和B代表两个备选小区，左右图分别展示了节点A选与不选时网络结构的区别。整个结构可以用一个目标值来评价优劣，分值越大代表这种拓扑的全局性能越好。比如假定左侧拓扑结构的分值是10，右侧是8，那说明节点A和B同时被选的决策比单选B更优。按照这样的逻辑，全局最优的宏观选址就转化成了求解由节点组成的所有图结构中谁最优？ 的问题。
求解过程细化为数学建模和算法高效求解两步，具体实现在第四节介绍。
【数学建模】：设计一个目标函数模型，可以评价柜机网每一种图拓扑结构的分值
【算法高效求解】：在合理的计算资源和时间约束下完成基于目标函数的大规模群体评价
3.2 仿真效果
我们已将这一仿真过程落，实现了空间和价值双目标下对柜机网选址的全局优化。这种策略不光考虑了最大的潜在价值收益，还兼具合理空间分布。以效果仿真示意图为例，10个绿色已投放柜机和10个红色备选小区在4秒内计算出最优的结果，显示在备选小区组合 X*=(11,12,13,16,17,18,19,20) 投放柜机可达到全局最优选址效果。之所以选择这8台的原因，是它们整体的加入比起其他方案，使柜机网络在最大收益提升的同时也达到了较好空间分布效果。这就回答了前面提出的“某个区域备选小区中哪些应该被选择？” 和 “为什么被选择？”的问题。
可以看出，用运筹优化模型进行数理支撑解决了决策精度上的难点，它保证了决策过程是稳定的、标准的，不会因为地域、时间、决策者或场景的不同而发生变化。同时我们也能够很明确的知晓每一个场景的结果是怎么获得的，在现实业务中代表什么意思，具备了良好的解释性。进一步，高效求解算法使得在合理时间内求解能力由行政区级别（节点数为千级）扩展了10倍，到了市级别（节点数为万级），解决了规模上的难点，使得大规模全局选址成为可能。 下图是仿真界面展示的小区总数37000+规模的上海市再投放100台备选柜机的计算结果。蓝色是已投放柜机，黄色代表最优备选柜机投放点，整个决策过程在6分钟内完成。
四、建模及算法实现
4.1 数学建模
建模的目标是设计出一个评价柜机网每一种图拓扑结构分值的统一函数，需要完成：
- 首先定义评价备选解（拓扑结构）性能的统一指标
- 再枚举所有可能的备选解并计算各自的性能值
- 最后找出性能值最好的，对应的解即为最优拓扑结构
关于如何评价备选拓扑结构的性能，根据实际问题有多种处理方式，这里介绍一种基于图论电流距离中心性（Current Flow Closeness Centrality）的二次组合优化评价指标。
- 首先完成备选节点的单点评价：认为备选节点的价值是由已存在节点传播来的价值决定的，且价值随着节点间“距离”衰减，类似电流传导过程。如下图白色备选节点受到来自周围彩色节点的价值注入，彩色箭头表示价值的流动。生成所有节点的单点评价值向量V后进入下一步。
- 再对图拓扑全局进行性能评价：备选点对图拓扑整体带来的效应，除了和自己是否被选中有关，还与其他备选点是否被选中有关，这一关系用矩阵W来表达。明确了参数V和W之后运用二次组合优化模型Score进行全局性能的评价，其中红色部分强调了节点间相互影响的全局效应，xi 和 xj 是节点 i 与 j 被选中与否的二元决策变量，数字1表示选中，0表示未选中。加和后的Score就是某个拓扑X的性能评价值。
这样便完成了备选解评价的建模，我们再通过枚举所有可能的备选解并计算评分后，找出最大评分值对应的拓扑结构X*，视为最优解，用数学语言表达如下。
4.2 遗传算法高效求解
列举出所有备选解比想象的要困难的多，原因在于这些节点选还是不选的组合会造成解空间爆炸般的增长。备选解的个数O与节点个数N的关系用公式表示如下，
- 节点数为7时，拓扑结构有2^7 = 128个
- 节点数为20时，拓扑结构有2^20 = 1,048,576个
- 节点数为100时，拓扑结构有2^100 = 1,267,650,600,000,000,000,000,000,000,000个
而节点数100在实际场景中依然是个特别小规模的问题，考虑到实际应用中不管是计算资源还是计算时间都不能允许我们去穷尽所有备选解，那便要使用运筹中的元启发式算法来高效求解。
遗传算法 (Genetic Algorithm) 是借鉴进化生物学提出的元启发式算法，用于解决运筹规划的最优化问题。将备选解（拓扑结构）抽象为染色体，一个染色体代表一组节点决策向量X，染色体上的基因取值为1或0分别代表对应的节点被选中还是未被选中。然后使用上面提到的二次组合优化评价模型，挑选出优秀染色体，再将它们进行交叉、变异、次代生成等操作，使种群向更好的染色体进化。进化完成时最大的评价值所对应的染色体，就是最优拓扑结构。遗传算法的操作可以在多项式时间内将问题求解到比较好的准最优解，100个节点的运行时间可以在秒级完成。
五、后记
"夫未战而庙算胜者，得算多也；未战而庙算不胜者，得算少也。" 庙算，便是一种事前的理性规划。军事战略如此，企业经营亦如此。
无论问题规模还是评价维度，很多全局决策的难度都远超人类的主观判断能力。借助运筹优化模型这一数理支撑工具，可以为企业生产经营活动提供更加理性的工作指引，提高工作效率和决策准确度。接下来，会分别介绍柜机规格最优推荐模型和流式结构路网匹配模型，让大家从更多实例去体会运筹思想协助企业理性决策的能力，敬请期待。
网友评论