Debian Codegraph @

SYMPHONY/Applications/VRP/src/Heuristics/ins_routines2.c

raw
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 }