| 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 <math.h> |
| 18 |
|
| 19 |
#include "sym_constants.h" |
| 20 |
#include "ins_routines2.h" |
| 21 |
#include "sweep.h" |
| 22 |
#include "qsort.h" |
| 23 |
#include "sym_messages.h" |
| 24 |
#include "vrp_const.h" |
| 25 |
#include "sym_proccomm.h" |
| 26 |
#include "compute_cost.h" |
| 27 |
#include "heur_routines.h" |
| 28 |
#include <string.h> |
| 29 |
#include <stdio.h> |
| 30 |
/*------------------------------------------------------------------------*\ |
| 31 |
| These routines are associated with the near_cluster algorithm. They are | |
| 32 |
| very similar to those used for the nearest insert heuristic for the TSP | |
| 33 |
\*------------------------------------------------------------------------*/ |
| 34 |
|
| 35 |
void nearest_ins2(heur_prob *p, _node *tour, route_data *route_info, |
| 36 |
int from_size, int to_size, neighbor *nbtree, |
| 37 |
int *intour, int *last, int *zero_cost) |
| 38 |
{ |
| 39 |
int nearnode, size, host; |
| 40 |
int *demand = p->demand; |
| 41 |
int capacity = p->capacity; |
| 42 |
|
| 43 |
for (size = from_size; size < to_size;){ |
| 44 |
|
| 45 |
/* Get the node nearest to a particular route and its host */ |
| 46 |
|
| 47 |
nearnode = closest2(nbtree, intour, last, &host); |
| 48 |
|
| 49 |
/*--------------------------------------------------------------*\ |
| 50 |
| Check the feasibility of inserting this node on its host route | |
| 51 |
| If it is feasible, insert it. If not, get a new host for that | |
| 52 |
| node and add it back into the binary tree | |
| 53 |
\*--------------------------------------------------------------*/ |
| 54 |
|
| 55 |
if (route_info[tour[host].route].weight + demand[nearnode] |
| 56 |
<= capacity){ |
| 57 |
intour[nearnode] = IN_TOUR; |
| 58 |
tour[nearnode].route = tour[host].route; |
| 59 |
route_info[tour[nearnode].route].cost += insert_into_tour2 |
| 60 |
(p, tour, nearnode, route_info); |
| 61 |
ni_insert_edges2(p, nearnode, nbtree, intour, last, tour, route_info); |
| 62 |
size++; |
| 63 |
} |
| 64 |
else{ |
| 65 |
intour[nearnode] = NOT_NEIGHBOR; |
| 66 |
new_host2(p, nearnode, nbtree, intour, last, tour, route_info, zero_cost); |
| 67 |
} |
| 68 |
} |
| 69 |
return; |
| 70 |
} |
| 71 |
|
| 72 |
/*===========================================================================*/ |
| 73 |
|
| 74 |
int closest2(neighbor *nbtree, int *intour, int *last, int *host) |
| 75 |
{ |
| 76 |
int closest_node; |
| 77 |
int pos, ch; |
| 78 |
int cost; |
| 79 |
neighbor temp; |
| 80 |
|
| 81 |
/*-----------------------------------------------------------------------*\ |
| 82 |
| This routine deletes the item from the top of the binary tree where the | |
| 83 |
| distances are stored and adjusts the tree accordingly | |
| 84 |
\*-----------------------------------------------------------------------*/ |
| 85 |
|
| 86 |
closest_node = nbtree[1].nbor; |
| 87 |
*host = nbtree[1].host; |
| 88 |
(void) memcpy ((char *)&temp, (char *)(nbtree+*last), sizeof(neighbor)); |
| 89 |
cost = nbtree[*last].cost; |
| 90 |
--*last; |
| 91 |
pos = 1; |
| 92 |
while ((ch=2*pos) < *last){ |
| 93 |
if (nbtree[ch].cost > nbtree[ch+1].cost) |
| 94 |
ch++; |
| 95 |
if (cost <= nbtree[ch].cost) |
| 96 |
break; |
| 97 |
intour[nbtree[ch].nbor] = pos; |
| 98 |
(void) memcpy ((char *)(nbtree+pos), |
| 99 |
(char *)(nbtree+ch), sizeof(neighbor)); |
| 100 |
pos = ch; |
| 101 |
} |
| 102 |
if (ch == *last){ |
| 103 |
if (cost > nbtree[ch].cost){ |
| 104 |
intour[nbtree[ch].nbor] = pos; |
| 105 |
(void) memcpy ((char *)(nbtree+pos), |
| 106 |
(char *)(nbtree+ch), sizeof(neighbor)); |
| 107 |
pos=ch; |
| 108 |
} |
| 109 |
} |
| 110 |
intour[temp.nbor] = pos; |
| 111 |
(void) memcpy ((char *)(nbtree+pos), (char *)&temp, sizeof(neighbor)); |
| 112 |
return(closest_node); |
| 113 |
} |
| 114 |
|
| 115 |
/*===========================================================================*/ |
| 116 |
|
| 117 |
void ni_insert_edges2(heur_prob *p, int new_node, neighbor *nbtree, int *intour, |
| 118 |
int *last, _node *tour, route_data *route_info) |
| 119 |
|
| 120 |
/*-----------------------------------------------------------------------*\ |
| 121 |
| Scan through the edges incident to 'new_node' - the new node in the set. | |
| 122 |
| If the other end 'i' is in the set, do nothing. | |
| 123 |
| If the other end is not in nbtree then insert it. | |
| 124 |
| Otherwise update its distance if necessary: | |
| 125 |
| If the previous closest point of the set to 'i' is closer then | |
| 126 |
| 'new_node' then we don't have to do anything, otherwise update. | |
| 127 |
| (update: the min element is on the top of the tree | |
| 128 |
| Therefore the insertion and the update parts can be done | |
| 129 |
| with the same code, not like in fi_insert_edges.) | |
| 130 |
\*-----------------------------------------------------------------------*/ |
| 131 |
|
| 132 |
{ |
| 133 |
int cost, prevcost; |
| 134 |
int pos, ch; |
| 135 |
int i; |
| 136 |
int vertnum = p->vertnum; |
| 137 |
int *demand = p->demand; |
| 138 |
int capacity = p->capacity; |
| 139 |
|
| 140 |
for (i=1; i<vertnum; i++){ |
| 141 |
if ((intour[i] != IN_TOUR) && |
| 142 |
(demand[i]+route_info[tour[new_node].route].weight<=capacity)){ |
| 143 |
cost = ICOST(&p->dist, i, new_node); |
| 144 |
if (intour[i] == NOT_NEIGHBOR){ |
| 145 |
pos = ++(*last); |
| 146 |
prevcost = cost+1; |
| 147 |
}else{ |
| 148 |
prevcost = nbtree[pos = intour[i]].cost; |
| 149 |
} |
| 150 |
if (prevcost > cost){ |
| 151 |
while ((ch=pos/2) != 0){ |
| 152 |
if (nbtree[ch].cost <= cost) |
| 153 |
break; |
| 154 |
intour[nbtree[ch].nbor] = pos; |
| 155 |
(void) memcpy ((char *)(nbtree+pos), |
| 156 |
(char *)(nbtree+ch), sizeof(neighbor)); |
| 157 |
pos = ch; |
| 158 |
} |
| 159 |
nbtree[pos].nbor = i; |
| 160 |
nbtree[pos].host = new_node; |
| 161 |
nbtree[pos].cost = cost; |
| 162 |
intour[i] = pos; |
| 163 |
} |
| 164 |
} |
| 165 |
} |
| 166 |
} |
| 167 |
|
| 168 |
/*===========================================================================*/ |
| 169 |
|
| 170 |
int insert_into_tour2(heur_prob *p, _node *tour, int new_node, |
| 171 |
route_data *route_info) |
| 172 |
{ |
| 173 |
int change, minchange; |
| 174 |
int iminchange = 0; |
| 175 |
int v0=0, v1; |
| 176 |
int cur_route; |
| 177 |
|
| 178 |
cur_route = tour[new_node].route; |
| 179 |
v1 = route_info[cur_route].first; |
| 180 |
|
| 181 |
/*-------------------------------------------------------------------------*\ |
| 182 |
| Here we search for the cheapest place to insert the new customer on the | |
| 183 |
| tour and insert it in that position. Then tour and route_info data | |
| 184 |
| structures must be updated accordingly | |
| 185 |
\*-------------------------------------------------------------------------*/ |
| 186 |
|
| 187 |
minchange = ICOST(&p->dist, v0, new_node) + ICOST(&p->dist, new_node, v1) - ICOST(&p->dist, v0, v1); |
| 188 |
do{ |
| 189 |
v0 = v1; |
| 190 |
v1 = tour[v0].next; |
| 191 |
change = ICOST(&p->dist, v0,new_node) + ICOST(&p->dist, new_node,v1) - ICOST(&p->dist, v0,v1); |
| 192 |
if (change < minchange){ |
| 193 |
minchange = change; |
| 194 |
iminchange = v0; |
| 195 |
} |
| 196 |
}while (v1); /* check to see if we've reached the end of the route yet */ |
| 197 |
if (iminchange){ |
| 198 |
v1 = tour[v0 = iminchange].next; |
| 199 |
tour[new_node].next = v1; |
| 200 |
tour[v0].next = new_node; |
| 201 |
} |
| 202 |
else{ |
| 203 |
v1 = route_info[cur_route].first; |
| 204 |
tour[new_node].next = v1; |
| 205 |
route_info[cur_route].first = new_node; |
| 206 |
} |
| 207 |
route_info[cur_route].weight += p->demand[new_node]; |
| 208 |
route_info[cur_route].numcust++; |
| 209 |
if (v1 == 0){ |
| 210 |
route_info[cur_route].last = new_node; |
| 211 |
} |
| 212 |
return(minchange); |
| 213 |
} |
| 214 |
|
| 215 |
/*===========================================================================*/ |
| 216 |
|
| 217 |
void new_host2(heur_prob *p, int node, neighbor *nbtree, int *intour, |
| 218 |
int *last, _node *tour, route_data *route_info, int *zero_cost) |
| 219 |
{ |
| 220 |
int cost = 0, prevcost; |
| 221 |
int pos, ch; |
| 222 |
int i; |
| 223 |
int cur_route, r_bufid, parent, info; |
| 224 |
int numroutes = p->cur_tour->numroutes; |
| 225 |
int vertnum = p->vertnum; |
| 226 |
int *demand = p->demand; |
| 227 |
int capacity = p->capacity; |
| 228 |
|
| 229 |
/*-------------------------------------------------------------------------*\ |
| 230 |
| As mentioned earlier, it may be the case that a customer cannot be | |
| 231 |
| inserted on its host route because of capacity restrictions. In this case | |
| 232 |
| we must look for a new host. In the case that a new host cannot be found | |
| 233 |
| (i.e. the customer cannot be inserted on any route), the algorithm fails | |
| 234 |
| and sends the current partial solution back with a cost of zero which | |
| 235 |
| indicates that an error was encountered. The following loop searches all | |
| 236 |
| all customers in the current solution and takes as host the closest | |
| 237 |
| customer to whose route the customer in question can be feasibly added | |
| 238 |
\*-------------------------------------------------------------------------*/ |
| 239 |
|
| 240 |
for (i = 1; i<vertnum; i++){ |
| 241 |
if ((intour[i] == IN_TOUR) && |
| 242 |
(route_info[tour[i].route].weight + demand[node] <= capacity)){ |
| 243 |
cost = ICOST(&p->dist, node, i); |
| 244 |
if (intour[node] == NOT_NEIGHBOR){ |
| 245 |
pos = ++(*last); |
| 246 |
prevcost = cost+1; |
| 247 |
}else{ |
| 248 |
prevcost = nbtree[pos = intour[node]].cost; |
| 249 |
} |
| 250 |
if (prevcost > cost){ |
| 251 |
while ((ch=pos/2) != 0){ |
| 252 |
if (nbtree[ch].cost <= cost) |
| 253 |
break; |
| 254 |
intour[nbtree[ch].nbor] = pos; |
| 255 |
(void) memcpy ((char *)(nbtree+pos), |
| 256 |
(char *)(nbtree+ch), sizeof(neighbor)); |
| 257 |
pos = ch; |
| 258 |
} |
| 259 |
nbtree[pos].nbor = node; |
| 260 |
nbtree[pos].host = i; |
| 261 |
nbtree[pos].cost = cost; |
| 262 |
intour[node] = pos; |
| 263 |
} |
| 264 |
} |
| 265 |
} |
| 266 |
if (!intour[node]){ /* if there is no feasible insertion point, then abort */ |
| 267 |
printf( |
| 268 |
"\n\nError: customer cannot be inserted on any route .... aborting!\n"); |
| 269 |
tour[0].next = route_info[1].first; |
| 270 |
|
| 271 |
/*-----------------------------------------------------------------------*\ |
| 272 |
| This loop points the last node of each route to the first node of the | |
| 273 |
| next route. At the end of this procedure, the last node of each route is| |
| 274 |
| pointing at the depot, which is not what we want. | |
| 275 |
\*-----------------------------------------------------------------------*/ |
| 276 |
for (cur_route = 1; cur_route< numroutes; cur_route++) |
| 277 |
tour[route_info[cur_route].last].next = route_info[cur_route+1].first; |
| 278 |
cost = 0; |
| 279 |
*zero_cost = 1; |
| 280 |
|
| 281 |
parent = pvm_parent(); |
| 282 |
|
| 283 |
/*-----------------------------------------------------------------------*/ |
| 284 |
/* Transmit the partial tour back to the parent with cost zero (error) */ |
| 285 |
/*-----------------------------------------------------------------------*/ |
| 286 |
|
| 287 |
send_tour(tour, cost, numroutes, NEAR_CLUSTER, (double) 0, parent, |
| 288 |
vertnum, 1, route_info); |
| 289 |
|
| 290 |
if ( nbtree ) free ((char *) nbtree); |
| 291 |
if ( intour ) free ((char *) intour); |
| 292 |
|
| 293 |
free_heur_prob(p); |
| 294 |
|
| 295 |
} |
| 296 |
return; |
| 297 |
} |
| 298 |
|
| 299 |
/*===========================================================================*/ |
| 300 |
|
| 301 |
void seeds2(heur_prob *p, int *numroutes, int *intour, neighbor *nbtree) |
| 302 |
{ |
| 303 |
sweep_data *data; |
| 304 |
float depotx, depoty; |
| 305 |
float tempx, tempy; |
| 306 |
int i, cur_route = 0, cur_node; |
| 307 |
int weight = 0; |
| 308 |
int last; |
| 309 |
int vertnum = p->vertnum, farnode; |
| 310 |
int *demand = p->demand; |
| 311 |
int capacity = p->capacity; |
| 312 |
_node *tour = p->cur_tour->tour; |
| 313 |
route_data *route_info = NULL; |
| 314 |
|
| 315 |
/*-------------------------------------------------------------------*\ |
| 316 |
| The algorithm for calculating seed customers first clusters the | |
| 317 |
| customers as in the sweep heuristic and then takes the customer in | |
| 318 |
| each cluster that is farthest from the depot as the seed for a route| |
| 319 |
\*-------------------------------------------------------------------*/ |
| 320 |
|
| 321 |
if (!*numroutes){ |
| 322 |
data = (sweep_data *)calloc(vertnum-1, sizeof(sweep_data)); |
| 323 |
depotx = p->dist.coordx[0]; |
| 324 |
depoty = p->dist.coordy[0]; |
| 325 |
|
| 326 |
/*calculate angles for sorting*/ |
| 327 |
|
| 328 |
for (i=0; i<vertnum-1; i++){ |
| 329 |
tempx = p->dist.coordx[i+1] - depotx; |
| 330 |
tempy = p->dist.coordy[i+1] - depoty; |
| 331 |
data[i].angle = (float) atan2(tempy, tempx); |
| 332 |
if (data[i].angle < 0) data[i].angle += 2*M_PI; |
| 333 |
data[i].cust=i+1; |
| 334 |
} |
| 335 |
|
| 336 |
quicksort(data, vertnum-1); |
| 337 |
|
| 338 |
for (i=0; i<vertnum-1; i++){ |
| 339 |
if ((weight + demand[data[i].cust] <= capacity) && (cur_route)) |
| 340 |
weight += demand[data[i].cust]; |
| 341 |
else{ |
| 342 |
cur_route++; |
| 343 |
weight = demand[data[i].cust]; |
| 344 |
} |
| 345 |
} |
| 346 |
*numroutes = cur_route; |
| 347 |
free((char *) data); |
| 348 |
} |
| 349 |
|
| 350 |
route_info = p->cur_tour->route_info |
| 351 |
= (route_data *) calloc ((*numroutes)+1, sizeof(route_data)); |
| 352 |
|
| 353 |
last = 0; |
| 354 |
intour[0] = IN_TOUR; |
| 355 |
fi_insert_edges2(p, 0, nbtree, intour, &last); |
| 356 |
farnode = farthest2(nbtree, intour, &last); |
| 357 |
intour[farnode] = IN_TOUR; |
| 358 |
fi_insert_edges2 (p, farnode, nbtree, intour, &last); |
| 359 |
tour[farnode].next = 0; |
| 360 |
tour[0].next = farnode; |
| 361 |
farthest_ins_from_to2(p, tour, 2, *numroutes+1, nbtree, intour, &last); |
| 362 |
|
| 363 |
for (cur_route = 1, cur_node = tour[0].next; |
| 364 |
cur_route <= *numroutes; cur_route++, cur_node = tour[cur_node].next){ |
| 365 |
route_info[cur_route].first = route_info[cur_route].last |
| 366 |
= cur_node; |
| 367 |
route_info[cur_route].weight = p->demand[cur_node]; |
| 368 |
route_info[cur_route].numcust++; |
| 369 |
tour[cur_node].route = cur_route; |
| 370 |
route_info[cur_route].cost = 2*ICOST(&p->dist, 0, cur_node); |
| 371 |
} |
| 372 |
} |
| 373 |
|
| 374 |
/*===========================================================================*/ |
| 375 |
|
| 376 |
void farthest_ins_from_to2(heur_prob *p, _node *tour, int from_size, |
| 377 |
int to_size, neighbor *nbtree, |
| 378 |
int *intour, int *last) |
| 379 |
{ |
| 380 |
int farnode, size; |
| 381 |
int minchange, change; |
| 382 |
int i; |
| 383 |
int v0, v1, iminchange = 0; |
| 384 |
|
| 385 |
for (size = from_size; size < to_size; size++){ |
| 386 |
farnode = farthest2(nbtree, intour, last); |
| 387 |
intour[farnode] = IN_TOUR; |
| 388 |
for (i=0, minchange = MAXINT, v1=0; i<size; i++){ |
| 389 |
v0 = v1; |
| 390 |
v1 = tour[v0].next; |
| 391 |
change = (ICOST(&p->dist, v0, farnode) + ICOST(&p->dist, farnode,v1)) |
| 392 |
- ICOST(&p->dist, v0,v1); |
| 393 |
if (change < minchange){ |
| 394 |
minchange = change; |
| 395 |
iminchange = v0; |
| 396 |
} |
| 397 |
} |
| 398 |
v1 = tour[v0 = iminchange].next; |
| 399 |
tour[farnode].next = v1; |
| 400 |
tour[v0].next = farnode; |
| 401 |
fi_insert_edges2(p, farnode, nbtree, intour, last); |
| 402 |
} |
| 403 |
} |
| 404 |
|
| 405 |
/*===========================================================================*/ |
| 406 |
|
| 407 |
int farthest2(neighbor *nbtree, int *intour, int *last) |
| 408 |
{ |
| 409 |
int farthest_node; |
| 410 |
int pos, ch; |
| 411 |
int cost; |
| 412 |
neighbor temp; |
| 413 |
|
| 414 |
/*-----------------------------------------------------------------------*\ |
| 415 |
| This routine deletes the item from the top of the binary tree where the | |
| 416 |
| distances are stored and adjusts the tree accordingly | |
| 417 |
\*-----------------------------------------------------------------------*/ |
| 418 |
|
| 419 |
farthest_node = nbtree[1].nbor; |
| 420 |
(void) memcpy ((char *)&temp, (char *)(nbtree+*last), sizeof(neighbor)); |
| 421 |
cost = nbtree[*last].cost; |
| 422 |
--*last; |
| 423 |
pos = 1; |
| 424 |
while ((ch=2*pos) < *last){ |
| 425 |
if (nbtree[ch].cost < nbtree[ch+1].cost) |
| 426 |
ch++; |
| 427 |
if (cost >= nbtree[ch].cost) |
| 428 |
break; |
| 429 |
intour[nbtree[ch].nbor] = pos; |
| 430 |
(void) memcpy ((char *)(nbtree+pos), |
| 431 |
(char *)(nbtree+ch), sizeof(neighbor)); |
| 432 |
pos = ch; |
| 433 |
} |
| 434 |
if (ch == *last){ if (cost < nbtree[ch].cost){ |
| 435 |
intour[nbtree[ch].nbor] = pos; |
| 436 |
(void) memcpy ((char *)(nbtree+pos), |
| 437 |
(char *)(nbtree+ch), sizeof(neighbor)); |
| 438 |
pos=ch; |
| 439 |
} |
| 440 |
} |
| 441 |
intour[temp.nbor] = pos; |
| 442 |
(void) memcpy ((char *)(nbtree+pos), (char *)&temp, sizeof(neighbor)); |
| 443 |
return(farthest_node); |
| 444 |
} |
| 445 |
|
| 446 |
/*===========================================================================*/ |
| 447 |
|
| 448 |
void fi_insert_edges2(heur_prob *p, int new_node, neighbor *nbtree, int *intour, |
| 449 |
int *last) |
| 450 |
/*-----------------------------------------------------------------------*\ |
| 451 |
| Scan through the edges incident to 'new_node' - the new node in the set. | |
| 452 |
| If the other end 'i' is in the set, do nothing. | |
| 453 |
| If the other end is not in nbtree then insert it. | |
| 454 |
| Otherwise update its distance if necessary: | |
| 455 |
| If the previous closest point of the set to 'i' is closer then | |
| 456 |
| 'new_node' then we don't have to do anything, otherwise update. | |
| 457 |
| (update: the max element is on the top of the tree) | |
| 458 |
\*-----------------------------------------------------------------------*/ |
| 459 |
{ |
| 460 |
int cost; |
| 461 |
int pos, ch; |
| 462 |
int i; |
| 463 |
int vertnum = p->vertnum; |
| 464 |
|
| 465 |
for (i=0; i<vertnum; i++){ |
| 466 |
if ( intour[i] != IN_TOUR){ |
| 467 |
cost = ICOST(&p->dist, i, new_node); |
| 468 |
if (intour[i] == NOT_NEIGHBOR){ /* new neighbor, must insert it */ |
| 469 |
pos = ++(*last); |
| 470 |
while ((ch=pos/2) != 0){ |
| 471 |
if (nbtree[ch].cost >= cost) |
| 472 |
break; |
| 473 |
intour[nbtree[ch].nbor] = pos; |
| 474 |
(void) memcpy ((char *)(nbtree+pos), |
| 475 |
(char *)(nbtree+ch), sizeof(neighbor)); |
| 476 |
pos = ch; |
| 477 |
} |
| 478 |
nbtree[pos].nbor = i; |
| 479 |
nbtree[pos].host = new_node; |
| 480 |
nbtree[pos].cost = cost; |
| 481 |
intour[i] = pos; |
| 482 |
}else{ /*---- already neighbor, update it if needed ------------*/ |
| 483 |
if (nbtree[pos = intour[i]].cost > cost){ |
| 484 |
while ((ch=2*pos) < *last){ |
| 485 |
if (nbtree[ch].cost < nbtree[ch+1].cost) |
| 486 |
ch++; |
| 487 |
if (cost >= nbtree[ch].cost) |
| 488 |
break; |
| 489 |
intour[nbtree[ch].nbor] = pos; |
| 490 |
(void) memcpy ((char *)(nbtree+pos), |
| 491 |
(char *)(nbtree+ch), sizeof(neighbor)); |
| 492 |
pos = ch; |
| 493 |
} |
| 494 |
if (ch == *last){ |
| 495 |
if (cost < nbtree[ch].cost){ |
| 496 |
intour[nbtree[ch].nbor] = pos; |
| 497 |
(void) memcpy ((char *)(nbtree+pos), |
| 498 |
(char *)(nbtree+ch), sizeof(neighbor)); |
| 499 |
pos=ch; |
| 500 |
} |
| 501 |
} |
| 502 |
nbtree[pos].nbor = i; |
| 503 |
nbtree[pos].host = new_node; |
| 504 |
nbtree[pos].cost = cost; |
| 505 |
intour[i] = pos; |
| 506 |
} /*---------- end if{ had to be updated } */ |
| 507 |
} /*-------------- end if{ was not neighbor }else{ was neighbor} */ |
| 508 |
} /*------------------ end if ('i' is not in the tour) */ |
| 509 |
} /*---------------------- end for loop for all nodes */ |
| 510 |
} |