普通企业的规划类项目中,OptaPlanner更适合作为APS的规划优化引擎

在企业的规划、优化场景中,均需要开发规划类的项目,实现从各种可能方案中找出相对最优方案。如排班、生产计划(包括高层次的供应链优化,到细粒度的车间甚至机台作业指令)、车辆调度等。因为这类场景需要解决的问题,均可以归约为数学中的NP-C或NP-Hard问题。而解决此类问题,均需要通用的求解器才能实现。这类求解器也称规划引擎,通过它才能从天文数字的可能方案中,找出一个可行且相对优化的方案。

规划引擎的本质,是运用规划中的各种优化算法(目前用得比较多的是启发式算法),对一个NPC或NP-Hard 问题寻找最优解的过程。面对不同的问题、场景,会衍生出各种各样的运筹优化变种。但事实上这些问题都可以视作数学规划问题,可使用运筹学中的对应方法来处理。例如生产计划的排程,车辆路线规划与实时调度,工单的划分和开料问题等,都可以通过数学规划并优化。而求解器则提供了各种优化算法的软件,用于求解这类问题,也被称为规划引擎。

使用约束求解器实现求解,其中关键的步骤是问题进行建模。建模过程其实是把业务场景中的参数、变量、规则和优化目标等要素,转化成可被规划引擎识别,并运算的优化模型。在常见的商用求解器中,这些问题均需要被建模成数学模型,用数学语言来表达从业务流程中提练出来的业务规则与要求。求解器对数学模型求解,寻找并输出模型的最优解。客户端的程序再将最优解(即最优方案)转化成业务方案再,并传递给其它企业使用系统(例如ERP, MES等)。

目前市场上求解品的概况

商用求解器

当前市场上成熟的求解器并不多,且都被国外企业垄断而且价格昂贵,如Cplex, Gurobi等。这些都是目前世界上*的求解器,已发展多年;无论是性能与通用性上,都是数一数二的水平。其次,这些产品通常也会开放学术版本,只要提供符合要求的学术单位证明材料,即可获得学术版本,学术版通常是免费使用的,但仅限于学习、科研使用。商用场景则需要付费获得使用授权;因此,这类求解器很受运筹学领域的学术界欢迎。因为这些有运筹学或应用数学背景的高级人才,在学习、研究阶段已对这些求解器有一定应用基础,当他们毕业后从事相关领域工作时,这些他们熟悉的商用软件也相应地更有优势,更容易占领市场。

当然,依托大量资源的投入和长时间的技术积累和改进,商用求解器在性能、稳定性及售后支持方面占有绝对优势。但事物必然存在两面性,商用求解器也有它的不足之处。除了它的价格相对昂贵外,其实在某些条件下,还是存在一定使用上的劣势,下文详述。

开源求解器

开源求解器数量相对商用求解器更少,原因众多。优化核心的技术门槛,资源投入是主要因素。毕竟求解器所用到的优化算法,在学术上仍有不少改善空间,更不用说将技术理论实践到求解器中了。此外,开源技术主要依靠开源社区,或某些公司资助的团队负责开发与维护,与IBM等巨头可投入的资金与资源是比,有天壤之别的。因此,这方面的开源产品不多,开源的成熟产品更是少之又少。而目前较成熟的开源求解器,目前只有两个,一个是OptaPlanner, JBoss开源社区维护,主要由受雇于Red Hat的团队负责开发与更新。另一个是Google的OR-Tools, 由Google发布并维护;主要维护团队也是由Google资助。上述两个开源求解器都基于Apache License 2.0开源软件协助,对商用友好,且无开源传导性。对使用过它的系统并没有开源要求,仅需作出开源引用声明即可。

规划类项目(如APS项目)的设计开发过程

传统的商用规划引擎,通常直接面向数学优化问题,需要提供直接的数学模型,才能进行求解优化。因此,使用这类求解器,需要具体一定的数学功底,在业务模型的基础上设计数学模型。具体过程是:

业务分析与抽象

规划类项目(以APS项目为例),首先要对业务场景进行分析。从业务流程中获取并归纳业务实体、规则与优化目标。该工作的主要目的是对业务进行抽象、提练和业务模型设计。识别出业务实体,各个业务案例中有哪此约束,找出当前需要优化的要求。例如:生产计划中,结合订单与工艺信息,定义工单或生产任务。车辆路线规划场景中,根据车辆参数、运送物料的特性与要求等信息,识别出线路要求,走访节点顺序,最大运载量,节点走访时间限制等特性。在真实项目场景中,这些工作应该由经验丰富的APS顾问和业务顾问来完成。APS顾问应该从两个方面掌握这些抽象技巧。其一,必须掌握业务场景中的流程、规则和要求;必须识别出真实的规则,有哪些规则是同义且可合并的,有哪些规则是相冲的;并在此基础上作出最大可能的简化。其二,必须具备丰富的分析与抽象经验,掌握各种业务场景下的规则与要求,知道各种业务案例与要求,应该如何归纳成APS系统中的业务实体,规则约束和优化目标。

数学模型建立

完成了业务建模(即识别出业务实体,规则和优化目标)后,下一步则需要对这些业务模型转化成数学模型。因为常见的求解器(即规划引擎)其求解过程,其实是对数学模型最优解的寻找过程。各种优化规则与目标,需要通过各类参数与数学表达式来描述。对于有运筹或应用数学背景的研究人员,且经历过一定的数学建模实践训练后,这些工作并不困难。但我们常见的普通企业里,这类人才相对缺乏。通常情况下只能与高校、科研单位合作,才能获取此类人才资源。因此,数学模型这一步,也是普通企业难以解决的一步。而OptaPlanner规划引擎正好为我们省去这一步,只需完成业务分析、归纳,建立业务模型,即可作为引擎的输入进行求解。

求解

求解过程就是规划引擎对输入的模型+数据,在约定的规则范围内,在有限的求解时间内,通过各类优化算法,寻找相对最优解的过程。无论是常见的商业求解器,还是开源求解器,该过程都比较类似。但不同的求解器在不同的领域,求解的性能有较大的区别。有的面对大模型问题较有优势,有的则面对规则密集的场景能获取更佳质量。各求解器的具体特性,可以参照一些相关的评测文章。

OptaPlanner的求解特点

在求解过程中,OptaPlanner与其它求解器有所区别。因为OptaPlanner无需直接输入数学模型,仅需要通过Java+Drools表达的业务模型即可表达优化模型(未来的发展方向,将会侧重脱离Drools,直接通过Java即可表达丰富的约束,但目前的条件下,与Drools结合应用的方式并不会抛弃)。因此,在OptaPlanner求解过程的初始阶段,会有一个从业务模型到数学模型的转化过程,也就是把业务模型转化为规划核心程序可识别的数学模型,例如对于用Drools脚本表达的约束与优化目标(硬约束和软约束),编译成Java函数。而这些编译后的函数,可以反映出相应的数学模型。即OptaPlanner帮我们实现了从业务模型到数学模型的转化工作。

普通企业规划类项目限制与求解器使用

在普通企业(相对于各类资源丰富的央企或各类Top500企业)的IT部门,或较小型的软件公司;各级设计、开发人员,往往不具备深厚的数学建模能力,或有这方面背景的技术人员,但相关的优化项目实践经验也相对缺乏。因为,就算其中有部分人员在校时是研读相关专业,但若这类人员毕业后并没有持续这方面的工作,未能积累相当的规划方面项目经验,在面对零散、复杂的业务实体、约束与目标时,也很难将这些场景很好地建模成数学规划模型。因此,从业务模型到数学模型的转换,成了普通企业在进行规划类项目的最大门槛。

OptaPlanner在普通企业的规划类项目中可发挥的优势与限制

因应普通企业的人才资源限制,一个可以省却业务模型到数学模型转换的求解器,可以让规划类项目门槛降低不少。OptaPlanner则是这样的一个求解器。OptaPlanner可以通过Java的POJO来完整地表达业务实体;通过Drools脚本,或Java函数,或Java8以上的stream特性来表达约束和优化目标。因此,企业中的IT设计与开发人员,只需掌握这方面的技术,即可完成从业务模型到求解过程的过程,无经历困难的数学建模过程。因为,上述提到的OptaPlanner业务模型表达技术,都是一些与程序设计相关的技术,在以程序设计人才为主的普通企业中,这方面人才并不缺乏,掌握这方面的技术也不算非常困难。

但OptaPlanner也有一定的难点,主要表现在两方面的学习成本上,存在以下两个方面的成本:

Drools规则引擎的学习成本

在OptaPlanner目前主流的约束表达体系中,Drools仍然是不可或缺的,且是主流的技术。Drools是一个开源的规则引擎(注意:Drools是规则引擎,OptaPlanner是规划引擎,它们同属于开源项目KIE),它具有自己的语法、语义和表达方式。在OptaPlanner中,它是起到规则判断作用。但这种规则引擎在普通企业中,使用并不多。因此,对于IT设计、开发人来说,需要掌握Drools也需要一定的学习成本。但根据OptaPlanner项目的发展趋*来看,未来将会摆脱对Drools的依赖。其实现在也可以完全摆脱Drools,而完全使用Java来实现规则与约束的表达。但当前的版本特性下,很多场景下可表达的丰富性和灵活性,完全的Java语言还是难与Drools匹敌。而从最近的OptaPlanner数个版本发布的内容来看,将来会加大对Java8及以上版本的stream特性的支持。目前已经发布了一些基于stream的评分API,稍后有时候我将会写一篇这方面的文章。

求解的评价体系学习成本

OptaPlanner只需要使用者关注他们熟悉的业务,并对这些业务建立好相关的业务模型,即可实现规划求解。但是无论你是使用Drools,还是Java语言作为评分逻辑的实现方式,都需要掌握其评分体系,它是与表达方式无关的,在设计规划实体和约束时候的一种方法论。简而言之,OptaPlanner把数学规划模型中的限制条件,即s.t.,也即subject to.以及目标函数都通过约束来表达。suject to在OptaPlanner中可视作硬约束, 目标函数则对应于OptaPlanner中的软约。那么从业务上识别出哪些是硬性约束,哪些是优化目标后,应该如何通过约束实现不同的规则与优化目标,则需要对OptaPlanner中的评分体系有一定的理解,否则会较容易超出OptaPlanner的一些设计限制,引导各种异常,从而影响优化质量和结果的准确性。或所设计的评分规则无法真切地表达业务本意。本人在使用OptaPlanner过程中,总结了数种典型和异常情况,或约束表现正常,但并未能表达业务规则唯一性的情况;并分析了其中原因,以后有机会,我将会着重分享这些情况,详细论述各种异常,约束歧义和相应的规避原则。

无论如何,虽然OptaPlanner不需要我们把业务模型转化成数学模型,但能准确把业务模型中的各个实体、约束和优化目标转化成Java实体,约束表达脚本,还是需要一定的学习成本的。但这种能力的学习与实践,普通的IT软件设计人员即可掌握,而不需要具备应用数学或运筹学相关的学术人才。

总结

尽管OptaPlanner也有自己的学习成本,但在普通企业中,这此学习成本还是比培训数学建模相对更容易些,毕竟对人员的要求更低。毕竟使用OptaPlanner我们面对的都是一些软件设计的问题,这对于有丰富经验的软件开发人员,并不是不可逾越的鸿沟。但使用基于数学规划模型的求解器,则需要一定的应用数学背景和相关的数学知识和能力,且需要经过一定的数学建模实践训练,达到一定水平后,能才保证建模质量。无论是入门还是深入,后者对一普通企业来说,确实是更为困难。因此,我认为有规划方面项目的普通公司,还是优先使用OptaPlanner作为规划引擎更可行。

[Constraint satisfaction solver (Java™, Open Source)
​](www.optaplanner.org)

如需了解更多关于OptaPlanner的应用,请发电邮致:kentbill@gmail.com
或到讨论组发表你的意见:https://groups.google.com/forum/#!forum/optaplanner-cn
若有需要可添加本人微信(13631823503)或QQ(12977379)实时沟通,但因本人日常工作繁忙,通过微信,QQ等工具可能无法深入沟通,较复杂的问题,建议以邮件或讨论组方式提出。(讨论组属于google邮件列表,国内网络可能较难访问,需自行解决)

上一篇:在阿里云服务器上部署一个 flask 项目


下一篇:APS技术中的多目标规划问题