Shulou(Shulou.com)06/02 Report--

This article mainly introduces "how to achieve an efficient heuristic algorithm". In daily operation, I believe that many people have doubts about how to achieve an efficient heuristic algorithm. The editor consulted all kinds of data and sorted out simple and easy-to-use operation methods. I hope it will be helpful for you to answer the doubts about "how to achieve an efficient heuristic algorithm"! Next, please follow the editor to study!

1 calculation of time window

In fact, whether it is TSP or VRP, it is very easy to calculate the cost value of the neighbor solution. You just need to subtract the old edge from the value of the original solution and add the new edge. If you don't understand, please go back and take a good look at the contents of the last issue. However, with more time windows, the difficulty has increased by another order of magnitude.

Why is the time window difficult, because the order of the nodes is closely related to the time window, and the front nodes will affect the later nodes. In the classic VRPTW, it is stipulated that vehicles who arrive early must wait, and late arrival is not allowed (if late, the solution is not feasible). For any customer, the time window is, if the time point at which the vehicle arrives at the node is, then the start service time of the node is:

Because you have to wait to arrive early, you need to take the largest of the two. If the service time of the customer is, then the time when the vehicle leaves the customer is

Let's see, does it determine the time when the vehicle arrives at the next customer? If a subsequent customer is that the time required for the vehicle to drive along the side is, the time for the vehicle to arrive at the customer is:

Okay, now we're done with the principle. Let's talk about how to calculate the neighbor solution.

2 Fast update of neighbor solution

I'll take the previous diagram, and I won't say any more about the calculation of the path cost. I'll talk about the update of the time window here, because in the problem of VRPTW, the target value is generally the sum of the path cost and the time window violation. If the total amount of the time window violation of the solution is, obviously, it is a feasible solution. So how to calculate it?

The path that changes is and, to evaluate the time window of the neighbor solution, of course, the partners who have seen the previous issue will not recalculate the whole solution again. You can pick out the new sum separately, then calculate the path, and then subtract the path from the solution.

Because of the layer-by-layer correlation of the time window, it is still difficult for fast calculation, especially for the implementation of current coding, because there are a large number of intermediate variables to maintain. therefore, the choice of most students is to recalculate the two paths, saving time and effort. After all, sometimes choice is much more important than effort.

But of course, the editor can't back down, so today I'm going to talk about how the time window of the neighbor solution removes computational redundancy.

First, let's look at the scenario of removing a customer, and the following is formed after removing a customer between customer 11 and customer 17:

The change of the customer node will only affect the node time window after the node, so there is no need to recalculate the first half of the road section 0-> 15-> 12-> 11. Now the question is: do you need to update all the nodes on the second half of 17-> 7-> 0?

The answer is not necessarily. You only need to update the nodes that may change later. Then for the node, in the original path, the time when the vehicle arrives at the node is, if, the start time window of the node. Then in the new path, the node and subsequent nodes do not need to be updated.

As for why, because the early arrival requires waiting, if the vehicle arrives early in the original path, the service time start time of the vehicle will be reset to the customer's start time window, and after removing a customer, then the vehicle will certainly arrive in the new path earlier than the previous one. In short, the start time of the customer in the new path is the customer's start time window, which is consistent with the original path, and the customer and all that follow do not need to be updated.

Let's take a look at the scenario of inserting a customer:

I'm sure you don't have to worry about customers before 19. The update needs to start with the customer, update the time when the vehicle arrives at customer 19, and then customer 2, all the way to the end. Here is also the same as the above, there is a critical condition, after reaching this condition, you can jump out of the update. For the node, in the new path (note the difference from the above), the time when the vehicle arrives at the node is, if, the start time window of the node. Then in the new path, the node and subsequent nodes do not need to be updated.

Due to the need to wait for early arrival, if the vehicle arrives early in the original path, the service time start time of the vehicle will be reset to the customer's start time window, and after inserting a customer, then the vehicle will certainly arrive later in the new path than before, if the time point in the new path for the vehicle to arrive at the customer is still less than or equal to the customer's start time window, then the customer and all that follow need not be updated.

3 programming realization

Of course, we still have to put some code, because we are practical, do not brag, do not cook chicken soup. For the time window, each customer node still needs to maintain some intermediate variables, and the difficulty lies in how to maintain these intermediate variables correctly. The difficulty of writing redundant heuristics lies in debugging.

The first is to insert the code for a node:

/ * *

* 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

ITunes +

} / / 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

ITunes +

} / / 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

Then delete a customer's code:

/ * *

* 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

ITunes +

} / / 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 at this point, the study on "how to implement an efficient heuristic algorithm" is over, hoping to solve everyone's doubts. The collocation of theory and practice can better help you learn, go and try it! If you want to continue to learn more related knowledge, please continue to follow the website, the editor will continue to work hard to bring you more practical articles!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.