1、什么是运筹优化
运筹学(Operations Research)作为数学、计算机科学、管理学的交叉学科,最早起源于一战中的防空作战系统,由钱学森先生引入中国,最开始的用途是优化航空/军工等领域。如今广泛应用在企业的生产、运营、物流环节,通过算法指导和辅助人类管理者进行决策。在本博客中,我们将运筹优化概括为,通过求解一个最优化问题,在满足约束的条件下,最小化完成某件事所花费的成本。最优化问题常描述为一个数学规划问题,根据决策变量是连续或离散,可以分为两类:连续最优化问题与组合优化。
连续最优化问题的标准形式是:
这里x是决策变量,f(x)是目标函数,g(x)是不等式约束条件,h(x)是等式约束条件,且有m=p=0。若有m=p=0,则问题转化为无约束优化问题。函数f,g,h可以是线性或非线性,经典的求解算法有:牛顿法、梯度下降法、共轭法等等。
而当决策变量取值是(或部分是)整数,则是离散优化问题,常称为组合优化(Combinatorial Optimization),是运筹优化的一个重要分支,其标准形式是:
而当决策变量取值是(或部分是)整数,则是离散优化问题,常称为组合优化(Combinatorial Optimization),是运筹优化的一个重要分支,其标准形式是:
一般描述为混合整数规划(mixed integer programming,MIP),所有的参数(cj,dk,aij,gik,bi)取值是任意实数,只考虑线性表达式。$$m$$是约束条件的数量,$$n$$是连续变量数,$$p$$是整数变量数。若n=0则上述MIP转化为纯整数规划,若$$p=0$$则上述MIP转化为线性规划;特别的,若yk∈{0,1},全称量词k,则转化为二元(binary)规划问题。组合优化问题(如资源调度、生产排产、路径优化、运营排班等)是企业经营决策所面临的最常见的优化问题类型,覆盖商业决策优化的大部分流程,因此也是运筹学的主要研究对象之一。从航班和工厂的调度、金融资产配置、仓库货物存储到运输路线的设计,很多都可以建模成组合优化问题。本文讨论的对象是组合优化问题。
2、常见的组合优化问题及其求解方法
组合优化问题的离散特性为问题求解引入了特别的挑战,因为求解空间是随问题规模呈指数级增长的,其中有不少是NP-complete的。也就是说目前还找不到多项式时间复杂度的算法。NP-complete问题有很多,如经典的satisfiability(SAT)问题,minimum vertex cover(MVC)问题,max cut(MC)问题等等。它们之间可以在多项式复杂度内相互归约,也就是说其中一个被证明有多项式复杂度解法的话,所有的都有多项式复杂度解法。
2.1 常见的组合优化问题
NP-complete问题中最经典的问题之一要属旅行商问题(Traveling Salesman Problem,TSP),它是车辆路径问题(Vehicle Routing Problem, VRP)的一个特例。其迷人之处可能就在于看似描述很简单,日常生活中可能还常用到,但想要找到通用的高效解法却发现非常难。其可行解是所有点的全排列,随着点数的增加,会产生组合爆炸,暴力求解的复杂度O(n!)。问题描述为由n个城市组成的完全图,两个城市间有整数代价;有一个旅行商要走遍所有城市,每个城市只走一次且最后回到原点(即Hamilton回路),求所有城市的访问路径的顺序,且该路径的代价和最小。
很多时候对于中大规模TSP,尚无找到最优解的有效算法,其能找到的最好解与真正最优解的距离称为optimality gap。这也是评估很多TSP算法的重要指标,用来说明它的解接近最优的程度。自被提出后的几十年里,该问题在组合优化领域被反复地研究,从而衍生出基于精确算法、近似算法、启发式算法几大类成熟的方法。TSP问题在交通运输、电路板线路设计、物流配送等场景有着广泛的应用。
组合优化中的另一经典问题是车辆路径规划问题(Vehicle Routing Problem, VRP),描述为一定数量的客户,各自有不同数量的货物需求,从仓库向客户提供货物,由一个车队负责分送。需要组织适当的分配方案和行车路线,目标是使得客户的需求得到满足,并在一定的约束(时间窗、装载率)下,达到诸如路程最短、成本最小、耗费时间最少等目标。一个简单的有着16个客户(编号为1-16)、1个仓库(编号为0)的示意图如下所示,共需要4辆车完成配送(以不同颜色标识),每辆车服务4个客户,所有车均从仓库出发,服务完所有的客户之后,再返回仓库。