©2000-2012 ENGINEST. All rights reserved. NCL语言与一阶逻辑规划 The NCL Natural Constraint Language Programming in First-Order Logic 周建阳 ©2000-2012 ENGINEST. All rights reserved.

目录 Simpler • Smarter • Swifter 1. NCL语言 2. 算法框架 3. 工业应用

计算机语言可支撑起大规模应用 1. 优化计算语言NCL 支持优化计算的描述型数学语言 支持对工业问题的建模与求解 Simpler • Smarter • Swifter 支持优化计算的描述型数学语言 支持对工业问题的建模与求解 计算机语言可支撑起大规模应用 Ti1  [150.0, 240.0], To1  [250.0, 490.0], Ti2  [150.0, 190.0], To2  [210.0, 340.0], FE1  [2.941, 10.0], FE2  [3.158, 10.0], Fi1 ≥ 0.0, Fi2 ≥ 0.0, FB12 ≥ 0.0, FB21 ≥ 0.0, Fo1 ≥ 0.0, Fo2 ≥ 0.0, T11 = 500.0 – To1, T12 = 250.0 – Ti1, T21 = 350.0 – To2, T22 = 200.0 – Ti2, Fi1 + Fi2 = 10.0, Fo2 + FB12 = FE2, Fo1 + FB21 = FE1, Fi1 + FB12 = FE1, Fi2 + FB21 = FE2, FE2 × (To2 – Ti2) = 600.0, FE1 × (To1 – Ti1) = 1000.0, 150.0 × Fi1 + To2 × FB12 – Ti1 × FE1 = 0.0, 150.0 × Fi2 + To1 × FB21 – Ti2 × FE2 = 0.0, min 1300 × exp(0.6 × log(20000 × 6 / (4 × + (T11+T12)))) + 1300 × exp(0.6 × log(12000 × 6 / (4 × + (T21+T22)))) . NCL ©2000-2012. ENGINEST. All rights reserved.

计算机语言的类型 描述型语言(Description Language) NCL = 求解问题的数理逻辑描述语言 Simpler • Smarter • Swifter 描述型语言(Description Language) NCL = 求解问题的数理逻辑描述语言 Object-Oriented 高 级 形 式 声 明 型 语 言 建模语言(Scripting Modeling Language) AMPL, OPL = 求解问题的脚本型语言 Declarative Logic 逻辑约束语言(Constraint Logic Language) Prolog III, CLP(R), CHIP = Prolog + 约束 逻辑语言(Logic Language) Prolog = 谓词逻辑规划 过 程 语 言 Procedural 面向对象语言(Object-Oriented Language) C++, Java 命令型语言(Imperative Language) C, Pascal 初 级 形 式 Primitive Native 机 器 语 言 Native 汇编语言 Assembly Language NCL ©2000-2012. ENGINEST. All rights reserved.

求解系统(solver)与形式化(formalism) Simpler • Smarter • Swifter 线性规划(Canonical Form) 算法效率高 maximize cTx subject to Ax ≤ b and x ≥ 0 数值域（有理数） 线性模型 线性规划并非唯我独尊 一阶逻辑规划(机组排班问题) Pairing ⊂ PAIRING,  ∪i∈Pairing FlightPairingi = FLIGHT, min ∑i∈Pairing costPairingi  集合规划 一阶逻辑规划 面向对象规划 工程化应用 NCL ©2000-2012. ENGINEST. All rights reserved.

许多应用问题难以用线性模型与数值型变量表达 基于线性规划的算法解非线性问题时需作线性转换 线性解算器难以确保可读性,难以支持软件工程 背景与目标 Simpler • Smarter • Swifter 许多应用问题难以用线性模型与数值型变量表达 基于线性规划的算法解非线性问题时需作线性转换 线性解算器难以确保可读性,难以支持软件工程 数值域难以支持面向对象的、业务逻辑层面的建模 要求优化计算能超越线性模型与数值域 要求能对应用问题直接在业务逻辑层面建模并求解 NCL ©2000-2012. ENGINEST. All rights reserved.

逻辑编程与优化计算 高层级的逻辑求解系统 → 混合集合规划 将求解系统逻辑化 → 约束规划 传统数学规划有其局限性 Simpler • Smarter • Swifter 高层级的逻辑求解系统 → 混合集合规划 混合集合规划(Mixed Set Programming) 以一阶逻辑与集合推理为算法内核的逻辑求解系统 约束规划(Constraint Programming) 以约束形式描述变量间关系的规划框架 逻辑规划 (Logic Programming) 基于Mathematical Logic的计算机编程技术 Prolog 1972年A. Colmerauer 发明基于谓词逻辑的逻辑语言 将求解系统逻辑化 → 约束规划 传统数学规划有其局限性 概念的局限性 传统数学规划主要基于线性模型 方法的局限性 单纯型等算法及线性松弛 求解非线性问题需作复杂线性转化 应用的局限性 难于求解带复杂约束的非线性问题 难于应用于工业领域复杂运行环境 传统数学规划 线性规划(Linear Programming) 求解以线性函数为优化目标的线性约束系统的技术 Simplex 1947年Dantzig发明单纯型法解线性规划问题 NCL ©2000-2012. ENGINEST. All rights reserved.

Parser、Solver、Rules 三项技术的集成 求解系统的构成要素 Simpler • Smarter • Swifter Parser、Solver、Rules 三项技术的集成 建模 智能语法分析器 parser 简洁的、高层级的数学建模 一 体 化 求 解 系 统 解算 精确的解算器 solver 严谨的、完备的系统解算 规则 高效的求解规则 rules 快速的、个性化的规范求解 稳定求解大规模复杂问题的有效方法 Parser与Solver相结合，用简洁的数学模型自然清晰地定义问题 Rules与Solver相结合，用业务逻辑规范求解空间 NCL ©2000-2012. ENGINEST. All rights reserved.

NCL的资源优化模型 资源配置 Resource Allocation 资源 约束模板 Capacity约束 时间 人员 机器/设备/工位 Simpler • Smarter • Swifter 资源配置 Resource Allocation Capacity约束 资源 时间 人员 机器/设备/工位 运输工具 资金 人员排班 任务排程 路线规划 约束模板 异同 Distinctness 覆盖 Set Covering 求和 Sum 累积 Cumulation 排程 Scheduling 路径规划 Routing NCL ©2000-2012. ENGINEST. All rights reserved.

NCL发表物 专著 国际杂志 J. Zhou: The NCL Natural Constraint Language. Simpler • Smarter • Swifter 专著 J. Zhou: The NCL Natural Constraint Language. Springer, ISBN 978-3-642-23844-4, 2012. http://www.springer.com/computer/swe/book/978-3-642-23844-4 Science Press Beijing, ISBN 978-7-03-031784-1, 2012. 周建阳:《自然约束语言》，科学出版社. ISBN 978-7-03-024973-9 (2009). 国际杂志 J. Zhou: Introduction to the constraint language NCL. Journal of Logic Programming. 45 (1-3): 71-103 (2000). J. Zhou: A Permutation-Based Approach for Solving the Job-Shop Problem. Constraints 2(2): 185-213 (1997). NCL ©2000-2012. ENGINEST. All rights reserved.

超越“线性模型”与“数值域” 上升到“一阶逻辑” 支持“面向对象”的自然建模 2. 算法框架 Simpler • Smarter • Swifter 超越“线性模型”与“数值域” 上升到“一阶逻辑” 支持“面向对象”的自然建模 目标：超越线性模型与数值域 形式化框架：一阶逻辑 数据类型： 从数值类型扩展到布尔、日期/时间、集合类型的混合域 逻辑运算： 数值约束、布尔逻辑、量词、函数、日期/时间、集合运算等 NCL ©2000-2012. ENGINEST. All rights reserved.

支持以下逻辑推理 量词逻辑：∀i∈A (…), i∈A (…) 函数：func(x) 谓词：布尔函数 逻辑关系：∧,∨,,,, 一阶逻辑 Simpler • Smarter • Swifter 支持以下逻辑推理 量词逻辑：∀i∈A (…), i∈A (…) 函数：func(x) 谓词：布尔函数 逻辑关系：∧,∨,,,, 集合推理：∈,∉,⊂,⊄,≺,⊀,,,\ NCL ©2000-2012. ENGINEST. All rights reserved.

数据类型 类型 子类型 举例 布尔 (bool) 浮点数 (float) 整型 (integral) 集合 (set) Simpler • Smarter • Swifter 类型 子类型 举例 布尔 (bool) True, False 浮点数 (float) 0.01 整型 (integral) 整数 (int) 1 日期 (date) 31/01/2008 时间 (time) 08:00 日期-时间 (date-time) 31/01/2008 08:00 字符串 (str) "student" 指针 (ref) 布尔指针 (bool-ref) `T` 浮点数指针 (float-ref) `1.0` 整数指针 (int-ref) `1` 集合指针 (set-ref) `{1, 3, 5}` 集合 (set) 整数集合 (int set) {1, 3, 5} 日期集合 (date set) {31/01/2008} 时间集合 (time set) {08:00} 日期-时间集合 (date-time set) {31/01/2008 08:00} 字符串集合 (str set) {"boy", "girl"} 指针集合 (ref set) 布尔指针集合 (bool-ref set) {`T`, `F`} 浮点数指针集合 (float-ref set) {`1.0`, `3.0`, `5.0`} 整型指针集合 (integral-ref set) {`1`, `3`, `5`} 集合指针集合 (set-ref set) {`{1, 3}`, `[1, 5]`} NCL ©2000-2012. ENGINEST. All rights reserved.

运算关系及定义域 运算关系 定义域     →  ≢ 布尔 =  所有类型 < ≤ > ≥ 数值型, 日期/时间 Simpler • Smarter • Swifter 运算关系 定义域     →  ≢ 布尔 =  所有类型 < ≤ > ≥ 数值型, 日期/时间 ∈ ∉ 整型 / 集合 ⊂ ⊄ ⊃ ⊅ ≺ ⊀ ≻ ⊁ 集合 … NCL ©2000-2012. ENGINEST. All rights reserved.

数值型函数 函数 定义 -f negative | f | absolute arccos f arccosine arcsin f Simpler • Smarter • Swifter 函数 定义 -f negative | f | absolute arccos f arccosine arcsin f arcsine arctan f arctangent cos f cosine sin f sine tan f tangent exp f e g log f log e f √ square root f g exponentiation f + g addition 函数 定义 f - g subtraction f  g multiplication f / g division min(f, g) binary min max(f, g) binary max x  y integer division x mod y modulo ⌈f⌉ ceiling ⌊f⌋ floor min iA fi minimum max iA fi maximum iA fi sum … NCL ©2000-2012. ENGINEST. All rights reserved.

布尔型函数 函数 定义  a logical negation a  b logical and a  b logical or Simpler • Smarter • Swifter 函数 定义  a logical negation a  b logical and a  b logical or a  b exclusive-or a  b implication a  b equivalence a ≢ b not equivalence ∨i  A ai global or ∧iA ai global and iA ai global exclusive-or … NCL ©2000-2012. ENGINEST. All rights reserved.

集合型函数 函数 定义 {x} singleton [x, y] interval A  B set union A  B Simpler • Smarter • Swifter 函数 定义 {x} singleton [x, y] interval A  B set union A  B intersection A \ B set difference (complement) A \ x exclusion of an element from a set A << x leftward set shift A >> x rightward set shift #A cardinality inf A infimum of a set sup A supremum of a set ∪iA Ci global union ∩iA Ci global intersection … NCL ©2000-2012. ENGINEST. All rights reserved.

量词逻辑与逻辑分支 全称量词 ∀ i ∈ A ( … ) 存在量词 ∃ i ∈ A ( … ) 布尔表达式 ⇒ ( 分支1 条件式 ； Simpler • Smarter • Swifter ∃ i ∈ A ( … ) 存在量词 ∀ i ∈ A ( … ) 全称量词 布尔表达式 ⇒ ( 分支1 ； 分支2 ), 条件式 If-Then-Else ？(任意表达式) ( 表达式1 ：分支1 ; 表达式2 ：分支2 ; ：缺省分支 分支 Switch NCL ©2000-2012. ENGINEST. All rights reserved.

bool  [ [ program ], [ config ], level ] 逻辑函数与子模型 Simpler • Smarter • Swifter bool  [ [ program ], [ config ], level ] 布尔子模型 str = [ [ program ], [ config ], level ] 字符串子模型 <factorial>(n) ( n  2  ( factorial = n ; factorial = n × factorial(n-1) ) ), @ factorial(3). 自定义函数 函数即等同于一个用户定义的逻辑运算 子模型即等同于一个用户定义的逻辑过程 NCL ©2000-2012. ENGINEST. All rights reserved.

Cotangent：数值型自定义函数 <cotangent>(f) cotangent = cos(f) / sin(f), Simpler • Smarter • Swifter <cotangent>(f) cotangent = cos(f) / sin(f), pi  [3.0, 4.0], sin(pi) = 0, f  [1.0, 2.0], cotangent(f) = 0, @ (`pi` " = " pi "\n"), @ (`cotangent(pi/2)` " = " cotangent(pi/2) "\n"), @ (`f` " = " f "\n"). pi = <3.1415925025940..3.1415927410126> cotangent(pi/2) = <-0.0000000437114..0.0000000754979> f = <1.5707962512970..1.5707963705063> NCL ©2000-2012. ENGINEST. All rights reserved.

F T 上 中 下 孙膑的逻辑模型与求解 田忌的数学难题: 带约束的指派问题(assignment problem) Simpler • Smarter • Swifter 田忌的数学难题: 带约束的指派问题(assignment problem) 整体居于劣势的田忌如何取胜? 齐王 上 中 下 F T RANGE = { "上", "中", "下" },  i,j  RANGE tianjiWinsQiwangi,j = ○,  i  RANGE ( whichToFighti  RANGE, whichToFighti = ? ),  i  j  RANGE whichToFighti  whichToFightj , ∑ i  RANGE tianjiWinsQiwangi,whichToFighti ≥ 2 . 田忌 两两不等的整数 NCL 证明只有一个解: 上 胜 中: T 中 胜 下: T 下 胜 上: F 累加约束 NCL ©2000-2012. ENGINEST. All rights reserved.

Square Packing 将一些小正方形拼成一个大的正方形, 要求任意两个小正方形交集为空且正方形间不含间隙。 Simpler • Smarter • Swifter 将一些小正方形拼成一个大的正方形, 要求任意两个小正方形交集为空且正方形间不含间隙。 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个解。 NCL ©2000-2012. ENGINEST. All rights reserved.

Production Scheduling Simpler • Smarter • Swifter Simpler • Smarter • Swifter D. Applegate and B. Cook. A Computational Study of the Job Shop Scheduling Problem, Operations Research Society of America, vol 3, no 2, 1991. J. Zhou. A permutation-based approach for solving the Job-shop problem. Constraints 2(2): 185-213, (1997). NCL可最优求解Applegate & Cook的所有10×10问题(包括著名的MT10) NCL可最优求解Applegate & Cook的部分10×15与15×15的问题 NCL ©2000-2012. ENGINEST. All rights reserved.

NCL模型：二维排序(2D Sorting) Simpler • Smarter • Swifter Simpler • Smarter • Swifter 已知： TASK ：工序集合 ScheduleResourcek：资源k的可工作时间段的集合 未知： 资源轴: resourceTaski：工序i所用资源(整数变量) 时间轴: TimeTaski：工序i的加工时间段(集合变量) WorkTimeTaski：工序i实际加工时间集合 关键约束: 对任意不同工序i,j，所用资源不同或加工时间不冲突: ∀ i ≠ j ∈ TASK resourceTaski ≠ resourceTaskj  TimeTaski ∩ TimeTaskj = ∅ 工作日历约束： ∀ i ∈ TASK WorkTimeTaski = TimeTaski ∩ ScheduleResourceresourceTaski NCL ©2000-2012. ENGINEST. All rights reserved.

NCL可对此问题多组数据最优求解并证明最优。 Vehicle Routing Simpler • Smarter • Swifter - H.B.Li & A.Lim, A Meta-Heuristic for the Pickup and Delivery Problem with Time Windows, 2001. - J. Zhou: Routing By Mixed Set Programming. Proc. of The 8th International Symposium on Operations Research and Its Applications, 157-166 (2009). 带时间窗的取货送货问题(PDPTW) NCL可对此问题多组数据最优求解并证明最优。 约束：路径约束、运输能力、时间窗口、取货优先于送货、耦合约束等。 NCL ©2000-2012. ENGINEST. All rights reserved.

NCL模型：Routing 订单对卡车的集合划分 ∪i  TRUCK OrderTrucki = ORDER, Simpler • Smarter • Swifter 订单对卡车的集合划分 ∪i  TRUCK OrderTrucki = ORDER,  i  j  TRUCK OrderTrucki ∩ OrderTruckj = , 路径约束  i  SOURCEORDER TimeOrderi ≺ TimeOrdernextOrderi ,  i  j  SOURCEORDER nextOrderi  nextOrderj , 取货送货时序与耦合约束  i  PICKUPORDER ( TimeOrderi ≺ TimeOrderidxDeliveryOrderi , truckOrderi = truckOrderidxDeliveryOrderi ), NCL ©2000-2012. ENGINEST. All rights reserved.

需要支持 快速开发、低成本维护的 工程化平台 3. 工业应用 Simpler • Smarter • Swifter 工业问题远比学术问题复杂得多 数据逻辑复杂、约束繁琐、建模困难: 学术问题涉及少数约束，工业问题往往涉及种类繁多的约束. 工业问题往往可能是多个问题的叠加. 规模大: 100个订单的路径优化问题是学校里的问题， 工业问题可上升到十万个订单的数量级. 优化方案的技术含量高: 优化及可视化技术. 对实时性、可视化、直觉式交互、二次优化有很强需求. 用户需求分析在方案的研发过程中多变. 实施困难: 研发成本高、部署周期长、见效慢. 需要支持 快速开发、低成本维护的 工程化平台 NCL ©2000-2012. ENGINEST. All rights reserved.

POEMSolution Builder Simpler • Smarter • Swifter POEMSolution Builder 算法 + 逻辑规划 + 求解规则 + 可视化 系统集成 PoemServer：优化计算服务器 ComPoem ActiveX 组件: 优化引擎 ComView ActiveX 组件: 可视化引擎 NCL优化计算语言 - 智能的描述型语言 - 支持问题建模与求解 PoemView可视化脚本 - 可视化 - 基于场景的交互 支持云计算 支持电子商务 NCL ©2000-2012. ENGINEST. All rights reserved.

特殊行业 技术领域 国计民生 有赖优化 优化计算技术的应用领域 物流(能源、汽车) 制造业(电子、机械) 能源(石油、天然气、电力) 电子 Simpler • Smarter • Swifter 物流(能源、汽车) 制造业(电子、机械) 能源(石油、天然气、电力) 电子 航空(民航、机场)、航天 电子商务 金融(银行、保险、股票) 高铁 军事(后勤、指挥) 烟草 冶金 人力资源(呼叫中心、医院) … 特殊行业 民航：航线、航班、机组、维修... 高铁：开行方案、机车维修、收益管理... 技术领域 排程优化：航空、航天、电子、冶金、烟草 配送优化：能源(燃油、天然气)、冷链 人员排班：呼叫中心、医院、超市 国计民生 有赖优化 NCL ©2000-2012. ENGINEST. All rights reserved.

3.1 排产优化 (Production Scheduling) Simpler • Smarter • Swifter Scheduling jobs on resources so as to efficiently make products. NCL ©2000-2012. ENGINEST. All rights reserved.

生产排程的约束模型(1) 资源约束： 资源生产能力 资源并行加工能力 资源使用方式 日工作模式 资源工作日历 日工作时间段(多班次) Simpler • Smarter • Swifter 资源约束： 资源生产能力 资源并行加工能力 资源使用方式 日工作模式 资源工作日历 日工作时间段(多班次) 资源损耗上限 外协资源约束... 订单级约束： 订单多批次执行 最早开工时间 最晚完工时间 不同订单的资源耦合 不同订单间的执行间隔 订单间后继关系 订单的调度次序 订单相互间的次序关系 订单的优先级... NCL ©2000-2012. ENGINEST. All rights reserved.

生产排程的约束模型(2) 零部件级约束： 产品的零部件结构关系 与上周期零部件工序的衔接 不同零部件的资源耦合 零部件间前、后继关系 Simpler • Smarter • Swifter 零部件级约束： 产品的零部件结构关系 与上周期零部件工序的衔接 不同零部件的资源耦合 零部件间前、后继关系 零部件的调度次序... 工序级约束： 工序的资源需求 工序的工艺流程 工序的时序控制 工序的加工时间 工序的开工时间窗口... 繁杂的个性化约束： 下班前不开工 小批量遗留工序当班完成 投料间隔... 优化目标： 订单最小延迟时间量 最小化工期 主要设备最大利用率... NCL ©2000-2012. ENGINEST. All rights reserved.

大规模制造用于航空、航天的各式天线等精密产品 电子器件排产 Simpler • Smarter • Swifter 大规模制造用于航空、航天的各式天线等精密产品 NCL ©2000-2012. ENGINEST. All rights reserved.

冶金浇铸流程排程 Simpler • Smarter • Swifter 配料机 (AOD) 时限基 于钢锭 冷却 1 时限可变 滞留钢包时限 : ½h - 3h 基于钢锭 时限极短 1h 冷却 n 时限可变 转换 钢包 2 1 n 时限基于钢锭 ： 连续浇铸 40’ - 1h 钢锭 旋转 进料 熔炉1 时限 2h 熔炉2 旋转进料 NCL ©2000-2012. ENGINEST. All rights reserved.

厦门烟厂: 验证新工艺，优化排产 烟草生产排产 Simpler • Smarter • Swifter NCL ©2000-2012. ENGINEST. All rights reserved.

数据逻辑校验 作业排序、分组 优化 算子 优化 模型 分组迭代优化 松弛、滚动、合并 排程的系统算法 Simpler • Smarter • Swifter 确保数据相容性 数据逻辑校验 作业排序、分组 产品结构与 数据逻辑 削减数据规模 优化 算子 优化 模型 分组迭代优化 松弛、滚动、合并 高效的基础算法 NCL ©2000-2012. ENGINEST. All rights reserved.

分解、合并的算法示意图 分解、局部优化、松弛、滚动衔接 Simpler • Smarter • Swifter NCL ©2000-2012. ENGINEST. All rights reserved.

3.2 民航业务优化 (Optimization for Civil Aviation) Simpler • Smarter • Swifter 飞机排班(航班+维修) Aircraft Scheduling 不正常航班恢复 Irregular Flight Recovery 飞机+机组+加机组 航线规划 Airline Planning 人员排班(机组) Crew Scheduling 维修车间排程 Maintenance Jobshop Scheduling APS应用 收益管理 Revenue Management NCL ©2000-2012. ENGINEST. All rights reserved.

航线网络规划 (Airline Network Planning) Simpler • Smarter • Swifter 以OD流(客户需求)与机场及航段的capacity,制定航线计划. NCL ©2000-2012. ENGINEST. All rights reserved.

航线网络规划的约束模型 OD流： 航段： 个性化约束： 机场： 优化目标： 起始、终止机场； 运输路线(直达/中转)约束； 可中转机场； Simpler • Smarter • Swifter OD流： 起始、终止机场； 运输路线(直达/中转)约束； 可中转机场； 客货数量； 中转最大次数； 直达、中转比例限制； 流量平衡约束... 航段： 起始、终止机场； 流量(OD数量、飞机架次)限制； 航段的单位流运输成本... 个性化约束： 隐含约束: 中转折扣因子... 机场： 最大流量(OD数量、飞机架次)限制； 出、入量(OD数量、飞机架次)限制； 中转量(OD数量、飞机架次)限制... 优化目标： 最小化运输成本 最大化旅客便利... NCL ©2000-2012. ENGINEST. All rights reserved.

飞机排班(航班与维修) (Aircraft Scheduling) Simpler • Smarter • Swifter NCL ©2000-2012. ENGINEST. All rights reserved.

飞机排班的约束模型 维修约束： 短期(A检)及中长期维修(C、D检)等； 已固定的维修； 飞机的维修基地； Simpler • Smarter • Swifter 维修约束： 短期(A检)及中长期维修(C、D检)等； 已固定的维修； 飞机的维修基地； 飞机的维修资源: 机库、生产线等； 飞机的资源需求：数量、时间等； 资源维修能力：数量、日历等； 维修的时间窗口； 飞机维修间隔：飞行时间、起落、天数... 航班约束： 已安排飞机的航班； 所需飞机机型(子机组)； 每航班仅由一架飞机执行； 降落机场为起飞机场； 航班时段； 航班间过站时间； 限飞约束：高原、台湾等； 飞机耦合约束； 老飞机离基地天数约束； 航班优先级(要客)... 繁杂的个性化约束： 同一资源的维修间隔； 维修的准备及后处理时间； 飞行时间梯次分配； 维修分配均衡... 优化目标： 航班覆盖率最大化； 维修间隔最大化... NCL ©2000-2012. ENGINEST. All rights reserved.

国航SAP短期计划平台 Simpler • Smarter • Swifter NCL ©2000-2012. ENGINEST. All rights reserved.

机组排班 (Crew Scheduling) Simpler • Smarter • Swifter NCL ©2000-2012. ENGINEST. All rights reserved.

机组排班的约束模型 航班约束： 飞行条例约束： 航班环约束： 繁杂的个性化约束： 优化目标： 起止地点衔接； 时间衔接； Simpler • Smarter • Swifter 航班约束： 起止地点衔接； 时间衔接； 航班串内要求机组一致； 航班串内航班数的限制... 飞行条例约束： 每日值勤时间限制； 每日飞行时间限制； 每日休息时间约束； 周、月、年的作息约束... 航班环约束： 航班环内要求机组一致； 航班环时间跨度限制； 航班环内航班数的限制... 繁杂的个性化约束： 航班覆盖约束； 生活基地约束； 基地技术标准人员数量约束； 航班环机组类型需求约束... 优化目标： 最小化机组成本 NCL ©2000-2012. ENGINEST. All rights reserved.

不正常航班恢复优化 (Aircraft Schedule Recovery) Simpler • Smarter • Swifter 飞机： 恢复计划采用的飞机 原计划采用的飞机 航班： 飞机不变但延误超过15分钟 飞机更换且延误超过15分钟 NCL ©2000-2012. ENGINEST. All rights reserved.

不正常航班恢复的约束模型 航班约束： 航班恢复约束： 机组约束： 飞机约束： 繁杂的个性化约束： 优化目标： 必飞航班； Simpler • Smarter • Swifter 航班约束： 必飞航班； 航班与飞机、机组的耦合； 航班时段约束； 飞机起降机场； 航班时空衔接； 经停航班约束... 航班恢复约束： 飞机故障约束 机场故障约束 加机组(时间、起降机场等) 预计起飞时间不早于原计划时间； 重要航班调整约束... 机组约束： 机组覆盖航班； 机组起降机场约束； 机组适航性约束... 飞机约束： 飞机起降机场约束； 飞机适航性约束 机型流平衡约束... 繁杂的个性化约束： 机场宵禁约束； 过夜维修约束... 优化目标： 最大化航班覆盖率； 最小化延误成本... NCL ©2000-2012. ENGINEST. All rights reserved.

3.3 物流优化 (Logistics Optimization) Simpler • Smarter • Swifter Optimizing depots location and distribution of dangerous materials: oil, gas, fuel, … NCL ©2000-2012. ENGINEST. All rights reserved.

配送的约束模型(1) 车辆/司机约束： 运输能力：多车次、载量、时间量、时间跨度 相容性：车辆对客户的相容性(产品、吨位、日期) Simpler • Smarter • Swifter 车辆/司机约束： 运输能力：多车次、载量、时间量、时间跨度 相容性：车辆对客户的相容性(产品、吨位、日期) 耦合性：不同目的地要求两个订单由不同的车辆服务 其他：客户优先级、司机在岗与否、工作条例... 线路约束： 距离约束：时间、里程、费用为度量的距离约束 工作条例：工作时间量、间休、工作时间跨度 时间窗口：例如, 要求早上8:00到9:00之间供货 优先约束：订单A优先订单B... 客户约束： 定期定量：周期、频率及配送量 储存能力：储存下限及上限... NCL ©2000-2012. ENGINEST. All rights reserved.

配送的约束模型(2) 安全性约束： 危险品仓储：某些区域禁止储存危险品 危险品禁止：某些区域或路段的某些时间段禁止通行危险品 Simpler • Smarter • Swifter 安全性约束： 危险品仓储：某些区域禁止储存危险品 危险品禁止：某些区域或路段的某些时间段禁止通行危险品 危险品限量：在某些区域或路段危险品的最大通行量 危险品限时：在某些区域或路段危险品的最大滞留时间... 仓库约束： 部分的仓库选址已确定 仓库设在经济区的需求重心 仓储量的上下限 仓库的最大覆盖半径 配送份额与仓储能力相符... 优化目标： 最小化配送成本 最小化卡车数 最小化工作时间量 最小化工作时间跨度 最小化行程... NCL ©2000-2012. ENGINEST. All rights reserved.

仓储选址优化(Depot Optimization) Simpler • Smarter • Swifter 仓库选址 划分经济区 分配仓储份额 NCL ©2000-2012. ENGINEST. All rights reserved.

卡车计划与路径优化 Simpler • Smarter • Swifter NCL ©2000-2012. ENGINEST. All rights reserved.

车次实时跟踪 Tour 031201009291 Tracing by GPS Simpler • Smarter • Swifter NCL ©2000-2012. ENGINEST. All rights reserved.

法国天然气供应商Antargaz通过70多个仓储中心向全法国30多万家客户进行天然气的液罐车输送。 法国Elf Antargaz天然气集团 Simpler • Smarter • Swifter 法国天然气供应商Antargaz通过70多个仓储中心向全法国30多万家客户进行天然气的液罐车输送。 采用POEM优化管理，要求将调度中心从原先的16精减为2以大幅削减管理成本。 优化前 优化后 调度中心 16 2 调度员（个） 80 40 配送成本（欧元/吨） 120-130 90-100 客户数量 22万 32万 某项业务配送车辆数 470 310 市场占有率 第3位 第2位 NCL ©2000-2012. ENGINEST. All rights reserved.

谢谢 营智优化 ENGINEST (Nancy) 1, Allée de l’Alzette Simpler • Smarter • Swifter 谢谢 ENGINEST (Nancy) 1, Allée de l’Alzette 54500, Vandoeuvre-Lès-Nancy, France www.enginest.com Tel : +33 (0) 3 83 55 12 99 Fax: +33 (0) 3 83 97 05 52 ENGINEST (Beijing) 710-712, 26, Shang Di Xin Xi Road Haidian District, 100085 Beijing, China www.enginest.cn Tel : +86 (10) 82 89 87 52 Fax: +86 (10) 62 98 72 90 NCL ©2000-2012. ENGINEST. All rights reserved.