VRP工具or-tools调研 王羚宇 2017.03.10.

Slides:



Advertisements
Similar presentations
高考英语阅读分析 —— 七选五. 题型解读: 试题模式: 给出一篇缺少 5 个句子的文章, 对应有七个选项,要求同学们根据文章结构、 内容,选出正确的句子,填入相应的空白处。 考查重点: 主要考查考生对文章的整体内容 和结构以及上下文逻辑意义的理解和掌握。 (考试说明) 选项特点: 主旨概括句(文章整体内容)
Advertisements

期末考试作文讲解 % 的同学赞成住校 30% 的学生反对住校 1. 有利于培养我们良好的学 习和生活习惯; 1. 学生住校不利于了解外 界信息; 2 可与老师及同学充分交流有 利于共同进步。 2. 和家人交流少。 在寄宿制高中,大部分学生住校,但仍有一部分学生选 择走读。你校就就此开展了一次问卷调查,主题为.
仪 容. 一、化妆的技巧 眼部的化妆 唇部化妆 眉部化妆 鼻部化妆 根据脸型化妆 根据脸型选发型.
湖南省长沙市第一中学 黄旭华. 开心辞典 1 、现在美国国旗星条旗上有多少颗星 ? 2 、英国绅士为什么总要手提一把雨伞,为什么? 3 、北极的气温比南极的气温高吗? 4 、企鹅是否可以生活在赤道附近? 5 、 “ 沪宁杭 ” 地区的 “ 宁 ” 是指哪座城市? 6 、 “ 七月流火 ” 指天气发生了什么变化?
加油添醋話擴寫 日新國小 鄒彩完.
Java Programming Hygiene - for DIDC
Web of Science新平台纵览 Jan. 2014
Performance Evaluation
1. 理想的路由算法 有关路由选择协议的几个基本概念 算法必须是正确的和完整的。 算法在计算上应简单。
實用日常英文用語 陳辟賢老師                          .
Operating System Process Management - 4 Monday, August 11, 2008.
Minimum Spanning Trees
An Adaptive Cross-Layer Multi-Path Routing Protocol for Urban VANET
指導教授:許子衡 教授 報告學生:翁偉傑 Qiangyuan Yu , Geert Heijenk
Tree(樹) 什麼是「樹」? 「樹」的範例 「樹」的定義 「樹」的表示法.
Calling about an apartment for rent II Objectives
SAT and max-sat Qi-Zhi Cai.
前言 本論文以資源限制專案排程(Resource Constrained Project Scheduling; RCPSP)之理論為基礎
Decision Support System (靜宜資管楊子青)
第4章(2) 空间数据库 —关系数据库 北京建筑工程学院 王文宇.
Course 9 NP Theory序論 An Introduction to the Theory of NP
Simulated Annealing 報告者:李怡緯 OPLAB in NTUIM.
加油添醋話擴寫 鄒彩完.
3D PACMAN! Student: Chia-Wei Yao ID:
Journal of High Speed Networks 15(2006)
The expression and applications of topology on spatial data
高级数据结构.
Yonghui Wu, Mike Schuster, Zhifeng Chen, Quoc V. Le, Mohammad Norouzi
在本章節中,將為各位介紹台達變頻器專用軟體, VFDSoft
子博弈完美Nash均衡 我们知道,一个博弈可以有多于一个的Nash均衡。在某些情况下,我们可以按照“子博弈完美”的要求,把不符合这个要求的均衡去掉。 扩展型博弈G的一部分g叫做一个子博弈,如果g包含某个节点和它所有的后继点,并且一个G的信息集或者和g不相交,或者整个含于g。 一个Nash均衡称为子博弈完美的,如果它在每.
数据库内容及检索功能 – 如何利用这些资源帮助科技论文的写作与发表 钟似璇 (Sixuan Zhong s.
客户服务 询盘惯例.
簡易 Visual Studio 2005 C++ 使用手冊
Decision Support System (靜宜資管楊子青)
樹 2 Michael Tsai 2013/3/26.
Network Design in the Supply Chain (Part1)
Advisor : Prof. Frank Y.S. Lin Presented by Yen-Yi, Hsu
Chapter 9 (三维几何变换) To Discuss The Methods for Performing Geometric Transformations.
感謝同學們在加分題建議. 我會好好研讀+反省~
马亚鹏 Webofknowledge.com Jan. 2014
IBM SWG Overall Introduction
資料結構 Data Structures Fall 2006, 95學年第一學期 Instructor : 陳宗正.
Version Control System Based DSNs
高性能计算与天文技术联合实验室 智能与计算学部 天津大学
Mechanics Exercise Class Ⅰ
Supply Chain Management
3.5 Region Filling Region Filling is a process of “coloring in” a definite image area or region. 2019/4/19.
中国科学技术大学计算机系 陈香兰 2013Fall 第七讲 存储器管理 中国科学技术大学计算机系 陈香兰 2013Fall.
中央社新聞— <LTTC:台灣學生英語聽說提升 讀寫相對下降>
突出语篇语境,夯实词汇语法 一模试卷单选完形分析 及相应的二轮复习对策 永嘉罗浮中学 周晓媚.
关联词 Writing.
線性規劃模式 Linear Programming Models
OvidSP Introduction Flexible. Innovative. Precise.
Representation Learning of Knowledge Graphs with Hierarchical Types
计算机问题求解 – 论题 算法方法 2016年11月28日.
计算机问题求解 – 论题1-5 - 数据与数据结构 2018年10月16日.
Efficient Query Relaxation for Complex Relationship Search on Graph Data 李舒馨
磁共振原理的临床应用.
最短通路问题.
名词从句(2).
Unit 1 How do you study for a test?
赵才荣 同济大学,电子与信息工程学院,智信馆410室
第6章 运输系统及运输优化.
English article read(英文文章閱讀)
認識 Visual Studio 李明山
進階 WWW 程式設計 -- PHP Array 靜宜大學資訊管理學系 蔡奇偉副教授
2012 程式設計比賽 Openfind 天使帝國 v2.0 (蓋亞的紋章).
句子成分的省略(3).
When using opening and closing presentation slides, use the masterbrand logo at the correct size and in the right position. This slide meets both needs.
Presentation transcript:

VRP工具or-tools调研 王羚宇 2017.03.10

OUTLINE TSP问题与VRP问题 or-tools 工具包介绍 求解VRP问题示例 TSP问题 VRP问题 关键变量、函数

TSP问题 旅行推销员问题(Travelling salesman problem, TSP)是 这样一个问题:给定一系列 城市和每对城市之间的距离, 求解访问每一座城市一次并 回到起始城市的最短回路。 它是组合优化中的一个NP 困难问题,在运筹学和理论 计算机科学中非常重要。 尽管问题在计算上很困难,但已经有了大量的启发式和精确方法。,因此可以完全求解城市数量上万的实例,并且甚至能在误差1%范围内估计上百万个城市的问题

TSP问题-问题定义 问题定义如下:给定若干城市与城市间的距离集 合,求经过所有城市恰好一次的最短回路。即: 给定图G=(V, E, W),其中V为顶点集合,|V|=n, E为边集合,W为边权函数,求集合{1, 2, …, n}的 一个排列π 使得下式最小。

TSP问题-整数规划问题 问题同样可以用整数线性规划问题来形式化,我们用数字1,…,𝑛标 记这些城市,并定义 x 𝑖𝑗 = 1 路径选择从i到j 0 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒 并选择优化: 第一组等式要求每个城市都能另一个城市前来,而第二组等式要求每个城市都能出发。最后的约束迫使覆盖所有城市的路径只有一条,而不是两条或者多条分散的路径在一起覆盖的。 证明可行解中的每个子回路经过1号城市(注意到等式保证了只有一条这样的路径),就能证明所有可行解只包含一个封闭城市序列。对于若我们对所有xij=1 对应的不等式求和的话,对 k 步不经过1号城市的任何子回路,我们得到:nk≤(n−1)k, 矛盾。

VRP问题 TSP问题考虑一辆车依次遍历每一个节点一次,求满足条 件的遍历方法的最小代价。 What about 多辆车,每个节点有不同的需求? 车辆路线问题(VRP):一定数量的客户,各自有不同数量 的货物需求,配送中心向客户提供货物,由一个车队负 责分送货物,组织适当的行车路线,目标是使得客户的 需求得到满足,并能在一定的约束下,达到诸如路程最 短、成本最小、耗费时间最少等目的。

VRP问题-问题定义 设有一场站,共有M 辆货车,车辆容量为Q,有 N位顾客,每位顾客有其需求量D。车辆从场站 出发对客户进行配送服务最后返回场站,要求所 有顾客都被配送,每位顾客一次配送完成,且不 能违反车辆容量的限制,目的是所有车辆路线的 总距离最小。

VRP问题-整数规划问题 问题同样可以用整数线性规划问题来形式化,我们用数字1,…,𝑛标 记这些城市,并定义 x 𝑖𝑗 = 1 路径选择从i到j 0 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒 并选择优化: 其中r(s)是服务集合S中各节点所需的最少车辆数目。

VRP问题变种(1) 与一般的VR问题相比,变种的VRP问题通常增加了一些额外的 限制,这些限制通常包括:装卸货的顺序,时间(时间窗),是 否要求回到场点,容量限制等。 有时间窗车辆路径问题(VRPTW,VRP with Time Windows) 考虑需求点对于车辆到达的时间有所要求之下,在车辆途程 问题之中加入时窗的限制,在VRPTW问题中,除了行驶成本 之外, 成本函数还要包括由于早到某个客户而引起的等待时间 和客户需要的服务时间。 与一般的VR问题相比,变种的VRP问题通常增加了一些额外的限制,这些限制通常包括:装卸货的顺序,时间(时间窗),是否要求回到场点,容量限制等。以下是几种比较常见的变种VRP问题: 在VRPTW中,车辆除了要满足VRP问题的限制之外,还必须要满足需求点的时窗限制,而需求点的时窗限制可以分为两种,一种是硬时窗(Hard Time Window),硬时窗要求车辆必须要在时窗内到达,早到必须等待,而迟到则拒收;另一种是软时窗(Soft Time Window),不一定要在时窗内到达,但是在时窗之外到达必须要处罚,以处罚替代等待与拒收是软时窗与硬时窗最大的不同。

VRP问题变种(2) 接送货物的车辆路径问题(VRPPD,Vehicle Routing Problem with Pickup and Delivery) 按序接送货物的车辆路径问题(Vehicle Routing Problem with LIFO) 问题要求最近接收的货物需要最早的被运送、卸货。 开放的车辆路径问题(OVRP,Open Vehicle Routing Problem) 车辆在运送货物后并不需要返回场点。

OUTLINE TSP问题与VRP问题 or-tools 工具包介绍 求解VRP问题示例 TSP问题 VRP问题 关键变量、函数

or-tools介绍(1) or-tools 是 Google 的优化搜索工具。优化工具包括: 约束编程解决方案(N-皇后问题,数字谜问题) 背包算法 图算法 (最短路径,线性和分配,最小费用流,最大流) 路径规划问题(TSP,VRP) 为线性规划和混合整数规划解决方案提供简单统一接口 Constraint programming is the name given to identifying feasible solutions out of a very large set of candidates, where the problem can be modeled in terms of arbitrary constraints.

or-tools介绍(2)-主要特性 开源免费 持续维护,改进和开发 详细的文档,提供 C++, Python, Java 和 C# 示例 便捷,可以在以下平台编译: Ubuntu 14.04 and 16.04 up (64-bit). Mac OS X El Capitan with Xcode 7.x (64 bit). Microsoft Windows with Visual Studio 2013 and 2015 (64-bit) 高效,用户友好 良好测试

or-tools 代码结构 FlatZinc, a solver input language that is understood by a wide range of solvers.

OUTLINE TSP问题与VRP问题 or-tools 工具包介绍 求解VRP问题示例 TSP问题 VRP问题 关键变量、函数

使用到的相关代码 求解TSP问题的直接依赖在 base graph constraint_solver utils 文件夹中

关键变量 求解相关 routing_first_solution: default : select the first node with an unbound successor and connect it to the first available node GlobalCheapestArc LocalCheapestArc PathCheapestArc GlobalCheapestArc :iteratively connect two nodes which produce the cheapest route segment LocalCheapestArc:select the first node with an unbound successor and connect it to the node which produces the cheapest route segment PathCheapestArc :starting from a route “start” node, connect it to the node which produces the cheapest route segment, then extend the route by iterating on the last node added to the route

关键变量 搜索过程 Meta-heuristics启发式算法策略 routing_guided_local_search (default: false): activates guided local search Generally the most efficient metaheuristic for vehicle routing routing_simulated_annealing (default: false): activates simulated annealing routing_tabu_search (default: false): activates tabu search 模拟退火: 模拟退火算法新解的产生和接受可分为如下四个步骤: 第一步是由一个产生函数从当前解产生一个位于解空间的新解;为便于后续的计算和接受,减少算法耗时,通常选择由当前新解经过简单地变换即可产生新解的方法,如对构成新解的全部或部分元素进行置换、互换等,注意到产生新解的变换方法决定了当前新解的邻域结构,因而对冷却进度表的选取有一定的影响。 第二步是计算与新解所对应的目标函数差。因为目标函数差仅由变换部分产生,所以目标函数差的计算最好按增量计算。事实表明,对大多数应用而言,这是计算目标函数差的最快方法。 第三步是判断新解是否被接受,判断的依据是一个接受准则,最常用的接受准则是Metropolis准则: 若Δt′<0则接受S′作为新的当前解S,否则以概率exp(-Δt′/kT)接受S′作为新的当前解S。 第四步是当新解被确定接受时,用新解代替当前解,这只需将当前解中对应于产生新解时的变换部分予以实现,同时修正目标函数值即可。此时,当前解实现了一次迭代。可在此基础上开始下一轮试验。而当新解被判定为舍弃时,则在原当前解的基础上继续下一轮试验。 模拟退火算法与初始值无关,算法求得的解与初始解状态S(是算法迭代的起点)无关;模拟退火算法具有渐近收敛性,已在理论上被证明是一种以概率l 收敛于全局最优解的全局优化算法;模拟退火算法具有并行性。 禁忌算法: 它从一个初始可行解出发,选择一系列的特定搜索方向(移动)作为试探,选择实现让特定的目标函数值变化最多的移动。为了避免陷入局部最优解,TS搜索中采用了一种灵活的“记忆”技术,对已经进行的优化过程进行记录和选择,指导下一步的搜索方向, 当兔子们再寻找的时候,一般地会有意识地避开泰山,因为他们知道,这里已经找过,并且有一只兔子在那里看着了。这就是禁忌搜索中“禁忌表(tabu list)”的含义。那只留在泰山的兔子一般不会就安家在那里了,它会在一定时间后重新回到找最高峰的大军,因为这个时候已经有了许多新的消息,泰山毕竟也有一个不错的高度,需要重新考虑,这个归队时间,在禁忌搜索里面叫做“禁忌长度(tabu length)”;如果在搜索的过程中,留守泰山的兔子还没有归队,但是找到的地方全是华北平原等比较低的地方,兔子们就不得不再次考虑选中泰山,也就是说,当一个有兔子留守的地方优越性太突出,超过了“best so far”的状态,就可以不顾及有没有兔子留守,都把这个地方考虑进来,这就叫“特赦准则(aspiration criterion)”。这三个概念是禁忌搜索和一般搜索准则最不同的地方,算法的优化也关键在这里。

关键变量搜索相关 Local search neighborhoods routing_no_lns (default: false): 使用LNS,可能会找到更好的解 法,不过通常比较慢 routing_no_TSP (default: true): 在求解当前模型时不使用精确 算法求解“子”TSP问题 searching for solution  routing_solution_limit (default: kint64max) 在找到若干次更好的 解后停止 routing_time_limit (default: kint64max) 在查找若干时间后停止

Routing相关 路径相关的变量 Dimension相关的变量 next(i):i节点的直接后继的节点号(可以通过 IndexToNode()得到该节点) vehicle(i):返回该节点属于车辆路径的编号 Dimension相关的变量 dimension变量 cumul(i, d) 节点i的累积值 transit(i, d) 节点i的delta值 if j == next(i), cumul(j) = cumul(i) + transit(i) + slack(i)

关键API RoutingModel RoutingModel (int nodes, int vehicles, NodeIndex depot) : 构造VRP问题 const Assignment* RoutingModel :: SolveWithParameters (const RoutingSearchParameters& search_parameters): 求解VRP问题 void SetArcCostEvaluatorOfAllVehicles(NodeEvaluator2* evaluator):定义最小化变量问题 ResultCallback2<int64, NodeIndex, NodeIndex>

关键API AddDimension(): bool AddDimension(NodeEvaluator2* evaluator, evaluator: 加入限制变量的callback函数 相关的两个变量: cumul(累加变量) transit(站点变量) if j == next(i), cumul(j) = cumul(i) + transit(i) + slack(i) capacity: cumul变量的最大值 fix_start_cumul_to_zero:开始时是否置为0 bool AddDimension(NodeEvaluator2* evaluator, int64 slack_max, int64 capacity, bool fix_start_cumul_to_zero, const std::string& name );

关键API VRP问题:加入若干节点属于同一辆车的约束: 示例:solver->AddSoftSameVehicleConstraint(); 标注数组中的节点应该分到同一辆车上,如果没在同一辆 车上,每多一个特例,总成本函数增加cost. // Adds a soft contraint to force a set of nodes to be on the same vehicle. // If all nodes are not on the same vehicle, each extra vehicle used adds // 'cost' to the cost function.

关键API VRP问题:加入两个节点存在接送关系: 满足:1. node1,node2由同一辆车服务; 示例: https://github.com/google/or-tools/blob/c11c96f1dce24893de5357e7c643aa6958496ada/src/constraint_solver/routing.h line 580. // Notifies that node1 and node2 form a pair of nodes which should belong // to the same route. This methods helps the search find better solutions, // especially in the local search phase. // It should be called each time you have an equality constraint linking // the vehicle variables of two node (including for instance pickup and // delivery problems): // Solver* const solver = routing.solver(); // solver->AddConstraint(solver->MakeEquality( // routing.VehicleVar(routing.NodeToIndex(node1)), // routing.VehicleVar(routing.NodeToIndex(node2)))); // solver->AddPickupAndDelivery(node1, node2); // // TODO(user): Remove this when model introspection detects linked nodes. void AddPickupAndDelivery(NodeIndex node1, NodeIndex node2) { pickup_delivery_pairs_.push_back( {{NodeToIndex(node1)}, {NodeToIndex(node2)}}); }

关键API 自定义条件:在constraint_solver中加入constraint 示例: 表示需要满足left <= right. 还有很多这样的API: https://github.com/google/or-tools/blob/master/src/constraint_solver/constraint_solver.h line 1200+-

关键API 自定义条件 https://github.com/google/or-tools/blob/master/src/constraint_solver/constraint_solver.h line 1200+-

TSP问题示例 准备数据 构造求解器 准备callback函数 调用求解器

TSP问题示例 准备数据--给定若干个城市和他们之间的距离

TSP问题示例 构造求解器

TSP问题示例 构造求解器

TSP问题示例 准备callback函数 callback: a function that takes any pair of nodes in the graph for the problem and returns the distance between them — and then passes it to the solver

TSP问题示例 调用求解器 输出示例

VRP问题示例 与TSP相比,示例VRP程序加入了车辆的容量限制,同时调度 多辆车完成规划问题。 准备数据:生成每个站点的位置跟其货物需求;定义距离调 用函数

VRP问题示例 Callback函数

VRP问题示例 准备demand的调用函数

VRP问题示例 AddDimension(): bool AddDimension(NodeEvaluator2* evaluator, evaluator: 加入限制变量的callback函数 相关的两个变量: cumul(累加变量) transit(站点变量) if j == next(i), cumul(j) = cumul(i) + transit(i) + slack(i) capacity: cumul变量的最大值 fix_start_cumul_to_zero:开始时是否置为0 bool AddDimension(NodeEvaluator2* evaluator, int64 slack_max, int64 capacity, bool fix_start_cumul_to_zero, const std::string& name );

VRP问题示例 加入约束

VRP问题示例 示例输出

VRPTW示例 问题说明: VRP + Time Windows. 在这个例子中,我们定义总的时间为服务时间+路 上花费的时间,其中服务时间与每个站点所需货 物量成正比,路上花费的时间跟站点间的距离成 正比。

VRPTW示例 准备数据: VRP + Time Windows.在这个例子中,我们定义 总的时间为服务时间+路上花费的时间,其中服务 时间与每个站点所需货物量成正比,路上花费的 时间跟站点间的距离成正比。

VRPTW示例 定义callback函数: 服务时间与每个站点所需货物量成正比

VRPTW示例 定义callback函数 路上花费的时间跟站点间的距离成正比。

VRPTW示例 定义callback函数 总时间=服务时间+路程时间

VRPTW示例 加入时间维度

VRPTW示例 加入时间维度限制: 获取该dimension 为其中的每个站点设置开始、结束时间值,加 入约束

Q&A?

reference https://en.wikipedia.org/wiki/Travelling_salesman_problem https://en.wikipedia.org/wiki/Vehicle_routing_problem https://developers.google.com/optimization/reference/constraint_solver/routing/ https://acrogenesis.com/or- tools/documentation/documentation_hub.html#user_manual https://developers.google.com/optimization/ https://developers.google.com/optimization/routing/TSP/TSP https://developers.google.com/optimization/routing/TSP/vehicle_routing_time_w indows https://github.com/google/or-tools/blob/master/src/constraint_solver/routing.h