5
Tôi đang cố gắng triển khai thuật toán Clarke và Wright để xây dựng giải pháp VRP ban đầu. Dường như chạy đúng cách nhưng vì lý do nào đó chất lượng của giải pháp tôi nhận được không phải là mong đợi. Để có mô tả của thuật toán thấy hereBạn có thể giúp tôi thực hiện thuật toán Clarke và Wright của mình không?
Dưới đây là mã của tôi để tính toán các yếu tố tiết kiệm:
private void computeSavingsElements() {
for(int i = 0; i<vrp.getDimension(); i++) {
for(int j = 0; j < i; j++) {
double savingValue = vrp.distance(i, 0) + vrp.distance(0, j) - lamda * vrp.distance(i, j);
SavingsElement savingElement = new SavingsElement (i,j, savingValue);
savingsElements.add(savingElement);
}
}
Collections.sort(savingsElements); // sort in ascending order
Collections.reverse(savingsElements); // but we need descending order
}
Phương pháp này để xây dựng các giải pháp:
private void constructSolution() {
List<VRPNode> nodes = this.vrp.getNodesList();
VRPNode depot = this.vrp.getDepot();
double vehicleCapacity = this.vrp.getVehicleCapacity();
VRPSolution solution = new VRPSolution(vehicleCapacity, depot);
/*
* In the initial solution, each vehicle serves exactly one customer
*/
for (VRPNode customer:nodes) {
if (customer.getId()!=0) { // if not depot
VRPRoute route = new VRPRoute(vehicleCapacity, depot);
route.addCustomer(customer);
solution.addRoute(route);
route = null; // eliminate obsolete reference to free resources
}
}
//System.out.println("INITIAL SOLUTION: \n"+solution.toString());
int mergesCounter=0;
for (SavingsElement savingElement : this.savingsElements) {
if (savingElement.getSavingValue() > 0) { // If serving customers consecutively in a route is profitable
VRPNode i = this.vrp.getNode(savingElement.getNodeId1());
VRPNode j = this.vrp.getNode(savingElement.getNodeId2());
VRPRoute route1 = solution.routeWhereTheCustomerIsTheLastOne(i);
VRPRoute route2 = solution.routeWhereTheCustomerIsTheFirstOne(j);
if ((route1!=null) & (route2!=null)) {
if (route1.getDemand() + route2.getDemand() <= this.vrp.getVehicleCapacity()) { // if merge is feasible
/*
* Merge the two routes
*/
solution.mergeRoutes(route1, route2);
mergesCounter++;
}
}
}
}
//System.out.println("\n\nAfter "+mergesCounter+" Merges"+"\n"+solution.toString());
this.solutionConstructed = solution;
}
Và đối với các tuyến đường kết hợp:
public void mergeRoutes(VRPRoute a, VRPRoute b) {
/*
* Provided that feasibility check has already been performed
*/
List<VRPNode> customersFromRouteA = new LinkedList<VRPNode>(a.getCustomersInRoute());
List<VRPNode> customersFromRouteB = new LinkedList<VRPNode>(b.getCustomersInRoute());
/*
* Remove the old routes
*/
solutionRoutes.remove(a);
solutionRoutes.remove(b);
/*
* Construct a new merged route
*/
VRPRoute mergedRoute = new VRPRoute(vehicleCapacity,depot);
/*
* The new route has to serve all the customers
* both from route a and b
*/
for (VRPNode customerFromA: customersFromRouteA) {
mergedRoute.addCustomer(customerFromA);
}
for (VRPNode customerFromB: customersFromRouteB) {
mergedRoute.addCustomer(customerFromB);
}
addRoute(mergedRoute);
evaluateSolutionCost();
}
Có vẻ như tính toán e tiết kiệm một cách chính xác và hợp nhất các tuyến đường như nó cần. Nhưng chi phí của giải pháp xây dựng là quá nhiều. Ví dụ trong một trường hợp cho tôi nhận được 1220 trong khi nó phải được 820.