Specify package: java in pom.xmlmitsuo

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;
+	}
+}