文章作者：Tyan
博客：noahsnail.com  |  CSDN  |  简书

本文为美团文章学习的笔记整理。

1. 美团智能配送系统架构

美团配送业务场景复杂，单量规模大。在大规模的业务场景下，配送智能化就变得非常重要，而智能配送的核心就是做资源的优化配置。

外卖配送既有线上的业务，也有线下的复杂运营。配送连接订单需求和运力供给。为了达到需求和供给的平衡，不仅要在线下运营商家、运营骑手，还要在线上将这些需求和运力供给做合理的配置，其目的是提高整体的效率。只有将配送效率最大化，才能带来良好的顾客体验，实现较低的配送成本。资源优化配置的过程，实际上是有分层的。在美团的理解中，可以分为三层：

1. 基础层是结构优化，它直接决定了配送系统效率的上限。这种基础结构的优化，周期比较长，频率比较低，包括配送网络规划、运力结构规划等等。
2. 中间层是市场调节，相对来说是中短期的，主要通过定价或者营销手段，使供需达到一个相对理想的平衡状态。
3. 再上层是实时匹配，通过调度做实时的资源最优匹配。 实时匹配的频率是最高的，决策的周期也最短。

Note:

• 基础层：例如调整运力，周期较长，频率较低，运力调整需要考虑的因素较多
• 中间层：动态定价，营销活动等，可以提前预估一定时间范围内的单量和运力，提前进行运力调度或动态定价
• 更高层：骑手的实时调度、实时订单分配

如上图所示，右边三个子系统分别对应这三层体系，最底层是规划系统，中间层是定价系统，最上层是调度系统。运筹优化是调度系统、定价系统、规划系统的核心技术。

Note:

• 机器学习系统：例如ETA预估
• 调度系统：根据订单进行骑手的分配
• LBS系统：路径规划
• 定价系统：根据时间、天气、运力情况进行动态定价
• 规划系统：可以使用行政区域划分，在此基础上再进行调整

2. 实战业务项目

2.1 智能区域规划

配送连接的是商家、顾客、骑手三方，配送网络决定了这三方的连接关系。当用户打开App，查看哪些商家可以点餐，这由商家配送范围决定，每个商家的配送范围不一样。用户在美团点外卖，为他服务的骑手是谁呢？又是怎么确定的呢？这些是由配送区域边界来决定的，配送区域边界指的是一些商家集合所对应的范围。

Note:

• 商家：商家配送范围
• 骑手：配送区域边界

在传统物流中，影响末端配送效率最关键的点，是配送员对他所负责区域的熟悉程度。越熟悉，配送效率就会越高。即时配送场景也类似，每个骑手需要尽量固定地去熟悉一片商家或者配送区域。对于管理而言，站点的管理范围也比较明确。如果有新商家上线，也很容易确定由哪个配送站来提供服务。所以，这个问题有很多运营管理的诉求在其中。

区域规划项目要解决的问题：1.配送区域里的商家不聚合；2.区域奇形怪状，空驶严重；3.站点的大小不合理。什么是好的区域规划方案？基于统计分析的优化目标设定。

优化的三要素是：目标、约束、决策变量。

1. 首先要确定优化目标。区域规划影响的主要是骑手的顺路性、空驶率，也就是骑手平均为每一单付出的路程成本。所以，将问题的业务目标定为优化骑手的单均行驶距离。基于现有的大量区域和站点积累的数据，做大量的统计分析后，可以定义出这样几个指标：商家聚合度、订单的聚合度、订单重心和商家重心的偏离程度。数据分析结果说明，这几个指标和单均行驶距离的相关性很强。经过这一层的建模转化，问题明确为优化这三个指标。
2. 梳理业务约束。区域单量有上限和下限；区域之间不能有重合，不能有商家归多个区域负责；所有的AOI(area of interest)不能有遗漏，都要被某个区域覆盖到，不能出现商家没有站点的服务；区域边界必须沿路网。

在目标和约束条件确定了之后，整体技术方案分成三部分：

1. 首先，根据三个目标函数，确定商家最优集合。
2. 配送团队和美团地图团队进行合作。先利用路网信息，把城市切成若干互不重叠的多边形，然后根据计算几何，将一批商家对应的多边形拼成完整的区域边界。
3. 最后，用美团自主研发的配送仿真系统进行仿真评测。

在区域规划过程中，人工介入还是非常必要的。

2.2 智能骑手排班

外卖配送场景的订单“峰谷效应”非常明显。上图是一个实际的进单曲线。

配送团队最终选用的是按组排班的方式，把所有骑手分成几组，规定每个组的开工时段。然后大家可以按组轮岗，每个人的每个班次都会轮到。算法要有自己的优化目标，为了解决这个问题，首先要做设计决策变量，把时间做了离散化，以半小时为粒度。对于一天来讲，只有48个时间单元，决策空间大幅缩减。然后，目标定为运力需求满足订单量的时间单元最多。在建模层面，标准化和通用的模型才是最优选。美团把人数做了归一化，算法分配每个班次的骑手比例，但不分人数。在算法决策的时候，不决策人数、只决策比例，这样也可以把单量进行归一化。每个时间单元的进单量除以每天峰值时间单元的单量，也变成了0~1之间的数字。如果某个时间单元内人数比例大于单量比例，叫作运力得到满足。

算法核心思想：基于约束条件，根据启发式算法构造初始方案，再用局部搜索迭代优化。

2.3 骑手路径规划

骑手的路径规划问题，不是简单的路线规划，一个骑手身上有很多配送任务，这些配送任务存在各种约束，怎样选择最优配送顺序去完成所有任务，这是一个NP难问题。当有5个订单、10个任务点的时候，就存在11万多条可能的顺序。系统派单、系统改派，都依赖路径规划算法。在骑手端，给每个骑手推荐任务执行顺序。路径规划算法核心的诉求是优化效果必须是稳定的好。不能这次的优化结果好，下次就不好。另外，运行时间一定要短。

求解路径规划这类问题经历过的阶段：起初，采用类似遗传算法的迭代搜索算法，但是随着业务的单量变大，发现算法耗时太慢，根本不可接受。然后，改为大规模邻域搜索算法，但算法依然有很强的随机性，因为没有随机性在就没办法得到比较好的解。而这种基于随机迭代的搜索策略，带来很强的不确定性，在问题规模大的场景会出现非常多的Bad Case。另外，迭代搜索耗时太长了。在这个项目中，基本可以确定这样的技术路线。首先，只能做启发式定向搜索，不能在算法中加随机扰动。不能允许同样的输入在不同运行时刻给出不一样的优化结果。然后，不能用普通迭代搜索，必须把这个问题结构特性挖掘出来，做基于知识的定制化搜索。

美团认为，最重要的是看待这个问题的视角。这里的路径规划问题，对应的经典问题模型，是开环TSP问题，或是开环VRP的变种么？可以是，也可以不是。美团做了一个有意思的建模转换，把它看作流水线调度问题：每个订单可以认为是job；一个订单的两个任务取餐和送餐，可以认为是一个job的operation。任意两个任务点之间的通行时间，可以认为是序列相关的准备时间。每一单承诺的送达时间，包括预订单和即时单，可以映射到流水线调度问题中的提前和拖期惩罚上。

美团把一个经典的基于问题特征的启发式算法做了适当适配和改进，得到了非常好的效果。相比于之前的算法，耗时下降70%，优化效果不错。

2.4 订单智能调度

配送调度场景，可以用数学语言描述。它不仅是一个业务问题，更是一个标准的组合优化问题，并且是一个马尔可夫决策过程。并非对于某个时刻的一批订单做最优分配就足够，还需要考虑整个时间窗维度，每一次指派对后面的影响。要考虑长周期的优化，而不是一个静态优化问题。

这个问题的挑战：

1. 性能要求极高，要做到万单对万人的秒级求解。
2. 动态性。作为一个MDP问题，需要考虑动态优化场景，这涉及大量的预估环节。目前的思路，是通过其它的建模转换手段进行解决。
3. 配送业务的随机因素多。比如商家的出餐时间，也许是很长时间内都无法解决的随机性。就连历史每一个已完成订单，商家出餐时间的真值都很难获得。商家出餐时刻不确定，这个随机因素永远存在，并且非常制约配送效率的提升。另外，在顾客位置交付的时间也不确定。写字楼工作日的午高峰，上电梯、下电梯的时间，很难准确进行预估。对于骑手来说，平台没法规定每个骑手的任务执行顺序。骑手在配送过程中可以自由发挥，所以骑手执行顺序的不确定性也一直存在。

Reference

1. 美团智能配送系统的运筹优化实战

目录

Part 1《学习立行》公众号发布(13篇)

Part 2《运筹优化与地理信息》公众号发布(23篇)

Part 3 CSDN账号发布

运筹优化编程开发系列教程 (8篇)

运筹优化学习系列 (26篇)

本文系统总结了截至2021年12月5日以来，个人团队在CSDN和微信公众平台上发布的，与运筹优化相关的博客和微信公众号文章。整理出来，以飨读者。

Part 1《学习立行》公众号发布(13篇)

优化 | 01 求解TSP的2-opt算法原理与python实现

​​​​​​优化 | 02 背包问题-算法及python源码

优化 | 03 背包问题建模与gurobipy和Lingo求解

优化 | 04 车辆路径问题的doccplex求解

优化 | 05 车辆路径问题的gurobipy求解

优化 | 06 非线性下料问题的lingo建模与求解

【干货】C#调用Cplex入门基础总结

01 基于NetworkX的VRP最优解转路径

02 基于NetworkX绘制VRP及其拓展问题关系图

03 TensorFlow之Computational Graph详解

04 Bender分解算法数值案例与gurobipy实现

05 Gurobipy处理无界/不可行模型

06 对偶理论与多面体

Part 2《运筹优化与地理信息》公众号发布(23篇)

简单模糊决策及scikit-fuzzy实现

Gurobipy求解二次规划问题及案例代码

Python单变量函数优化

Scipy求解无约束非线性规划问题

SciPy.optimize.minimize接口解析与示例

Cplex基础知识与示例详解

Cplex OPL 编程实战案例

Gurobi+Python求解多目标指派问题

VRP建模推导：基础模型到集分割模型

拉格朗日分解技术案例及Python实现

Gurobi+python求解hub_and_spoke问题

运筹学笔记 | 01运用数学模型解决

运筹学笔记 | 02 运筹学中的确定性优化模型

运筹学笔记 | 03 dotNet下的Gurobi开发基础

运筹学笔记04 | 时间约束最短路问题模型及算例

运筹学笔记05 | No module named 'docplex'

线性规划python手册01：基本概念介绍

线性规划python手册02：一些例子

线性规划python手册03：使用Scipy包解LP

线性规划python手册04：使用pulp包解LP

线性规划手册05：使用Cplex的OPL语言解LP

线性规划手册06：C#调用Cplex解LP

Lingo求解VRP模型及代码

Part 3 CSDN账号发布

运筹优化编程开发系列教程 (8篇)

​​​​​​基于Gurobi编程开发教程01：python环境配置及列生成求解CVRP示例_m1m2m3mmm的博客-CSDN博客

Gurobi运筹学开发教程02：基于系数矩阵和右侧项的python+gurobi建模_m1m2m3mmm的博客-CSDN博客

Gurobi运筹学开发教程03：python+gurobi实现bender decomposition 算法示例代码_m1m2m3mmm的博客-CSDN博客

Gurobi运筹学开发教程04：拉格朗日分解技术及其实现_m1m2m3mmm的博客-CSDN博客

Cplex OPL语言实战案例_m1m2m3mmm的博客-CSDN博客

GAMS建模技术案例01 求解简单的线性规划模型_m1m2m3mmm的博客-CSDN博客

GAMS建模技术案例02 基于Elements的建模_m1m2m3mmm的博客-CSDN博客

GAMS建模技术案例03 使用Table(generator, *) 生成模型_m1m2m3mmm的博客-CSDN博客

运筹优化学习系列 (26篇)

运筹优化学习01：Lingo入门与错误列表分析_m1m2m3mmm的博客-CSDN博客

​​​​​​运筹优化学习02：Lingo求解带容量约束的车辆路径问题（CVRP）_m1m2m3mmm的博客-CSDN博客_cvrp问题模型约束条件含义​​​​​​运筹优化学习03：Lingo非唯一最优解问题--油气开采构造处最优选择问题_m1m2m3mmm的博客-CSDN博客

运筹优化学习04：Lingo的sum函数和for函数的使用方法介绍_m1m2m3mmm的博客-CSDN博客_lingo中sum函数用法

运筹优化学习05：Lingo进行TSP路径优化源码分享与经典文献分析_m1m2m3mmm的博客-CSDN博客

运筹优化学习06：拉格朗日松弛算法（一）_m1m2m3mmm的博客-CSDN博客_拉格朗日松弛

运筹优化学习07：Lingo的 @if 函数的使用方法_m1m2m3mmm的博客-CSDN博客

运筹优化学习08：Repairing MIP infeasibility through local branching_m1m2m3mmm的博客-CSDN博客

运筹优化学习09：一个示例带你入门如何使用C++、C#、Java、Python、Matlab调用Cplex_m1m2m3mmm的博客-CSDN博客

运筹优化学习10：分支定界算法求解整数规划问题及其Matlab实现_m1m2m3mmm的博客-CSDN博客_用分支定界法求解下列整数规划问题

运筹优化学习11：java调用Cplex求解TSP_m1m2m3mmm的博客-CSDN博客

运筹优化学习12：模拟退火算法求解TSP原理及C++实现代码_m1m2m3mmm的博客-CSDN博客

运筹优化学习13：C#中Gurobi的配置及测试_m1m2m3mmm的博客-CSDN博客

运筹优化学习14：LocalBranching用法手册_m1m2m3mmm的博客-CSDN博客

运筹优化学习15：求解线性规划的单纯形法【手把手计算，够你应付考试了，看不懂算我输】_m1m2m3mmm的博客-CSDN博客

运筹优化学习16：【电招问题】Dial-a-Ride问题模型及C#实现的VNS程序_m1m2m3mmm的博客-CSDN博客

运筹优化学习17：马尔科夫决策规划--例题及Matlab、Lingo和Cplex的建模实现_m1m2m3mmm的博客-CSDN博客

​​​​​​运筹优化学习18：马尔科夫决策过程与动态规划 (手算及Matlab源码剖析)_m1m2m3mmm的博客-CSDN博客

运筹优化学习19：Cplex中文教程与实例详解_m1m2m3mmm的博客-CSDN博客_cplex教程

运筹优化学习20：C#调用Cpex入门指南_m1m2m3mmm的博客-CSDN博客

运筹优化学习21：Java调用Cplex实现求解Cuting Stock Porblem的列生成算法详解_m1m2m3mmm的博客-CSDN博客

运筹优化学习22：新项目研发项目进度制定与优化研究_m1m2m3mmm的博客-CSDN博客

运筹优化学习23：单因素方差分析理论及Matlab代码实现_m1m2m3mmm的博客-CSDN博客

运筹优化学习24：Gurobi902注册、下载、安装教程【保姆级手把手教学】_m1m2m3mmm的博客-CSDN博客

运筹优化25：ModuleNotFoundError: No module named ‘docplex‘_m1m2m3mmm的博客-CSDN博客

运筹优化学习26：Python求解线性规划问题入门手册_m1m2m3mmm的博客-CSDN博客

欢迎关注个人团队平台账号，多谢支持

        运筹学：主要运用数学方法研究各种系统的优化途径及方案，为决策者提供科学决策的依据。最优化方法的主要研究对象是各种有组织系统的管理问题及其生产经营活动。最优化方法的目的在于针对所研究的系统，求得一个合理运用人力、物力和财力的最佳方案，发挥和提高系统的效能及效益，最终达到系统的最优目标。

运筹学的具体内容包括：规划论（包括线性规划、非线性规划、整数规划和动态规划）、库存论、图论、决策论、对策论、排队论、可靠性理论等。

规划论：

• 线性规划

当目标函数f是线性函数而且集合A是由线性等式函数和线性不等式函数来确定的， 这一类问题为线性规划。

运筹优化（二）--线性规划概念及应用模型

运筹优化（三）--线性规划之单纯形法

运筹优化（四）--线性规划之对偶问题和灵敏度分析

运筹优化（五）--线性规划之内点法

• 整数规划

当规划问题的部分或所有的变量局限于整数值时， 这一类问题为整数规划问题。

运筹优化（九）--整数规划模型

运筹优化（十）--整数规划求解

• 非线性规划

研究的是目标函数或是约束函数中含有关于决策变量的非线性函数的问题。

运筹优化（十一）--无约束非线性规划

运筹优化（十二）--带约束非线性规划

• 随机规划

研究的是某些变量是随机变量的问题。

• 目标规划

线性规划只讨论一个线性目标函数在一组线性约束条件下的极值问题；而目标规划是多个目标决策，可求得更切合实际的解。线性规划求最优解；目标规划是找到一个满意解。线性规划中的约束条件是同等重要的，是硬约束；而目标规划中有轻重缓急和主次之分，即有优先权。线性规划的最优解是绝对意义下的最优，但需花去大量的人力、物力、财力才能得到；实际过程中，只要求得满意解，就能满足需要（或更能满足需要）。

运筹优化（六）--目标规划定义及解法

• 动态规划

研究的是最优策略基于将问题分解成若干个较小的子问题的优化问题。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法 — — 动态规划。 1957年出版了他的名著Dynamic Programming，这是该领域的第一本著作。
虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划(如线性规划、非线性规划)，只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。

运筹优化（七）--动态规划解析

• 组合最优化

研究的是可行解是离散或是可转化为离散的问题，是一类在离散状态下求极值的问题。一部分离散优化问题，实际上跟整数规划有关，设计到精确最优解，另外一部分是近似解，即启发式算法求解。大多数情况下，是由于大规模算例无法求得精确最优解。组合最优化又称组合规划，是在给定有限集的所有具备某些特性的子集（也就是有限可行解）中，按某种目标找出一个最优子集（最优解）的一类数学规划。初期，它所研究的问题，如广播网的设计、旅游路线的安排、课程表的制订等，都是网络上的一些极值问题。后来，对这些问题进行概括和抽象，在理论上研究了拟阵中一些更一般的组合最优化问题及算法。主要研究内容有：线性组合最优化问题；网络上的最优化问题；独立系统和拟阵，拟阵是组合优化中一个基本而重要的概念，许多组合问题都可化为拟阵问题。贪心算法是求拟阵的最优独立集的简单算法；交错链算法是求解最优交问题的基本算法。对问题算法的分类也是一类主要研究内容。某些算法具有多项式时间复杂度，如贪心算法、交错链算法，称之为多项式时间算法，能用多项式算法求解的问题为P问题（注意其结果是判定问题）。还有一类问题从求解的计算量角度看有如下共性：①它们都未找到多项式算法。②若对其中的某一个问题存在多项式算法，则这一类的所有问题也都有多项式算法。这些问题组成的等价类称为NP完备问题，如装箱问题、推销员问题等。人们在求解这类问题时，往往采用“启发式”算法，不能保证求得最优解，但常常能求得较好的近似解 。

运筹优化（十三）--大规模优化方法

运筹优化（十四）--离散优化的启发式算法

• 无限维最优化

研究的是可行解的集合是无限维空间的子集的问题，一个无限维空间的例子是函数空间。

排队论：

排队论(queueing theory)也称随机服务系统理论 , 它研究的内容有下列三部分。

(1) 性态问题, 即研究各种排队系统的概率规律性, 主要是研究队长分布、等待时间分布和忙期分布等 , 包括了瞬态和稳态两种情形。

(2) 最优化问题, 又分静态最优和动态最优,前者指最优设计, 后者指现有排队系统的最优运营。

(3) 排队系统的统计推断,即判断一个给定的排队系统符合于哪种模型,以便根据排 队理论进行分析研究。

运筹优化（十六）--排队论基础及其最优化求解

库存论：

研究如何确定合理的存贮量及相应的订货周期、生产批量和生产周期，保证供应且使总的费用支出保持最小值的一种数学方法。控制和保持存货是每个经济部门和单位的共同课题。存货有四个方面的功能因素： 时间性、不连续性、不确定性和经济性。时间性因素是指货物在到达最终消费者手中之前要经过一个漫长的生产和分配过程。没有人愿意在购买商品时等这么长的时间，如果备有存货，则可以缩短前置时间，满足需求; 不连续性因素使得有可能按独立和经济的方法去处理各种相互依存的业务; 不确定因素是指使组织改变原定计划的不测事件; 经济性因素使企业可以利用成本进行方案的选择。按未来需求量情况来划分存货问题的类型有确定性、风险型和不确定型三种。确定型是指未来的需求量确切地知道的存货问题; 风险型是指知道未来需求量的概率分布的存货问题，不确定型是指未来的需求没有确定的概率的存货问题

运筹优化（十七）--存储论基础及其最优化求解

图论：

图论〔Graph Theory〕是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。

图论（一）--基础概念

图论（二）--各种图介绍

图论（三）--各种基础图算法总结

对策论

博弈论又被称为对策论（Game Theory），既是现在数学的一个新分支，也是运筹学的一个重要学科。博弈论主要研究公式化了的激励结构间的相互作用，是研究具有斗争或竞争性质现象的数学理论和方法。 博弈论考虑游戏中的个体的预测行为和实际行为，并研究它们的优化策略。生物学家使用博弈理论来理解和预测进化论的某些结果。博弈论已经成为经济学的标准分析工具之一。在金融学、证券学、生物学、经济学、国际关系、计算机科学、政治学、军事战略和其他很多学科都有广泛的应用。

运筹优化（十八）--对策论基础及其最优化求解

决策论：

研究为了达到预期目的，从多个可供选择的方案中如何选取最好或满意方案的学科。一般决策分为确定型决策、风险型决策和不确定型决策三类。确定型决策又分为静态确定型决策和动态确定型决策两种；不确定型决策分为静态不确定型决策和动态不确定型决策两种。风险型和不确定型等决策问题，都是随机型决策问题。随机型决策的基本特点是后果的不确定性和后果的效用表示。如果决策者采用的策略和依据的客观条件（简称状态）是不确定的，作出某种决策所出现的后果又将会是不确定的，后果的这种不确定性是随机型决策问题的主要特征之一。此外在进行决策之前，必须确定各种后果的效用，效用是对后果价值的定量分析。

运筹优化（十九）--决策论基础及其最优化求解