一、前言
今年开年那会还在做一个课题的实验,那时候想用large neighborhood search来做一个问题,但是后来发现常规的一些repair、destroy算子效果并不是很好。后来才知道,large neighborhood search以及它的衍生算法,这类框架给人一种非常通用的感觉,就是无论啥问题都能往里面套。
往往的结果是套进去效果也是一般。这也是很多刚入行的小伙伴经常喜欢干的事吧,各种算法框架套一个问题,发现结果不好了就感觉换下一个。最后复现了N多个算法发现依然no process,这时候就会怀疑人生了。其实要想取得好的performance,肯定还是要推导一些问题特性,设计相应的算子也好,邻域结构也好。
好了,回到正题。当时我试了好几个large neighborhood search算子,发现没啥效果的时候,心里难受得很。那几天晚上基本上是转辗反侧,难以入眠,当然了是在思考问题。然后一个idea突然浮现在我的脑瓜子里,常规的repair算子难以在问题中取得好的performance,是因为约束太多了,插入的时候很容易违背约束。
在不违背约束的条件下又难以提升解的质量,我就想能不能插入的啥时候采取branch and bound。遍历所有的可能插入方式,然后记录过程中的一个upper bound用来删掉一些分支。
感觉是有搞头的,后来想想,这个branch的方法以及bound的方法似乎是有点难设计。然后又搁置了几天,最后没进展的时候突然找了一篇论文,是好多年前的一篇文章了。里面详细讲解了large neighborhood search中如何利用branch and bound进行插入,后来实现了以下感觉还可以。感觉这个方法还是有一定的参考价值的,因此今天就来写写(其实当时就想写了,只不过一直拖到了现在。。。)
关于这个算法,我在此前的推文中已经有过相应的介绍,详情小伙伴们可以戳这篇的链接进行查看:
自适应大邻域搜索(Adaptive Large Neighborhood Search)入门到精通超详细解析-概念篇
有关该算法更详细的介绍可以参考Handbook Of Metaheuristics这本书2019版本中的Chapter 4 Large Neighborhood Search(David Pisinger and Stefan Ropke),文末我会放出下载的链接。
关于destroy算子呢,有很多种,比如随机移除几个点,贪心移除一些比较差的点,或者基于后悔值排序移除一些点等,这里我给出文献中的一种移除方式,Shaw (1998)提出的基于
进行移除:
代码实现放两个,一个是我当时写的一个DFSEXPLORER,采用的是思路2作为bound的,(代码仅仅提供思路)如下:
private void DFSEXPLORER5(LNSSolution node, LNSSolution upperBound, int dep) {
Queue<LNSSolution> queue = new LinkedList<LNSSolution>();
LNSSolution s_c_ = node;
queue.add(s_c_);
int es = 1;
while (!queue.isEmpty()) {
s_c_ = queue.remove();
//v是一个完整的解
if(s_c_.removalCustomers.isEmpty()) {
if(s_c_.cost < upperBound.cost && Math.abs(s_c_.cost-upperBound.cost)>0.001) {
//System.out.println("new found > "+s_c_.cost+" feasible = "+s_c_.feasible());
upperBound.cost = s_c_.cost;
upperBound.routes = s_c_.routes;
}
}else {
//System.out.println("l > "+s_c_.removalCustomers.size() + " cost = "+s_c_.cost);
double minIDelta = Double.POSITIVE_INFINITY;
int minIndex = -1;
Customer c=null;
for(int i = 0; i < s_c_.removalCustomers.size(); ++i) {
Customer cu = s_c_.removalCustomers.get(i);
double d1 = s_c_.minInsertionDeltas[cu.getCustomerNo()];
if(minIDelta > d1) {
minIDelta = d1;
c = cu;
minIndex = i;
}
}
ArrayList<LNSSolution> neighborI_c = new ArrayList<LNSSolution>();
for( int i = 0; i < s_c_.routes.length; ++i) {
Route route = s_c_.routes[i];
if(!MyUtil.checkCompatibility(c, route.getAssignedVehicle())) {
continue;
}
for (int j = 0; j <= route.getCustomersLength(); j++) {
LNSSolution s_i = s_c_.solClones();
s_i.insertCustomer(s_i.routes[i], s_i.removalCustomers.get(minIndex), j, minIndex);
//updateIDAfterOneInserted(s_i, s_i.routes[i]);
//s_i.calcLowerBound();
double o_c = s_i.lb;
updateInsertionDelta(s_i);
double n_c = s_i.lb;
//if(o_c != n_c)System.out.println("o = "+o_c+" n = "+n_c);
neighborI_c.add(s_i);
}
}
Collections.sort(neighborI_c);
for(LNSSolution s:neighborI_c) {
//System.out.println("lBound "+s.lb+" upperBound = "+upperBound.cost);
//updateInsertionDelta(s);
//s.calcLowerBound();
if(s.lb < upperBound.cost /*&& dep > 0*/) {
//System.out.println("lBound "+s.lb+" upperBound = "+upperBound.cost);
//System.out.println(s.removalCustomers.size());
queue.add(s);
es++;
dep--;
}
}
}
}
//System.out.println(es);
}
第二个是GitHub上找到的一个人复现的,我已经fork到我的仓库中了:
https://github.com/dengfaheng/vrp
这个思路bound的思路呢没有按照paper中的,应该还是用的贪心进行bound。看起来在R和RC系列的算例中效果其实也一般般,因为用了LDS吧可能。下面是运行的c1_2_1的截图:
导入idea或者eclipse后等他安装完依赖,运行下面的文件即可,更改算例的位置如图所示:
这个思路是直到借鉴的,大家在用LNS的时候也可以想想有什么更好的bound方法。
好了,这就是今天的分享了。可能有很多地方没写的很明白,因为涉及的点太多了我也只能讲个大概提供一个思路而已。大家来了就帮我点个在看再走吧~