专栏首页程序猿声基于branch and bound插入的large neighborhood search

基于branch and bound插入的large neighborhood search

一、前言

今年开年那会还在做一个课题的实验,那时候想用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进行插入,后来实现了以下感觉还可以。感觉这个方法还是有一定的参考价值的,因此今天就来写写(其实当时就想写了,只不过一直拖到了现在。。。)

二、large neighborhood search

关于这个算法,我在此前的推文中已经有过相应的介绍,详情小伙伴们可以戳这篇的链接进行查看:

自适应大邻域搜索(Adaptive Large Neighborhood Search)入门到精通超详细解析-概念篇

有关该算法更详细的介绍可以参考Handbook Of Metaheuristics这本书2019版本中的Chapter 4 Large Neighborhood Search(David Pisinger and Stefan Ropke),文末我会放出下载的链接。

关于destroy算子呢,有很多种,比如随机移除几个点,贪心移除一些比较差的点,或者基于后悔值排序移除一些点等,这里我给出文献中的一种移除方式,Shaw (1998)提出的基于

relateness

进行移除:

三、branch and bound

3.1 branch

3.2 bound

四、代码环节

代码实现放两个,一个是我当时写的一个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方法。

好了,这就是今天的分享了。可能有很多地方没写的很明白,因为涉及的点太多了我也只能讲个大概提供一个思路而已。大家来了就帮我点个在看再走吧~

本文分享自微信公众号 - 程序猿声(ProgramDream),作者:邓发珩

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-11-02

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 干货|自适应大规模邻域搜索算法求解带时间窗的车辆路径规划问题(上)

    不知道大家在使用启发式算法求解车辆路径规划问题时有没有这样的困惑:设计邻域搜索算子实在是太太太太难了,邻域搜索算子必须在算子搜索范围以及算子复杂度之间达到平衡,...

    用户1621951
  • 具有同时取货和时间窗口的车辆路线的模因搜索(CS)

    在过去的十年中,具有同时取货和时间窗口(VRPSPDTW)的车辆路径问题由于在双向物流中的现代物流中得到了广泛应用而备受关注。在本文中,我们提出了一种有效的局部...

    用户8380959
  • 干货 | Adaptive Large Neighborhood Search入门到精通超详细解析-概念篇

    关于neighborhood serach,这里有好多种衍生和变种出来的胡里花俏的算法。大家在上网搜索的过程中可能看到什么Large Neighborhood ...

    短短的路走走停停
  • 干货 | 自适应大邻域搜索入门到精通超详细解析-概念篇

    各位小伙伴大家好呀~最近好久没有给大家推过干货了,不过小编可没有闲着。最近一直在苦苦研究的neighborhood search终于有了结果。

    用户1621951
  • 车辆路径规划中的Dial A Ride 问题简介

    今天我们给大家带来的是Dial a ride问题(DAR)的介绍,文中所用资料多参考于文献。先上目录

    用户1621951
  • 通过拉格朗日分解改进神经网络验证的分支和边界(CS LG)

    我们改进了用于正式证明神经网络输入输出特性的分支和边界(Branch and Bound,BaB)算法的可扩展性。首先,我们提出了基于拉格朗日分解的新型边界算法...

    用户8128510
  • 【论文推荐】最新八篇主题模型相关论文—主题建模优化、变分推断、情绪强度、神经语言模型、搜索、社区聚合、主题建模的问题、光谱学习

    【导读】专知内容组整理了最近八篇主题模型(Topic Model)相关文章,为大家进行介绍,欢迎查看! 1. Application of Rényi and ...

    WZEARW
  • 干货 | 10分钟带你全面掌握branch and bound(分支定界)算法-概念篇

    之前一直做启发式算法,最近突然对精确算法感兴趣了。但是这玩意儿说实话是真的难,刚好boss又叫我学学column generation求解VRP相关的内容。

    短短的路走走停停
  • 机器学习在组合优化中的应用(上)

    运筹学自二战诞生以来,现已被广泛应用于工业生产领域了,比如交通运输、供应链、能源、经济以及生产调度等。离散优化问题(discrete optimization ...

    短短的路走走停停

扫码关注云+社区

领取腾讯云代金券