Page 1 of 1

## 6 Replies - 301 Views - Last Post: 07 February 2018 - 03:43 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'https://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=409171&amp;s=00cf927dca0892664eb20075e57822ca&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 chehab.salah

Reputation: 0
• Posts: 4
• Joined: 07-February 18

Posted 07 February 2018 - 01:41 PM

hello,

I'am new in VRP and C++ but i have a made a simple source code for solving the TSP and i don't know how to add the capacity and time constraints.

here is my source code attached.

[quote name='chehab.salah' date='07 February 2018 - 01:36 PM' timestamp='1518035802' post='2353621']
hello,

I'am new in VRP and C++ but i have a made a simple source code for solving the TSP and i don't know how to add the capacity and time constraints.

here is my source code attached.

```#include <iostream>
#include <math.h>
#include <stdlib.h>
#include <time.h>

using namespace std;

int main()
{
int temp1=0,temp2=0,tempR_1=0,tempR_2=0;

// distance Matrix 2 dimension array
int distances[31][31]= {{ 0, 10, 15, 20, 12, 17, 47, 32, 52, 67, 48, 29, 37, 57, 41, 43, 42, 81, 71, 61, 41, 20, 30, 45, 29, 37, 15, 23, 43, 54, 32 },
/* C1  */{  10,  0, 35, 25,  9, 13, 32, 21, 66, 63, 54, 41, 39, 36, 39, 49, 15, 17, 23, 33, 47, 45, 57, 70, 77, 69, 63, 41, 83, 15, 18 },
/* C2  */{  15, 35,  0, 13, 27, 16, 34, 12, 73, 54, 39, 55, 67, 61, 33, 29, 27, 41, 45, 57, 68, 89, 91, 15, 27, 35, 39, 22, 81, 68, 55 },
/* C3  */{  20, 25, 13,  0,  5, 19, 12, 14, 29, 33, 81, 87, 71, 61, 54, 33, 21, 17, 65, 18, 55, 61, 31, 81, 54, 74, 37, 57, 22, 29, 33 },
/* C4  */{  12,  9, 27,  5,  0, 22, 23, 24, 77, 78, 62, 53, 37, 29, 12, 17, 83, 93, 78, 32, 45, 89, 35, 46, 58, 25, 10, 24, 37, 47, 21 },
/* C5  */{  17, 13, 16, 19, 22, 0,  67, 15, 21, 37, 46, 75, 57, 28, 24, 57, 20, 49, 58, 35, 47, 58, 69, 60, 70, 78, 65, 35, 46, 57, 12 },
/* C6  */{  47, 32, 34, 12, 23, 67, 0,  31, 36, 54, 57, 68, 25, 16, 17, 57, 25, 47, 59, 69, 96, 36, 31, 90, 50, 70, 29, 25, 47, 58, 98 },
/* C7  */{  32, 21, 12, 14, 24, 15, 31,  0, 47, 58, 25, 46, 73, 57, 75, 22, 93, 64, 47, 75, 95, 86, 53, 32, 64, 55, 89, 90, 56, 76, 89 },
/* C8  */{  52, 66, 73, 29, 77, 21, 36, 47,  0, 46, 45, 12, 71, 52, 74, 63, 52, 92, 79, 74, 82, 83, 94, 85, 99, 23, 74, 89, 28, 94, 62 },
/* C9  */{  67, 63, 54, 33, 78, 37, 54, 58, 46,  0, 84, 26, 86, 24, 25, 80, 94, 82, 62, 53, 74, 65, 39, 20, 10, 37, 17, 16, 71, 92, 76 },
/* C10 */{  48, 54, 39, 81, 62, 46, 57, 25, 45, 84,  0, 23, 25, 45, 67, 87, 54, 23, 45, 98, 67, 93, 65, 87, 34, 23, 76, 45, 21, 13, 34 },
/* C11 */{  29, 41, 55, 87, 53, 75, 68, 46, 12, 26, 23,  0, 23, 24, 76, 54, 65, 32, 12, 98, 76, 54, 76, 54, 37, 98, 21, 54, 76, 43, 23 },
/* C12 */{  37, 39, 67, 71, 37, 57, 25, 73, 71, 86, 25, 23,  0, 23, 45, 98, 76, 54, 34, 23, 12, 54, 87, 98, 94, 43, 76, 53, 98, 95, 45 },
/* C13 */{  57, 36, 61, 61, 29, 28, 16, 57, 52, 24, 45, 24, 23,  0, 23, 65, 47, 87, 16, 19, 27, 39, 48, 19, 37, 38, 83, 92, 73, 62, 76 },
/* C14 */{  41, 39, 33, 54, 12, 24, 17, 75, 74, 25, 67, 76, 45, 23,  0, 83, 43, 76, 54, 32, 13, 76, 98, 65, 34, 89, 54, 36, 54, 12, 37 },
/* C15 */{  43, 49, 29, 33, 17, 57, 57, 22, 63, 80, 87, 54, 98, 65, 83,  0, 32, 47, 89, 67, 51, 72, 64, 59, 54, 12, 10, 17, 19, 15, 65 },
/* C16 */{  42, 15, 27, 21, 83, 20, 25, 93, 52, 94, 54, 65, 76, 47, 43, 32,  0, 12, 34, 65, 32, 87, 54, 12, 17, 45, 48, 98, 72, 54, 23 },
/* C17 */{  81, 17, 41, 17, 93, 49, 47, 64, 92, 82, 23, 32, 54, 87, 76, 47, 12,  0, 43, 47, 68, 54, 13, 25, 69, 65, 34, 16, 76, 54, 28 },
/* C18 */{  71, 23, 45, 65, 78, 58, 59, 47, 79, 62, 45, 12, 34, 16, 54, 89, 34, 43,  0, 32, 54, 12, 17, 75, 98, 53, 23, 65, 71, 32, 45 },
/* C19 */{  61, 33, 57, 18, 32, 35, 69, 75, 74, 53, 98, 98, 23, 19, 32, 67, 65, 47, 32,  0, 32, 45, 32, 76, 23, 76, 34, 13, 17, 75, 34 },
/* C20 */{  41, 47, 68, 55, 45, 47, 96, 95, 82, 74, 67, 76, 12, 27, 13, 51, 32, 68, 54, 32,  0, 32, 54, 76, 24, 13, 64, 24, 76, 23, 65 },
/* C21 */{  20, 45, 89, 61, 89, 58, 36, 86, 83, 65, 93, 54, 54, 39, 76, 72, 87, 54, 12, 45, 32,  0, 43, 23, 65, 23, 54, 23, 12, 10, 34 },
/* C22 */{  30, 57, 91, 31, 35, 69, 31, 53, 94, 39, 65, 76, 87, 48, 98, 64, 54, 13, 17, 32, 54, 43,  0, 25, 34, 12, 76, 34, 23, 87, 24 },
/* C23 */{  45, 70, 15, 81, 46, 60, 90, 32, 85, 20, 87, 54, 98, 19, 65, 59, 12, 25, 75, 76, 76, 23, 25,  0, 54, 34, 12, 17, 65, 35, 32 },
/* C24 */{  29, 77, 27, 54, 58, 70, 50, 64, 99, 10, 34, 37, 94, 37, 34, 54, 17, 69, 98, 23, 24, 65, 34, 54,  0, 76, 87, 31, 12, 76, 58 },
/* C25 */{  37, 69, 35, 74, 25, 78, 70, 55, 23, 37, 23, 98, 43, 38, 89, 12, 45, 65, 53, 76, 13, 23, 12, 34, 76,  0, 34, 58, 99, 75, 35 },
/* C26 */{  15, 63, 39, 37, 10, 65, 29, 89, 74, 17, 76, 21, 76, 83, 54, 10, 48, 34, 23, 34, 64, 54, 76, 12, 87, 34,  0, 54, 74, 75, 52 },
/* C27 */{  23, 41, 22, 57, 24, 35, 25, 90, 89, 16, 45, 54, 53, 92, 36, 17, 98, 16, 65, 13, 24, 23, 34, 17, 31, 58, 54,  0, 37, 19, 93 },
/* C28 */{  43, 83, 81, 22, 37, 46, 47, 56, 28, 71, 21, 76, 98, 73, 54, 19, 72, 76, 71, 17, 76, 12, 23, 65, 13, 99, 74, 37,  0, 20, 81 },
/* C29 */{  54, 15, 68, 29, 47, 57, 58, 76, 94, 92, 13, 43, 95, 62, 12, 15, 54, 54, 32, 75, 23, 10, 87, 35, 76, 75, 75, 19, 20,  0, 62 },
/* C30 */{  32, 18, 55, 33, 21, 12, 98, 89, 62, 76, 34, 23, 45, 76, 37, 65, 23, 28, 45, 34, 65, 34, 24, 32, 58, 35, 52, 93, 81, 62,  0 }};

// initial solution
int route[32]={0,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,0};

int k=0,w=0;

srand(time(NULL));

for(int j=1; j<=10; j++)
{

cout<<"--------------------------  iteration number= "<<j<<"  ------------------------"<<endl;

// calculating the total distance for the previous route
int total_dist=0;
for(int i=0;i<32;i++) total_dist = total_dist + distances[route[i]][route[i+1]]; cout<<"last minimum total distance = "<<total_dist<<endl;

// selecting 2 random numbers to use them as random cities

int a=(rand()%30)+1, b=(rand()%30)+1;
cout<<"Random city 1: "<<a<<"        Random city 2: "<<b<<endl;

// changing the route according to the selected random numbers
for(int i=0;i<32;i++)
if (route[i]==a && i!=30)
{
temp1=i; tempR_1=route[temp1+1];
for(int i2=0;i2<32;i2++)  if (route[i2]==B)/>/>/>    temp2=i2; tempR_2=route[temp2];

route[temp1+1]=b;   route[temp2]=tempR_1;

// printing on the screen the new route
cout<<"New route: ";
for(int i=0;i<32;i++)    cout<<route[i]<<"   ";cout<<endl;

// calculating the new distance of the new route generated

int total_dist2=0;
for(int i=0;i<32;i++)    total_dist2 = total_dist2 + distances[route[i]][route[i+1]];
cout<<"new total distance: "<<total_dist2<<endl;

// comparing the generated new distance with the previous one and update the route with the minimum distance of both

if (total_dist2>=total_dist)
{
route[temp1+1]=tempR_1;
route[temp2]=tempR_2;
cout<<endl<<"minimum total distance until now= "<<total_dist<<endl;
}
else
{
cout<<"IMPROVEMENT!! "<<endl<<"minimum total distance until now= "<<total_dist2<<endl;
k++;
}

// printing the updated route

cout<<"best route until now: ";
for(int i=0;i<32;i++)    cout<<route[i]<<"   ";cout<<endl;

}

// ignoring the iterations that have the 30th place as city 1

else if(route[i]==a && i==30)
{
cout<<"iteration ignored"<<endl;
w++;
}

// counting the improvements and the ignored iterations
cout<<"-----  number of the improvements= "<<k<<"  ------- ignored iterations= "<<w<<"--------"<<endl<<endl<<endl;

}
return 0;
}
```

This post has been edited by modi123_1: 07 February 2018 - 01:43 PM
Reason for edit:: In the future use the [code] button in the editor.

Is This A Good Question/Topic? 0

### #2 chehab.salah

Reputation: 0
• Posts: 4
• Joined: 07-February 18

Posted 07 February 2018 - 01:47 PM

Hello, i'am new in VRP and programming and i want to add the capacity and time constraint but i don't know how to do it in C++

here is my source code.

``` #include <iostream>
#include <math.h>
#include <stdlib.h>
#include <time.h>

using namespace std;

int main()
{
int temp1=0,temp2=0,tempR_1=0,tempR_2=0;

// distance Matrix 2 dimension array
int distances[31][31]= {{ 0, 10, 15, 20, 12, 17, 47, 32, 52, 67, 48, 29, 37, 57, 41, 43, 42, 81, 71, 61, 41, 20, 30, 45, 29, 37, 15, 23, 43, 54, 32 },
/* C1  */{  10,  0, 35, 25,  9, 13, 32, 21, 66, 63, 54, 41, 39, 36, 39, 49, 15, 17, 23, 33, 47, 45, 57, 70, 77, 69, 63, 41, 83, 15, 18 },
/* C2  */{  15, 35,  0, 13, 27, 16, 34, 12, 73, 54, 39, 55, 67, 61, 33, 29, 27, 41, 45, 57, 68, 89, 91, 15, 27, 35, 39, 22, 81, 68, 55 },
/* C3  */{  20, 25, 13,  0,  5, 19, 12, 14, 29, 33, 81, 87, 71, 61, 54, 33, 21, 17, 65, 18, 55, 61, 31, 81, 54, 74, 37, 57, 22, 29, 33 },
/* C4  */{  12,  9, 27,  5,  0, 22, 23, 24, 77, 78, 62, 53, 37, 29, 12, 17, 83, 93, 78, 32, 45, 89, 35, 46, 58, 25, 10, 24, 37, 47, 21 },
/* C5  */{  17, 13, 16, 19, 22, 0,  67, 15, 21, 37, 46, 75, 57, 28, 24, 57, 20, 49, 58, 35, 47, 58, 69, 60, 70, 78, 65, 35, 46, 57, 12 },
/* C6  */{  47, 32, 34, 12, 23, 67, 0,  31, 36, 54, 57, 68, 25, 16, 17, 57, 25, 47, 59, 69, 96, 36, 31, 90, 50, 70, 29, 25, 47, 58, 98 },
/* C7  */{  32, 21, 12, 14, 24, 15, 31,  0, 47, 58, 25, 46, 73, 57, 75, 22, 93, 64, 47, 75, 95, 86, 53, 32, 64, 55, 89, 90, 56, 76, 89 },
/* C8  */{  52, 66, 73, 29, 77, 21, 36, 47,  0, 46, 45, 12, 71, 52, 74, 63, 52, 92, 79, 74, 82, 83, 94, 85, 99, 23, 74, 89, 28, 94, 62 },
/* C9  */{  67, 63, 54, 33, 78, 37, 54, 58, 46,  0, 84, 26, 86, 24, 25, 80, 94, 82, 62, 53, 74, 65, 39, 20, 10, 37, 17, 16, 71, 92, 76 },
/* C10 */{  48, 54, 39, 81, 62, 46, 57, 25, 45, 84,  0, 23, 25, 45, 67, 87, 54, 23, 45, 98, 67, 93, 65, 87, 34, 23, 76, 45, 21, 13, 34 },
/* C11 */{  29, 41, 55, 87, 53, 75, 68, 46, 12, 26, 23,  0, 23, 24, 76, 54, 65, 32, 12, 98, 76, 54, 76, 54, 37, 98, 21, 54, 76, 43, 23 },
/* C12 */{  37, 39, 67, 71, 37, 57, 25, 73, 71, 86, 25, 23,  0, 23, 45, 98, 76, 54, 34, 23, 12, 54, 87, 98, 94, 43, 76, 53, 98, 95, 45 },
/* C13 */{  57, 36, 61, 61, 29, 28, 16, 57, 52, 24, 45, 24, 23,  0, 23, 65, 47, 87, 16, 19, 27, 39, 48, 19, 37, 38, 83, 92, 73, 62, 76 },
/* C14 */{  41, 39, 33, 54, 12, 24, 17, 75, 74, 25, 67, 76, 45, 23,  0, 83, 43, 76, 54, 32, 13, 76, 98, 65, 34, 89, 54, 36, 54, 12, 37 },
/* C15 */{  43, 49, 29, 33, 17, 57, 57, 22, 63, 80, 87, 54, 98, 65, 83,  0, 32, 47, 89, 67, 51, 72, 64, 59, 54, 12, 10, 17, 19, 15, 65 },
/* C16 */{  42, 15, 27, 21, 83, 20, 25, 93, 52, 94, 54, 65, 76, 47, 43, 32,  0, 12, 34, 65, 32, 87, 54, 12, 17, 45, 48, 98, 72, 54, 23 },
/* C17 */{  81, 17, 41, 17, 93, 49, 47, 64, 92, 82, 23, 32, 54, 87, 76, 47, 12,  0, 43, 47, 68, 54, 13, 25, 69, 65, 34, 16, 76, 54, 28 },
/* C18 */{  71, 23, 45, 65, 78, 58, 59, 47, 79, 62, 45, 12, 34, 16, 54, 89, 34, 43,  0, 32, 54, 12, 17, 75, 98, 53, 23, 65, 71, 32, 45 },
/* C19 */{  61, 33, 57, 18, 32, 35, 69, 75, 74, 53, 98, 98, 23, 19, 32, 67, 65, 47, 32,  0, 32, 45, 32, 76, 23, 76, 34, 13, 17, 75, 34 },
/* C20 */{  41, 47, 68, 55, 45, 47, 96, 95, 82, 74, 67, 76, 12, 27, 13, 51, 32, 68, 54, 32,  0, 32, 54, 76, 24, 13, 64, 24, 76, 23, 65 },
/* C21 */{  20, 45, 89, 61, 89, 58, 36, 86, 83, 65, 93, 54, 54, 39, 76, 72, 87, 54, 12, 45, 32,  0, 43, 23, 65, 23, 54, 23, 12, 10, 34 },
/* C22 */{  30, 57, 91, 31, 35, 69, 31, 53, 94, 39, 65, 76, 87, 48, 98, 64, 54, 13, 17, 32, 54, 43,  0, 25, 34, 12, 76, 34, 23, 87, 24 },
/* C23 */{  45, 70, 15, 81, 46, 60, 90, 32, 85, 20, 87, 54, 98, 19, 65, 59, 12, 25, 75, 76, 76, 23, 25,  0, 54, 34, 12, 17, 65, 35, 32 },
/* C24 */{  29, 77, 27, 54, 58, 70, 50, 64, 99, 10, 34, 37, 94, 37, 34, 54, 17, 69, 98, 23, 24, 65, 34, 54,  0, 76, 87, 31, 12, 76, 58 },
/* C25 */{  37, 69, 35, 74, 25, 78, 70, 55, 23, 37, 23, 98, 43, 38, 89, 12, 45, 65, 53, 76, 13, 23, 12, 34, 76,  0, 34, 58, 99, 75, 35 },
/* C26 */{  15, 63, 39, 37, 10, 65, 29, 89, 74, 17, 76, 21, 76, 83, 54, 10, 48, 34, 23, 34, 64, 54, 76, 12, 87, 34,  0, 54, 74, 75, 52 },
/* C27 */{  23, 41, 22, 57, 24, 35, 25, 90, 89, 16, 45, 54, 53, 92, 36, 17, 98, 16, 65, 13, 24, 23, 34, 17, 31, 58, 54,  0, 37, 19, 93 },
/* C28 */{  43, 83, 81, 22, 37, 46, 47, 56, 28, 71, 21, 76, 98, 73, 54, 19, 72, 76, 71, 17, 76, 12, 23, 65, 13, 99, 74, 37,  0, 20, 81 },
/* C29 */{  54, 15, 68, 29, 47, 57, 58, 76, 94, 92, 13, 43, 95, 62, 12, 15, 54, 54, 32, 75, 23, 10, 87, 35, 76, 75, 75, 19, 20,  0, 62 },
/* C30 */{  32, 18, 55, 33, 21, 12, 98, 89, 62, 76, 34, 23, 45, 76, 37, 65, 23, 28, 45, 34, 65, 34, 24, 32, 58, 35, 52, 93, 81, 62,  0 }};

// initial solution
int route[32]={0,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,0};

int k=0,w=0;

srand(time(NULL));

for(int j=1; j<=10; j++)
{

cout<<"--------------------------  iteration number= "<<j<<"  ------------------------"<<endl;

// calculating the total distance for the previous route
int total_dist=0;
for(int i=0;i<32;i++) total_dist = total_dist + distances[route[i]][route[i+1]]; cout<<"last minimum total distance = "<<total_dist<<endl;

// selecting 2 random numbers to use them as random cities

int a=(rand()%30)+1, b=(rand()%30)+1;
cout<<"Random city 1: "<<a<<"        Random city 2: "<<b<<endl;

// changing the route according to the selected random numbers
for(int i=0;i<32;i++)
if (route[i]==a && i!=30)
{
temp1=i; tempR_1=route[temp1+1];
for(int i2=0;i2<32;i2++)  if (route[i2]==B)/>/>/>    temp2=i2; tempR_2=route[temp2];

route[temp1+1]=b;   route[temp2]=tempR_1;

// printing on the screen the new route
cout<<"New route: ";
for(int i=0;i<32;i++)    cout<<route[i]<<"   ";cout<<endl;

// calculating the new distance of the new route generated

int total_dist2=0;
for(int i=0;i<32;i++)    total_dist2 = total_dist2 + distances[route[i]][route[i+1]];
cout<<"new total distance: "<<total_dist2<<endl;

// comparing the generated new distance with the previous one and update the route with the minimum distance of both

if (total_dist2>=total_dist)
{
route[temp1+1]=tempR_1;
route[temp2]=tempR_2;
cout<<endl<<"minimum total distance until now= "<<total_dist<<endl;
}
else
{
cout<<"IMPROVEMENT!! "<<endl<<"minimum total distance until now= "<<total_dist2<<endl;
k++;
}

// printing the updated route

cout<<"best route until now: ";
for(int i=0;i<32;i++)    cout<<route[i]<<"   ";cout<<endl;

}

// ignoring the iterations that have the 30th place as city 1

else if(route[i]==a && i==30)
{
cout<<"iteration ignored"<<endl;
w++;
}

// counting the improvements and the ignored iterations
cout<<"-----  number of the improvements= "<<k<<"  ------- ignored iterations= "<<w<<"--------"<<endl<<endl<<endl;

}
return 0;
}

```

### #3 Skydiver

• Code herder

Reputation: 6166
• Posts: 21,273
• Joined: 05-May 12

Posted 07 February 2018 - 02:03 PM

Before going too far with modifying your existing code, you have several cases of accessing your arrays out of bounds. For example line 59.

### #4 chehab.salah

Reputation: 0
• Posts: 4
• Joined: 07-February 18

Posted 07 February 2018 - 02:26 PM

hello, i can't got your point since am new in programming, do you see that there is a solution??
can you clarify more

This post has been edited by Skydiver: 07 February 2018 - 03:06 PM
Reason for edit:: Removed unnecessary quote. No need to quote the post above yours.

### #5 Skydiver

• Code herder

Reputation: 6166
• Posts: 21,273
• Joined: 05-May 12

Posted 07 February 2018 - 03:03 PM

Arrays in C and C++ are zero based. Given:
```int myarray[10];

```

has only valid indices of myarray[0] to myarray[9].

Look at line 59. Your loop has i ranging from 0 to 31. Notice the code that accesses route[i+1]. 31+1 == 32. Now check to see how you declared your route array.

Also, there is no need to quote the post above yours. Just use the big Reply button or the Fast Reply area.

### #6 chehab.salah

Reputation: 0
• Posts: 4
• Joined: 07-February 18

Posted 07 February 2018 - 03:09 PM

i have made it this way and it gave me a solution when i run it , but i don't know exactly what should i modify in the code to add time and capacity constraint. can you modify that?

### #7 Skydiver

• Code herder

Reputation: 6166
• Posts: 21,273
• Joined: 05-May 12

Posted 07 February 2018 - 03:43 PM

By going out of bounds on an array, you are invoking undefined behavior. Things may work. It may work weirdly. It may crash. That's the wonders of undefined behavior.

No, we cannot modify the code for you. That would be us doing your work for you and goes against rule #1 of this site.

We can guide you towards a solution.

If you were solving this problem on paper, how would you add those constraints? Talk it through. Write out an outline. See how that outline jives with your existing code.