车辆路径优化基础支持文档.pdfVIP

车辆路径优化 车辆路径优化 技术支持文档 技术支持文档 北京营智优化科技有限公司 目 录 1 业务逻辑分析3 1.1 优化问题分析3 1.1.1 问题的主要约束3 1.1.2 优化目标4 1.1.3 问题的结果输出4 2 数据逻辑分析5 2.1 数据建模中的问题和解决方案 6 2.1.1 车辆载量上下限约束6 2.1.2 车辆工作时间量、工作时间跨度约束6 2.1.3 车辆多趟次约束6 2.1.4 订单耦合性约束6 2.1.5 订单优先级约束6 2.1.6 订单时间窗口约束6 3 NCL 建模6 3.1 NCL 语言建模思想 6 3.2 路径优化问题的NCL 建模 7 3.2.1 车辆载量上下限约束7 3.2.2 车辆工作时间量、工作时间跨度约束7 3.2.3 车辆多趟次约束 8 3.2.4 订单优先级约束 8 3.2.5 订单时间窗口约束9 3.2.6 优化目标9 4 系统集成 10 4.1 路径优化系统与其他系统的集成 10 ?2000-2008. ENGINEST. All rights reserved. - 1 - 4.2 路径优化系统集成示例 11 5 路径优化系统的运行环境 13 5.1 硬件环境 13 5.2 软件环境 13 6 数据结构 13 6.1 地址信息表 (SITE) 13 6.2 仓库信息表 (DEPOT) 14 6.3 车辆信息表 (TRUCK) 14 6.4 货物信息表 (PRODUCT) 18 6.5 客户信息表 (CLIENT) 18 6.6 订单信息表 (ORDER) 19 6.7 输出结果表 (PLAN) 21 6.8 优化参数配置信息表 (CONFIG) 22 6.9 地图数据 (MAP) 24 附录1 NCL 语言简介25 附录2 北京营智优化科技有限公司27 附录3 路径优化应用案例介绍30 法国天然气供应商Antargaz 30 法国天然气供应商Rh?ne Méditerranée Gaz 31 ?2000-2008. ENGINEST. All rights reserved. - 2 - 1 业务逻辑分析 路径优化VRP (Vehicle Routing Problem)及其特例取货送货问题PDP (Pickup and Delivery Problem)是供应链节点上的主要优化问题，它涉及对车辆的全局最 优调度及最优的路线规划。 NCL 语言是以数理逻辑为语法的运筹学的自然语言，集逻辑、优化及有哪些信誉好的足球投注网站 规则为一体。与国际市场上其他的解算器相比，NCL 对复杂大规模问题可以直 接在业务逻辑一级上进行建模并求解，而不用像混合整数规划MIP（Mixed Integer Programming ）那样将非线性问题作复杂的线性转换后再进行求解。 NCL 的优势就是求解大规模的非线性的组合优化问题。特别是Scheduling、 Routing 等用线性规划或混合整数规划很难求解的问题。 NCL 可以方便地对路径优化问题进行建模和求解。 通过对路径优化问题的需求分析，形成对问题业务逻辑的完备描述，建立概 念模型。在进行业务逻辑分析的基础上，建立路径优化问题的数据模型，数据模 型建立的好坏直接关系到模型的鲁棒性和简洁性，这是建立NCL 模型的关键。 最后对路径优化问题用NCL 语言进行建模。 1.1 优化问题分析 1.1.1 问题的主要约束