专栏首页程序猿声如何实现一个高效的启发式算法?(VRPTW篇)

如何实现一个高效的启发式算法?(VRPTW篇)

上一期大家的反馈还不错,希望小编多多写写这种类似心得的文章。刚好小编最近也要学新东西了,打算把之前学的东西都整理一下写写,希望给大家带来一点小小的帮助吧~所以今天还是基于上一篇的主题,不过今天讲讲VRP加上了TW之后的算法实现,如何去除冗余。

如果大家觉得还不错的,可以在末尾打赏一下小编,或者点个再看哦,你们的支持是小编深夜写文稿最大的动力呢。

1 时间窗的计算

其实无论是TSP或者是VRP,计算邻居解的cost值都是非常简便的。只需要用原解的值减去旧的边再加上新的边即可。不明白的小伙伴请回去好好看看上一期的内容哦。但是多了时间窗以后,难度又上升了一个量级。

时间窗为什么难呢,因为节点的先后顺序是时间窗密切相关,并且前面的节点会影响到后面的节点。在经典的VRPTW中,规定了车辆早到必须等待,不允许晚到(如果晚到,该解不可行)。对于任意一个客户,其时间窗为,假如车辆到达该节点的时间点为,那么该节点的开始服务时间为:

w_i = \max\{a_i, t_i\} \tag{1}

因为早到必须等待,因此需要取两者中最大的。客户的服务时间为,那么车辆离开客户的时间点为

l_i = w_i + S_i \tag{2}

大家看,是不是决定了车辆到达下一个客户的时间点呢?假如之后的一个客户是,车辆行驶边<i,j>所需要的时间为,则车辆到达客户的时间点为:

t_j = l_i + c_{ij} \tag{3}

好了现在原理讲完了。下面讲讲邻居解怎样计算。

2 邻居解快速更新

我就拿之前的图过来了,关于路径cost的计算我就不再多讲了,这里讲讲时间窗的更新,因为在VRPTW的问题中,目标值一般是路径cost和时间窗违背的总和。假如解的时间窗违背总量为,显然当时,为可行解。那么如何计算呢?

发生变化的路径为和,要评估邻居解的时间窗,当然了看过上一期的小伙伴肯定不会整个解再重新计算一遍。可以单独把新的和拎出来,然后计算路径的,再用解的减去路径的即可。

C(S_2) = C(S_1) - C(r_2) - C(r_3) + C(r'_2) + C(r'_3)

由于时间窗层层关联的这种特性,对于快速计算和还是有一定的难度,这种难度尤其是提现在编码的实现上,因为要维护大量的中间变量,因此大部分同学的选择就是将两条路径重新计算,省时省力。毕竟有时候选择比努力重要得多。

不过小编当然不能退缩,因此今天就来讲讲邻居解的时间窗如何去除计算冗余。

首先我们来看移除一个客户的情景,移除了客户11和客户17之间的一个客户之后形成的如下:

客户节点变动只会影响该节点之后的节点时间窗,因此对于前半截路段0->15->12->11是不需要重新计算的。现在问题来了:对于后半段17->7->0上的所有节点需要重新全部更新吗?

答案是不一定需要。只需要更新后面有可能发生改变的节点即可。那么对于节点而言,在原先的路径中,车辆到达该节点的时间点为,如果,其中为节点的开始时间窗。那么在新的路径中,该节点以及该节点以后的节点都不需要进行更新了。

至于为什么,因为早到需要等待,如果在原先的路径中,车辆早到了,那么车辆的服务时间开始时间会重置到客户的开始时间窗,在移除一个客户后,那么车辆在新的路径中肯定会比之前的更早到达。总之,新路径中该客户处的开始服务时间就是客户的开始时间窗,与原路径保持一致,该客户以及后面所有的都无需更新了。

再来看看插入一个客户的场景:

客户19之前的肯定不用管了。更新需要从该客户起,更新车辆到达客户19的时间,然后是客户2,一直到末尾。这里也和上面的一样,有一个临界条件的,达到该条件后就可以跳出更新。对于节点而言,在新的(注意和上面的区别)的路径中,车辆到达该节点的时间点为,如果,其中为节点的开始时间窗。那么在新的路径中,该节点以及该节点以后的节点都不需要进行更新了。

因为早到需要等待,如果在原先的路径中,车辆早到了,那么车辆的服务时间开始时间会重置到客户的开始时间窗,在插入一个客户后,那么车辆在新的路径中肯定会比之前的更晚到达,如果新路径中车辆到达客户的时间点仍然小于等于客户的开始时间窗,那么该客户以及后面所有的都无需更新了。

3 编程实现

当然了,还是得放一下代码,因为咱们是实干派,不吹牛皮不煲鸡汤。对于时间窗,每个客户节点还是需要维护一些中间变量的,难点就在于如何正确无误的维护这些中间变量。写去冗余的启发式难就难在调试……

首先是插入一个节点的代码:

    /**
     * This function simulate the insertion of the customer in the given route on the given position.
     * Computes the new cost and return it.
     * It is an optimized version of the evaluate route. Calculates only for the customers affected
     * by the insertion. Starts from the given position and could finish before reaching the end of
     * the list if there is no modification in the arrive time at the customers.
     * Does not alter the route or the customer
     * @param route
     * @param customer
     * @param position
     * @return
     */
    private Cost evaluateInsertRoute(Route route, Customer customer, int position) {
     Cost varCost = new Cost(route.getCost());
     double arriveCustomer = 0;
     double arriveNextCustomer = 0;
     double waitingTimeCustomer = 0;
     double waitingTimeNextCustomer = 0;
     double twViolCustomer = 0;
     double twViolNextCustomer = 0;

     // if route is empty insert: depot - customer - depot
     if(route.isEmpty()) {
      varCost.initialize();
      // arrive time at the customer
      arriveCustomer = route.getDepot().getStartTw()
               + instance.getTravelTime(route.getDepotNr(), customer.getNumber());
         // waiting time for the customer if any
      waitingTimeCustomer = Math.max(0, customer.getStartTw() - arriveCustomer);
      // time window violation of the customer if any
      twViolCustomer = Math.max(0, arriveCustomer - customer.getEndTw());
      // arrive time at the depot
      arriveNextCustomer = Math.max(customer.getStartTw(), arriveCustomer)
                   + customer.getServiceDuration()
                   + instance.getTravelTime(customer.getNumber(), route.getDepotNr());
      // time window violation of the depot if any
      twViolNextCustomer = Math.max(0, arriveNextCustomer - route.getDepot().getEndTw());
      //variation of the travel time
      varCost.travelTime = instance.getTravelTime(route.getDepotNr(), customer.getNumber())
             + instance.getTravelTime(customer.getNumber(), route.getDepotNr());
      // variation of the capacity
      varCost.load = customer.getCapacity();
      // route service time
      varCost.serviceTime = customer.getServiceDuration();
      //variation of the waiting time
      varCost.waitingTime = waitingTimeCustomer;
      // variation of the time windows violation
      varCost.twViol = twViolCustomer + twViolNextCustomer;
      
     }else{     
      // insertion at the end of the list: customer before - customer - depot
      if(position == route.getCustomersLength()){
       Customer customerBefore = route.getCustomer(position - 1);
       arriveCustomer = Math.max(customerBefore.getStartTw(), customerBefore.getArriveTime())
                + customerBefore.getServiceDuration()
                + instance.getTravelTime(customerBefore.getNumber(), customer.getNumber());
          // waiting time for the customer if any
       waitingTimeCustomer = Math.max(0, customer.getStartTw() - arriveCustomer);
       // time window violation of the customer if any
       twViolCustomer = Math.max(0, arriveCustomer - customer.getEndTw());
       // arrive time at the depot
       arriveNextCustomer = Math.max(customer.getStartTw(), arriveCustomer)
                    + customer.getServiceDuration()
                    + instance.getTravelTime(customer.getNumber(), route.getDepotNr());
       // time window violation of the depot if any
       twViolNextCustomer = Math.max(0, arriveNextCustomer - route.getDepot().getEndTw());
       //variation of the travel time
       varCost.travelTime += - instance.getTravelTime(customerBefore.getNumber(), route.getDepotNr())
                       + instance.getTravelTime(customerBefore.getNumber(), customer.getNumber())
              + instance.getTravelTime(customer.getNumber(), route.getDepotNr());
       // variation of the capacity
       varCost.load += customer.getCapacity();
       // route service time
       varCost.serviceTime += customer.getServiceDuration();
       //variation of the waiting time
       varCost.waitingTime += waitingTimeCustomer;
       // variation of the time windows violation
       varCost.twViol += - varCost.depotTwViol + twViolCustomer + twViolNextCustomer;
      }else {
       double variation = 0;
       Customer customerAfter = route.getCustomer(position);
       // insertion on the first position: depot - customer - customer after
       if(position == 0){
        // time before arrive at the customer
        arriveCustomer = route.getDepot().getStartTw()
                 + instance.getTravelTime(route.getDepotNr(), customer.getNumber());
        //variation of the travel time
        varCost.travelTime += - instance.getTravelTime(route.getDepotNr(), customerAfter.getNumber())
                        + instance.getTravelTime(route.getDepotNr(), customer.getNumber())
               + instance.getTravelTime(customer.getNumber(), customerAfter.getNumber());
      
       // insertion in the middle of the list:  customer before - customer - customer after
       }else {
        Customer customerBefore = route.getCustomer(position - 1);
        // time before arrive at the customer
        arriveCustomer = Math.max(customerBefore.getStartTw(), customerBefore.getArriveTime())
                 + customerBefore.getServiceDuration()
                 + instance.getTravelTime(customerBefore.getNumber(), customer.getNumber());
        //variation of the travel time
        varCost.travelTime += - instance.getTravelTime(customerBefore.getNumber(), customerAfter.getNumber())
                        + instance.getTravelTime(customerBefore.getNumber(), customer.getNumber())
               + instance.getTravelTime(customer.getNumber(), customerAfter.getNumber());
       } // end if else beginning or middle
       
       // this code runs when inserting at the beginning or in the middle
          // waiting time for the customer if any
       waitingTimeCustomer = Math.max(0, customer.getStartTw() - arriveCustomer);
       // time window violation of the customer if any
       twViolCustomer = Math.max(0, arriveCustomer - customer.getEndTw());
       // before arrive time at the customer after
       arriveNextCustomer = Math.max(customer.getStartTw(), arriveCustomer)
                    + customer.getServiceDuration()
                    + instance.getTravelTime(customer.getNumber(), customerAfter.getNumber());
       // waiting time for the customer after if any
       waitingTimeNextCustomer = Math.max(0, customerAfter.getStartTw() - arriveNextCustomer);
       // time window violation of the customer after if any
       twViolNextCustomer = Math.max(0, arriveNextCustomer - customerAfter.getEndTw());
       
       // variation of the capacity
       varCost.load += customer.getCapacity();
       // route service time
       varCost.serviceTime += customer.getServiceDuration();
       //variation of the waiting time
       varCost.waitingTime += - customerAfter.getWaitingTime() + waitingTimeCustomer + waitingTimeNextCustomer;
       // variation of the time windows violation
       varCost.twViol +=  - customerAfter.getTwViol() + twViolCustomer + twViolNextCustomer;
       
//       variation = Math.max(customerAfter.getStartTw(), arriveNextCustomer) - Math.max(customerAfter.getStartTw(), customerAfter.getArriveTime());
       variation = arriveNextCustomer + waitingTimeNextCustomer - customerAfter.getArriveTime() - customerAfter.getWaitingTime();
       variation = Math.abs(variation) < instance.getPrecision() ? 0 : variation;

       // if there is a variation update the nodes after too
       int i = position + 1;
       while (variation != 0 && i < route.getCustomersLength()){ 
         customerAfter = route.getCustomer(i);
         // arrive at the customer after
         arriveNextCustomer = customerAfter.getArriveTime() + variation;
            waitingTimeNextCustomer = Math.max(0, customerAfter.getStartTw() - arriveNextCustomer);
            twViolNextCustomer = Math.max(0, arriveNextCustomer - customerAfter.getEndTw());
            //variation of the waiting time
            varCost.waitingTime += - customerAfter.getWaitingTime() + waitingTimeNextCustomer;
            // variation of the time windows violation
            varCost.twViol += - customerAfter.getTwViol() + twViolNextCustomer;
            
//            variation = Math.max(customerAfter.getStartTw(), arriveNextCustomer) - Math.max(customerAfter.getStartTw(), customerAfter.getArriveTime());
            variation = arriveNextCustomer + waitingTimeNextCustomer - customerAfter.getArriveTime() - customerAfter.getWaitingTime();
            variation = Math.abs(variation) < instance.getPrecision() ? 0 : variation;

            i++;
       }// end while
        
       if(i == route.getCustomersLength() && variation != 0 ){
        // update the return to the depot
        arriveNextCustomer = varCost.returnToDepotTime + variation;
        twViolNextCustomer = Math.max(0, arriveNextCustomer - route.getDepot().getEndTw());
        // variation of the time windows violation
           varCost.twViol += - varCost.depotTwViol + twViolNextCustomer;
           
       }// end if return to depot
       
       } // end if else of position cases
     } // end if else route is empty
     
  varCost.waitingTime = Math.abs(varCost.waitingTime) < instance.getPrecision() ? 0 : varCost.waitingTime;
  varCost.twViol = Math.abs(varCost.twViol) < instance.getPrecision() ? 0 : varCost.twViol;
     
  varCost.setLoadViol(Math.max(0, varCost.load - route.getLoadAdmited()));
  varCost.setDurationViol(Math.max(0, varCost.getDuration() - route.getDurationAdmited()));

  return varCost;
    } // end method evaluate insert route
 
 
 /**
  * This function simulate the deletion of a customer in the given route on the given position.
     * Computes the new cost and return it.
     * It is an optimized version of the evaluate route. Calculates only for the customers affected
     * by the deletion. Starts from the given position and could finish before reaching the end of
     * the list if there is no modification in the arrive time at the customers.
     * Does not alter the route.
  * @param route
  * @param position
  * @return
  */
    private Cost evaluateDeleteRoute(Route route, Customer customer, int position) {
     Cost varCost = new Cost(route.getCost());
     double arriveNextCustomer = 0;
     double waitingTimeNextCustomer = 0;
     double twViolNextCustomer = 0;

     // if route has only the customer that will be deleted
     if(route.getCustomersLength() - 1 == 0) {
      varCost.initialize();      
     
     }else{     
      // case when customer is the last one: customer before - depot
      if(position == route.getCustomersLength() - 1){
       Customer customerBefore = route.getCustomer(position - 1);
       //arrive time at the depot
       arriveNextCustomer = Math.max(customerBefore.getStartTw(), customerBefore.getArriveTime())
                    + customerBefore.getServiceDuration()
                    + instance.getTravelTime(customerBefore.getNumber(), route.getDepotNr());
       // time window violation of the depot if any
       twViolNextCustomer = Math.max(0, arriveNextCustomer - route.getDepot().getEndTw());
       //variation of the travel time
       varCost.travelTime += - instance.getTravelTime(customerBefore.getNumber(), customer.getNumber())
              - instance.getTravelTime(customer.getNumber(), route.getDepotNr())
               + instance.getTravelTime(customerBefore.getNumber(), route.getDepotNr());
                     
       // variation of the capacity
       varCost.load -= customer.getCapacity();
       // route service time
       varCost.serviceTime -= customer.getServiceDuration();
       //variation of the waiting time
       varCost.waitingTime -= customer.getWaitingTime();
       // variation of the time windows violation
       varCost.twViol += - customer.getTwViol() - route.getDepotTwViol() + twViolNextCustomer;

      }else{
       double variation = 0;
       Customer customerAfter = route.getCustomer(position + 1);
       // delete on the first position
       if(position == 0){
        // time before arrive at customer after
        arriveNextCustomer = route.getDepot().getStartTw()
                           + instance.getTravelTime(route.getDepotNr(), customerAfter.getNumber());
        //variation of the travel time
        varCost.travelTime  += - instance.getTravelTime(route.getDepotNr(), customer.getNumber())
                - instance.getTravelTime(customer.getNumber(), customerAfter.getNumber())
                         + instance.getTravelTime(route.getDepotNr(), customerAfter.getNumber());
      
       // insertion in the middle of the list
       }else{
        Customer customerBefore = route.getCustomer(position - 1);
        // time before arrive at customer after
        arriveNextCustomer = Math.max(customerBefore.getStartTw(), customerBefore.getArriveTime())
                           + customerBefore.getServiceDuration()
                           + instance.getTravelTime(customerBefore.getNumber(), customerAfter.getNumber());
        //variation of the travel time
        varCost.travelTime += - instance.getTravelTime(customerBefore.getNumber(), customer.getNumber())
               - instance.getTravelTime(customer.getNumber(), customerAfter.getNumber())
                        + instance.getTravelTime(customerBefore.getNumber(), customerAfter.getNumber());
        } // end if else beginning or middle
       // this code runs when inserting at the beginning or in the middle
       
          // waiting time for the customer after if any
       waitingTimeNextCustomer = Math.max(0, customerAfter.getStartTw() - arriveNextCustomer);
       // time window violation of the customer after if any
       twViolNextCustomer = Math.max(0, arriveNextCustomer - customerAfter.getEndTw());
       
       // variation of the capacity
       varCost.load -= customer.getCapacity();
       // route service time
       varCost.serviceTime -= customer.getServiceDuration();
       //variation of the waiting time
       varCost.waitingTime += - customer.getWaitingTime() - customerAfter.getWaitingTime() + waitingTimeNextCustomer;
       // variation of the time windows violation
       varCost.twViol += - customer.getTwViol() - customerAfter.getTwViol() +  twViolNextCustomer;
       
//       variation = Math.max(customerAfter.getStartTw(), arriveNextCustomer) - Math.max(customerAfter.getStartTw(), customerAfter.getArriveTime());
//       variation = arriveNextCustomer -customerAfter.getArriveTime();
       variation = arriveNextCustomer + waitingTimeNextCustomer - customerAfter.getArriveTime() - customerAfter.getWaitingTime();
       variation = Math.abs(variation) < instance.getPrecision() ? 0 : variation;   

       // if there is a variation update the nodes after too
       // the node after the customer is already updated
       int i = position + 2;
       while (variation != 0 && i < route.getCustomersLength()){ 
         customerAfter = route.getCustomer(i);
         // arrive at the customer after
         arriveNextCustomer = customerAfter.getArriveTime() + variation;
            waitingTimeNextCustomer = Math.max(0, customerAfter.getStartTw() - arriveNextCustomer);
            twViolNextCustomer = Math.max(0, arriveNextCustomer - customerAfter.getEndTw());
            //variation of the waiting time
            varCost.waitingTime += -customerAfter.getWaitingTime() + waitingTimeNextCustomer;
            // variation of the time windows violation
            varCost.twViol += -customerAfter.getTwViol() + twViolNextCustomer;
            
//            variation = Math.max(customerAfter.getStartTw(), arriveNextCustomer) - Math.max(customerAfter.getStartTw(), customerAfter.getArriveTime());
//            variation = arriveNextCustomer -customerAfter.getArriveTime();
            variation = arriveNextCustomer + waitingTimeNextCustomer - customerAfter.getArriveTime() - customerAfter.getWaitingTime();
            variation = Math.abs(variation) < instance.getPrecision() ? 0 : variation; 
                        
            i++;
       }// end while
        
       // update depot violation too if any
       if(i == route.getCustomersLength() && variation != 0 ){
        // update the return to the depot
        arriveNextCustomer = route.getReturnToDepotTime() + variation;
        twViolNextCustomer = Math.max(0, arriveNextCustomer - route.getDepot().getEndTw());
        // variation of the time windows violation
           varCost.twViol += - route.getDepotTwViol() + twViolNextCustomer;
                      
       }// end if return to depot
       
       
       
       
       } // end if else of position cases
     } // end if else route is empty

//     route.removeCustomer(position);
     // be careful about precision; if there are subtraction
  varCost.waitingTime = Math.abs(varCost.waitingTime) < instance.getPrecision() ? 0 : varCost.waitingTime;
  varCost.twViol = Math.abs(varCost.twViol) < instance.getPrecision() ? 0 : varCost.twViol;
  
  varCost.setLoadViol(Math.max(0, varCost.load - route.getLoadAdmited()));
  varCost.setDurationViol(Math.max(0, varCost.getDuration() - route.getDurationAdmited()));
  
  return varCost;
    } // end method evaluate delete route

然后是删除一个客户的代码:

 /**
  * This function simulate the deletion of a customer in the given route on the given position.
     * Computes the new cost and return it.
     * It is an optimized version of the evaluate route. Calculates only for the customers affected
     * by the deletion. Starts from the given position and could finish before reaching the end of
     * the list if there is no modification in the arrive time at the customers.
     * Does not alter the route.
  * @param route
  * @param position
  * @return
  */
    private Cost evaluateDeleteRoute(Route route, Customer customer, int position) {
     Cost varCost = new Cost(route.getCost());
     double arriveNextCustomer = 0;
     double waitingTimeNextCustomer = 0;
     double twViolNextCustomer = 0;

     // if route has only the customer that will be deleted
     if(route.getCustomersLength() - 1 == 0) {
      varCost.initialize();      
     
     }else{     
      // case when customer is the last one: customer before - depot
      if(position == route.getCustomersLength() - 1){
       Customer customerBefore = route.getCustomer(position - 1);
       //arrive time at the depot
       arriveNextCustomer = Math.max(customerBefore.getStartTw(), customerBefore.getArriveTime())
                    + customerBefore.getServiceDuration()
                    + instance.getTravelTime(customerBefore.getNumber(), route.getDepotNr());
       // time window violation of the depot if any
       twViolNextCustomer = Math.max(0, arriveNextCustomer - route.getDepot().getEndTw());
       //variation of the travel time
       varCost.travelTime += - instance.getTravelTime(customerBefore.getNumber(), customer.getNumber())
              - instance.getTravelTime(customer.getNumber(), route.getDepotNr())
               + instance.getTravelTime(customerBefore.getNumber(), route.getDepotNr());
                     
       // variation of the capacity
       varCost.load -= customer.getCapacity();
       // route service time
       varCost.serviceTime -= customer.getServiceDuration();
       //variation of the waiting time
       varCost.waitingTime -= customer.getWaitingTime();
       // variation of the time windows violation
       varCost.twViol += - customer.getTwViol() - route.getDepotTwViol() + twViolNextCustomer;

      }else{
       double variation = 0;
       Customer customerAfter = route.getCustomer(position + 1);
       // delete on the first position
       if(position == 0){
        // time before arrive at customer after
        arriveNextCustomer = route.getDepot().getStartTw()
                           + instance.getTravelTime(route.getDepotNr(), customerAfter.getNumber());
        //variation of the travel time
        varCost.travelTime  += - instance.getTravelTime(route.getDepotNr(), customer.getNumber())
                - instance.getTravelTime(customer.getNumber(), customerAfter.getNumber())
                         + instance.getTravelTime(route.getDepotNr(), customerAfter.getNumber());
      
       // insertion in the middle of the list
       }else{
        Customer customerBefore = route.getCustomer(position - 1);
        // time before arrive at customer after
        arriveNextCustomer = Math.max(customerBefore.getStartTw(), customerBefore.getArriveTime())
                           + customerBefore.getServiceDuration()
                           + instance.getTravelTime(customerBefore.getNumber(), customerAfter.getNumber());
        //variation of the travel time
        varCost.travelTime += - instance.getTravelTime(customerBefore.getNumber(), customer.getNumber())
               - instance.getTravelTime(customer.getNumber(), customerAfter.getNumber())
                        + instance.getTravelTime(customerBefore.getNumber(), customerAfter.getNumber());
        } // end if else beginning or middle
       // this code runs when inserting at the beginning or in the middle
       
          // waiting time for the customer after if any
       waitingTimeNextCustomer = Math.max(0, customerAfter.getStartTw() - arriveNextCustomer);
       // time window violation of the customer after if any
       twViolNextCustomer = Math.max(0, arriveNextCustomer - customerAfter.getEndTw());
       
       // variation of the capacity
       varCost.load -= customer.getCapacity();
       // route service time
       varCost.serviceTime -= customer.getServiceDuration();
       //variation of the waiting time
       varCost.waitingTime += - customer.getWaitingTime() - customerAfter.getWaitingTime() + waitingTimeNextCustomer;
       // variation of the time windows violation
       varCost.twViol += - customer.getTwViol() - customerAfter.getTwViol() +  twViolNextCustomer;
       
//       variation = Math.max(customerAfter.getStartTw(), arriveNextCustomer) - Math.max(customerAfter.getStartTw(), customerAfter.getArriveTime());
//       variation = arriveNextCustomer -customerAfter.getArriveTime();
       variation = arriveNextCustomer + waitingTimeNextCustomer - customerAfter.getArriveTime() - customerAfter.getWaitingTime();
       variation = Math.abs(variation) < instance.getPrecision() ? 0 : variation;   

       // if there is a variation update the nodes after too
       // the node after the customer is already updated
       int i = position + 2;
       while (variation != 0 && i < route.getCustomersLength()){ 
         customerAfter = route.getCustomer(i);
         // arrive at the customer after
         arriveNextCustomer = customerAfter.getArriveTime() + variation;
            waitingTimeNextCustomer = Math.max(0, customerAfter.getStartTw() - arriveNextCustomer);
            twViolNextCustomer = Math.max(0, arriveNextCustomer - customerAfter.getEndTw());
            //variation of the waiting time
            varCost.waitingTime += -customerAfter.getWaitingTime() + waitingTimeNextCustomer;
            // variation of the time windows violation
            varCost.twViol += -customerAfter.getTwViol() + twViolNextCustomer;
            
//            variation = Math.max(customerAfter.getStartTw(), arriveNextCustomer) - Math.max(customerAfter.getStartTw(), customerAfter.getArriveTime());
//            variation = arriveNextCustomer -customerAfter.getArriveTime();
            variation = arriveNextCustomer + waitingTimeNextCustomer - customerAfter.getArriveTime() - customerAfter.getWaitingTime();
            variation = Math.abs(variation) < instance.getPrecision() ? 0 : variation; 
                        
            i++;
       }// end while
        
       // update depot violation too if any
       if(i == route.getCustomersLength() && variation != 0 ){
        // update the return to the depot
        arriveNextCustomer = route.getReturnToDepotTime() + variation;
        twViolNextCustomer = Math.max(0, arriveNextCustomer - route.getDepot().getEndTw());
        // variation of the time windows violation
           varCost.twViol += - route.getDepotTwViol() + twViolNextCustomer;
                      
       }// end if return to depot
       
       
       
       
       } // end if else of position cases
     } // end if else route is empty

//     route.removeCustomer(position);
     // be careful about precision; if there are subtraction
  varCost.waitingTime = Math.abs(varCost.waitingTime) < instance.getPrecision() ? 0 : varCost.waitingTime;
  varCost.twViol = Math.abs(varCost.twViol) < instance.getPrecision() ? 0 : varCost.twViol;
  
  varCost.setLoadViol(Math.max(0, varCost.load - route.getLoadAdmited()));
  varCost.setDurationViol(Math.max(0, varCost.getDuration() - route.getDurationAdmited()));
  
  return varCost;
    } // end method evaluate delete route

完整代码我会再做一期文章讲解的,因为这个写得实在是太经典了。来源是国外一个大学的一个课堂小组作业?嗯,就是你们上课上到一半老师突然说咱们做一个课堂小作业吧,然后你开始抽出一张白纸开始写字的那种课堂作业。不得不承认,人家国外讲课,还是比较注重实践呀~

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

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

原始发表时间:2020-10-13

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 如何实现一个高效的启发式算法?

    小伙伴们好,说起来已经好久好久好久没见了呢!之前一直忙着做其他事情去了(泛指学习一类),公众号已经落下好久好久了。今天来写点好玩的东西。

    短短的路走走停停
  • 教你使用Column Generation求解VRPTW的线性松弛模型

    此前向大家介绍了列生成算法的详细过程,以及下料问题的代码。相信各位小伙伴对Column Generation已经有了一个透彻的了解了。如果不熟悉的请再回去复习一...

    用户1621951
  • 教你使用Column Generation求解VRPTW的线性松弛模型

    此前向大家介绍了列生成算法的详细过程,以及下料问题的代码。相信各位小伙伴对Column Generation已经有了一个透彻的了解了。

    短短的路走走停停
  • 好码分享:开源算法框架Open Tabu Search求解VRPTW的JAVA代码

    很早之前就想写这篇文章了,由于各种不可描述的原因拖延到了现在,今儿就把坑给填上吧~

    短短的路走走停停
  • 【干货】算法学习必备诀窍:算法可视化解密

    受困于繁复的代码块里,每天看着密密麻麻的变量和语句,拿着别人提供的代码跑出结果也不知道结果是什么?

    用户1621951
  • 干货|遗传算法解决带时间窗的车辆路径规划问题(附java代码及详细注释)

    各位读者大家好,今天小编给大家分享如何用遗传算法求解带时间窗的车辆路径规划问题。算法的主要思想来自于论文:A simple and effective evol...

    用户1621951
  • 干货|十分钟快速掌握CPLEX求解VRPTW数学模型(附JAVA代码及CPLEX安装流程)

    号外!号外!常年用 TSP 举例的某干货分享板块终于 倒闭 改革了!小编终于被boss揪去关·禁·闭、学·习·进·阶、突·破·自·我了! 本着 独学学 ...

    用户1621951
  • 禁忌搜索算法求解带时间窗的车辆路径规划问题详解(附Java代码)

    所以赶紧趁考试周来临前,码出了这篇禁忌搜索算法解决VRPTW的文章,临时抱佛脚,假装自己今年学了一点东西。

    用户1621951
  • 干货|十分钟快速掌握CPLEX求解VRPTW数学模型(附JAVA代码及CPLEX安装流程)

    提到带时间窗车辆路径问题(vehicle routing problems with time windows,VRPTW),就不得不先说说车辆路径问题(...

    短短的路走走停停

扫码关注云+社区

领取腾讯云代金券