diff options
Diffstat (limited to 'back/aco-mdvrptw/src')
8 files changed, 803 insertions, 0 deletions
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<Build_tour> pareto_sols = new ArrayList<Build_tour>(); + List<Integer> min_vehinum_tracker = new ArrayList<Integer>(); + List<Double> min_distance_tracker = new ArrayList<Double>(); + + public static Ant_colony_opt ant_main(Load_problem problem, long start){ + Ant_colony_opt aco = new Ant_colony_opt(); + List<List<Double>> tau = new ArrayList<List<Double>>(); //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<problem.customer.size(); i++) { + List<Double> phe_mat = new ArrayList<Double>(); + for (int j=0; j<problem.customer.size(); j++) { + phe_mat.add(0.0); + } + tau.add(phe_mat); + } + for (int i=0; i<problem.customer.size()-1; i++) { + for (int j=i+1; j<problem.customer.size(); j++) { + tau.get(i).set(j, tau_0); + tau.get(j).set(i, tau.get(i).get(j)); + } + } + //Initialize solution and pheromone + + int improve_check = 0; + double fix_tau_0 = tau_0; + for (int criteria=0; criteria<problem.iteration; criteria++) { + long end = System.currentTimeMillis(); + long e_s = end - start; + if (e_s > 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<Build_tour> dominated_sols_ind = new ArrayList<Build_tour>(Pareto_check.rm_ind(aco.pareto_sols, solution)); + for (int j=0; j<dominated_sols_ind.size(); j++) aco.pareto_sols.remove(dominated_sols_ind.get(j)); //remove dominated solutions from aco.pareto_sols + aco.pareto_sols.add(solution); //new solution is added to pareto_sols + } + } + + double P_n = 0.0; + double P_J = 0.0; + for (int i=0; i<aco.pareto_sols.size(); i++) { + P_n = P_n + aco.pareto_sols.get(i).n; + P_J = P_J + aco.pareto_sols.get(i).J; + } + P_n = P_n / aco.pareto_sols.size(); //the average value in pareto solutions + P_J = P_J / aco.pareto_sols.size(); //the average value in pareto solutions + + double tau_0t = 1 / (P_n * P_J); //calculate tau_0t + if (tau_0t > 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<problem.customer.size(); i++) { + for (int j=i+1; j<problem.customer.size(); j++) { + tau.get(i).set(j, tau_0); + tau.get(j).set(i, tau_0); + } + } + */ + } + + //evaporate pheromone + for (int i=0; i<problem.customer.size(); i++) { + for (int j=i+1; j<problem.customer.size(); j++) { + tau.get(i).set(j, (1.0-problem.alpha) * tau.get(i).get(j)); + tau.get(j).set(i, tau.get(i).get(j)); + } + } + + + //global pheromon update + for (int p=0; p<aco.pareto_sols.size(); p++) { + for (int vehi=0; vehi<aco.pareto_sols.get(p).route.size(); vehi++) { + for (int i=0; i<aco.pareto_sols.get(p).route.get(vehi).size()-1; i++) { + int cus_i = aco.pareto_sols.get(p).route.get(vehi).get(i); + int cus_j = aco.pareto_sols.get(p).route.get(vehi).get(i+1); + tau.get(cus_i).set(cus_j, tau.get(cus_i).get(cus_j) + problem.alpha / P_J); + tau.get(cus_j).set(cus_i, tau.get(cus_i).get(cus_j)); + } + } + } + + + } + + //tracking minimum vehicle number, total time and total distance + int min_vehinum = aco.pareto_sols.get(0).n - (problem.customer.size() - 1); + double min_distance = aco.pareto_sols.get(0).J; + for (int i=1; i<aco.pareto_sols.size(); i++) { + min_vehinum = Math.min(min_vehinum, aco.pareto_sols.get(i).n - (problem.customer.size() - 1)); + min_distance = Math.min(min_distance, aco.pareto_sols.get(i).J); + } + + aco.min_vehinum_tracker.add(min_vehinum); + aco.min_distance_tracker.add(min_distance); + } + + return aco; + } +} diff --git a/back/aco-mdvrptw/src/main/java/com/odiparpack/acovrptw/Build_tour.java b/back/aco-mdvrptw/src/main/java/com/odiparpack/acovrptw/Build_tour.java new file mode 100644 index 0000000..7422724 --- /dev/null +++ b/back/aco-mdvrptw/src/main/java/com/odiparpack/acovrptw/Build_tour.java @@ -0,0 +1,218 @@ +package com.odiparpack.acovrptw; + +import java.util.ArrayList; +import java.util.Arrays; +import java.util.Collections; +import java.util.List; +import java.util.Random; +import java.lang.Math; + +public class Build_tour { + List<List<Integer>> route = new ArrayList<List<Integer>>(); + List<Integer> capacity = new ArrayList<Integer>(); + List<Double> distance = new ArrayList<Double>(); + 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<List<Double>> tau, double tau_0){ + Build_tour sol = new Build_tour(); + List<Integer> unsearved_customers = new ArrayList<Integer>(); //customers have not already served by a vehicle + List<Integer> route_ = new ArrayList<Integer>(Arrays.asList(0)); + sol.route.add(route_); + sol.distance.add(0.0); + sol.capacity.add(0); + for (int i=1; i<problem.customer.size(); i++) unsearved_customers.add(i); + long seed = Runtime.getRuntime().freeMemory(); + Random rnd = new Random(seed); + + while(unsearved_customers.size() != 0) { + int last_vehicle_ind = sol.route.size()-1; + int last_customer = sol.route.get(last_vehicle_ind).get(sol.route.get(last_vehicle_ind).size()-1); + int counter = 0; + for (int i=0; i<sol.route.get(last_vehicle_ind).size(); i++) if (sol.route.get(last_vehicle_ind).get(i) == 0) counter = counter + 1; //check if the route is finished or not + List<Double> prob = new ArrayList<Double>(); + double prob_denom = 0.0; //denominator of probability + List<Double> prob_nume = new ArrayList<Double>(); //numerator of probability + List<Double> nu_L = new ArrayList<Double>(); //the formula considered time window + switch(counter) { + case 2: //construct a new route (the route was finished constructing) + List<Integer> route_1 = new ArrayList<Integer>(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<Integer> meet_const_customer = new ArrayList<Integer>(); + 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<meet_const_customer.size(); i++) { + double ct_j = Math.max(problem.dist.get(0).get(meet_const_customer.get(i)),problem.customer.get(meet_const_customer.get(i)).ready_time); + double delta_tij = ct_j; + double d_ij = Math.max(1.0, delta_tij * problem.customer.get(meet_const_customer.get(i)).due_time); + nu_L.add(1 / d_ij); + } + //calculate the numerator of the probability and the power of nu_L + for(int i=0; i<nu_L.size(); i++) { + nu_L.set(i, Math.pow(nu_L.get(i), problem.beta)); + prob_nume.add(tau.get(0).get(meet_const_customer.get(i)) * nu_L.get(i)); + } + //calculate the denominator of the probability and search max value in probability + double max_prob_nume = prob_nume.get(0); + int index = 0; + for (int i=0; i<nu_L.size(); i++) { + prob_denom = prob_denom + prob_nume.get(i); + if (max_prob_nume < prob_nume.get(i)) { + max_prob_nume = prob_nume.get(i); + index = i; + } + } + //calculate the probabilities + for (int i=0; i<nu_L.size(); i++) prob.add(prob_nume.get(i)/prob_denom); + + if (rnd.nextDouble() < problem.q0) { //the case where the node j is chosen as next customer within probability q0 + 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)); + } + + else {//the case where the node j is chosen as next customer with probabilities + //choose the next node j at probabilities + double prob_sum = 0.0; + index = 0; + List<Double> prob_tmp = new ArrayList<Double>(prob); + Collections.sort(prob); + for (int i=0; i<prob.size(); i++) { + prob_sum = prob_sum + prob.get(i); + if (prob_sum > 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<Integer>(); + 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<meet_const_customer.size(); i++) { + double ct_j = Math.max(sol.distance.get(last_vehicle_ind) + problem.dist.get(last_customer).get(meet_const_customer.get(i)), problem.customer.get(meet_const_customer.get(i)).ready_time); + double delta_tij = ct_j - sol.distance.get(last_vehicle_ind); + double d_ij = Math.max(1.0, delta_tij * (problem.customer.get(meet_const_customer.get(i)).due_time - sol.distance.get(last_vehicle_ind))); + nu_L.add(1 / d_ij); + } + //calculate the numerator of the probability and the power of nu_L + for(int i=0; i<nu_L.size(); i++) { + nu_L.set(i, Math.pow(nu_L.get(i), problem.beta)); + prob_nume.add(tau.get(last_customer).get(meet_const_customer.get(i)) * nu_L.get(i)); + } + //calculate the denominator of the probability + max_prob_nume = prob_nume.get(0); + index = 0; + for (int i=0; i<nu_L.size(); i++) { + prob_denom = prob_denom + prob_nume.get(i); + if (max_prob_nume < prob_nume.get(i)) { + max_prob_nume = prob_nume.get(i); + index = i; + } + } + //calculate the probabilities + for (int i=0; i<nu_L.size(); i++) prob.add(prob_nume.get(i)/prob_denom); + + if (rnd.nextDouble() < problem.q0) { //the case where the node j is chosen as next customer within probability q0 + 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)); + } + + else {//the case where the node j is chosen as next customer with probabilities + //choose the next node j at probabilities + double prob_sum = 0.0; + index = 0; + List<Double> prob_tmp = new ArrayList<Double>(prob); + Collections.sort(prob); + for (int i=0; i<prob.size(); i++) { + prob_sum = prob_sum + prob.get(i); + if (prob_sum > 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<sol.route.size(); i++) { + for (int j=0; j<sol.route.get(i).size()-1; j++) { + sol.J = sol.J + problem.dist.get(sol.route.get(i).get(j)).get(sol.route.get(i).get(j+1)); + } + } + return sol; + } +}
\ No newline at end of file diff --git a/back/aco-mdvrptw/src/main/java/com/odiparpack/acovrptw/Customer.java b/back/aco-mdvrptw/src/main/java/com/odiparpack/acovrptw/Customer.java new file mode 100644 index 0000000..e47d6cf --- /dev/null +++ b/back/aco-mdvrptw/src/main/java/com/odiparpack/acovrptw/Customer.java @@ -0,0 +1,13 @@ +package com.odiparpack.acovrptw; + +public class Customer{ + int[] pos = new int[2]; + int demand; + int ready_time; + int due_time; + int service_time; + Customer(int x, int y){ + this.pos[0] = x; + this.pos[1] = y; + } +} diff --git a/back/aco-mdvrptw/src/main/java/com/odiparpack/acovrptw/Load_problem.java b/back/aco-mdvrptw/src/main/java/com/odiparpack/acovrptw/Load_problem.java new file mode 100644 index 0000000..4958ddc --- /dev/null +++ b/back/aco-mdvrptw/src/main/java/com/odiparpack/acovrptw/Load_problem.java @@ -0,0 +1,159 @@ +package com.odiparpack.acovrptw; + +import java.io.FileInputStream; +import java.io.IOException; +import java.io.InputStreamReader; +import java.io.BufferedReader; +import java.util.ArrayList; +import java.util.List; + +public class Load_problem{ + List<Customer> customer = new ArrayList<Customer>(); + List<List<Double>> dist = new ArrayList<List<Double>>(); + + 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<String> line1 = new ArrayList<String>(); + 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<datas.length; i++){ + if (datas[i].isEmpty() != true){ + line1.add(datas[i]); + } + } + if (count == 4){ + problem.max_vehi_num = Integer.parseInt(line1.get(0)); + problem.max_capacity = Integer.parseInt(line1.get(1)); + } + if (count > 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<problem.customer.size(); i++) { + List<Double> dist_ = new ArrayList<Double>(); + for (int j=0; j<problem.customer.size(); j++) { + dist_.add(0.0); + } + problem.dist.add(dist_); + } + for (int i=0; i<problem.customer.size()-1; i++) { + for (int j=i+1; j<problem.customer.size(); j++) { + problem.dist.get(i).set(j, (double) Math.sqrt(Math.pow(problem.customer.get(i).pos[0]-problem.customer.get(j).pos[0],2) + Math.pow(problem.customer.get(i).pos[1]-problem.customer.get(j).pos[1],2))); + problem.dist.get(j).set(i, problem.dist.get(i).get(j)); + } + } + return problem; + } +} + + + diff --git a/back/aco-mdvrptw/src/main/java/com/odiparpack/acovrptw/Main.java b/back/aco-mdvrptw/src/main/java/com/odiparpack/acovrptw/Main.java new file mode 100644 index 0000000..d3ff898 --- /dev/null +++ b/back/aco-mdvrptw/src/main/java/com/odiparpack/acovrptw/Main.java @@ -0,0 +1,32 @@ +package com.odiparpack.acovrptw; + +/** + * How to use: + * Benchmark_filename Parameters_filename iteration_number + */ + +public class Main{ + public static void main(String[] args) { + + //load problem and parameters + Load_problem load = new Load_problem(); + load = Load_problem.load_problem(args); + + //time start + long start = System.currentTimeMillis(); + + //apply ACO + Ant_colony_opt solutions = new Ant_colony_opt(); + solutions = Ant_colony_opt.ant_main(load,start); + + //time end + long end = System.currentTimeMillis(); + long e_s = end - start; + + //output as .dat file + Output.output_minimum_transition(load, e_s, solutions); + Output.output_positions(load, e_s, solutions); + + System.out.println("fin"); + } +}
\ No newline at end of file diff --git a/back/aco-mdvrptw/src/main/java/com/odiparpack/acovrptw/Nearest_neighbor_heuristic.java b/back/aco-mdvrptw/src/main/java/com/odiparpack/acovrptw/Nearest_neighbor_heuristic.java new file mode 100644 index 0000000..d95c173 --- /dev/null +++ b/back/aco-mdvrptw/src/main/java/com/odiparpack/acovrptw/Nearest_neighbor_heuristic.java @@ -0,0 +1,118 @@ +package com.odiparpack.acovrptw; + +import java.util.ArrayList; +import java.util.Arrays; +import java.util.List; + +public class Nearest_neighbor_heuristic { + List<List<Integer>> route = new ArrayList<List<Integer>>(); + List<Integer> capacity = new ArrayList<Integer>(); + List<Double> distance = new ArrayList<Double>(); + 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<Integer> unsearved_customers = new ArrayList<Integer>(); //customers have not already served by a vehicle + List<Integer> route_ = new ArrayList<Integer>(Arrays.asList(0)); + ini_sol.route.add(route_); + ini_sol.distance.add(0.0); + ini_sol.capacity.add(0); + for (int i=1; i<problem.customer.size(); i++) unsearved_customers.add(i); + + while(unsearved_customers.size() != 0) { + int last_vehicle_ind = ini_sol.route.size()-1; + int last_customer = ini_sol.route.get(last_vehicle_ind).get(ini_sol.route.get(last_vehicle_ind).size()-1); + int counter = 0; + for (int i=0; i<ini_sol.route.get(last_vehicle_ind).size(); i++) if (ini_sol.route.get(last_vehicle_ind).get(i) == 0) counter = counter + 1; //check if the route is finished or not + switch(counter) { + case 2: //construct a new route (the route was finished constructing) + List<Integer> route_1 = new ArrayList<Integer>(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<Integer> meet_const_customer = new ArrayList<Integer>(); + 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<Integer>(); + 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<ini_sol.route.size(); i++) { + for (int j=0; j<ini_sol.route.get(i).size()-1; j++) { + ini_sol.J_nnh = ini_sol.J_nnh + problem.dist.get(ini_sol.route.get(i).get(j)).get(ini_sol.route.get(i).get(j+1)); + } + } + return ini_sol; + } +} diff --git a/back/aco-mdvrptw/src/main/java/com/odiparpack/acovrptw/Output.java b/back/aco-mdvrptw/src/main/java/com/odiparpack/acovrptw/Output.java new file mode 100644 index 0000000..93abe22 --- /dev/null +++ b/back/aco-mdvrptw/src/main/java/com/odiparpack/acovrptw/Output.java @@ -0,0 +1,116 @@ +package com.odiparpack.acovrptw; + +import java.io.File; +import java.io.FileWriter; +import java.io.IOException; +import java.nio.file.Files; +import java.nio.file.Path; +import java.nio.file.Paths; + +public class Output { + public static void output_minimum_transition(Load_problem problem, long e_s, Ant_colony_opt solutions){ + String make_filename = problem.benchmark+"_ant"+String.valueOf(problem.ant_num)+"_beta"+String.valueOf(problem.beta)+"_q0"+String.valueOf(problem.q0)+"_alpha"+String.valueOf(problem.alpha)+"_rho"+String.valueOf(problem.rho); + Path path1 = Paths.get("/Users/shimizukengo/Desktop/important/study_abroad/research/ACO_VRPTW/outputs/"+problem.experiment); + Path path2 = Paths.get(path1+"/"+make_filename); + + //If the folder does NOT exit, make this folder in this path + if (Files.exists(path1) == false) { + try{ + Files.createDirectory(path1); + }catch(IOException e){ + System.out.println(e); + } + } + + //If the folder does NOT exit, make this folder in this path + if (Files.exists(path2) == false) { + try{ + Files.createDirectory(path2); + }catch(IOException e){ + System.out.println(e); + } + } + + //make file + String path = "/Users/shimizukengo/Desktop/important/study_abroad/research/ACO_VRPTW/outputs/"+problem.experiment+"/"+make_filename+"/"+make_filename+"_"+problem.ite_num+".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]\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("#iteration\tvehi_num\ttotal_distance\ttotal_time\n"); + + //write data in .dat file + for (int i=0; i<solutions.min_vehinum_tracker.size(); i++) { + filewriter.write(String.valueOf(i)+"\t"+String.valueOf(solutions.min_vehinum_tracker.get(i))+"\t"+String.valueOf(solutions.min_distance_tracker.get(i))+"\n"); + } + + filewriter.close(); + }catch(IOException e){ + System.out.println(e); + } + } + + + public static void output_positions(Load_problem problem, long e_s, Ant_colony_opt solutions){ + String make_filename = problem.benchmark+"_ant"+String.valueOf(problem.ant_num)+"_beta"+String.valueOf(problem.beta)+"_q0"+String.valueOf(problem.q0)+"_alpha"+String.valueOf(problem.alpha)+"_rho"+String.valueOf(problem.rho); + Path path1 = Paths.get("/Users/shimizukengo/Desktop/important/study_abroad/research/ACO_VRPTW/outputs/"+problem.experiment); + Path path2 = Paths.get(path1+"/"+make_filename); + + //If the folder does NOT exit, make this folder in this path + if (Files.exists(path1) == false) { + try{ + Files.createDirectory(path1); + }catch(IOException e){ + System.out.println(e); + } + } + + //If the folder does NOT exit, make this folder in this path + if (Files.exists(path2) == false) { + try{ + Files.createDirectory(path2); + }catch(IOException e){ + System.out.println(e); + } + } + + for (int p=0; p<solutions.pareto_sols.size(); p++) { + String path = "/Users/shimizukengo/Desktop/important/study_abroad/research/ACO_VRPTW/outputs/"+problem.experiment+"/"+make_filename+"/"+make_filename+"_"+problem.ite_num+"_position"+p+".dat"; + int count = 0; + if (solutions.pareto_sols.size() != 1) { + if (solutions.pareto_sols.get(0).route.size() > 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<solutions.pareto_sols.get(p).route.size(); i++) { + for (int j=0; j<solutions.pareto_sols.get(p).route.get(i).size(); j++) { + filewriter.write(problem.customer.get(solutions.pareto_sols.get(p).route.get(i).get(j)).pos[0]+"\t"+problem.customer.get(solutions.pareto_sols.get(p).route.get(i).get(j)).pos[1]+"\n"); + } + } + + + filewriter.close(); + }catch(IOException e){ + System.out.println(e); + } + } + } +} diff --git a/back/aco-mdvrptw/src/main/java/com/odiparpack/acovrptw/Pareto_check.java b/back/aco-mdvrptw/src/main/java/com/odiparpack/acovrptw/Pareto_check.java new file mode 100644 index 0000000..5927826 --- /dev/null +++ b/back/aco-mdvrptw/src/main/java/com/odiparpack/acovrptw/Pareto_check.java @@ -0,0 +1,25 @@ +package com.odiparpack.acovrptw; + +import java.util.ArrayList; +import java.util.List; + +public class Pareto_check { + public static boolean check(List<Build_tour> pareto_sols, Build_tour solution){ + for(int i=0; i<pareto_sols.size(); i++) { + if(solution.n >= 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<Build_tour> rm_ind(List<Build_tour> pareto_sols, Build_tour solution){ + List<Build_tour> dominated_sols_ind = new ArrayList<Build_tour>(); + for(int i=0; i<pareto_sols.size(); i++) { + if(solution.n <= pareto_sols.get(i).n && solution.J <= pareto_sols.get(i).J) { + dominated_sols_ind.add(pareto_sols.get(i)); + } + } + return dominated_sols_ind; + } +} |