溫馨提示×
您好，登錄后才能下訂單哦！
點(diǎn)擊 登錄注冊(cè) 即表示同意《億速云用戶服務(wù)條款》
您好，登錄后才能下訂單哦！
這篇文章主要介紹“怎么實(shí)現(xiàn)一個(gè)高效的啟發(fā)式算法”，在日常操作中，相信很多人在怎么實(shí)現(xiàn)一個(gè)高效的啟發(fā)式算法問題上存在疑惑，小編查閱了各式資料，整理出簡(jiǎn)單好用的操作方法，希望對(duì)大家解答”怎么實(shí)現(xiàn)一個(gè)高效的啟發(fā)式算法”的疑惑有所幫助！接下來，請(qǐng)跟著小編一起來學(xué)習(xí)吧！
其實(shí)無論是TSP或者是VRP，計(jì)算鄰居解的cost值都是非常簡(jiǎn)便的。只需要用原解的值減去舊的邊再加上新的邊即可。不明白的小伙伴請(qǐng)回去好好看看上一期的內(nèi)容哦。但是多了時(shí)間窗以后，難度又上升了一個(gè)量級(jí)。
時(shí)間窗為什么難呢，因?yàn)楣?jié)點(diǎn)的先后順序是時(shí)間窗密切相關(guān)，并且前面的節(jié)點(diǎn)會(huì)影響到后面的節(jié)點(diǎn)。在經(jīng)典的VRPTW中，規(guī)定了車輛早到必須等待，不允許晚到（如果晚到，該解不可行）。對(duì)于任意一個(gè)客戶 ，其時(shí)間窗為 ，假如車輛到達(dá)該節(jié)點(diǎn)的時(shí)間點(diǎn)為 ，那么該節(jié)點(diǎn)的開始服務(wù)時(shí)間 為：
因?yàn)樵绲奖仨毜却?，因此需要取兩者中最大的。客? 的服務(wù)時(shí)間為 ，那么車輛離開客戶 的時(shí)間點(diǎn)為
大家看， 是不是決定了車輛到達(dá)下一個(gè)客戶的時(shí)間點(diǎn)呢？假如 之后的一個(gè)客戶是 ，車輛行駛邊<i,j>所需要的時(shí)間為 ，則車輛到達(dá)客戶 的時(shí)間點(diǎn)為：
好了現(xiàn)在原理講完了。下面講講鄰居解怎樣計(jì)算。
我就拿之前的圖過來了，關(guān)于路徑cost的計(jì)算我就不再多講了，這里講講時(shí)間窗的更新，因?yàn)樵赩RPTW的問題中，目標(biāo)值一般是路徑cost和時(shí)間窗違背的總和。假如解 的時(shí)間窗違背總量為 ，顯然當(dāng) 時(shí)， 為可行解。那么如何計(jì)算 呢？
發(fā)生變化的路徑為 和 ，要評(píng)估鄰居解 的時(shí)間窗，當(dāng)然了看過上一期的小伙伴肯定不會(huì)整個(gè)解再重新計(jì)算一遍。可以單獨(dú)把新的 和 拎出來，然后計(jì)算路徑的，再用解的減去路徑的即可。
由于時(shí)間窗層層關(guān)聯(lián)的這種特性，對(duì)于快速計(jì)算 和 還是有一定的難度，這種難度尤其是提現(xiàn)在編碼的實(shí)現(xiàn)上，因?yàn)橐S護(hù)大量的中間變量，因此大部分同學(xué)的選擇就是將兩條路徑重新計(jì)算，省時(shí)省力。畢竟有時(shí)候選擇比努力重要得多。
不過小編當(dāng)然不能退縮，因此今天就來講講鄰居解的時(shí)間窗如何去除計(jì)算冗余。
首先我們來看移除一個(gè)客戶的情景， 移除了客戶11和客戶17之間的一個(gè)客戶之后形成的 如下：
客戶節(jié)點(diǎn)變動(dòng)只會(huì)影響該節(jié)點(diǎn)之后的節(jié)點(diǎn)時(shí)間窗，因此對(duì)于前半截路段0->15->12->11是不需要重新計(jì)算的。現(xiàn)在問題來了：對(duì)于后半段17->7->0上的所有節(jié)點(diǎn)需要重新全部更新嗎？
答案是不一定需要。只需要更新后面有可能發(fā)生改變的節(jié)點(diǎn)即可。那么對(duì)于節(jié)點(diǎn) 而言，在原先的路徑中，車輛到達(dá)該節(jié)點(diǎn)的時(shí)間點(diǎn)為 ，如果 ，其中 為節(jié)點(diǎn) 的開始時(shí)間窗。那么在新的路徑中，該節(jié)點(diǎn)以及該節(jié)點(diǎn)以后的節(jié)點(diǎn)都不需要進(jìn)行更新了。
至于為什么，因?yàn)樵绲叫枰却绻谠鹊穆窂街?，車輛早到了，那么車輛的服務(wù)時(shí)間開始時(shí)間會(huì)重置到客戶的開始時(shí)間窗，在移除一個(gè)客戶后，那么車輛在新的路徑中肯定會(huì)比之前的更早到達(dá)?？傊侣窂街性摽蛻籼幍拈_始服務(wù)時(shí)間就是客戶的開始時(shí)間窗，與原路徑保持一致，該客戶以及后面所有的都無需更新了。
再來看看插入一個(gè)客戶 的場(chǎng)景：
客戶19之前的肯定不用管了。更新需要從該客戶起，更新車輛到達(dá)客戶19的時(shí)間，然后是客戶2，一直到末尾。這里也和上面的一樣，有一個(gè)臨界條件的，達(dá)到該條件后就可以跳出更新。對(duì)于節(jié)點(diǎn) 而言，在新的（注意和上面的區(qū)別）的路徑中，車輛到達(dá)該節(jié)點(diǎn)的時(shí)間點(diǎn)為 ，如果 ，其中 為節(jié)點(diǎn) 的開始時(shí)間窗。那么在新的路徑中，該節(jié)點(diǎn)以及該節(jié)點(diǎn)以后的節(jié)點(diǎn)都不需要進(jìn)行更新了。
因?yàn)樵绲叫枰却?，如果在原先的路徑中，車輛早到了，那么車輛的服務(wù)時(shí)間開始時(shí)間會(huì)重置到客戶的開始時(shí)間窗，在插入一個(gè)客戶后，那么車輛在新的路徑中肯定會(huì)比之前的更晚到達(dá)，如果新路徑中車輛到達(dá)客戶的時(shí)間點(diǎn)仍然小于等于客戶的開始時(shí)間窗，那么該客戶以及后面所有的都無需更新了。
當(dāng)然了，還是得放一下代碼，因?yàn)樵蹅兪菍?shí)干派，不吹牛皮不煲雞湯。對(duì)于時(shí)間窗，每個(gè)客戶節(jié)點(diǎn)還是需要維護(hù)一些中間變量的，難點(diǎn)就在于如何正確無誤的維護(hù)這些中間變量。寫去冗余的啟發(fā)式難就難在調(diào)試……
首先是插入一個(gè)節(jié)點(diǎn)的代碼：
/**
* 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
然后是刪除一個(gè)客戶的代碼：
/**
* 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到此，關(guān)于“怎么實(shí)現(xiàn)一個(gè)高效的啟發(fā)式算法”的學(xué)習(xí)就結(jié)束了，希望能夠解決大家的疑惑。理論與實(shí)踐的搭配能更好的幫助大家學(xué)習(xí)，快去試試吧！若想繼續(xù)學(xué)習(xí)更多相關(guān)知識(shí)，請(qǐng)繼續(xù)關(guān)注億速云網(wǎng)站，小編會(huì)繼續(xù)努力為大家?guī)砀鄬?shí)用的文章！
免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱：is@yisu.com進(jìn)行舉報(bào)，并提供相關(guān)證據(jù)，一經(jīng)查實(shí)，將立刻刪除涉嫌侵權(quán)內(nèi)容。
億速云公眾號(hào)
手機(jī)網(wǎng)站二維碼