运筹学语言NCL及其工业应用.ppt

运筹学语言NCL及其工业应用,2000-2008 ENGINEST. All rights reserved.,NCL语言,NCL语言 2000-2008. ENGINEST. All rights reserved,Simpler Smarter Swifter,语法分析器（parser）：模式识别技术 支持自然建模 支持可视化模型调测及诊断 解算器（solver）：混合集合规划 求解实数、整数、布尔值、时间、索引 及集合类型上的混合约束; 支持一阶逻辑、集合推理、数值分析等 求解规则编程（rules） 支持启发式求解策略 支持业务规则：快速构建解决方案,NCL是一门集逻辑、优化及求解规则为一体的智能描述型语言， 支持业务建模和问题求解，独立于领域，跨行业。,2000年国际逻辑编程协会的官方杂志JLP发表 J. Zhou: Introduction to the constraint language NCL. JLP: 45(1-3): 71-103 (2000).,顶级创新企业 法国参议院奖,法国科技创新奖,Solving by Describing,混合集合规划: 超越线性模型的建模,Simpler Smarter Swifter,NCL语言 2000-2008. ENGINEST. All rights reserved,混合域(实数、整数、布尔值、索引及集合)上的联合求解系统; 支持一阶逻辑、集合推理、实数域数值分析等。,集合对信息的聚合性（基数、上界、下界、交、并、差、前继、后继） 动态量词逻辑增强模糊推理的能力，支持更强大的问题描述与求解: - “ i A () - i A () - i A xi 基于算法耦合的推理 - NCL有300多种域切割算法; - 算法之间耦合形成网状关系，进一步提升求解能力。,“ i 1,6 xi = O， A 1,6, #A = 2, i A xi = 6,1，3，2，4，6，7,NCL可在预求解（pre-solve）阶段确定 : A = 3, 4 x3 = 2, x4 = 4, x3 + x4 = 6,NCL语言的求解框架,NCL语言 2000-2008. ENGINEST. All rights reserved,Simpler Smarter Swifter,约束切割（Constraint Cut）和树搜索（Tree Search）,Simpler Smarter Swifter,NCL求解规则,最小化松弛度(Least Slack) 一般来说，松弛度越小，非确定性越小，产生回溯的可能性也越小； 最大化松弛度(Greatest Slack) 域越大，分枝后变化越大, 域切割的扩散性越大。一般来说，很适用于实数变量； 最小化遗憾度(Least Regret) 分枝时分枝点处的搜索准则的差异越大，选枝越容易，回溯时遗憾度越小。 本例中，我们倾向选择这样的order：它距离可能的nextOrder中最近的与次近的 差距最大，即最大化“次小与最小之差”。那么该order相对其他“次小与最小之 差”较小的order，选枝选错的可能性要小，因而该步回溯时遗憾度要小； 顺序性(Ordering Search) 根据一些实际的业务规则选枝搜索以使解空间尽量保持凸性； 贪婪性(Greedy Search) 局部最贪婪地向有利于优化目标的方向选枝搜索。该准则一般用作最后一条。,NCL语言 2000-2008. ENGINEST. All rights reserved,Simpler Smarter Swifter,NCL语言 2000-2008. ENGINEST. All rights reserved,Square Packing: NCL描述建模的例子,将一些小正方形拼成一个大的正方形, 要求任意两个小正方形交集为空且 相邻的正方形间不含间隙。,d = 112, n = 21, i 1, n ( si = , Xi 1, d , Yi 1, d , Xi = xi, xi + (si-1) , Yi = yi, yi + (si-1) , ), i j 1, n Xi Xj = Yi Yj = , i 1, n (min xi) Xi = ? (), i 1, n (min yi) Yi = ? ().,21个小正方形的边长为: 50, 42, 37, 35, 33, 29, 27, 25, 24, 19, 18, 17, 16, 15, 11, 9, 8, 7, 6, 4, 2。 大正方形的边长为112 。 NCL可以找到符合条件的所有8个解。,所有的小正方形不可以重叠，所以任意两个小正方形的横坐标两两不交或纵坐标两两不交。,来源: C.J. Bouwkamp & A.J.W. Duijvestijn. Catalogue of simple perfect squared Squares of orders 21 through 25. Eindhoven University of Technology, Technical Report 92 WSK 03, The Netherlands, November 1992.,Simpler Smarter Swifter,两两不等与两两不交,“两两不等的整数”与“两两不交的集合”的约束遍布组合优化问题： 整数变量的两两不等 i j 1, n xi xj , 集合变量的互不相交 i j 1, n Ai Aj = ,NCL语言 2000-2008. ENGINEST. All rights reserved,集合覆盖与拼排,Simpler Smarter Swifter,“集合划分”和“拼排”的约束常见于计划与排程问题中： 集合划分 C = i 1, n Ai , i j 1, n Ai Aj = , 二维拼排 i j 1, n xi xj yi yj, i j 1, n xi xj Ai Aj = , i j 1, n Ai Aj = Bi Bj = ,NCL语言 2000-2008. ENGINEST. All rights reserved,整数索引与排序,Simpler Smarter Swifter,整数排序 i 1, n ( xi 1, n, yi = zxi ), i j 1, n ( xi xj , zi zj ),整数递归排序 i 1, n-1 ( xi 2, n , zi zxi ) , i j 1, n-1 xi xj ,整数索引与排序的算法遍布计算机系统的各级运算中。 整数索引与排序的约束更是NCL语言的基础。,NCL语言 2000-2008. ENGINEST. All rights reserved,集合索引与排序,Simpler Smarter Swifter,集合排序 i 1, n ( xi 1, n, Ai = Bxi ), i j 1, n ( xi xj , Bi Bj ),集合递归排序 “ i 1, n-1 ( xi 2, n , Bi Bxi ) , i j 1, n-1 xi xj ,集合索引与排序的约束是scheduling及routing类问题的基础。,NCL语言 2000-2008. ENGINEST. All rights reserved,求和约束,Simpler Smarter Swifter,变量求和的约束常见于能力(capacity)及背包等类问题： 实数求和 f = i A gi , 整数求和 y = i A xi , 布尔值求和 y = i A ai ,NCL语言 2000-2008. ENGINEST. All rights reserved,累积约束,Simpler Smarter Swifter,二维累积: i D yi = j A (i Cj) xj , 递归累积: i 1, n-1 ( xi 2, n, zxi = z i + wxi ),NCL语言 2000-2008. ENGINEST. All rights reserved,NCL建模举例: Set Partitioning(定义),Simpler Smarter Swifter,给定任务集合TASK及班次集合SHIFT，对应每个班次i给定: 任务子集 TaskShifti 班次成本 costShifti 问题要求从SHIFT中选出最优的子集Partition，覆盖所有任务且使成本最小。 该模型可以应用于如 Crew scheduling等物流优化问题。,NCL语言 2000-2008. ENGINEST. All rights reserved,来源: K.L. Hoffman & M. Padberg, Solving airline crew scheduling problems by branch-and-cut, Management Science, vol. 39, no. 6, pp657-682, June 1993.,NCL建模举例: Set Partitioning(NCL 模型),Simpler Smarter Swifter,nbTask = , % Number of tasks nbShift = , % Number of shifts TASK = 1, nbTask, SHIFT = 1, nbShift, i SHIFT ( costShfiti = , % cost of shift i TaskShifti = , % set of tasks of shift i ), Partition SHIFT, i Partition TaskShifti = TASK, % set partioning constraint i j Partition TaskShifti TaskShiftj = , min i PartitioncostShfiti i SHIFT ( min inf TaskShifti % ordering search min costShfiti % greedy search max # TaskShifti % greedy search ) i Partition ?,NCL语言 2000-2008. ENGINEST. All rights reserved,NCL建模举例: Set Partitioning(结果),Simpler Smarter Swifter,对于nw19, nw09, nw06, nw07, NCL在20分钟内可以找到并证明最优解； 对于nw11, NCL在46分钟内可以找到并证明最优解。,NCL语言 2000-2008. ENGINEST. All rights reserved,nw19: k Partition costShfiti = 10898 Partition = 62, 134, 484, 942, 1543, 2126, 2699 nw09: k Partition costShfiti = 67760 Partition = 3, 10, 18, 27, 42, 108, 210, 424, 810, 1217, 1306, 1929, 2170, 2581, 2651, 2904 nw06: k Partition costShfiti = 7810 Partition = 4, 136, 200, 421, 874, 1538, 2901, 3845 nw07: k Partition costShfiti = 5476 Partition = 23, 88, 591, 1943, 3017, 5150 nw11: k Partition costShfiti = 116256 Partition = 9, 52, 135, 221, 333334, 368, 2414, 2960, 3638, 4077, 6286, 6940, 7380, 7511, 8438, 8696, 8753, 8819,NCL建模举例: Set Partitioning(比较),Simpler Smarter Swifter,NCL语言 2000-2008. ENGINEST. All rights reserved,对比德国的Oz小组的结果：T. Mller. Solving set partitioning problems with constraint programming. In PAPPACT98, pp313-332, 1998.,Mller 的Oz 算法: pre-processing + CP solver + global constraint,Mller98中所有其他问题均能被NCL轻易地求解在此不作赘述,Simpler Smarter Swifter,NCL建模举例: Job-shop Scheduling(定义),- 次序变量: orderi,j 表征作业 j 在机器 i 上的工序的执行次序; - 工序时间段变量: Taski,j表征作业 j 在机器 i 上的工序的执行时间段; - 排序后时间段变量: Sortedi,j表征在机器 i 上的排在第j个执行的作业的工序时间段; - 集合排序模型用来描述(资源独占性)生产排程问题: i MACHINE i MACHINE j JOB j k JOB ( Taski, j = Sortedi, orderi,j , orderi,j orderi,k, Sortedi,j Sortedi,k ),来源: J.F. Muth & G.L. Thompson. Industrial Scheduling. Prentice Hall, 1963.,工序时限约束 优先执行约束 资源独占约束,优化目标: 最小化工期,Simpler Smarter Swifter,10台机器10件作业的MT10问题在1963-1988的25年间无人能解。,仅3类约束:,NCL语言 2000-2008. ENGINEST. All rights reserved,Simpler Smarter Swifter,NCL建模举例: Job-shop Scheduling(NCL 模型),nbJob = O, % number of jobs nbMachine = O, % number of machines TIME = O, % time horizon JOB = 1, nbJob, MACHINE = 1, nbMachine, i MACHINE ( j JOB ( Taski,j = releasei,j, duei,j, % time interval of job j on machine i Sortedi,j = t1i,j, t2i,j, % task of the job sorted j-th on machine i Taski,j TIME, Sortedi,j TIME, orderi,j JOB, % job execution order on a machine Taski,j = Sorted i, orderi,j , % Taski,j permuted to Sortedi,_ by orderi,j ) j JOB ( oi,j = O, % order of job j on machines is known Task oi,j , j = O, % task duration is known ), j k JOB ( orderi,j orderi,k, % permutation constraint over order Sortedi,j Sortedi,k , % precedence constraint over sorted tasks ) ),Simpler Smarter Swifter,NCL语言 2000-2008. ENGINEST. All rights reserved,Simpler Smarter Swifter,NCL建模举例: Job-shop Scheduling(NCL 模型), j JOB i k MACHINE Taskoi,j, j Taskok,j, j , % ordering of job j on the machines i MACHINE ( min k JOB Sortedi,k , % select the most saturated machine ) j JOB ( min k orderi,j Sortedi,k / orderi,j, % select the job with least slack max Taski,j % select the task with least slack ) orderi,j = ? (), % query on execution order i MACHINE j JOB releasei,j = ?, % query on release min maxi MACHINE t2i,n . % minimize the maximum of due dates,Simpler Smarter Swifter,NCL语言 2000-2008. ENGINEST. All rights reserved,Simpler Smarter Swifter,NCL建模举例: Job-shop Scheduling (结果与比较),参见: D. Applegate and B. Cook. A Computational Study of the Job Shop Scheduling Problem, Operations Research Society of America, vol 3, no 2, 1991.,NCL在2 分钟内可求解著名的MT10 (10*10的问题),简洁纯净的数理逻辑模型 NCL的集合排序模型可求解上文中所有10*10的问题 NCL可求解（最优证明）部分10*15，15*15的问题,Simpler Smarter Swifter,NCL语言 2000-2008. ENGINEST. All rights reserved,Simpler Smarter Swifter,带时间窗口的取货送货问题(PDPTW)涉及到的约束有：递归排序、累积能力约束、时间窗口约束、优先约束、耦合约束等。,NCL建模举例: Pickup and Delivery(定义),NCL语言 2000-2008. ENGINEST. All rights reserved,来源： H.B.Li & A.Lim, A Meta-Heuristic for the Pickup and Delivery Problem with Time Windows, 2001.,Li & Lim使用启发式方法求解可行解。无法求证最优性。,Simpler Smarter Swifter,NCL建模举例: Pickup and Delivery(NCL 模型), i j SOURCEORDER ( TimeOrderi TimeOrdernextOrder i , nextOrderi nextOrderi ),路径约束(集合递归排序),i TRUCK OrderTrucki = ORDER, i j TRUCK OrderTrucki OrderTruckj = ,订单的集合划分约束,NCL语言 2000-2008. ENGINEST. All rights reserved, i ORDER ( toOrderi 0 ( TimeOrderi TimeOrdertoOrderi, truckOrderi = truckOrdertoOrderi ), ),时序约束与偶合约束,Simpler Smarter Swifter,NCL建模举例: Pickup and Delivery(结果与比较),LC101结果图,LC201结果图,Li & Lim使用启发式方法求解可行解。无法求证最优性。 NCL可以对此问题的多组数据，找到最优解并证明最优解。,NCL语言 2000-2008. ENGINEST. All rights reserved,Simpler Smarter Swifter,NCL建模举例: Pickup and Delivery(结果与比较),LRC101结果图 Li&Lim找到的解: 1708 NCL找到最优解: 1702,LR101结果图 Li&Lim找到的解: 1650 NCL找到最优解: 1638,NCL语言 2000-2008. ENGINEST. All rights reserved,Li & Lim使用启发式方法求解可行解。无法求证最优性。 NCL可以对此问题的多组数据，找到最优解并证明最优解。,工业化,Simpler Smarter Swifter,NCL语言 2000-2008. ENGINEST. All rights reserved,应用举例 运输：车辆路径优化、多模式运输 生产制造：流程优化与离散排程优化 人力资源：特殊使命与呼叫中心排班,从实验室到实战应用是个艰难的过程，将求解系统工业化是在诸多技术成熟的基础上得来的,面对工业问题,Simpler Smarter Swifter,NCL语言 2000-2008. ENGINEST. All rights reserved,工业问题远比单纯的学术问题复杂得多 约束复杂、建模困难: 学术问题涉及几类约束，工业问题往往涉及数十类 规模大: 10台机器10件作业的Jobshop问题是学校的问题， 工业问题可上升到数万道工序的数量级 对实时性、可视化、直觉式交互、二次优化有很强需求 实施困难: 研发成本高、部署周期长、见效慢 需要平台化的开发工具进行工程化的开发,POEM平台,Simpler Smarter Swifter,POEM Solution Builder,集优化及求解规则为一体的支持业务逻辑建模和复杂问题求解的智能描述型语言。,NCL语言,管理(地图、时间等)可视化和 “What If.” (如果.会怎样)式的交互。,PoemView可视化脚本,不仅是一个开发工具,而且是一个部件化的应用平台。 内嵌SQL语言,支持Oracle、DB2、SQL Server等数据库。 支持与C+ 、Java、VB等编程语言的接口；支持web应用(例如：) 。 在培训、管理、开发、部署和维护上均显优越性。,逻辑 + 运筹学算法 + 求解规则 + 可视化,POEM支持模块化的优化方案: 一个系统 各类业务优化方案 一套软件 开发应用部署,NCL语言 2000-2008. ENGINEST. All rights reserved,Simpler Smarter Swifter,法国天然气供应商Antargaz采用NCL优化管理70多个仓储中心向全法国22万家客户进行天然气的液罐车输送。采用NCL优化管理，使Antargaz大幅削减成本，显著提高配送效率，使用户得到业界最佳的服务，获得市场最佳的口碑。,危险品运输受公路的准入限制较高 对数据的精准度要求较高 对软件系统的逻辑性、灵活性、优化能力要求较高,NCL优化 = 盈利 + 胜出,NCL优化的效益: 例1,NCL语言 2000-2008. ENGINEST. All rights reserved,Simpler Smarter Swifter,法国天然气供应商Aquitaine Pyrnes Gaz、Gaz Est Distribution、Rhne Mditerrane Gaz、Nord GPL、Wogegal、Maison du Butane等采用POEM优化天然气的定量周期性(8星期)配送计划。,对客户的配送频率及卡车的客户分配的重组优化带来20%配送量的提升 削减 5-25% 的运输费用 降低物流配送成本，减少车辆使用量，优化行车路径 提高调度计划及排程的效率，使商业运作更逻辑化、合理化 支持直觉式的“What If.”交互, 可灵活、及时的再调度 减少对业务操作人员的依赖性.,NCL优化的效益: 例2,一个实例：Rhne Mditerrane Gaz的反馈信息,NCL语言 2000-2008. ENGINEST. All rights reserved,路径优化与配送,路径优化VRP (Vehicle Routing Problem)及其特例取货送货问题PDP (Pickup and Delivery Problem)是供应链节点上的主要优化问题，它涉及对车辆的全局最优调度及最优的路线规划。,车辆约束： 运输能力: 载量、时间量、时间跨度、多车次 相容性：车辆对客户的相容性(产品类、准入吨位、工作日期) 耦合性：不同的目的港要求两个订单由不同的车辆服务 客户优先级 其他: 在岗与否、工作条例、订单优先权.,优化目标： 最小化费用 最小化卡车数 最小化工作时间量 最小化工作时间跨度 最小化行程.,线路约束： 距离约束: 时间、里程、费用为度量的距离约束 工作条例: 工作时间量、间休、工作时间跨度 时间窗口: 要求早上（而非下午）供货 优先约束: 订单A优先订单B.,Simpler Smarter Swifter,NCL语言 2000-2008. ENGINEST. All rights reserved,集成到IE上的VRP/PDP系统,Simpler Smarter Swifter,NCL语言 2000-2008. ENGINEST. All rights reserved,模块化集成 优化与可视化 Web Service技术 支持多客户端的访问,客户服务器架构 客户端: Internet Explorer 计算服务器: PoemServer 数据库服务器： Oracle, DB2, SQL Server,多模式运输优化MMTP,多模式运输优化是将传统运输方式下相互独立的各种运输方式按照科学、合理的流程有效地组织起来，减少中间储存和中转时间，从而使客户获得最佳的运输路线、最短的运输时间、最高的运输效率、最安全的运输保障和最低的运输成本。,约束: 运输工具: 飞机、卡车、火车、轮船 供货商的供货能力 运输班次的运输能力 运输班次的时刻表