人人澡人人爽人人精品,国产在线观看,午夜无码操逼逼,色老板成人无码版在线播放,国语对白在线免费视频,啪啪啪在线网站,苍井空A连接,操逼网站大全

上一期大家的反饋還不錯(cuò)，希望小編多多寫寫這種類似心得的文章。剛好小編最近也要學(xué)新東西了，打算把之前學(xué)的東西都整理一下寫寫，希望給大家?guī)?lái)一點(diǎn)小小的幫助吧~所以今天還是基于上一篇的主題，不過(guò)今天講講VRP加上了TW之后的算法實(shí)現(xiàn)，如何去除冗余。

如果大家覺(jué)得還不錯(cuò)的，可以在末尾打賞一下小編，或者點(diǎn)個(gè)再看哦，你們的支持是小編深夜寫文稿最大的動(dòng)力呢。

1 時(shí)間窗的計(jì)算

其實(shí)無(wú)論是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è)客戶是，車輛行駛邊所需要的時(shí)間為，則車輛到達(dá)客戶的時(shí)間點(diǎn)為：

好了現(xiàn)在原理講完了。下面講講鄰居解怎樣計(jì)算。

2 鄰居解快速更新

我就拿之前的圖過(guò)來(lái)了，關(guān)于路徑cost的計(jì)算我就不再多講了，這里講講時(shí)間窗的更新，因?yàn)樵赩RPTW的問(wèn)題中，目標(biāo)值一般是路徑cost和時(shí)間窗違背的總和。假如解的時(shí)間窗違背總量為，顯然當(dāng)時(shí)，為可行解。那么如何計(jì)算呢？

發(fā)生變化的路徑為和，要評(píng)估鄰居解的時(shí)間窗，當(dāng)然了看過(guò)上一期的小伙伴肯定不會(huì)整個(gè)解再重新計(jì)算一遍。可以單獨(dú)把新的和拎出來(lái)，然后計(jì)算路徑的，再用解的減去路徑的即可。

由于時(shí)間窗層層關(guān)聯(lián)的這種特性，對(duì)于快速計(jì)算和還是有一定的難度，這種難度尤其是提現(xiàn)在編碼的實(shí)現(xiàn)上，因?yàn)橐S護(hù)大量的中間變量，因此大部分同學(xué)的選擇就是將兩條路徑重新計(jì)算，省時(shí)省力。畢竟有時(shí)候選擇比努力重要得多。

不過(guò)小編當(dāng)然不能退縮，因此今天就來(lái)講講鄰居解的時(shí)間窗如何去除計(jì)算冗余。

首先我們來(lái)看移除一個(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)在問(wèn)題來(lái)了：對(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)樵绲叫枰却绻谠鹊穆窂街校囕v早到了，那么車輛的服務(wù)時(shí)間開始時(shí)間會(huì)重置到客戶的開始時(shí)間窗，在移除一個(gè)客戶后，那么車輛在新的路徑中肯定會(huì)比之前的更早到達(dá)。總之，新路徑中該客戶處的開始服務(wù)時(shí)間就是客戶的開始時(shí)間窗，與原路徑保持一致，該客戶以及后面所有的都無(wú)需更新了。

再來(lái)看看插入一個(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)樵绲叫枰却绻谠鹊穆窂街校囕v早到了，那么車輛的服務(wù)時(shí)間開始時(shí)間會(huì)重置到客戶的開始時(shí)間窗，在插入一個(gè)客戶后，那么車輛在新的路徑中肯定會(huì)比之前的更晚到達(dá)，如果新路徑中車輛到達(dá)客戶的時(shí)間點(diǎn)仍然小于等于客戶的開始時(shí)間窗，那么該客戶以及后面所有的都無(wú)需更新了。

3 編程實(shí)現(xiàn)

當(dāng)然了，還是得放一下代碼，因?yàn)樵蹅兪菍?shí)干派，不吹牛皮不煲雞湯。對(duì)于時(shí)間窗，每個(gè)客戶節(jié)點(diǎn)還是需要維護(hù)一些中間變量的，難點(diǎn)就在于如何正確無(wú)誤的維護(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)?0?:?variation;

???????//?if?there?is?a?variation?update?the?nodes?after?too
???????int?i?=?position?+?1;
???????while?(variation?!=?0?&&?i??????????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)?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)?0?:?varCost.waitingTime;
??varCost.twViol?=?Math.abs(varCost.twViol)?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)?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??????????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)?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)?0?:?varCost.waitingTime;
??varCost.twViol?=?Math.abs(varCost.twViol)?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)?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??????????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)?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)?0?:?varCost.waitingTime;
??varCost.twViol?=?Math.abs(varCost.twViol)?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

完整代碼我會(huì)再做一期文章講解的，因?yàn)檫@個(gè)寫得實(shí)在是太經(jīng)典了。來(lái)源是國(guó)外一個(gè)大學(xué)的一個(gè)課堂小組作業(yè)？嗯，就是你們上課上到一半老師突然說(shuō)咱們做一個(gè)課堂小作業(yè)吧，然后你開始抽出一張白紙開始寫字的那種課堂作業(yè)。不得不承認(rèn)，人家國(guó)外講課，還是比較注重實(shí)踐呀~

如何實(shí)現(xiàn)一個(gè)高效的啟發(fā)式算法?(VRPTW篇)