From ad36264b0c99c983b91fbef0ea75e60d6bcf2934 Mon Sep 17 00:00:00 2001 From: Mitsuo Tokumori Date: Mon, 6 Jun 2022 21:26:50 -0500 Subject: Specify package: java in pom.xml --- back/aco-mdvrptw/.idea/.gitignore | 3 + back/aco-mdvrptw/.idea/compiler.xml | 13 ++ .../.idea/inspectionProfiles/Project_Default.xml | 12 ++ back/aco-mdvrptw/.idea/jarRepositories.xml | 20 ++ back/aco-mdvrptw/.idea/misc.xml | 14 ++ back/aco-mdvrptw/.idea/vcs.xml | 6 + back/aco-mdvrptw/.run/main.run.xml | 9 + .../com/odiparpack/acovrptw/Ant_colony_opt.java | 122 ++++++++++++ .../java/com/odiparpack/acovrptw/Build_tour.java | 218 +++++++++++++++++++++ .../java/com/odiparpack/acovrptw/Customer.java | 13 ++ .../java/com/odiparpack/acovrptw/Load_problem.java | 159 +++++++++++++++ .../main/java/com/odiparpack/acovrptw/Main.java | 32 +++ .../acovrptw/Nearest_neighbor_heuristic.java | 118 +++++++++++ .../main/java/com/odiparpack/acovrptw/Output.java | 116 +++++++++++ .../java/com/odiparpack/acovrptw/Pareto_check.java | 25 +++ back/odiparback/pom.xml | 2 + 16 files changed, 882 insertions(+) create mode 100644 back/aco-mdvrptw/.idea/.gitignore create mode 100644 back/aco-mdvrptw/.idea/compiler.xml create mode 100644 back/aco-mdvrptw/.idea/inspectionProfiles/Project_Default.xml create mode 100644 back/aco-mdvrptw/.idea/jarRepositories.xml create mode 100644 back/aco-mdvrptw/.idea/misc.xml create mode 100644 back/aco-mdvrptw/.idea/vcs.xml create mode 100644 back/aco-mdvrptw/.run/main.run.xml create mode 100644 back/aco-mdvrptw/src/main/java/com/odiparpack/acovrptw/Ant_colony_opt.java create mode 100644 back/aco-mdvrptw/src/main/java/com/odiparpack/acovrptw/Build_tour.java create mode 100644 back/aco-mdvrptw/src/main/java/com/odiparpack/acovrptw/Customer.java create mode 100644 back/aco-mdvrptw/src/main/java/com/odiparpack/acovrptw/Load_problem.java create mode 100644 back/aco-mdvrptw/src/main/java/com/odiparpack/acovrptw/Main.java create mode 100644 back/aco-mdvrptw/src/main/java/com/odiparpack/acovrptw/Nearest_neighbor_heuristic.java create mode 100644 back/aco-mdvrptw/src/main/java/com/odiparpack/acovrptw/Output.java create mode 100644 back/aco-mdvrptw/src/main/java/com/odiparpack/acovrptw/Pareto_check.java diff --git a/back/aco-mdvrptw/.idea/.gitignore b/back/aco-mdvrptw/.idea/.gitignore new file mode 100644 index 0000000..26d3352 --- /dev/null +++ b/back/aco-mdvrptw/.idea/.gitignore @@ -0,0 +1,3 @@ +# Default ignored files +/shelf/ +/workspace.xml diff --git a/back/aco-mdvrptw/.idea/compiler.xml b/back/aco-mdvrptw/.idea/compiler.xml new file mode 100644 index 0000000..ab69004 --- /dev/null +++ b/back/aco-mdvrptw/.idea/compiler.xml @@ -0,0 +1,13 @@ + + + + + + + + + + + + + \ No newline at end of file diff --git a/back/aco-mdvrptw/.idea/inspectionProfiles/Project_Default.xml b/back/aco-mdvrptw/.idea/inspectionProfiles/Project_Default.xml new file mode 100644 index 0000000..09dbac8 --- /dev/null +++ b/back/aco-mdvrptw/.idea/inspectionProfiles/Project_Default.xml @@ -0,0 +1,12 @@ + + + + \ No newline at end of file diff --git a/back/aco-mdvrptw/.idea/jarRepositories.xml b/back/aco-mdvrptw/.idea/jarRepositories.xml new file mode 100644 index 0000000..712ab9d --- /dev/null +++ b/back/aco-mdvrptw/.idea/jarRepositories.xml @@ -0,0 +1,20 @@ + + + + + + + + + + + \ No newline at end of file diff --git a/back/aco-mdvrptw/.idea/misc.xml b/back/aco-mdvrptw/.idea/misc.xml new file mode 100644 index 0000000..82dbec8 --- /dev/null +++ b/back/aco-mdvrptw/.idea/misc.xml @@ -0,0 +1,14 @@ + + + + + + + + + + \ No newline at end of file diff --git a/back/aco-mdvrptw/.idea/vcs.xml b/back/aco-mdvrptw/.idea/vcs.xml new file mode 100644 index 0000000..b2bdec2 --- /dev/null +++ b/back/aco-mdvrptw/.idea/vcs.xml @@ -0,0 +1,6 @@ + + + + + + \ No newline at end of file diff --git a/back/aco-mdvrptw/.run/main.run.xml b/back/aco-mdvrptw/.run/main.run.xml new file mode 100644 index 0000000..1b28a52 --- /dev/null +++ b/back/aco-mdvrptw/.run/main.run.xml @@ -0,0 +1,9 @@ + + + + \ No newline at end of file diff --git a/back/aco-mdvrptw/src/main/java/com/odiparpack/acovrptw/Ant_colony_opt.java b/back/aco-mdvrptw/src/main/java/com/odiparpack/acovrptw/Ant_colony_opt.java new file mode 100644 index 0000000..a353d44 --- /dev/null +++ b/back/aco-mdvrptw/src/main/java/com/odiparpack/acovrptw/Ant_colony_opt.java @@ -0,0 +1,122 @@ +package com.odiparpack.acovrptw; + +import java.util.ArrayList; +import java.util.List; + + +public class Ant_colony_opt { + List pareto_sols = new ArrayList(); + List min_vehinum_tracker = new ArrayList(); + List min_distance_tracker = new ArrayList(); + + public static Ant_colony_opt ant_main(Load_problem problem, long start){ + Ant_colony_opt aco = new Ant_colony_opt(); + List> tau = new ArrayList>(); //tau = pheromone matrix + + //Initialize solution and pheromone + Nearest_neighbor_heuristic ini_sol = new Nearest_neighbor_heuristic(); + ini_sol = Nearest_neighbor_heuristic.nnh(problem); //initial solution which is perfectly meet constrains + double tau_0 = 1 / (ini_sol.n * ini_sol.J_nnh); //initial pheromone + for (int i=0; i phe_mat = new ArrayList(); + for (int j=0; j problem.time*1000) return aco; + + + for (int i=1; i<=problem.ant_num; i++) { + Build_tour solution = new Build_tour(); //ant i create a solution + solution = Build_tour.buld_tour(problem, tau, fix_tau_0); + if (aco.pareto_sols.size() == 0) aco.pareto_sols.add(solution); + if (Pareto_check.check(aco.pareto_sols, solution) == true && aco.pareto_sols.size() != 0) { //the case where the solution is in pareto solutions + List dominated_sols_ind = new ArrayList(Pareto_check.rm_ind(aco.pareto_sols, solution)); + for (int j=0; j tau_0) { //pareto solutions are better than before + improve_check = 0; + tau_0 = tau_0t; //update tau_0 + System.out.println("better solution was found"); + } + + else { //pareto solutions are not better than before (global update) + improve_check = improve_check + 1; + if (improve_check >= problem.improve) { + return aco; + /* + for (int i=0; i> route = new ArrayList>(); + List capacity = new ArrayList(); + List distance = new ArrayList(); + int n; //the number of customers and depots + double J=0.0; //J_nnh is total distance (without considering waiting time) + + public static Build_tour buld_tour(Load_problem problem, List> tau, double tau_0){ + Build_tour sol = new Build_tour(); + List unsearved_customers = new ArrayList(); //customers have not already served by a vehicle + List route_ = new ArrayList(Arrays.asList(0)); + sol.route.add(route_); + sol.distance.add(0.0); + sol.capacity.add(0); + for (int i=1; i prob = new ArrayList(); + double prob_denom = 0.0; //denominator of probability + List prob_nume = new ArrayList(); //numerator of probability + List nu_L = new ArrayList(); //the formula considered time window + switch(counter) { + case 2: //construct a new route (the route was finished constructing) + List route_1 = new ArrayList(Arrays.asList(0)); + sol.route.add(route_1); //start from depot + sol.distance.add(0.0); + sol.capacity.add(0); + last_vehicle_ind = sol.route.size()-1; //last_vehicle_ind was changed because the new route was created + + //search customers do not violate constrains + List meet_const_customer = new ArrayList(); + for (int i = 0; i < unsearved_customers.size(); i++) { + if (sol.distance.get(sol.distance.size()-1) + problem.dist.get(last_customer).get(unsearved_customers.get(i)) <= problem.customer.get(unsearved_customers.get(i)).due_time) { //meet time constrain + meet_const_customer.add(unsearved_customers.get(i)); + } + } + + //calculate and nu_L (array) + for (int i=0; i prob_tmp = new ArrayList(prob); + Collections.sort(prob); + for (int i=0; i rnd.nextDouble()) { + index = prob_tmp.indexOf(prob.get(i)); + break; + } + } + //the next customer is added to the route + int next = meet_const_customer.get(index); + sol.capacity.set(sol.capacity.size()-1, sol.capacity.get(last_vehicle_ind) + problem.customer.get(next).demand); + if (problem.dist.get(0).get(next) + sol.distance.get(sol.distance.size()-1) < problem.customer.get(next).ready_time) { + sol.distance.set(sol.distance.size()-1, (double) (problem.customer.get(next).ready_time + problem.customer.get(next).service_time)); + } + else sol.distance.set(sol.distance.size()-1, problem.dist.get(0).get(next) + problem.customer.get(next).service_time); + sol.route.get(last_vehicle_ind).add(next); + unsearved_customers.remove((Integer)next); + //the ant drop pheromone as tracking + tau.get(0).set(next, (1.0-problem.rho) * tau.get(0).get(next) + problem.rho * tau_0); + tau.get(next).set(0, tau.get(0).get(next)); + } + + break; + + default: //search next customer to be ridden + //search customers do not violate constrains + meet_const_customer = new ArrayList(); + for (int i = 0; i < unsearved_customers.size(); i++) { //search nearest route from customer i + if (sol.distance.get(sol.distance.size()-1) + problem.dist.get(last_customer).get(unsearved_customers.get(i)) <= problem.customer.get(unsearved_customers.get(i)).due_time) { //meet time constrain + if (sol.capacity.get(sol.capacity.size()-1) + problem.customer.get(unsearved_customers.get(i)).demand <= problem.max_capacity) { //meet capacity constrain + meet_const_customer.add(unsearved_customers.get(i)); + } + } + } + + switch(meet_const_customer.size()) { + case 0: //there is no customer meets constrains + //go back to depot + sol.route.get(last_vehicle_ind).add(0); + sol.distance.set(sol.distance.size()-1, sol.distance.get(sol.distance.size()-1) + problem.dist.get(last_customer).get(0)); + break; + + default: //there are customers meet constrains + //calculate and nu_L (array) + for (int i=0; i prob_tmp = new ArrayList(prob); + Collections.sort(prob); + for (int i=0; i rnd.nextDouble()) { + index = prob_tmp.indexOf(prob.get(i)); + break; + } + } + + //the next customer is added to the route + int next = meet_const_customer.get(index); + sol.capacity.set(sol.capacity.size()-1, sol.capacity.get(last_vehicle_ind) + problem.customer.get(next).demand); + if (problem.dist.get(last_customer).get(next) + sol.distance.get(sol.distance.size()-1) < problem.customer.get(next).ready_time) { + sol.distance.set(sol.distance.size()-1, (double) (problem.customer.get(next).ready_time + problem.customer.get(next).service_time)); + } + else sol.distance.set(sol.distance.size()-1, sol.distance.get(last_vehicle_ind) + problem.dist.get(last_customer).get(next) + problem.customer.get(next).service_time); + sol.route.get(last_vehicle_ind).add(next); + unsearved_customers.remove((Integer)next); + //the ant drop pheromone as tracking + tau.get(last_customer).set(next, (1.0-problem.rho) * tau.get(last_customer).get(next) + problem.rho * tau_0); + tau.get(next).set(last_customer, tau.get(last_customer).get(next)); + } + } + } + } + sol.route.get(sol.route.size()-1).add(0); + sol.n = sol.route.size() + problem.customer.size() - 1; + for (int i=0; i customer = new ArrayList(); + List> dist = new ArrayList>(); + + String benchmark; + String experiment; + + //constrain information + int max_vehi_num; + int max_capacity; + + //parameters used in ACO + int ant_num; + float beta; //the weight in the probability formula + float q0; //the probability to choose next node j + float alpha; //parameter of evaporation (global update) + float rho; //parameter of evaporation (local update) + + //ending criteria + int iteration; + float time; + int improve; + + //the number of iteration + String ite_num; + + public static Load_problem load_problem(String[] args){ + // this method loads the parameters used in ACO and information in + // VRPTW (coordinates, distances and so on) + Load_problem problem = new Load_problem(); + + problem.ite_num = args[2]; + + //args[0] = name of benchmark + String txt = ".txt"; + String path = "/Users/shimizukengo/Desktop/important/study_abroad/research/In/"; + String benchmark_path = path + args[0] + txt; + problem.benchmark = args[0]; + + //load benchmark information + String inFilePath = benchmark_path; + try(FileInputStream f = new FileInputStream(inFilePath);) { + InputStreamReader fReader = new InputStreamReader(f,"UTF8"); + BufferedReader bufferedReader = new BufferedReader(fReader); + String data; + int count = 0; + int count_customer = 0; + List line1 = new ArrayList(); + while ((data = bufferedReader.readLine()) != null) { // read lines one by one + line1.clear(); + data = data.replace("\n",""); + data = data.replace("\r",""); + String[] datas = data.split(" "); + for (int i=0; i 8){ + problem.customer.add(new Customer(Integer.parseInt(line1.get(1)), Integer.parseInt(line1.get(2)))); + problem.customer.get(count_customer).demand = Integer.parseInt(line1.get(3)); + problem.customer.get(count_customer).ready_time = Integer.parseInt(line1.get(4)); + problem.customer.get(count_customer).due_time = Integer.parseInt(line1.get(5)); + problem.customer.get(count_customer).service_time = Integer.parseInt(line1.get(6)); + count_customer += 1; + } + count += 1; + } + } catch (IOException e) { + e.printStackTrace(); + } + + //args[1] = parameters + String txt2 = ".txt"; + String path2 = "/Users/shimizukengo/Desktop/important/study_abroad/research/ACO_VRPTW/src/parameter/"; + String parafilename_path2 = path2 + args[1] + txt2; + String inFilePath2 = parafilename_path2; + try(FileInputStream f2 = new FileInputStream(inFilePath2);) { + InputStreamReader f2Reader = new InputStreamReader(f2,"UTF8"); + BufferedReader bufferedReader2 = new BufferedReader(f2Reader); + String data; + int count = 0; + while ((data = bufferedReader2.readLine()) != null) { // read lines one by one + data = data.replace("\n",""); + data = data.replace("\r",""); + String[] datas = data.split(" "); + if (count == 0){ + problem.ant_num = Integer.parseInt(datas[2]); + } + + if (count == 1){ + problem.iteration = Integer.parseInt(datas[2]); + } + + if (count == 2){ + problem.beta = Float.parseFloat(datas[2]); + } + + if (count == 3){ + problem.q0 = Float.parseFloat(datas[2]); + } + + if (count == 4){ + problem.alpha = Float.parseFloat(datas[2]); + } + + if (count == 5){ + problem.rho = Float.parseFloat(datas[2]); + } + + if (count == 6){ + problem.time = Float.parseFloat(datas[2]); + } + + if (count == 7){ + problem.improve = Integer.parseInt(datas[2]); + } + + if (count == 8){ + problem.experiment = String.valueOf(datas[2]); + } + + count += 1; + } + } catch (IOException e) { + e.printStackTrace(); + } + for (int i=0; i dist_ = new ArrayList(); + for (int j=0; j> route = new ArrayList>(); + List capacity = new ArrayList(); + List distance = new ArrayList(); + double n; //the number of customers and depots + double J_nnh; //J_nnh is total traveling time (without considering waiting time) + + public static Nearest_neighbor_heuristic nnh(Load_problem problem){ + Nearest_neighbor_heuristic ini_sol = new Nearest_neighbor_heuristic(); + List unsearved_customers = new ArrayList(); //customers have not already served by a vehicle + List route_ = new ArrayList(Arrays.asList(0)); + ini_sol.route.add(route_); + ini_sol.distance.add(0.0); + ini_sol.capacity.add(0); + for (int i=1; i route_1 = new ArrayList(Arrays.asList(0)); + ini_sol.route.add(route_1); //start from depot + ini_sol.distance.add(0.0); + ini_sol.capacity.add(0); + last_vehicle_ind = ini_sol.route.size()-1; //last_vehicle_ind was changed because the new route was created + + //search customers do not violate constrains + List meet_const_customer = new ArrayList(); + for (int i = 0; i < unsearved_customers.size(); i++) { + if (ini_sol.distance.get(ini_sol.distance.size()-1) + problem.dist.get(last_customer).get(unsearved_customers.get(i)) <= problem.customer.get(unsearved_customers.get(i)).due_time) { //meet time constrain + meet_const_customer.add(unsearved_customers.get(i)); + } + } + + //find nearest route from depot from meet_const_customer + double min_dist = problem.dist.get(0).get(meet_const_customer.get(0)); + int index = meet_const_customer.get(0); + for (int i = 1; i < meet_const_customer.size(); i++) { //search nearest route from depot + double x = problem.dist.get(0).get(meet_const_customer.get(i)); + if (x < min_dist) { + min_dist = x; + index = meet_const_customer.get(i); + } + } + //find nearest route from depot from meet_const_customer + + //first customer is added to route and capacity and distance and remove from unsearved_customers + ini_sol.capacity.set(ini_sol.capacity.size()-1, ini_sol.capacity.get(last_vehicle_ind) + problem.customer.get(index).demand); + if (problem.dist.get(0).get(index) + ini_sol.distance.get(ini_sol.distance.size()-1) < problem.customer.get(index).ready_time) { + ini_sol.distance.set(ini_sol.distance.size()-1, (double) (problem.customer.get(index).ready_time + problem.customer.get(index).service_time)); + } + else ini_sol.distance.set(ini_sol.distance.size()-1, problem.dist.get(0).get(index) + problem.customer.get(index).service_time); + ini_sol.route.get(last_vehicle_ind).add(index); + unsearved_customers.remove((Integer)index); + break; + + default: //search next customer to be ridden + //search customers do not violate constrains + meet_const_customer = new ArrayList(); + for (int i = 0; i < unsearved_customers.size(); i++) { //search nearest route from customer i + if (ini_sol.distance.get(ini_sol.distance.size()-1) + problem.dist.get(last_customer).get(unsearved_customers.get(i)) <= problem.customer.get(unsearved_customers.get(i)).due_time) { //meet time constrain + if (ini_sol.capacity.get(ini_sol.capacity.size()-1) + problem.customer.get(unsearved_customers.get(i)).demand <= problem.max_capacity) { //meet capacity constrain + meet_const_customer.add(unsearved_customers.get(i)); + } + } + } + + switch(meet_const_customer.size()) { + case 0: //there is no customer meets constrains + //go back to depot + ini_sol.route.get(last_vehicle_ind).add(0); + ini_sol.distance.set(ini_sol.distance.size()-1, ini_sol.distance.get(ini_sol.distance.size()-1) + problem.dist.get(last_customer).get(0)); + break; + + default: //there are customers meet constrains + + //find nearest route from last_customer from meet_const_customer + min_dist = problem.dist.get(last_customer).get(meet_const_customer.get(0)); + index = meet_const_customer.get(0); + for (int i = 1; i < meet_const_customer.size(); i++) { + double x = problem.dist.get(0).get(meet_const_customer.get(i)); + if (x < min_dist) { + min_dist = x; + index = meet_const_customer.get(i); + } + } + //find nearest route from last_customer from meet_const_customer + + //customer is added to route and capacity and distance and remove from unsearved_customers + ini_sol.capacity.set(ini_sol.capacity.size()-1, ini_sol.capacity.get(ini_sol.capacity.size()-1) + problem.customer.get(index).demand); + if (problem.dist.get(last_customer).get(index) + ini_sol.distance.get(ini_sol.distance.size()-1) < problem.customer.get(index).ready_time) { + ini_sol.distance.set(ini_sol.distance.size()-1, (double) (problem.customer.get(index).ready_time + problem.customer.get(index).service_time)); + } + else ini_sol.distance.set(ini_sol.distance.size()-1, ini_sol.distance.get(ini_sol.distance.size()-1) + problem.dist.get(last_customer).get(index) + problem.customer.get(index).service_time); + ini_sol.route.get(last_vehicle_ind).add(index); + unsearved_customers.remove((Integer)index); + } + } + } + ini_sol.route.get(ini_sol.route.size()-1).add(0); + ini_sol.n = ini_sol.route.size() + problem.customer.size() - 1; + for (int i=0; i solutions.pareto_sols.get(1).route.size()) { + path = "/Users/shimizukengo/Desktop/important/study_abroad/research/ACO_VRPTW/outputs/"+problem.experiment+"/"+make_filename+"/"+make_filename+"_"+problem.ite_num+"_position1.dat"; + count = count + 1; + } + + } + if (count == 1) path = "/Users/shimizukengo/Desktop/important/study_abroad/research/ACO_VRPTW/outputs/"+problem.experiment+"/"+make_filename+"/"+make_filename+"_"+problem.ite_num+"_position0.dat"; + File newfile = new File(path); + try{ + newfile.createNewFile(); + FileWriter filewriter = new FileWriter(newfile); + + //write comment in .dat file + filewriter.write("#computetime:"+String.valueOf(e_s)+"[ms]\tvehi_num:"+String.valueOf(solutions.pareto_sols.get(p).route.size())+"\tdistance:"+String.valueOf(solutions.pareto_sols.get(p).J)+"\n"); + filewriter.write("#ant_num:"+String.valueOf(problem.ant_num)+"\titeration:"+String.valueOf(problem.iteration)+"\tbeta:"+String.valueOf(problem.beta)+"\tq0:"+String.valueOf(problem.q0)+"\talpha:"+String.valueOf(problem.alpha)+"\trho:"+String.valueOf(problem.rho)+"\n"); + filewriter.write("#position x\tposition y\n"); + + + for (int i=0; i pareto_sols, Build_tour solution){ + for(int i=0; i= pareto_sols.get(i).n && solution.J >= pareto_sols.get(i).J) { + return false; //new solution is not a pareto solution + } + } + return true; //new solution is a pareto solution + } + + public static List rm_ind(List pareto_sols, Build_tour solution){ + List dominated_sols_ind = new ArrayList(); + for(int i=0; iodiparback 0.0.1-SNAPSHOT odiparback + + jar Demo project for Spring Boot 11 -- cgit v1.2.3