C++

Forum

 
insert function

yat89 (81)
Hi everyone. I'm new to c++. Currently I'm doing project on vehicle routing problem in waste collection.

Given 4 set of routes as follows:
0 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
0 6 27 29 33 19 18 16 9 3 5 11 13 12 25 24 32 28 30 4 31 10 7 8 14 17 15 20 22 23 21 26
0 5 3 9 16 18 19 33 29 27 6 31 4 30 28 32 24 25 12 13 11 26 21 23 22 20 15 17 14 8 7 10
0 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3

Each route consists of one depot (known as 0), two disposal facility (which is 1 and 2) and customer (from 3 until 33). Each stop/customer has its own load that need to be collected as follows:

0 0
1 0
2 0
3 10
4 10
5 10
6 10
7 10
8 20
9 20
10 20
11 20
12 20
13 10
14 10
15 10
16 10
17 10
18 20
19 20
20 20
21 20
22 20
23 10
24 10
25 10
26 10
27 10
28 20
29 20
30 20
31 20
32 15
33 5

Here is the situation. For each of route, the vehicle start from depot 0, then served each of the customer based on the given sequence. When the vehicle reach its maximum limit, the driver need to emptied the vehicle at the closest disposal facility. After that, they will continue collecting waste from the remaining customer until the vehicle reach its maximum limit. Multiple trip to the disposal facility will occurred to served all the customers. Maximum vehicle limit is denoted as Q. Q is 150.

I had try write the code. I only know how to insert only one disposal facility. But here, I need to choose the closest disposal facility between (1 and 2) from the last visited customer. I don't have idea how to do it. Hopefully someone can help me.

Here is the code. If i need to explain further on this, please let me know. Thanks for your kindness.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
 
#include <iostream>  // for cout
#include <fstream>
#include <vector>    // for vector
#include <iomanip>	 // for setw
#include <numeric>   // for partial_sum
#include <algorithm> // for upper_bound

using namespace std;

const int routeRow = 4;	 // Route row / population size
const int routeCol = 32; // Route column
const int m = 34;	     // Number of stop
const int dataCol = 2;	 // Data column consist number of load for each stop
const int tdd = 3;		 // Total number of depot & disposal sites
const int d = tdd - 1;		 // Number of disposal site

vector<vector<int> > data(m, vector <int>(dataCol, 0));
vector<vector<int> > route(routeRow, vector <int>(routeCol, 0));
vector<vector<long double> > dist(m, vector <long double>(m, 0));
vector<int> load(m);

int i, j;

int main()
{
	// Input file
	ifstream inpLoad("myLoad.txt");
	ifstream inpRoute("myRoute.txt");
	ifstream inpDistance("myDistance.txt");

	// Assign data into array 
	cout << "The load data are: "; 
		cout << endl;
	for (i = 0; i < m; i++)
	{
		for (j = 0; j < dataCol; j++)
		{
			inpLoad >> data[i][j];
			//cout << setw(3) << data[i][j] << '	';
		}
		//cout << endl;
	}
	//cout << endl;

	// Assign route into array 
	cout << "The routes are: "; 
		cout << endl;
	for (i = 0; i < routeRow; i++)
	{
		for (j = 0; j < routeCol; j++)
		{
			inpRoute >> route[i][j];
			cout << route[i][j] << '	';
		}
		cout << endl;
	}
	cout << endl;

	// Assign distance into array 
	//cout << "The distances are: "; 
		//cout << endl;
	for (i = 0; i < m; i++)
	{
		for (j = 0; j < m; j++)
		{
			inpDistance >> dist[i][j];
			//cout << setw(10) << dist[i][j] << ' ';
		}
		//cout << endl;
	}
	//cout << endl;

	// Assign load into array
	for (i = 0; i < m; i++)
	{
		load[i] = data[i][1];
	}

	// Close input files
	inpLoad.close();
	inpRoute.close();
	inpDistance.close();

	cout << "Loads for each stop in route:"; 
		cout << endl;

	// Transform route into loads for each stop in route
	vector<vector<int> > sums;
	
	for(i = 0; i < routeRow; i++)
	{
		vector<int> temp;
		for(j = 0; j < routeCol; j++)
		{
			temp.push_back( load[route[i][j]] );
		}
		sums.push_back(temp);
	}

	// Display the solution of load for each stop
	for(i = 0; i < routeRow; i++)
	{
		for(int j = 0; j < routeCol; j++)
		{
			cout << sums[i][j] << '	';
		}
		cout << endl;
	}
	cout << endl;

	cout << "Partial sum:"; 
		cout << endl;

	// Compute the partial sum
	// Reserve space for the partial sums
	vector<vector<int> > partialSum(routeRow, vector<int>(routeCol));
	
	for(i = 0; i < routeRow; i++)
	{
		partial_sum(sums[i].begin(), sums[i].end(), partialSum[i].begin());
	}

	// Display the solution of partial sum
	for(i = 0; i < routeRow; i++)
	{
		for(int j = 0; j < routeCol; j++)
		{
			cout << partialSum[i][j] << '	';
		}
		cout << endl;
	}
	cout << endl;

	for (int i = 0; i < routeRow; i++)
	{
		int Q = 150;

		// Iterator used to store the position of searched element 
		vector<int>::iterator upper;
    
		// upper_bound function call 
		upper = upper_bound (partialSum[i].begin(), partialSum[i].end(), Q); 

		int i1 = (upper - partialSum[i].begin());

		cout << "For row " << i << ", first disposal trip, positions " << i1 << " were chosen.\n";

		route[i].insert(route[i].begin() + i1, 1);
		partialSum[i].insert(partialSum[i].begin() + i1, 1);
	}
	cout << endl;

	cout << "Display original route with insert element: ";
		cout << endl;

	for(int i = 0; i < route.size(); i++)
	{
		for(int j = 0; j < route[i].size(); j++)
		{
			cout << route[i][j] << '	';
		}
		cout << endl;
	}
	cout << endl;

	cout << "Display partial sum with insert element: ";
		cout << endl;

	for(int i = 0; i < route.size(); i++)
	{
		for(int j = 0; j < route[i].size(); j++)
		{
			cout << partialSum[i][j] << '	';
		}
		cout << endl;
	}
	cout << endl;

	system("pause");
	return 0;
}
Handy Andy (5051)
Hello yat89,

Your program does not compile.

The first problem I see is on line 17 The prototype describes a function called "data", which I do not see the definition for, and on line 38 you have a variable "data" that looks like a 2D array or maybe you wanted a 2D vector. Not sure because I do not find a definition for this variable before it is used.

The next problem is line 38 is giving me an error, which translates to, Which "data" do you want to use? Your function "data", the variable "data" or the function "std::data()", which the compiler is trying to use?

Some tips:

When defining a constant variable it is generally accepted to use capital letters for the variable name.

Also try not to use a single letter for a variable name as it makes it hard to understand.

Lines 20 and 22 are better defined in "main". Try to avoid regular global variables like these as the whole file has access to them and it makes it harder to find where an unwanted change was made.

As for the variables "i" and "j" unless you have a need for them outside the for loop they are used in it is better to define them in the for loop(s) and keep them local to the for loop(s).

This creates a warning and will not keep the program from running for(int i = 0; i < route.size(); i++). The problem here is that route.size() returns a"size_type" or "size_t", which is a type def for an "unsigned int", most of the time. And you are trying to compare an "unsigned int" to an "int". It works, but it is a type mismatch. Not a big problem, but something to keep in mind.

You open three files on lines 27 - 29, but how do you know that they are open? Over time I came up with this:
1
2
3
4
5
6
7
8
9
10
 
const std::string inFileName{ "myLoad.txt" };

std::ifstream inFile(inFileName);

if (!inFile)
{
	std::cout << "\n File \"" << inFileName << "\" did not open" << std::endl;
	std::this_thread::sleep_for(std::chrono::seconds(3));  // <--- Needs header files chrono" and "thread".
	return 1;  //exit(1);  // If not in "main".
}

Line 8. Is optional. if you do not need it you can delete it or put a comment on it.

For line 9 if the code is in "main" the return is best to use. If this code is in a function the "exit" will be needed. Since zero is considered a normal return value any number greater than zero is considered a problem. The number can be used outside the, (by whatever called the program) or yo can use this number to figure out where the problem is in your code.

You open three input files. Knowing the data contained in these files helps to understand what the program is doing and gives anyone trying to run your program the same data that you are using, so there is no guessing on how to create the files or using different data. The actual input files will help or a better explanation of what you have posted.

I will see what I can do with your program to get it to compile and try to run it.

Hope that helps,

Andy
ne555 (10692)
> I had try write the code. I only know how to insert only one disposal
> facility. But here, I need to choose the closest disposal facility between (1
> and 2) from the last visited customer. I don't have idea how to do it.
> Hopefully someone can help me.
I fail to see the problem.
you have two dispolsal facilites: 'a' and `b'
when the truck if full you simply check 
1
2
3
4
 
if(distance(t, a) < distance(t, b))
   t.move_to(a);
else
   t.move_to(b);
yat89 (81)
Hi Handy Andy,

The first problem I see is on line 17 The prototype describes a function called "data", which I do not see the definition for, and on line 38 you have a variable "data" that looks like a 2D array or maybe you wanted a 2D vector. Not sure because I do not find a definition for this variable before it is used.

I have data in matrix form (34x2). First column is the stop id, second column is the load for each stop. (I had show the data at above).

The next problem is line 38 is giving me an error, which translates to, Which "data" do you want to use? Your function "data", the variable "data" or the function "std::data()", which the compiler is trying to use?

I can compile the program. I think it is because I'm using older version c++98. I will change the variable data to loadData.

You open three input files. Knowing the data contained in these files helps to understand what the program is doing and gives anyone trying to run your program the same data that you are using, so there is no guessing on how to create the files or using different data. The actual input files will help or a better explanation of what you have posted.

Yes, I have three input data which as route data(as above), load data(as above) and distance data(I forgot to attach earlier). The distance data too long. I will try attached it after I submit this comment.

Actually I had problem here. (line 134-151)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
for (int i = 0; i < routeRow; i++)
	{
		int Q = 150;

		// Iterator used to store the position of searched element 
		vector<int>::iterator upper;
    
		// upper_bound function call 
		upper = upper_bound (partialSum[i].begin(), partialSum[i].end(), Q); 

		int i1 = (upper - partialSum[i].begin());

		cout << "For row " << i << ", first disposal trip, positions " << i1 << " were chosen.\n";

		route[i].insert(route[i].begin() + i1, 1);
		partialSum[i].insert(partialSum[i].begin() + i1, 0);
	}
	cout << endl;


Herein, I only know how to insert if the disposal is one. But here, there are two disposal facility (given id as 1 and 2). I need to choose the closest disposal from [i1-1]. i1 is the position where I need to insert the disposal. [i1-1] is the last visited customer before go to the disposal on the current route. I don't know how to do it.

Based on ne555 comment,
I had try insert the suggested code.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
for (int i = 0; i < routeRow; i++)
	{
		int Q = 150;

		// Iterator used to store the position of searched element 
		vector<int>::iterator upper;
    
		// upper_bound function call 
		upper = upper_bound (partialSum[i].begin(), partialSum[i].end(), Q); 

		int i1 = (upper - partialSum[i].begin());

		cout << "For row " << i << ", first disposal trip, positions " << i1 << " were chosen.\n";

		if (dist[i1-1][1] < dist[i1-1][2])
			[i1-1].move_to[1];
		else 
			[i1-1].move_to[2];

		route[i].insert(route[i].begin() + i1, 1);
		partialSum[i].insert(partialSum[i].begin() + i1, 0);
	}
	cout << endl;


I don't have idea how it should work. How to change for this.
route[i].insert(route[i].begin() + i1, 1);

Sorry. I really don't know how to do it. Can someone show me.




Last edited on
yat89 (81)
Handy Andy, here is the distance data.

0.000 2.914 58.554 2.877 2.281 3.704 3.063 1.720 1.095 2.274 32.924 32.760 18.339 33.277 1.812 4.527 2.663 7.054 2.770 33.491 34.706 33.033 2.772 4.250 33.139 33.139 33.159 33.139 1.932 18.186 18.186 32.780 3.543 2.165
2.914 0.000 56.129 5.791 5.196 6.618 5.977 4.634 4.009 4.700 30.010 29.846 15.425 30.363 4.386 2.300 5.577 5.309 5.684 30.576 31.791 30.119 5.686 7.164 30.225 30.225 30.245 30.225 4.846 15.271 15.271 29.866 6.457 5.079
58.554 56.129 0.000 58.209 56.567 59.836 60.832 59.093 59.580 60.829 28.594 28.098 44.461 28.625 60.366 54.027 56.420 51.501 58.142 27.852 26.628 29.040 58.681 58.134 28.417 28.417 28.390 28.417 58.916 44.263 44.263 28.720 58.311 56.518
2.877 5.791 58.209 0.000 1.643 1.626 2.623 1.158 1.783 3.045 35.802 35.637 21.216 36.154 2.157 4.182 1.789 6.709 0.107 36.368 37.583 35.910 0.471 1.373 36.016 36.016 36.036 36.016 0.945 21.063 21.063 35.657 0.665 1.691
2.281 5.196 56.567 1.643 0.000 3.269 4.265 2.526 3.013 4.262 35.206 35.042 20.620 35.558 3.799 2.896 0.381 5.066 1.575 35.772 36.987 35.315 2.114 1.968 35.420 35.420 35.441 35.420 2.349 20.467 20.467 35.062 1.744 0.116
3.704 59.836 6.618 1.626 3.269 0.000 0.996 1.985 2.610 3.872 36.629 36.464 22.043 36.981 2.232 5.809 3.416 8.335 1.694 37.195 38.410 36.737 1.155 1.702 36.843 36.843 36.863 36.843 1.773 21.890 21.890 36.484 1.525 3.318
3.063 5.977 60.832 2.623 4.265 0.996 0.000 1.739 1.969 3.231 35.988 35.823 21.402 36.340 1.591 6.805 4.412 9.331 2.690 36.554 37.769 36.096 2.152 2.698 36.202 36.202 36.222 36.202 1.917 21.249 21.249 35.843 2.522 4.314
1.720 4.634 59.093 1.158 2.526 1.985 1.739 0.000 0.625 1.888 34.644 34.480 20.059 34.996 1.273 5.066 2.673 7.592 1.051 35.210 36.425 34.753 1.052 2.530 34.858 34.858 34.879 34.858 0.212 19.905 19.905 34.500 1.823 2.575
1.095 4.009 59.580 1.783 3.013 2.610 1.969 0.625 0.000 1.263 34.019 33.855 19.434 34.371 0.787 5.552 3.159 8.079 1.676 34.585 35.800 34.128 1.677 3.155 34.233 34.233 34.254 34.233 0.837 19.280 19.280 33.875 2.448 3.062
2.274 4.700 60.829 3.045 4.262 3.872 3.231 1.888 1.263 0.000 32.756 32.731 18.171 33.109 1.640 6.802 4.409 9.328 2.938 33.323 34.538 32.865 2.940 4.418 32.971 32.971 32.991 32.971 2.100 18.018 18.018 32.612 3.711 4.311
32.924 28.594 30.010 35.802 35.206 36.629 35.988 34.644 34.019 32.756 0.000 0.497 15.867 0.352 34.396 32.310 35.587 35.320 35.695 0.742 1.966 0.446 35.696 37.174 0.214 0.214 0.235 0.214 34.856 15.669 15.669 0.144 36.467 35.090
32.760 29.846 28.098 35.637 35.042 36.464 35.823 34.480 33.855 32.731 0.497 0.000 16.364 0.527 34.232 32.146 35.423 35.155 35.530 0.730 1.945 0.943 35.532 37.010 0.379 0.379 0.399 0.379 34.692 16.166 16.166 0.622 36.303 34.925
18.339 15.425 44.461 21.216 20.620 22.043 21.402 20.059 19.434 18.171 15.867 16.364 0.000 15.837 19.811 17.724 21.002 20.734 21.109 16.609 17.833 15.421 21.111 22.589 16.044 16.044 16.071 16.044 20.271 0.198 0.198 15.742 21.882 20.504
33.277 28.625 30.363 36.154 35.558 36.981 36.340 34.996 34.371 33.109 0.352 0.527 15.837 0.000 34.749 32.662 35.940 35.672 36.047 0.773 1.997 0.416 36.048 37.527 0.208 0.208 0.234 0.208 35.208 15.638 15.638 0.496 36.819 35.442
1.812 4.386 60.366 2.157 3.799 2.232 1.591 1.273 0.787 1.640 34.396 34.232 19.811 34.749 0.000 6.339 3.946 8.865 2.224 34.963 36.178 34.505 1.685 2.778 34.611 34.611 34.631 34.611 1.451 19.658 19.658 34.252 2.071 3.848
4.527 2.300 54.027 4.182 2.896 5.809 6.805 5.066 5.552 6.802 32.310 32.146 17.724 32.662 6.339 0.000 3.277 3.010 4.115 32.876 34.091 32.419 4.653 4.864 32.524 32.524 32.545 32.524 4.888 17.571 17.571 32.166 4.283 2.780
2.663 5.577 56.420 1.789 0.381 3.416 4.412 2.673 3.159 4.409 35.587 35.423 21.002 35.940 3.946 3.277 0.000 4.920 1.722 36.153 37.369 35.696 2.260 1.713 35.802 35.802 35.822 35.802 2.495 20.848 20.848 35.443 1.890 0.498
7.054 5.309 51.501 6.709 5.066 8.335 9.331 7.592 8.079 9.328 35.320 35.155 20.734 35.672 8.865 3.010 4.920 0.000 6.641 35.886 37.101 35.428 7.180 6.633 35.534 35.534 35.555 35.534 7.415 20.581 20.581 35.176 6.810 5.017
2.770 5.684 58.142 0.107 1.575 1.694 2.690 1.051 1.676 2.938 35.695 35.530 21.109 36.047 2.224 4.115 1.722 6.641 0.000 36.261 37.476 35.803 0.538 1.480 35.909 35.909 35.929 35.909 0.838 20.956 20.956 35.550 0.772 1.624
33.491 30.576 27.852 36.368 35.772 37.195 36.554 35.210 34.585 33.323 0.742 0.730 16.609 0.773 34.963 32.876 36.153 35.886 36.261 0.000 1.224 1.188 36.262 37.740 0.565 0.565 0.538 0.565 35.422 16.411 16.411 0.867 37.033 35.656
34.706 31.791 26.628 37.583 36.987 38.410 37.769 36.425 35.800 34.538 1.966 1.945 17.833 1.997 36.178 34.091 37.369 37.101 37.476 1.224 0.000 2.412 37.477 38.955 1.789 1.789 1.762 1.789 36.637 17.635 17.635 2.092 38.248 36.871
33.033 30.119 29.040 35.910 35.315 36.737 36.096 34.753 34.128 32.865 0.446 0.943 15.421 0.416 34.505 32.419 35.696 35.428 35.803 1.188 2.412 0.000 35.805 37.283 0.623 0.623 0.650 0.623 34.965 15.223 15.223 0.321 36.576 35.198
2.772 58.681 5.686 0.471 2.114 1.155 2.152 1.052 1.677 2.940 35.696 35.532 21.111 36.048 1.685 4.653 2.260 7.180 0.538 36.262 37.477 35.805 0.000 1.478 35.911 35.911 35.931 35.911 0.840 20.957 20.957 35.552 0.771 2.163
4.250 58.134 7.164 1.373 1.968 1.702 2.698 2.530 3.155 4.418 37.174 37.010 22.589 37.527 2.778 4.864 1.713 6.633 1.480 37.740 38.955 37.283 1.478 0.000 37.389 37.389 37.409 37.389 2.318 22.435 22.435 37.030 0.707 2.085
33.139 30.225 28.417 36.016 35.420 36.843 36.202 34.858 34.233 32.971 0.214 0.379 16.044 0.208 34.611 32.524 35.802 35.534 35.909 0.565 1.789 0.623 35.911 37.389 0.000 0.000 0.027 0.000 35.070 15.846 15.846 0.359 36.681 35.304
33.139 30.225 28.417 36.016 35.420 36.843 36.202 34.858 34.233 32.971 0.214 0.379 16.044 0.208 34.611 32.524 35.802 35.534 35.909 0.565 1.789 0.623 35.911 37.389 0.000 0.000 0.027 0.000 35.070 15.846 15.846 0.359 36.681 35.304
33.159 30.245 28.390 36.036 35.441 36.863 36.222 34.879 34.254 32.991 0.235 0.399 16.071 0.234 34.631 32.545 35.822 35.555 35.929 0.538 1.762 0.650 35.931 37.409 0.027 0.027 0.000 0.027 35.091 15.873 15.873 0.379 36.702 35.324
33.139 30.225 28.417 36.016 35.420 36.843 36.202 34.858 34.233 32.971 0.214 0.379 16.044 0.208 34.611 32.524 35.802 35.534 35.909 0.565 1.789 0.623 35.911 37.389 0.000 0.000 0.027 0.000 35.070 15.846 15.846 0.359 36.681 35.304
1.932 4.846 58.916 0.945 2.349 1.773 1.917 0.212 0.837 2.100 34.856 34.692 20.271 35.208 1.451 4.888 2.495 7.415 0.838 35.422 36.637 34.965 0.840 2.318 35.070 35.070 35.091 35.070 0.000 20.117 20.117 34.712 1.611 2.398
18.186 15.271 44.263 21.063 20.467 21.890 21.249 19.905 19.280 18.018 15.669 16.166 0.198 15.638 19.658 17.571 20.848 20.581 20.956 16.411 17.635 15.223 20.957 22.435 15.846 15.846 15.873 15.846 20.117 0.000 0.000 15.544 21.728 20.351
18.186 15.271 44.263 21.063 20.467 21.890 21.249 19.905 19.280 18.018 15.669 16.166 0.198 15.638 19.658 17.571 20.848 20.581 20.956 16.411 17.635 15.223 20.957 22.435 15.846 15.846 15.873 15.846 20.117 0.000 0.000 15.544 21.728 20.351
32.780 28.720 29.866 35.657 35.062 36.484 35.843 34.500 33.875 32.612 0.144 0.622 15.742 0.496 34.252 32.166 35.443 35.176 35.550 0.867 2.092 0.321 35.552 37.030 0.359 0.359 0.379 0.359 34.712 15.544 15.544 0.000 36.323 34.945
3.543 6.457 58.311 0.665 1.744 1.525 2.522 1.823 2.448 3.711 36.467 36.303 21.882 36.819 2.071 4.283 1.890 6.810 0.772 37.033 38.248 36.576 0.771 0.707 36.681 36.681 36.702 36.681 1.611 21.728 21.728 36.323 0.000 1.793
2.165 5.079 56.518 1.691 0.116 3.318 4.314 2.575 3.062 4.311 35.090 34.925 20.504 35.442 3.848 2.780 0.498 5.017 1.624 35.656 36.871 35.198 2.163 2.085 35.304 35.304 35.324 35.304 2.398 20.351 20.351 34.945 1.793 0.000
yat89 (81)
Hi Handy Andy and ne555,

I had made some improvement to my code. Nothing error occurred but result obtained is wrong for second route. I don't know why. I don't know if I coded it wrong.

Here is the code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
 
#include <iostream>
#include <fstream>
#include <vector>    // for vector
#include <iomanip>	 // for setw
#include <numeric>   // for partial_sum
#include <algorithm> // for upper_bound

using namespace std;

const int routeRow = 4;	 // Route row / population size
const int routeCol = 32; // Route column
const int m = 34;	     // Number of stop
const int dataCol = 2;	 // Data column consist number of load for each stop
const int tdd = 3;		 // Total number of depot & disposal sites
const int d = tdd - 1;		 // Number of disposal site

vector<vector<int> > loadData(m, vector <int>(dataCol, 0));
vector<vector<int> > route(routeRow, vector <int>(routeCol, 0));
vector<vector<long double> > dist(m, vector <long double>(m, 0));
vector<int> load(m);

int i, j;

int main()
{
	// Input file
	ifstream inpLoad("myLoad.txt");
	ifstream inpRoute("myRoute.txt");
	ifstream inpDistance("myDistance.txt");

	// Assign data into array 
	cout << "The load data are: ";
	cout << endl;
	for (i = 0; i < m; i++)
	{
		for (j = 0; j < dataCol; j++)
		{
			inpLoad >> loadData[i][j];
			//cout << setw(3) << data[i][j] << '	';
		}
		//cout << endl;
	}
	//cout << endl;

	// Assign route into array 
	cout << "The routes are: ";
	cout << endl;
	for (i = 0; i < routeRow; i++)
	{
		for (j = 0; j < routeCol; j++)
		{
			inpRoute >> route[i][j];
			cout << route[i][j] << '	';
		}
		cout << endl;
	}
	cout << endl;

	// Assign distance into array 
	//cout << "The distances are: "; 
		//cout << endl;
	for (i = 0; i < m; i++)
	{
		for (j = 0; j < m; j++)
		{
			inpDistance >> dist[i][j];
			//cout << setw(10) << dist[i][j] << ' ';
		}
		//cout << endl;
	}
	//cout << endl;

	// Assign load into array
	for (i = 0; i < m; i++)
	{
		load[i] = loadData[i][1];
	}

	// Close input files
	inpLoad.close();
	inpRoute.close();
	inpDistance.close();

	cout << "Loads for each stop in route:";
	cout << endl;

	// Transform route into loads for each stop in route
	vector<vector<int> > sums;

	for (i = 0; i < routeRow; i++)
	{
		vector<int> temp;
		for (j = 0; j < routeCol; j++)
		{
			temp.push_back(load[route[i][j]]);
		}
		sums.push_back(temp);
	}

	// Display the solution of load for each stop
	for (i = 0; i < routeRow; i++)
	{
		for (int j = 0; j < routeCol; j++)
		{
			cout << sums[i][j] << '	';
		}
		cout << endl;
	}
	cout << endl;

	cout << "Partial sum:";
	cout << endl;

	// Compute the partial sum
	// Reserve space for the partial sums
	vector<vector<int> > partialSum(routeRow, vector<int>(routeCol));

	for (i = 0; i < routeRow; i++)
	{
		partial_sum(sums[i].begin(), sums[i].end(), partialSum[i].begin());
	}

	// Display the solution of partial sum
	for (i = 0; i < routeRow; i++)
	{
		for (int j = 0; j < routeCol; j++)
		{
			cout << partialSum[i][j] << '	';
		}
		cout << endl;
	}
	cout << endl;

	for (int i = 0; i < routeRow; i++)
	{
		int Q = 150;

		// Iterator used to store the position of searched element 
		vector<int>::iterator upper;

		// upper_bound function call 
		upper = upper_bound(partialSum[i].begin(), partialSum[i].end(), Q);

		int i1 = (upper - partialSum[i].begin());

		cout << "For row " << i << ", first disposal trip, positions " << i1 << " were chosen.\n";

		if (dist[i1 - 1][1] < dist[i1 - 1][2])
		{
			route[i].insert(route[i].begin() + i1, 1);
			partialSum[i].insert(partialSum[i].begin() + i1, 0);
		}
		else
		{
			route[i].insert(route[i].begin() + i1, 2);
			partialSum[i].insert(partialSum[i].begin() + i1, 0);
		}
	}
	cout << endl;

	cout << "Display original route with insert element: ";
	cout << endl;

	for (int i = 0; i < routeRow; i++)
	{
		for (int j = 0; j < route[i].size(); j++)
		{
			cout << route[i][j] << '	';
		}
		cout << endl;
	}
	cout << endl;

	cout << "Display partial sum with insert element: ";
	cout << endl;

	for (int i = 0; i < routeRow; i++)
	{
		for (int j = 0; j < route[i].size(); j++)
		{
			cout << partialSum[i][j] << '	';
		}
		cout << endl;
	}
	cout << endl;

	system("pause");
	return 0;
}


Here is result obtained:

Display original route with insert element:
0       3       4       5       6       7       8       9       10      11      12      1       13      14      15
16      17      18      19      20      21      22      23      24      25      26      27      28      29      30
31      32      33
0       6       27      29      33      19      18      16      9       3       5       1       11      13      12
25      24      32      28      30      4       31      10      7       8       14      17      15      20      22
23      21      26
0       5       3       9       16      18      19      33      29      27      6       1       31      4       30
28      32      24      25      12      13      11      26      21      23      22      20      15      17      14
8       7       10
0       33      32      31      30      29      28      27      26      25      24      23      2       22      21
20      19      18      17      16      15      14      13      12      11      10      9       8       7       6
5       4       3


For second route, supposed to visit disposal 2 because disposal 2 more closer to customer 5.
Topic archived. No new replies allowed.