Inserting a value in the middle of array

[yat89]

Hi everyone, I got a task to insert a value (1 or 2) into each row. But, the chosen value is based on the minimum distance from the previous number.

And the position in the row where the new value are inserted are based on this two condition:

1. total capacity (currentQ) must less or equal to Q (then, insert 1 or 2)
2. total capacity (totalQ) must less or equal to maxQ (then, insert 1 or 2, after that insert 0)

Q is the vehicle capacity. While, maxQ is the max vehicle capacity per day.

We need to reset currentQ = 0 whenever the load is less than or equal to Q after inserting new value.

Hopefully, you will understand what i'm trying to explain.

For example, route row 0:
0 3 6 9 7 5 0

should be:
0 3 6 1 9 7 2 0 5 1 0


Here is the route data:
0 3 6 9 7 5 0
0 4 12 8 10 3 0
0 12 11 6 4 7 0

Distance data:
0 2.914204545 58.55435606 2.877083333 2.281439394 3.704166667 3.063068182 1.719507576 1.094507576 2.274431818 32.92443182 32.76022727 18.33901515
2.914204545 0 56.12916667 5.791287879 5.195643939 6.618371212 5.977272727 4.633712121 4.008712121 4.699621212 30.01022727 29.84602273 15.42481061
58.55435606 56.12916667 0 58.2094697 56.56685606 59.83579545 60.83219697 59.09280303 59.57954545 60.82878788 28.59431818 28.09753788 44.46117424
2.877083333 5.791287879 58.2094697 0 1.642613636 1.626325758 2.622727273 1.157575758 1.782575758 3.045075758 35.80151515 35.63731061 21.21609848
2.281439394 5.195643939 56.56685606 1.642613636 0 3.268939394 4.265340909 2.52594697 3.012689394 4.261931818 35.20587121 35.04166667 20.62045455
3.704166667 6.618371212 59.83579545 1.626325758 3.268939394 0 0.996401515 1.984659091 2.609659091 3.872159091 36.62859848 36.46439394 22.04318182
3.063068182 5.977272727 60.83219697 2.622727273 4.265340909 0.996401515 0 1.739393939 1.968560606 3.231060606 35.9875 35.82329545 21.40208333
1.719507576 59.09280303 4.633712121 1.157575758 2.52594697 1.984659091 1.739393939 0 0.625 1.8875 34.64393939 34.47973485 20.05852273
1.094507576 59.57954545 4.008712121 1.782575758 3.012689394 2.609659091 1.968560606 0.625 0 1.2625 34.01893939 33.85473485 19.43352273
2.274431818 4.699621212 60.82878788 3.045075758 4.261931818 3.872159091 3.231060606 1.8875 1.2625 0 32.75643939 32.73125 18.17102273
32.92443182 28.59431818 30.01022727 35.80151515 35.20587121 36.62859848 35.9875 34.64393939 34.01893939 32.75643939 0 0.496780303 15.86685606
32.76022727 28.09753788 29.84602273 35.63731061 35.04166667 36.46439394 35.82329545 34.47973485 33.85473485 32.73125 0.496780303 0 16.36363636
18.33901515 15.42481061 44.46117424 21.21609848 20.62045455 22.04318182 21.40208333 20.05852273 19.43352273 18.17102273 15.86685606 16.36363636 0

Load/capacity data:
0 0
1 0
2 0
3 14
4 17
5 16
6 15
7 18
8 20
9 26
10 30
11 33
12 12

I had try do the the coded but it seem wrong somewhere and the error also occurred. I don't know how to solve it. Hope anyone can help me.

#include <iostream> 
#include <vector> 
#include <iomanip>	// setw
#include <fstream>

using namespace std;

const int routeRow = 3;	// Route row / population size
const int routeCol = 7;	// Route column
const int m = 13;	// Number of nodes / stop
const int dataCol = 2;	// Data column
long double Q = 50.0;	// Vehicle capacity 
long double maxQ = 80.0;	// Max vehicle capacity per day

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

int i, j;

int main()
{
	// Input file
	ifstream inpData("myData.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++)
		{
			inpData >> 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 << setw(3) << 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
	inpData.close();
	inpRoute.close();
	inpDistance.close();

	for(i = 0; i < routeRow; i++)
	{
		
		double currentQ = 0;
		double totalQ = 0;

		for(j = 0; j < routeCol; j++)
		{
			if ((currentQ + load[route[i][j]] <= Q) 
			&& (totalQ + load[route[i][j]] <= maxQ))
			{
				// Inserts '1' or '2' (choose minimum distance from previous number) 
				// when currentQ less or equal to Q and totalQ less or equal to maxQ).
				vector<int>::iterator it = route[i].insert(route[i].begin(), route[i].end(), 1);
			}	
		}
	}
	cout << endl;

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

	system("pause");
	return 0;
}

[dutch]

Your description is gibberish to me.

[Zhuge]

Sorry to say I don't really understand what you are being asked to do! I might be able to reverse engineer it from the code you've given but I wonder if you could give the explanation another go?

Specifically, how do you decide what numbers to insert? You mentioned distance, but didn't say exactly how it is relevant to deciding the new values to insert.

[Duthomhas]

I also am confused. It looks like you are doing some kind of weighted traveling salesman problem, but the constraints (Q?) mean nothing to me.

And, alas, I’m already giving myself a headache on another problem of my own that I want to do. Not gonna try to decipher your code.

[yat89]

Hi dutch and Zhuge, sorry for my unclear description.

I will try with another explanation. Hopefully you will understand.

Given 3 route:
0 3 6 9 7 5 0
0 4 12 8 10 3 0
0 12 11 6 4 7 0

For each row, i need to calculate the total capacity. When the capacity is reach to Q (<=), then insert new value. The new value is either 1 or 2. The new value is choose based on the minimum distance from previous number. Q = 50.

for example, row 0,
load[0] + load[3] + load[6] + load[9] + load[7] + load[5] + load[0]
0 + 14 + 15 + 26 + 18 + 16 + 0

When, i sum up from number 0, 3 and 6, the total capacity is 29.
if i continue sum up until number 9, the capacity is 55. It mean exceed Q. So, i need to include new value after number 6. in order to include the new value i need to choose between 1 and 2.

Based on the distance. the distance from:
6 to 1 is 5.977272727, or
6 to 2 is 60.83219697

So, i need to choose the minimum distance. Then, need to insert 1 after 6

Then, the route should be,
0 3 6 1 9 7 5 0

For the second condition,
Also, need to sum up from the beginning of the route. From number 0, 3, 6, 9, 7, 5 until 0. When the capacity is reach to maxQ (<=), then insert new value. Same as first condition but after insert 1 or 2, I need to insert 0. maxQ = 80.

For example,
load[0] + load[3] + load[6] + load[1] + load[9] + load[7] = 73, if continue add load[5], the total capacity is 89. Exceed the maxQ, in which exceed the maximum vehicle capacity per day. So, i need to include new value either 1 or 2 after value 7.

Then, choose minimum distance between
7 to 1: 59.09280303, or
7 to 2: 4.633712121

The minimum distance is number 2. Then insert 2 after 7. Then insert 0 after 2.

The route should be:
0 3 6 1 9 7 2 0 5 0

Before going back to end number which is 0, I need to visit 1 or 2 to emptied the vehicle. Then, choose minimum distance between
5 to 1: 6.618371212, or
5 to 2: 59.83579545

The minimum distance is from 5 to 1. Then insert 1 after 5

The final route or the solution should be:
0 3 6 1 9 7 2 0 5 1 0

Hopefully, u understand what i'm trying to explain.

[yat89]

Hi Duthomhas,

I also am confused. It looks like you are doing some kind of weighted traveling salesman problem, but the constraints (Q?) mean nothing to me.

Sorry, actually its hard for me to explain it in words. Yeah, it quite similar to weighted traveling salesman problem. But, specifically it about vehicle routing problem in waste collection.

That is the reason i need to include 1 or 2. 1 and 2 is the place to dispose waste.

Q is the vehicle capacity constraint. Each time capacity of vehicle reach to Q, need to visit disposal, to emptied the vehicle.

maxQ is the max vehicle capacity per day. If the vehicle reach the maxQ, need to visit disposal then going back to 0.

[Duthomhas]

Ah, that makes a lot more sense.

Routes[route][stops] is a list of stops to make for any given route.
Distances[u][v] is a lookup matrix for distance from (stop u)→(stop v).
Loads[u][1] is the known amount of waste to be obtained from any (stop u).

Is this a homework? Did you design the input files or did your professor/employer?
(Because both could use some refinement, if that is acceptable, otherwise we’ll work with what you are given.)

[edit] BTW, this has absolutely nothing to do with traveling salesman. [/edit]

[yat89]

Is this a homework?

Yes this is a part of my homework.

Did you design the input files or did your professor/employer?

Actually i need to test it on some benchmark dataset. But, my professor always ask to test on the small data first, if its work then test on the bigger data. So, i just design my own data for testing purpose.

I had done other function, but stuct here.

[Duthomhas]

Ok. Lines 90 and 91 are tripping you up.

I am still a little confused about QMax. If a truck reaches capacity Q, then goes and dumps his load, his current load (q) is again starting at zero.

What I am saying is that QMax is mis-named. It is more like Q2nd_trip_plus_first_trip, because that is how you are collecting it from the data.)

In any case, what this means is that QMax - Q = 30 is the maximum capacity for the second trip, not 50. Why? Shouldn’t the Q be the same for every foray into the city to collect trash? (The third trip doesn’t seem to verify against maximum load, Q.)


What exactly does your assignment say?
Is it something like:

You are given a route with stops.
Every time the truck hits capacity it needs to go and dump its load.
Insert the times that it needs to dump into the route.
Choose from the closest dumping station.

?

Sorry, I’m not stringing you along, but the design of your algorithm depends entirely on how this actually works...

[yat89]

Q is the vehicle capacity.
maxQ is the maximum vehicle capacity per day.

For example,

In easier word, the vehicle start from depot 0, the collect waste from 3, 4, 5. Then when the vehicle reach the vehicle capacity limit which is Q. The driver my dump all wastes at disposal and continue collecting other wastes from other customer. If the vehicle is fully loaded, again must visit disposal to dump all the collected wastes. Before return back to depot 0, they must visit the disposal site to emptied the vehicles.

Meanwhile, maxQ is the max vehicle capacity per day. The concept is similar as above, start from depot 0, collect waste from customer 3, 4, 5 and so on. When the total capacity reach the max vehicle capacity per day which is maxQ. The driver need to dump all the wastes carried by her at the disposal site and return back to the depot 0. Other vehicle will continue collecting the waste.

For example for bigger data,
0 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 0

For example after collect waste from customer 3, 4, 5, 6, 7. The vehicle capacity is 50. Then must be emptied at disposal site. As example, disposal 1 is nearest disposal from 7. After the vehicle emptied, continue collecting waste from 8, 9, 10. Then reach max allowed capacity per day. The driver need to emptied the vehicle at nearest disposal. For example, disposal 2. After disposed it, the vehicle need to return to the depot. The next vehicle will continue collect from 11, 12, 13, 14, 15 until reach vehicle capacity limit Q. Dispose waste at nearest disposal 1 and continue collect from others 15, 16, 17, 18, 19, 20, 21, 22 until reach maximum vehicle capacity per day. Then emptied the vehicle at disposal 2 before return back to depot 0.

So, the solution for example should be:
0 3 4 5 6 7 1 8 9 10 2 0 11 12 13 14 1 15 16 17 18 19 20 21 22 2 0

[yat89]

Hi Duthomhas
Could you help me. I'm trying to fulfilled the first constraint first before adding the second constraint.

Which is when the vehicles are fully loaded during the collection, they need to be emptied at one of the nearest disposal facility (either 1 or 2) before continuing collecting waste from other customers.

I'm trying to write the coded by sum up all the load generated by the customers, and if the collected waste meets the vehicle capacity limit which is Q, I need to visit the nearby landfill to empty the vehicle before continue collecting waste from the customer.

#include <iostream> 
#include <vector> 
#include <iomanip>	// setw
#include <fstream>

using namespace std;

const int routeRow = 3;	// Route row / population size
const int routeCol = 7;	// Route column
const int m = 13;	// Number of nodes / stop
const int dataCol = 2;	// Data column
long double Q = 50.0;	// Vehicle capacity 
long double maxQ = 80.0;	// Max vehicle capacity per day

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

int i, j;

int main()
{
	// Input file
	ifstream inpData("myData.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++)
		{
			inpData >> 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 << setw(3) << 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
	inpData.close();
	inpRoute.close();
	inpDistance.close();

	 // Route rows
        for(i = 0; i < routeRow; i ++) 
	{
               double currentQ = 0;
		//double totalQ = 0;
		
		// Route cols
                for(j = 0; j < routeCol; j++) 
	        {
			currentQ += load[route[i][j]];
			//totalQ += load[route[i][j]];

			if (currentQ <= Q)// && (totalQ <= maxQ)
			{
				vector<int>::iterator it = route[i].insert(route[i].begin(), 1);
			}
                }
       }
		
	// Displaying solution
	for (int i = 0; i < routeRow; i++)
	{
		for (int j = 0; j < route[i].size(); j++)
		{
			cout << setw(3) << route[i][j] << ' ';
		}
		cout << endl;
	}
	cout << endl;

	system("pause");
	return 0;
}

But, when i run it, the code give me the wrong answer:
1 1 1 1 1 1 1 0 3 6 9 7 5 0
1 1 1 1 1 1 1 0 4 12 8 10 3 0
1 1 1 1 1 1 1 0 12 11 6 4 7 0

Is it the way I insert it is wrong. Could you help me.. Sorry for troubling you.

[Duthomhas]

Yeah, I was afraid the Q constraints were going to be stupid like that. (It is a “shortcut”, meaning it makes life harder.)

What you are doing involves something called the partial sum. It works like this:
Given an array of values:

    { 1, 7, 3, 42, -19, 0, 8 }

You generate a running count of the sum of all the values so far. So:

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

(0) ┌───┬───┬───┬───┬───┬───┬───┐ │ 1 │ 7 │ 3 │ 42│-19│ 0 │ 8 │ └───┴───┴───┴───┴───┴───┴───┘ ↓ ┌───┬───┬───┬───┬───┬───┬───┐ │ 1 │ │ │ │ │ │ │ └───┴───┴───┴───┴───┴───┴───┘ (1) ┌───┬───┬───┬───┬───┬───┬───┐ │ 1 │ 7 │ 3 │ 42│-19│ 0 │ 8 │ └───┴───┴───┴───┴───┴───┴───┘ ↓ ┌───┬───┬───┬───┬───┬───┬───┐ │ 1 │ 8 │ │ │ │ │ │ └───┴───┴───┴───┴───┴───┴───┘ (2) ┌───┬───┬───┬───┬───┬───┬───┐ │ 1 │ 7 │ 3 │ 42│-19│ 0 │ 8 │ └───┴───┴───┴───┴───┴───┴───┘ ↓ ┌───┬───┬───┬───┬───┬───┬───┐ │ 1 │ 8 │ 11│ │ │ │ │ └───┴───┴───┴───┴───┴───┴───┘ (3) ┌───┬───┬───┬───┬───┬───┬───┐ │ 1 │ 7 │ 3 │ 42│-19│ 0 │ 8 │ └───┴───┴───┴───┴───┴───┴───┘ ↓ ┌───┬───┬───┬───┬───┬───┬───┐ │ 1 │ 8 │ 11│ 53│ │ │ │ └───┴───┴───┴───┴───┴───┴───┘

(4) ┌───┬───┬───┬───┬───┬───┬───┐ │ 1 │ 7 │ 3 │ 42│-19│ 0 │ 8 │ └───┴───┴───┴───┴───┴───┴───┘ ↓ ┌───┬───┬───┬───┬───┬───┬───┐ │ 1 │ 8 │ 11│ 53│ 44│ │ │ └───┴───┴───┴───┴───┴───┴───┘ (5) ┌───┬───┬───┬───┬───┬───┬───┐ │ 1 │ 7 │ 3 │ 42│-19│ 0 │ 8 │ └───┴───┴───┴───┴───┴───┴───┘ ↓ ┌───┬───┬───┬───┬───┬───┬───┐ │ 1 │ 8 │ 11│ 53│ 44│ 44│ │ └───┴───┴───┴───┴───┴───┴───┘ (6) ┌───┬───┬───┬───┬───┬───┬───┐ │ 1 │ 7 │ 3 │ 42│-19│ 0 │ 8 │ └───┴───┴───┴───┴───┴───┴───┘ ↓ ┌───┬───┬───┬───┬───┬───┬───┐ │ 1 │ 8 │ 11│ 53│ 44│ 44│ 52│ └───┴───┴───┴───┴───┴───┴───┘ Hence, the final array of partial sums is: ┌───┬───┬───┬───┬───┬───┬───┐ │ 1 │ 8 │ 11│ 53│ 44│ 44│ 52│ └───┴───┴───┴───┴───┴───┴───┘

Write a function to compute the partial sum.

Your first route is

    0 3 6 9 7 5 0

Transform that to a (new) vector of the corresponding rates:

    0 14 15 26 18 16 0

Apply the partial sum:

    0 14 29 55 73 89 89

Now you just need to find the first a_n ≥ Q.

    0 14 29 55 73 89 89
            ^here is where a_n ≥ Q; (n == 3)

Conveniently, it is also where you should insert a new value, for the station closest to where you are.

Write a function to find this insertion point.

Once you find it, you can modify both your route vector AND the partial sum vector.
  • Insert the closest dump (1 or 2) in your route vector.
  • Insert a zero in your partial sum vector.

Now you can repeat for the second Q.
At this point, your main() should look something like this:

int main()
{
  // Data
  vector <vector <int> > routes;
  vector <vector <int> > loads;
  vector <vector <double> > distance_lookup;

  stuff to load data goes here

  // For each route
  for (auto route : routes)
  {
    vector <int> sums;

    // Transform route → loads for each stop in route
    for (int n = 0; n < route.size(); n++)
      sums.push_back( loads[ route[n] ] );

    // Compute the partial sum
    partial_sum( sums.begin(), sums.end() );

    // Find where to insert the first trip to a dump
    auto n = find_insert_point( route, Q );

    // Modify!
    route.insert( next( route.begin(), n ), closest_point_to( route[n-1] ) );
    sums .insert( next( sums .begin(), n ), 0 );

    // Find where to insert the second trip to a dump
    n = find_insert_point( route, maxQ );

    // Modify!
    route.insert( next( route.begin(), n ), 0 );
    route.insert( next( route.begin(), n ), closest_point_to( route[n-1] ) );

    // Now all we need to do is visit the dump before the final location
    route.insert( prev( route.end() ), closest_point_to( *prev( route.end(), 2 ) );

    // Print the modified route:
    copy( route.begin(), route.end(), ostream_iterator <int> ( cout, " " ) );
    cout << "\n";
  }

Hint: Check out the Standard Library:
  • numeric (http://www.cplusplus.com/reference/numeric/)
  • algorithm (http://www.cplusplus.com/reference/algorithm/)

Hope this helps.

[edit] Fixed a typo.

[yat89]

Hi Duthomhas, thanks a lot for your help.. I will try to modify this code based on the problem. Hopefully, I would get the accurate/right solution.

Before that, I would like to ask a few things.

// Modify!
    route.insert( next( route.begin(), n ), closest_point_to( route[n-1] ) );
    sums .insert( next( sums .begin(), n ), 0 );

What do you mean by closest_point_to( route[n-1] ).

Why [n-1]?

Do i need to create 1 more function to find the closest disposal from the last visited customer ? If yes, how can I do that. Sorry for troubling you again and again.

[Duthomhas]

n is the element that you need to insert the dump-trip before.
So the element to find the closest dump to is (n-1). Right?

You will have to answer the last question yourself. Given a location in the city, do you need more than one function to find the closest dump to that location? Even if the location is different each time you use the function?


BTW, all the stuff I write, like “closest_point_to” is part of my description. You should find a way to think about and name things yourself. Perhaps “closest_dump_to” or “find_dump_closest_to” or even (I used this in my own code) “closest”, LOL.

[yat89]

n is the element that you need to insert the dump-trip before.
So the element to find the closest dump to is (n-1). Right?

Yes, i think i could understand this. The element to find the closest dump is (n-1).

You will have to answer the last question yourself. Given a location in the city, do you need more than one function to find the closest dump to that location? Even if the location is different each time you use the function?

But, what is playing in my mind is there are two disposal sites. After visit the last customer, the driver need to choose to go to dump 1 or dump 2, which is more closer to the last visited customer.

Here is where the disposal to be insert right?
route.insert( next( route.begin(), n ), closest_point_to( route[n-1] ) )

But, how they identify where to dump the waste? either disposal 1 or 2.

Do i need to create one more function to choose which disposal to visit from the last visited customer.

Oh i'm really sorry for troubling by asking so much question. Oh. Now, suddenly I became blurred.

I think I have to start it from the beginning. Compute the partial sum and find the insertion point.

[Duthomhas]

Er, your brain is too fuzzy. Get some sleep. (I’m going to do the same myself right now.)