Debian Codegraph @

SYMPHONY/Applications/VRP/src/Heuristics/ins_routines.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 <stdlib.h>
18 #include <string.h>
19 #include "sym_constants.h"
20 #include "ins_routines.h"
21 #include "route_heur.h"
22 #include "vrp_const.h"
23 #include "compute_cost.h"
24
25 /*--------------------------------------------------------------------------*\
26 | These routines relate to the construction of the routings for the clusters |
27 | determined by the clustering algorithms |
28 \*--------------------------------------------------------------------------*/
29
30 /*===========================================================================*/
31
32 int farthest_ins_from_to(heur_prob *p, _node *tour, int cost, int from_size,
33 int to_size, int starter, neighbor *nbtree,
34 int *intour, int *last, route_data *route_info,
35 int cur_route)
36 {
37 int farnode, size;
38
39 for (size = from_size; size < to_size; size++){
40 farnode = farthest(nbtree, intour, last);
41 intour[farnode] = IN_TOUR;
42 cost += insert_into_tour(p, tour, starter, size, farnode,
43 route_info, cur_route);
44 fi_insert_edges(p, farnode, nbtree, intour, last, tour, cur_route);
45 }
46 return(cost);
47 }
48
49 /*===========================================================================*/
50
51 int nearest_ins_from_to(heur_prob *p, _node *tour, int cost, int from_size,
52 int to_size, int starter, neighbor *nbtree,
53 int *intour, int *last, route_data *route_info,
54 int cur_route)
55 {
56 int nearnode, size;
57
58 for (size = from_size; size < to_size; size++){
59 nearnode = closest(nbtree, intour, last);
60 intour[nearnode] = IN_TOUR;
61 cost += insert_into_tour(p, tour, starter, size, nearnode,
62 route_info, cur_route);
63 ni_insert_edges(p, nearnode, nbtree, intour, last, tour, cur_route);
64 }
65 return(cost);
66 }
67
68 /*===========================================================================*/
69
70 int closest(neighbor *nbtree, int *intour, int *last)
71 {
72 int closest_node;
73 int pos, ch;
74 int cost;
75 neighbor temp;
76
77 /*-----------------------------------------------------------------------*\
78 | This routine deletes the item from the top of the binary tree where the |
79 | distances are stored and adjusts the tree accordingly |
80 \*-----------------------------------------------------------------------*/
81
82 closest_node = nbtree[1].nbor;
83 (void) memcpy ((char *)&temp, (char *)(nbtree+*last), sizeof(neighbor));
84 cost = nbtree[*last].cost;
85 --*last;
86 pos = 1;
87 while ((ch=2*pos) < *last){
88 if (nbtree[ch].cost > nbtree[ch+1].cost)
89 ch++;
90 if (cost <= nbtree[ch].cost)
91 break;
92 intour[nbtree[ch].nbor] = pos;
93 (void) memcpy ((char *)(nbtree+pos),
94 (char *)(nbtree+ch), sizeof(neighbor));
95 pos = ch;
96 }
97 if (ch == *last){
98 if (cost > nbtree[ch].cost){
99 intour[nbtree[ch].nbor] = pos;
100 (void) memcpy ((char *)(nbtree+pos),
101 (char *)(nbtree+ch), sizeof(neighbor));
102 pos=ch;
103 }
104 }
105 intour[temp.nbor] = pos;
106 (void) memcpy ((char *)(nbtree+pos), (char *)&temp, sizeof(neighbor));
107 return(closest_node);
108 }
109
110 /*===========================================================================*/
111
112 void ni_insert_edges(heur_prob *p, int new_node, neighbor *nbtree, int *intour,
113 int *last, _node *tour, int cur_route)
114
115 /*-----------------------------------------------------------------------*\
116 | Scan through the edges incident to 'new_node' - the new node in the set. |
117 | If the other end 'i' is in the set, do nothing. |
118 | If the other end is not in nbtree then insert it. |
119 | Otherwise update its distance if necessary: |
120 | If the previous closest point of the set to 'i' is closer then |
121 | 'new_node' then we don't have to do anything, otherwise update. |
122 | (update: the min element is on the top of the tree |
123 | Therefore the insertion and the update parts can be done |
124 | with the same code, not like in fi_insert_edges.) |
125 \*-----------------------------------------------------------------------*/
126
127 {
128 int cost, prevcost;
129 int pos, ch;
130 int i;
131 int vertnum = p->vertnum;
132
133 for (i=0; i<vertnum; i++){
134 if (( intour[i] != IN_TOUR) &&
135 ((tour[i].route == cur_route) ||
136 (tour[i].route == 0))){ /* We must check to make sure that the customer
137 we are trying to insert is in the cluster we
138 are routing */
139 cost = ICOST(&p->dist, i, new_node);
140 if (intour[i] == NOT_NEIGHBOR){
141 pos = ++(*last);
142 prevcost = cost+1;
143 }else{
144 prevcost = nbtree[pos = intour[i]].cost;
145 }
146 if (prevcost > cost){
147 while ((ch=pos/2) != 0){
148 if (nbtree[ch].cost <= cost)
149 break;
150 intour[nbtree[ch].nbor] = pos;
151 (void) memcpy ((char *)(nbtree+pos),
152 (char *)(nbtree+ch), sizeof(neighbor));
153 pos = ch;
154 }
155 nbtree[pos].nbor = i;
156 nbtree[pos].host = new_node;
157 nbtree[pos].cost = cost;
158 intour[i] = pos;
159 }
160 }
161 }
162 }
163
164 /*===========================================================================*/
165
166 int farthest(neighbor *nbtree, int *intour, int *last)
167 {
168 int farthest_node;
169 int pos, ch;
170 int cost;
171 neighbor temp;
172
173 /*-----------------------------------------------------------------------*\
174 | This routine deletes the item from the top of the binary tree where the |
175 | distances are stored and adjusts the tree accordingly |
176 \*-----------------------------------------------------------------------*/
177
178 farthest_node = nbtree[1].nbor;
179 (void) memcpy ((char *)&temp, (char *)(nbtree+*last), sizeof(neighbor));
180 cost = nbtree[*last].cost;
181 --*last;
182 pos = 1;
183 while ((ch=2*pos) < *last){
184 if (nbtree[ch].cost < nbtree[ch+1].cost)
185 ch++;
186 if (cost >= nbtree[ch].cost)
187 break;
188 intour[nbtree[ch].nbor] = pos;
189 (void) memcpy ((char *)(nbtree+pos),
190 (char *)(nbtree+ch), sizeof(neighbor));
191 pos = ch;
192 }
193 if (ch == *last){
194 if (cost < nbtree[ch].cost){
195 intour[nbtree[ch].nbor] = pos;
196 (void) memcpy ((char *)(nbtree+pos),
197 (char *)(nbtree+ch), sizeof(neighbor));
198 pos=ch;
199 }
200 }
201 intour[temp.nbor] = pos;
202 (void) memcpy ((char *)(nbtree+pos), (char *)&temp, sizeof(neighbor));
203 return(farthest_node);
204 }
205
206 /*===========================================================================*/
207
208 void fi_insert_edges(heur_prob *p, int new_node, neighbor *nbtree, int *intour,
209 int *last, _node *tour, int cur_route)
210 /*-----------------------------------------------------------------------*\
211 | Scan through the edges incident to 'new_node' - the new node in the set. |
212 | If the other end 'i' is in the set, do nothing. |
213 | If the other end is not in nbtree then insert it. |
214 | Otherwise update its distance if necessary: |
215 | If the previous closest point of the set to 'i' is closer then |
216 | 'new_node' then we don't have to do anything, otherwise update. |
217 | (update: the max element is on the top of the tree) |
218 \*-----------------------------------------------------------------------*/
219
220 {
221 int cost;
222 int pos, ch;
223 int i;
224 int vertnum = p->vertnum;
225
226 for (i=0; i<vertnum; i++){
227 if (( intour[i] != IN_TOUR) &&
228 ((tour[i].route == cur_route) ||
229 (tour[i].route == 0))){ /* We must check to make sure that the customer
230 we are trying to insert is in the cluster we
231 are routing */
232 cost = ICOST(&p->dist, i, new_node);
233 if (intour[i] == NOT_NEIGHBOR){ /* new neighbor, must insert it */
234 pos = ++(*last);
235 while ((ch=pos/2) != 0){
236 if (nbtree[ch].cost >= cost)
237 break;
238 intour[nbtree[ch].nbor] = pos;
239 (void) memcpy ((char *)(nbtree+pos),
240 (char *)(nbtree+ch), sizeof(neighbor));
241 pos = ch;
242 }
243 nbtree[pos].nbor = i;
244 nbtree[pos].host = new_node;
245 nbtree[pos].cost = cost;
246 intour[i] = pos;
247 }else{ /*---- already neighbor, update it if needed ------------*/
248 if (nbtree[pos = intour[i]].cost > cost){
249 while ((ch=2*pos) < *last){
250 if (nbtree[ch].cost < nbtree[ch+1].cost)
251 ch++;
252 if (cost >= nbtree[ch].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 if (ch == *last){
260 if (cost < nbtree[ch].cost){
261 intour[nbtree[ch].nbor] = pos;
262 (void) memcpy ((char *)(nbtree+pos),
263 (char *)(nbtree+ch), sizeof(neighbor));
264 pos=ch;
265 }
266 }
267 nbtree[pos].nbor = i;
268 nbtree[pos].host = new_node;
269 nbtree[pos].cost = cost;
270 intour[i] = pos;
271 } /*---------- end if{ had to be updated } */
272 } /*-------------- end if{ was not neighbor }else{ was neighbor} */
273 } /*------------------ end if ('i' is not in the tour) */
274 } /*---------------------- end for loop for all nodes */
275 }
276
277 /*===========================================================================*/
278
279 int insert_into_tour(heur_prob *p, _node *tour, int starter, int size,
280 int new_node, route_data *route_info, int cur_route)
281 {
282 int change, minchange;
283 int i, iminchange = 0;
284 int v0, v1;
285
286 /*-------------------------------------------------------------------------*\
287 | Here we search for the cheapest place to insert the new customer on the |
288 | tour and insert it in that position. Then tour and route_info data |
289 | structures must be updated accordingly |
290 \*-------------------------------------------------------------------------*/
291
292 for (i=0, minchange = MAXINT, v1=starter; i<size; i++){
293 v0 = v1;
294 v1 = tour[v0].next;
295 change = ICOST(&p->dist, v0,new_node) + ICOST(&p->dist, new_node,v1) - ICOST(&p->dist, v0,v1);
296 if (change < minchange){
297 minchange = change;
298 iminchange = v0;
299 }
300 }
301 v1 = tour[v0 = iminchange].next;
302 tour[new_node].next = v1;
303 tour[v0].next = new_node;
304 if (new_node == 0){
305 route_info[cur_route].last = v0;
306 route_info[cur_route].first = v1;
307 }
308 if (v0 == 0)
309 route_info[cur_route].first = new_node;
310 if (v1 == 0)
311 route_info[cur_route].last = new_node;
312 return(minchange);
313 }
314
315 void starters(heur_prob *p, int *starter, route_data *route_info,
316 int start)
317 {
318 _node *tour;
319 int numroutes, start_pos;
320 int dist;
321 int cur_node = 0, other_node = 0, cust;
322 int cur_route, count;
323
324 /*-------------------------------------------------------------------------*\
325 | This routine computes the starters for the construction of the routings |
326 | of the clusters. For the first trial, the starter is just the node in the |
327 | the cluster that is the farthest away from some other node in the cluster.|
328 | Fpr all other trials, the starter is a random node on the route. |
329 \*-------------------------------------------------------------------------*/
330
331 tour = p->cur_tour->tour;
332 numroutes = p->cur_tour->numroutes;
333
334 route_calc(&p->dist, tour, numroutes, route_info, p->demand);
335
336 for (cur_route = 1; cur_route<=numroutes; cur_route++){
337 count = 0;
338 cur_node = route_info[cur_route-1].last;
339 if (start == FAR_INS){
340 dist = -MAXINT;
341 do{
342 cur_node = tour[cur_node].next;
343 other_node = cur_node;
344 do{
345 other_node = tour[other_node].next;
346 if (cur_route != numroutes)
347 if(other_node == route_info[cur_route+1].first)
348 other_node = 0;
349 if (ICOST(&p->dist, cur_node, other_node) > dist){
350 dist = ICOST(&p->dist, cur_node, other_node);
351 starter[cur_route-1] = cur_node;
352 }
353 }while (other_node);
354 }while (cur_node != route_info[cur_route].last);
355 }
356 else{
357 start_pos = rand()%route_info[cur_route].numcust+1;
358 for (cust = 1; count<start_pos; cust++)
359 if (tour[cust].route == cur_route) count ++;
360 starter[cur_route-1] = cust-1;
361 }
362 }
363 return;
364 }