/** * 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;
// 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;
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;
// 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;
// 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;
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;
// 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;
// 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;
