5
私はClarkeとWrightアルゴリズムを実装して、初期VRPソリューションを構築しようとしています。 これは正しく動作しているようですが、何らかの理由で私が得るソリューションの品質が期待通りではありません。ソリューション構築するClarke and Wrightアルゴリズムの実装を手伝ってもらえますか？
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
}
方法： アルゴリズムの説明はhere
を参照してくださいここでは貯蓄要素を計算するために私のコードです
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;
}
をし、ルートのためにマージします。
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();
}
節約を正しく行い、必要に応じてルートをマージします。しかし、構築されたソリューションのコストは高すぎます。指定されたインスタンスの例では、私はそれが820