大连海事大学现代优化技术第5讲：传统启发式算法之构筑法

1、大连海事大学现代优化技术第5讲：传统启发式算法之构筑法,1,现代优化技术,第5讲：传统启发式算法之构筑法,大连海事大学现代优化技术第5讲：传统启发式算法之构筑法,2,主要内容,启发式算法含义 启发式算法的宿命论 启发式算法求解问题的一般程序 启发式算法策略 几种典型的构筑法 （1）背包问题的构筑法 （2）旅行商问题的构筑法 （3）配送问题的构筑法,大连海事大学现代优化技术第5讲：传统启发式算法之构筑法,3,启发式算法（heuristics）,含义：启发性算法是一种优化技术，可以在可接 受计算时间下给出待求解问题每一个实例的近似最优解，但无法保证所得解的精确度。 目标：求得“满意解”，而非最优解

2、 1）精确解无法找到； 2）过高精度的解无实际意义； 3）求最优解代价太高。,大连海事大学现代优化技术第5讲：传统启发式算法之构筑法,4,启发式方法的概念图,全局最优解,可行解集合,目标函数,局部最优解,大连海事大学现代优化技术第5讲：传统启发式算法之构筑法,5,启发式算法的宿命论例：Traveling Salesman Problem (TSP),大连海事大学现代优化技术第5讲：传统启发式算法之构筑法,6,启发式算法的宿命论：计算复杂性例：Traveling Salesman Problem (TSP),个客户的TSP問題 ( 30! 1030 ) 高性能計算機求解最优解需要日 (n-1)(

3、n-2)321=(n-1)! 1 PIPS (Peta Instruction Per Second)=1015 30!/1015 （秒） 1015 （秒） 105 （世紀） （穷举法）,大连海事大学现代优化技术第5讲：传统启发式算法之构筑法,7,启发式算法的宿命论：问题复杂性例：TSP的各种扩展问题及其现实应用,VRP问题:(vehicle routing problems） VRPTW问题: （vehicle routing problem with time windows） VRPPD问题： (VRP with pickup 相反，如wikw*, 则 zik=0,Step 3. 如 k

4、n-1, 则 k=k+1, 返回 step 2. 如 k=n, 输出最终解z.,大连海事大学现代优化技术第5讲：传统启发式算法之构筑法,20,构筑法,nearest neighbor for TSP,TSP的最近近邻法：从某一个客户出发，选择尚未访问的客户中距现在的客户最近的作为下一个要访问的客户，反复这一步骤，直到所有访问完毕。,V: 客户的集合 SV: 尚未访问的客户的集合,构筑中的部分巡回路,大连海事大学现代优化技术第5讲：传统启发式算法之构筑法,21,构筑法,nearest neighbor 法图示,大连海事大学现代优化技术第5讲：传统启发式算法之构筑法,22,构筑法,Nearest

5、neighbor algorithm for TSP,Step 1. 令 k=1，S=V. 从 iV 任选一客户,Step 2. 设,Step 3. 令 返回 step 2.,此时若,则输出巡回路,探索终了。,以及,大连海事大学现代优化技术第5讲：传统启发式算法之构筑法,23,构筑法,Random nearest neighbor 法,将对目标函数值的贡献度（如巡回路增加值）作为评价指标，以评价值从大到小的顺序（距现行出发点从近到远的顺序），作为几个可行的部分解，然后，从中随机选取一个作为下一个出发点，,反复这一步骤直到得到完整的可行解。 与单纯的nearest neighbor 法对比，加入

6、了随机选择性，使解具有多样性。,大连海事大学现代优化技术第5讲：传统启发式算法之构筑法,24,构筑法,Random nearest neighbor 法,Random nearest 法图示,1,2,a,b,c,大连海事大学现代优化技术第5讲：传统启发式算法之构筑法,25,构筑法,Random nearest neighbor algorithm for TSP,Step 1. 令 k=1，S=V. 从 iV 任选一客户,Step 2. 设,Step 3. 对于现在的 i, 从集合S中按dij的从小到大的顺序选择候补客户 j, 其集合为 . Step 4. 从集合 中随机选取一个 ，作为 i

7、, , 返回 step 2.,此时若,则输出巡回路,探索终了。,大连海事大学现代优化技术第5讲：传统启发式算法之构筑法,26,构筑法,Multiple fragment method for TSP,Multiple fragment method 多部分巡回路法 思路：首先生成多个部分巡回路（subtour)， 然后连接这些部分，形成完整的巡回路。 条件：在生成部分巡回路的过程中， 1.与各都市相连的枝的个数不超过2个； 2.不能出现部分闭巡回路。 过程：在满足上述2条件的前提下，按dij 的从小到大的顺序多个生成部分巡回路，最后形成完整的巡回路。,Greedy 性,大连海事大学现代优化技术

8、第5讲：传统启发式算法之构筑法,27,构筑法,Closed subtours,部分闭巡回路（closed subtour） 图示例,大连海事大学现代优化技术第5讲：传统启发式算法之构筑法,28,构筑法,多部分巡回路算法用符号,点（dot）：各个都市 枝 (edge)：连接两个客户的部分巡回路 通路 (path)：非闭的部分巡回路 现阶段部分巡回路中包含的枝的集合 现阶段部分巡回路中尚未包含的枝的集合 当中与客户i相连接的枝的个数 通路一端的端点i所对应的另一端端点（客户）号。,大连海事大学现代优化技术第5讲：传统启发式算法之构筑法,29,构筑法,多部分巡回路算法（1）,大连海事大学现代优化技术

9、第5讲：传统启发式算法之构筑法,30,构筑法,多部分巡回路算法（2）,大连海事大学现代优化技术第5讲：传统启发式算法之构筑法,31,构筑法,多部分巡回路法的实行例,(1).途中的多个部分巡回路,(2). 最终得到的完整巡回路,1,2,3,4,5,6,7,8,9,10,大连海事大学现代优化技术第5讲：传统启发式算法之构筑法,32,构筑法,VRP (vehicle routing problem),配送 中心,顾客,总費用或总距离最小化 route内的顧客需要量不能超过车的載重量 工作時間的上限 不能超过,大连海事大学现代优化技术第5讲：传统启发式算法之构筑法,33,构筑法,配送 中心,配送 中心

10、,Saving value Sij 的计算 （移動費用対称 cij=cji）,所有客户都从库存点的 之间的直行运输开始！,根据客户i,j连续运输时的節約量 （saving value）的从大到小顺序来连续运输！,Saving algorithm for VRP,大连海事大学现代优化技术第5讲：传统启发式算法之构筑法,34,构筑法,Saving algorithm for VRP,Step1. 计算所有的顧客对（ i,j）的saving value Sij Step2. saving value Sij的从大到小的顺序重新排列 得到新的顧客对顺序list Step3. 重复以下的操作直到list变空为止： (1). 按list的顺序，调查将顧客 i,j 間直接运输的実行可能性 (2).如果这种実行可能性存在，则连接 i与 j。 (3).如果不存在这