文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > Extension of LNS (Shaw [1998]) VNS (Hansen and Mladenovic [1999])
侵权投诉

Extension of LNS (Shaw [1998]) VNS (Hansen and Mladenovic [1999])

? Local search framework ? Simple algorithms compete to modify current solution ? Choose algorithm to destroy solution ? Choose algorithm to repair solution ? Accept new solution according to local search framework ? Choose destroy and repair alg. based on

Motivation Adaptive Large Neighborhood Search applied to mixed vehicle routing problems David Pisinger, Stefan Røpke NEXT workshop 2006 v v v v v v v v v v v v v v v v v v v v v v v v v v v v v v v v v v v v v

Uni ed algorithm, several VRP variants Automatic parameter tuning Adaptive Large Neighborhood Search Framework for combining several solution approaches Based on Large Neighborhood Search Applied to 12 variants af VRP Encouraging results (improved 40% instances)

2

2 v v v

Vehicle Routing Problem Depot Customers Vehicles Capacity of vehicle Time windows Multiple depots Site dependant Pickup-delivery Backhauls Open VRP

v v

Storeroom optimization (MBS) Exact methods (Jepsen, Petersen, Spoorendonk) Heuristic methods (Pisinger, Røpke) 1 2

Adaptive Large Neighborhood Search u u u u u u u u u u u u u u u u u u u u

Properties of ALNS Large Neighborhood Search f (x) 6

2 u

Local search framework Simple algorithms compete to modify current solution Choose algorithm to destroy solution Choose algorithm to repair solution Accept new solution according to local search framework Choose destroy and repair alg. based on past score Suited for tightly coupled problems where small neighborhoods cannot escape local minima Robust to changes in input, structure of instances Extension of LNS (Shaw[1998]) VNS (Hansen and Mladenovic[1999]) Calibration quite limited The more reasonable neighborhoods the better performance Not“either-or” but“both-and” VNS N1N2 N3 N1 Nk N5 N3 N2 N N4 ALNS -

Extension of LNS (Shaw [1998]) VNS (Hansen and Mladenovic [1999])

第1页

你可能喜欢

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email