您好，登录后才能下订单哦！
密码登录
登录注册
点击 登录注册 即表示同意《亿速云用户服务条款》
这篇文章主要介绍“怎么实现一个高效的启发式算法”，在日常操作中，相信很多人在怎么实现一个高效的启发式算法问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答”怎么实现一个高效的启发式算法”的疑惑有所帮助！接下来，请跟着小编一起来学习吧！
其实无论是TSP或者是VRP，计算邻居解的cost值都是非常简便的。只需要用原解的值减去旧的边再加上新的边即可。不明白的小伙伴请回去好好看看上一期的内容哦。但是多了时间窗以后，难度又上升了一个量级。
时间窗为什么难呢，因为节点的先后顺序是时间窗密切相关，并且前面的节点会影响到后面的节点。在经典的VRPTW中，规定了车辆早到必须等待，不允许晚到（如果晚到，该解不可行）。对于任意一个客户 ，其时间窗为 ，假如车辆到达该节点的时间点为 ，那么该节点的开始服务时间 为：
因为早到必须等待，因此需要取两者中最大的。客户 的服务时间为 ，那么车辆离开客户 的时间点为
大家看， 是不是决定了车辆到达下一个客户的时间点呢？假如 之后的一个客户是 ，车辆行驶边<i,j>所需要的时间为 ，则车辆到达客户 的时间点为：
好了现在原理讲完了。下面讲讲邻居解怎样计算。
我就拿之前的图过来了，关于路径cost的计算我就不再多讲了，这里讲讲时间窗的更新，因为在VRPTW的问题中，目标值一般是路径cost和时间窗违背的总和。假如解 的时间窗违背总量为 ，显然当 时， 为可行解。那么如何计算 呢？
发生变化的路径为 和 ，要评估邻居解 的时间窗，当然了看过上一期的小伙伴肯定不会整个解再重新计算一遍。可以单独把新的 和 拎出来，然后计算路径的，再用解的减去路径的即可。
由于时间窗层层关联的这种特性，对于快速计算 和 还是有一定的难度，这种难度尤其是提现在编码的实现上，因为要维护大量的中间变量，因此大部分同学的选择就是将两条路径重新计算，省时省力。毕竟有时候选择比努力重要得多。
不过小编当然不能退缩，因此今天就来讲讲邻居解的时间窗如何去除计算冗余。
首先我们来看移除一个客户的情景， 移除了客户11和客户17之间的一个客户之后形成的 如下：
客户节点变动只会影响该节点之后的节点时间窗，因此对于前半截路段0->15->12->11是不需要重新计算的。现在问题来了：对于后半段17->7->0上的所有节点需要重新全部更新吗？
答案是不一定需要。只需要更新后面有可能发生改变的节点即可。那么对于节点 而言，在原先的路径中，车辆到达该节点的时间点为 ，如果 ，其中 为节点 的开始时间窗。那么在新的路径中，该节点以及该节点以后的节点都不需要进行更新了。
至于为什么，因为早到需要等待，如果在原先的路径中，车辆早到了，那么车辆的服务时间开始时间会重置到客户的开始时间窗，在移除一个客户后，那么车辆在新的路径中肯定会比之前的更早到达。总之，新路径中该客户处的开始服务时间就是客户的开始时间窗，与原路径保持一致，该客户以及后面所有的都无需更新了。
再来看看插入一个客户 的场景：
客户19之前的肯定不用管了。更新需要从该客户起，更新车辆到达客户19的时间，然后是客户2，一直到末尾。这里也和上面的一样，有一个临界条件的，达到该条件后就可以跳出更新。对于节点 而言，在新的（注意和上面的区别）的路径中，车辆到达该节点的时间点为 ，如果 ，其中 为节点 的开始时间窗。那么在新的路径中，该节点以及该节点以后的节点都不需要进行更新了。
因为早到需要等待，如果在原先的路径中，车辆早到了，那么车辆的服务时间开始时间会重置到客户的开始时间窗，在插入一个客户后，那么车辆在新的路径中肯定会比之前的更晚到达，如果新路径中车辆到达客户的时间点仍然小于等于客户的开始时间窗，那么该客户以及后面所有的都无需更新了。
当然了，还是得放一下代码，因为咱们是实干派，不吹牛皮不煲鸡汤。对于时间窗，每个客户节点还是需要维护一些中间变量的，难点就在于如何正确无误的维护这些中间变量。写去冗余的启发式难就难在调试……
首先是插入一个节点的代码：
/**
* 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到此，关于“怎么实现一个高效的启发式算法”的学习就结束了，希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习，快去试试吧！若想继续学习更多相关知识，请继续关注亿速云网站，小编会继续努力为大家带来更多实用的文章！
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。