如何实现一个高效的启发式算法？（VRPTW篇）
程序猿声
共 9198字，需浏览 19分钟
·
2020-10-13 23:41
上一期大家的反馈还不错，希望小编多多写写这种类似心得的文章。刚好小编最近也要学新东西了，打算把之前学的东西都整理一下写写，希望给大家带来一点小小的帮助吧~所以今天还是基于上一篇的主题，不过今天讲讲VRP加上了TW之后的算法实现，如何去除冗余。
如果大家觉得还不错的，可以在末尾打赏一下小编，或者点个再看哦，你们的支持是小编深夜写文稿最大的动力呢。
1 时间窗的计算
其实无论是TSP或者是VRP，计算邻居解的cost值都是非常简便的。只需要用原解的值减去旧的边再加上新的边即可。不明白的小伙伴请回去好好看看上一期的内容哦。但是多了时间窗以后，难度又上升了一个量级。
时间窗为什么难呢，因为节点的先后顺序是时间窗密切相关，并且前面的节点会影响到后面的节点。在经典的VRPTW中，规定了车辆早到必须等待，不允许晚到（如果晚到，该解不可行）。对于任意一个客户，其时间窗为，假如车辆到达该节点的时间点为，那么该节点的开始服务时间为：
因为早到必须等待，因此需要取两者中最大的。客户的服务时间为，那么车辆离开客户的时间点为
大家看，是不是决定了车辆到达下一个客户的时间点呢？假如之后的一个客户是，车辆行驶边
好了现在原理讲完了。下面讲讲邻居解怎样计算。
2 邻居解快速更新
我就拿之前的图过来了，关于路径cost的计算我就不再多讲了，这里讲讲时间窗的更新，因为在VRPTW的问题中，目标值一般是路径cost和时间窗违背的总和。假如解的时间窗违背总量为，显然当时，为可行解。那么如何计算呢？
发生变化的路径为和，要评估邻居解的时间窗，当然了看过上一期的小伙伴肯定不会整个解再重新计算一遍。可以单独把新的和拎出来，然后计算路径的，再用解的减去路径的即可。
由于时间窗层层关联的这种特性，对于快速计算和还是有一定的难度，这种难度尤其是提现在编码的实现上，因为要维护大量的中间变量，因此大部分同学的选择就是将两条路径重新计算，省时省力。毕竟有时候选择比努力重要得多。
不过小编当然不能退缩，因此今天就来讲讲邻居解的时间窗如何去除计算冗余。
首先我们来看移除一个客户的情景，移除了客户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
完整代码我会再做一期文章讲解的，因为这个写得实在是太经典了。来源是国外一个大学的一个课堂小组作业？嗯，就是你们上课上到一半老师突然说咱们做一个课堂小作业吧，然后你开始抽出一张白纸开始写字的那种课堂作业。不得不承认，人家国外讲课，还是比较注重实践呀~
评论