| 1 |
/*===========================================================================*/ |
| 2 |
/* */ |
| 3 |
/* This file is part of a demonstration application for use with the */ |
| 4 |
/* SYMPHONY Branch, Cut, and Price Library. This application is a solver for */ |
| 5 |
/* the Vehicle Routing Problem and the Traveling Salesman Problem. */ |
| 6 |
/* */ |
| 7 |
/* This application was developed by Ted Ralphs ([email protected]) */ |
| 8 |
/* This file was modified by Ali Pilatin January, 2005 ([email protected]) */ |
| 9 |
/* */ |
| 10 |
/* (c) Copyright 2000-2005 Ted Ralphs. All Rights Reserved. */ |
| 11 |
/* */ |
| 12 |
/* This software is licensed under the Eclipse Public License. Please see */ |
| 13 |
/* accompanying file for terms. */ |
| 14 |
/* */ |
| 15 |
/*===========================================================================*/ |
| 16 |
|
| 17 |
#include "exchange2.h" |
| 18 |
#include <stdio.h> |
| 19 |
void exchange2(int parent, heur_prob *p) |
| 20 |
{ |
| 21 |
printf("\nIn exchange2....\n\n"); |
| 22 |
_node *tour; |
| 23 |
int numroutes; |
| 24 |
int mytid, info, r_bufid; |
| 25 |
int prev_node1, cur_node1, next_node1; |
| 26 |
int prev_node2, cur_node2, next_node2; |
| 27 |
int max_prev1 = 0, max_prev2 = 0, max_next1 = 0, max_next2 = 0; |
| 28 |
int max_node1 = 0, max_node2 = 0; |
| 29 |
best_tours *tours; |
| 30 |
int max_savings = 0, savings; |
| 31 |
int max_route1 = 0, max_route2 = 0, cur_route1, cur_route2; |
| 32 |
route_data *route_info; |
| 33 |
int cont = 1, capacity; |
| 34 |
int *demand; |
| 35 |
double t=0; |
| 36 |
|
| 37 |
(void) used_time(&t); |
| 38 |
|
| 39 |
mytid = pvm_mytid(); |
| 40 |
|
| 41 |
tours = p->cur_tour = (best_tours *) calloc (1, sizeof(best_tours)); |
| 42 |
|
| 43 |
/*-----------------------------------------------------------------------*\ |
| 44 |
| Receive the starting tour | |
| 45 |
\*-----------------------------------------------------------------------*/ |
| 46 |
|
| 47 |
PVM_FUNC(r_bufid, pvm_recv(-1, EXCHANGE_HEUR_TOUR)); |
| 48 |
PVM_FUNC(info, pvm_upkbyte((char *)tours, sizeof(best_tours), 1)); |
| 49 |
tour = p->cur_tour->tour = (_node *) calloc (p->vertnum, sizeof(_node)); |
| 50 |
PVM_FUNC(info, pvm_upkbyte((char *)tour, (p->vertnum)*sizeof(_node), 1)); |
| 51 |
numroutes = tours->numroutes; |
| 52 |
route_info = tours->route_info |
| 53 |
= (route_data *) calloc (numroutes+1, sizeof(route_data)); |
| 54 |
route_calc(&p->dist, tour, numroutes, tours->route_info, p->demand); |
| 55 |
capacity = p->capacity; |
| 56 |
demand = p->demand; |
| 57 |
|
| 58 |
/*------------------------------------------------------------------------*\ |
| 59 |
| This loop takes every pair of customers that are on different routes and | |
| 60 |
| considers the savings obtained by switching their positions. After | |
| 61 |
| considering all possible switches, the switch that is feasible and | |
| 62 |
| produces the greatest savings is made. This is iterated until no more | |
| 63 |
| savings can be obtained. | |
| 64 |
\*------------------------------------------------------------------------*/ |
| 65 |
|
| 66 |
while (cont){ |
| 67 |
max_savings = 0; |
| 68 |
|
| 69 |
/*----------------------------------------------------------------------*\ |
| 70 |
| In these nested loops, cur_node1 and cur_node2 are the nodes being | |
| 71 |
| considered for switching. prev_node1, prev_node2, next_node1, and | |
| 72 |
| next_node2 are the neighbors of these nodes on their current routes, | |
| 73 |
| which are denoted by cur_route1 and cur_route2. The current best nodes | |
| 74 |
| to switch are held in max_node1 and max_node2. Their neighbors are | |
| 75 |
| denoted max_prev1, max_next, max_prev2, and max_next2 respectively | |
| 76 |
| Since the depot is not included in the node list for the routes, we | |
| 77 |
| must always be sure to include node zero as a neighbor at the beginning| |
| 78 |
| and end of the routes (see comments below) | |
| 79 |
\*----------------------------------------------------------------------*/ |
| 80 |
|
| 81 |
for (cur_route1 = 1; cur_route1 <= numroutes; cur_route1++){ |
| 82 |
for (cur_node1 = route_info[cur_route1].first, prev_node1 = 0, |
| 83 |
next_node1 = tour[cur_node1].next; |
| 84 |
cur_node1 != route_info[cur_route1].last; |
| 85 |
prev_node1 = cur_node1, cur_node1 = tour[cur_node1].next, |
| 86 |
next_node1 = tour[cur_node1].next){ |
| 87 |
for (cur_route2 = cur_route1+1; cur_route2 <= numroutes; cur_route2++){ |
| 88 |
for (cur_node2 = route_info[cur_route2].first, prev_node2 = 0, |
| 89 |
next_node2 = tour[cur_node2].next; |
| 90 |
cur_node2 != route_info[cur_route2].last; |
| 91 |
prev_node2 = cur_node2, cur_node2 = tour[cur_node2].next, |
| 92 |
next_node2 = tour[cur_node2].next){ |
| 93 |
if ((savings = - (ICOST(&p->dist, prev_node1, cur_node2) + |
| 94 |
ICOST(&p->dist, cur_node2, next_node1) + |
| 95 |
ICOST(&p->dist, prev_node2, cur_node1) + |
| 96 |
ICOST(&p->dist, cur_node1, next_node2) - |
| 97 |
ICOST(&p->dist, prev_node1, cur_node1) - |
| 98 |
ICOST(&p->dist, cur_node1, next_node1) - |
| 99 |
ICOST(&p->dist, prev_node2, cur_node2) - |
| 100 |
ICOST(&p->dist, cur_node2, next_node2))) > |
| 101 |
max_savings){ |
| 102 |
if ((route_info[cur_route1].weight - demand[cur_node1] |
| 103 |
+demand[cur_node2] <= capacity) && |
| 104 |
(route_info[cur_route2].weight - demand[cur_node2] |
| 105 |
+demand[cur_node1] <= capacity)){ |
| 106 |
max_savings = savings; |
| 107 |
max_node1 = cur_node1; |
| 108 |
max_node2 = cur_node2; |
| 109 |
max_prev1 = prev_node1; |
| 110 |
max_prev2 = prev_node2; |
| 111 |
max_next1 = next_node1; |
| 112 |
max_next2 = next_node2; |
| 113 |
max_route1 = cur_route1; |
| 114 |
max_route2 = cur_route2; |
| 115 |
} |
| 116 |
} |
| 117 |
} |
| 118 |
|
| 119 |
/*-----------------------------------------------------------------*\ |
| 120 |
| We have now reached the end of cur_route2 and must set next_node2 | |
| 121 |
| to be zero and repeat the inner loop | |
| 122 |
\*-----------------------------------------------------------------*/ |
| 123 |
|
| 124 |
next_node2 = 0; |
| 125 |
if ((savings = - (ICOST(&p->dist, prev_node1, cur_node2) + |
| 126 |
ICOST(&p->dist, cur_node2, next_node1) + |
| 127 |
ICOST(&p->dist, prev_node2, cur_node1) + |
| 128 |
ICOST(&p->dist, cur_node1, next_node2) - |
| 129 |
ICOST(&p->dist, prev_node1, cur_node1) - |
| 130 |
ICOST(&p->dist, cur_node1, next_node1) - |
| 131 |
ICOST(&p->dist, prev_node2, cur_node2) - |
| 132 |
ICOST(&p->dist, cur_node2, next_node2))) > |
| 133 |
max_savings){ |
| 134 |
if ((route_info[cur_route1].weight - demand[cur_node1] |
| 135 |
+demand[cur_node2] <= capacity) && |
| 136 |
(route_info[cur_route2].weight - demand[cur_node2] |
| 137 |
+demand[cur_node1] <= capacity)){ |
| 138 |
max_savings = savings; |
| 139 |
max_node1 = cur_node1; |
| 140 |
max_node2 = cur_node2; |
| 141 |
max_prev1 = prev_node1; |
| 142 |
max_prev2 = prev_node2; |
| 143 |
max_next1 = next_node1; |
| 144 |
max_next2 = next_node2; |
| 145 |
max_route1 = cur_route1; |
| 146 |
max_route2 = cur_route2; |
| 147 |
} |
| 148 |
} |
| 149 |
} |
| 150 |
} |
| 151 |
|
| 152 |
/*---------------------------------------------------------------------*\ |
| 153 |
| We have now reached the end of cur_route1 and must set next_node1 | |
| 154 |
| to be 0 and repeat the outer loop | |
| 155 |
\*---------------------------------------------------------------------*/ |
| 156 |
|
| 157 |
next_node1 = 0; |
| 158 |
for (cur_route2 = cur_route1+1; cur_route2 <= numroutes; cur_route2++){ |
| 159 |
for (cur_node2 = route_info[cur_route2].first, prev_node2 = 0, |
| 160 |
next_node2 = tour[cur_node2].next; |
| 161 |
cur_node2 != route_info[cur_route2].last; |
| 162 |
prev_node2 = cur_node2, cur_node2 = tour[cur_node2].next, |
| 163 |
next_node2 = tour[cur_node2].next){ |
| 164 |
if ((savings = - (ICOST(&p->dist, prev_node1, cur_node2) + |
| 165 |
ICOST(&p->dist, cur_node2, next_node1) + |
| 166 |
ICOST(&p->dist, prev_node2, cur_node1) + |
| 167 |
ICOST(&p->dist, cur_node1, next_node2) - |
| 168 |
ICOST(&p->dist, prev_node1, cur_node1) - |
| 169 |
ICOST(&p->dist, cur_node1, next_node1) - |
| 170 |
ICOST(&p->dist, prev_node2, cur_node2) - |
| 171 |
ICOST(&p->dist, cur_node2, next_node2))) > |
| 172 |
max_savings){ |
| 173 |
if ((route_info[cur_route1].weight - demand[cur_node1] |
| 174 |
+demand[cur_node2] <= capacity) && |
| 175 |
(route_info[cur_route2].weight - demand[cur_node2] |
| 176 |
+demand[cur_node1] <= capacity)){ |
| 177 |
max_savings = savings; |
| 178 |
max_node1 = cur_node1; |
| 179 |
max_node2 = cur_node2; |
| 180 |
max_prev1 = prev_node1; |
| 181 |
max_prev2 = prev_node2; |
| 182 |
max_next1 = next_node1; |
| 183 |
max_next2 = next_node2; |
| 184 |
max_route1 = cur_route1; |
| 185 |
max_route2 = cur_route2; |
| 186 |
} |
| 187 |
} |
| 188 |
} |
| 189 |
next_node2 = 0; |
| 190 |
if ((savings = - (ICOST(&p->dist, prev_node1, cur_node2) + |
| 191 |
ICOST(&p->dist, cur_node2, next_node1) + |
| 192 |
ICOST(&p->dist, prev_node2, cur_node1) + |
| 193 |
ICOST(&p->dist, cur_node1, next_node2) - |
| 194 |
ICOST(&p->dist, prev_node1, cur_node1) - |
| 195 |
ICOST(&p->dist, cur_node1, next_node1) - |
| 196 |
ICOST(&p->dist, prev_node2, cur_node2) - |
| 197 |
ICOST(&p->dist, cur_node2, next_node2))) > |
| 198 |
max_savings){ |
| 199 |
if ((route_info[cur_route1].weight - demand[cur_node1] |
| 200 |
+demand[cur_node2] <= capacity) && |
| 201 |
(route_info[cur_route2].weight - demand[cur_node2] |
| 202 |
+demand[cur_node1] <= capacity)){ |
| 203 |
max_savings = savings; |
| 204 |
max_node1 = cur_node1; |
| 205 |
max_node2 = cur_node2; |
| 206 |
max_prev1 = prev_node1; |
| 207 |
max_prev2 = prev_node2; |
| 208 |
max_next1 = next_node1; |
| 209 |
max_next2 = next_node2; |
| 210 |
max_route1 = cur_route1; |
| 211 |
max_route2 = cur_route2; |
| 212 |
} |
| 213 |
} |
| 214 |
} |
| 215 |
} |
| 216 |
|
| 217 |
if (max_savings){/* If we found any cost saving switches, |
| 218 |
then make the best one */ |
| 219 |
|
| 220 |
/* Update the route costs */ |
| 221 |
|
| 222 |
route_info[max_route1].cost += ICOST(&p->dist, max_prev1, max_node2) + |
| 223 |
ICOST(&p->dist, max_node2, max_next1) - |
| 224 |
ICOST(&p->dist, max_prev1, max_node1) - |
| 225 |
ICOST(&p->dist, max_node1, max_next1); |
| 226 |
route_info[max_route2].cost += ICOST(&p->dist, max_prev2, max_node1) + |
| 227 |
ICOST(&p->dist, max_node1, max_next2) - |
| 228 |
ICOST(&p->dist, max_prev2, max_node2) - |
| 229 |
ICOST(&p->dist, max_node2, max_next2); |
| 230 |
|
| 231 |
/*--------------------------------------------------------------------*\ |
| 232 |
| This is a special case where we need to do the switching a little | |
| 233 |
| differently because the nodes are adjacent in the route lists, even | |
| 234 |
| though they are on different routes. | |
| 235 |
\*--------------------------------------------------------------------*/ |
| 236 |
|
| 237 |
if ((!max_next1) && (!max_prev2) && (max_route2 == max_route1+1)){ |
| 238 |
route_info[max_route1].last = max_node2; |
| 239 |
route_info[max_route2].first = max_node1; |
| 240 |
|
| 241 |
/*-------------------------------------------------------------------*\ |
| 242 |
| If max_next2 or max_prev1 are 0, we must correct their values so | |
| 243 |
| that the correct updates in the data structures are made | |
| 244 |
\*-------------------------------------------------------------------*/ |
| 245 |
|
| 246 |
if (!max_prev1){ |
| 247 |
max_prev1 = route_info[max_route1-1].last; |
| 248 |
route_info[max_route1].first = max_node2; |
| 249 |
} |
| 250 |
if (!max_next2) |
| 251 |
route_info[max_route2].last = max_node1; |
| 252 |
if ((!max_next2) && (max_route2 != numroutes)) |
| 253 |
max_next2 = route_info[max_route2+1].first; |
| 254 |
tour[max_prev1].next = max_node2; |
| 255 |
tour[max_node2].next = max_node1; |
| 256 |
tour[max_node1].next = max_next2; |
| 257 |
} |
| 258 |
else{ |
| 259 |
|
| 260 |
/*-------------------------------------------------------------------*\ |
| 261 |
| Again as above, if any of max_prev1, max_prev2, max_next1, or | |
| 262 |
| max_next2 are zero, these values must be corrected so that the data | |
| 263 |
| structure is updated correctly | |
| 264 |
\*-------------------------------------------------------------------*/ |
| 265 |
|
| 266 |
if (!max_prev1){ |
| 267 |
max_prev1 = route_info[max_route1-1].last; |
| 268 |
route_info[max_route1].first = max_node2; |
| 269 |
} |
| 270 |
if (!max_next1) |
| 271 |
route_info[max_route1].last = max_node2; |
| 272 |
if ((!max_next1) && (max_route1 != numroutes)) |
| 273 |
max_next1 = route_info[max_route1+1].first; |
| 274 |
if (!max_prev2){ |
| 275 |
max_prev2 = route_info[max_route2-1].last; |
| 276 |
route_info[max_route2].first = max_node1; |
| 277 |
} |
| 278 |
if (!max_next2) |
| 279 |
route_info[max_route2].last = max_node1; |
| 280 |
if ((!max_next2) && (max_route2 != numroutes)) |
| 281 |
max_next2 = route_info[max_route2+1].first; |
| 282 |
|
| 283 |
/* Update the tour data structure*/ |
| 284 |
|
| 285 |
tour[max_prev1].next = max_node2; |
| 286 |
tour[max_node2].next = max_next1; |
| 287 |
tour[max_prev2].next = max_node1; |
| 288 |
tour[max_node1].next = max_next2; |
| 289 |
} |
| 290 |
|
| 291 |
/* Update the route_info data structure*/ |
| 292 |
|
| 293 |
route_info[max_route1].weight += demand[max_node2] - demand[max_node1]; |
| 294 |
route_info[max_route2].weight += demand[max_node1] - demand[max_node2]; |
| 295 |
tour[max_node1].route = max_route2; |
| 296 |
tour[max_node2].route = max_route1; |
| 297 |
tours->cost -= max_savings; |
| 298 |
} |
| 299 |
else cont = 0; /* If no more savings found, then exit */ |
| 300 |
} |
| 301 |
|
| 302 |
/*-----------------------------------------------------------------------*\ |
| 303 |
| Transmit the final tour back to the parent | |
| 304 |
\*-----------------------------------------------------------------------*/ |
| 305 |
|
| 306 |
send_tour (tour, tours->cost, numroutes, tours->algorithm, used_time(&t), |
| 307 |
parent, p->vertnum, 0, NULL); |
| 308 |
|
| 309 |
free_heur_prob(p); |
| 310 |
|
| 311 |
} |