Debian Codegraph @

SYMPHONY/Applications/VRP/src/Heuristics/tsp_ins_rout.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 "sym_constants.h"
18 #include "tsp_ins_rout.h"
19 #include "vrp_const.h"
20 #include "compute_cost.h"
21 #include <string.h>
22 /*-------------------------------------------------------------------------*\
23 | These subroutines are used to construct TSp tours usinf simple insertion |
24 | heuristics. The tours are then used in route first - cluster second |
25 | algorithms |
26 \*-------------------------------------------------------------------------*/
27
28 /*===========================================================================*/
29
30 int tsp_farthest_ins_from_to(heur_prob *p, _node *tour, int cost, int from_size,
31 int to_size, int starter, neighbor *nbtree,
32 int *intour, int *last)
33 {
34 int farnode, size;
35
36 for (size = from_size; size < to_size; size++){
37 farnode = tsp_farthest(nbtree, intour, last);
38 intour[farnode] = IN_TOUR;
39 cost += tsp_insert_into_tour(p, tour, starter, size, farnode);
40 tsp_fi_insert_edges(p, farnode, nbtree, intour, last);
41 }
42 return(cost);
43 }
44
45 /*===========================================================================*/
46
47 int tsp_nearest_ins_from_to(heur_prob *p, _node *tour, int cost, int from_size,
48 int to_size, int starter, neighbor *nbtree,
49 int *intour, int *last)
50 {
51 int nearnode, size;
52
53 for (size = from_size; size < to_size; size++){
54 nearnode = tsp_closest(nbtree, intour, last);
55 intour[nearnode] = IN_TOUR;
56 cost += tsp_insert_into_tour(p, tour, starter, size, nearnode);
57 tsp_ni_insert_edges(p, nearnode, nbtree, intour, last);
58 }
59 return(cost);
60 }
61
62 /*===========================================================================*/
63
64 int tsp_closest(neighbor *nbtree, int *intour, int *last)
65 {
66 int closest_node;
67 int pos, ch;
68 int cost;
69 neighbor temp;
70
71 /*-----------------------------------------------------------------------*\
72 | This routine deletes the item from the top of the binary tree where the |
73 | distances are stored and adjusts the tree accordingly |
74 \*-----------------------------------------------------------------------*/
75
76 closest_node = nbtree[1].nbor;
77 (void) memcpy ((char *)&temp, (char *)(nbtree+*last), sizeof(neighbor));
78 cost = nbtree[*last].cost;
79 --*last;
80 pos = 1;
81 while ((ch=2*pos) < *last){
82 if (nbtree[ch].cost > nbtree[ch+1].cost)
83 ch++;
84 if (cost <= nbtree[ch].cost)
85 break;
86 intour[nbtree[ch].nbor] = pos;
87 (void) memcpy ((char *)(nbtree+pos),
88 (char *)(nbtree+ch), sizeof(neighbor));
89 pos = ch;
90 }
91 if (ch == *last){
92 if (cost > nbtree[ch].cost){
93 intour[nbtree[ch].nbor] = pos;
94 (void) memcpy ((char *)(nbtree+pos),
95 (char *)(nbtree+ch), sizeof(neighbor));
96 pos=ch;
97 }
98 }
99 intour[temp.nbor] = pos;
100 (void) memcpy ((char *)(nbtree+pos), (char *)&temp, sizeof(neighbor));
101 return(closest_node);
102 }
103
104 /*===========================================================================*/
105
106 void tsp_ni_insert_edges(heur_prob *p, int new_node, neighbor *nbtree, int *intour,
107 int *last)
108 /*-----------------------------------------------------------------------*\
109 | Scan through the edges incident to 'new_node' - the new node in the set. |
110 | If the other end 'i' is in the set, do nothing. |
111 | If the other end is not in nbtree then insert it. |
112 | Otherwise update its distance if necessary: |
113 | If the previous closest point of the set to 'i' is closer then |
114 | 'new_node' then we don't have to do anything, otherwise update. |
115 | (update: the min element is on the top of the tree |
116 | Therefore the insertion and the update parts can be done |
117 | with the same code, not like in fi_insert_edges.) |
118 \*-----------------------------------------------------------------------*/
119
120 {
121 int cost, prevcost;
122 int pos, ch;
123 int i;
124 int vertnum = p->vertnum;
125
126 for (i=0; i<vertnum; i++){
127 if ( intour[i] != IN_TOUR){
128 cost = ICOST(&p->dist, i, new_node);
129 if (intour[i] == NOT_NEIGHBOR){
130 pos = ++(*last);
131 prevcost = cost+1;
132 }else{
133 prevcost = nbtree[pos = intour[i]].cost;
134 }
135 if (prevcost > cost){
136 while ((ch=pos/2) != 0){
137 if (nbtree[ch].cost <= cost)
138 break;
139 intour[nbtree[ch].nbor] = pos;
140 (void) memcpy ((char *)(nbtree+pos),
141 (char *)(nbtree+ch), sizeof(neighbor));
142 pos = ch;
143 }
144 nbtree[pos].nbor = i;
145 nbtree[pos].host = new_node;
146 nbtree[pos].cost = cost;
147 intour[i] = pos;
148 }
149 }
150 }
151 }
152
153 /*===========================================================================*/
154
155 int tsp_farthest(neighbor *nbtree, int *intour, int *last)
156 {
157 int farthest_node;
158 int pos, ch;
159 int cost;
160 neighbor temp;
161
162 /*-----------------------------------------------------------------------*\
163 | This routine deletes the item from the top of the binary tree where the |
164 | distances are stored and adjusts the tree accordingly |
165 \*-----------------------------------------------------------------------*/
166
167 farthest_node = nbtree[1].nbor;
168 (void) memcpy ((char *)&temp, (char *)(nbtree+*last), sizeof(neighbor));
169 cost = nbtree[*last].cost;
170 --*last;
171 pos = 1;
172 while ((ch=2*pos) < *last){
173 if (nbtree[ch].cost < nbtree[ch+1].cost)
174 ch++;
175 if (cost >= nbtree[ch].cost)
176 break;
177 intour[nbtree[ch].nbor] = pos;
178 (void) memcpy ((char *)(nbtree+pos),
179 (char *)(nbtree+ch), sizeof(neighbor));
180 pos = ch;
181 }
182 if (ch == *last){
183 if (cost < nbtree[ch].cost){
184 intour[nbtree[ch].nbor] = pos;
185 (void) memcpy ((char *)(nbtree+pos),
186 (char *)(nbtree+ch), sizeof(neighbor));
187 pos=ch;
188 }
189 }
190 intour[temp.nbor] = pos;
191 (void) memcpy ((char *)(nbtree+pos), (char *)&temp, sizeof(neighbor));
192 return(farthest_node);
193 }
194
195 /*===========================================================================*/
196
197 void tsp_fi_insert_edges(heur_prob *p, int new_node, neighbor *nbtree, int *intour,
198 int *last)
199 /*-----------------------------------------------------------------------*\
200 | Scan through the edges incident to 'new_node' - the new node in the set. |
201 | If the other end 'i' is in the set, do nothing. |
202 | If the other end is not in nbtree then insert it. |
203 | Otherwise update its distance if necessary: |
204 | If the previous closest point of the set to 'i' is closer then |
205 | 'new_node' then we don't have to do anything, otherwise update. |
206 | (update: the max element is on the top of the tree) |
207 \*-----------------------------------------------------------------------*/
208 {
209 int cost;
210 int pos, ch;
211 int i;
212 int vertnum = p->vertnum;
213
214 for (i=0; i<vertnum; i++){
215 if ( intour[i] != IN_TOUR){
216 cost = ICOST(&p->dist, i, new_node);
217 if (intour[i] == NOT_NEIGHBOR){ /* new neighbor, must insert it */
218 pos = ++(*last);
219 while ((ch=pos/2) != 0){
220 if (nbtree[ch].cost >= cost)
221 break;
222 intour[nbtree[ch].nbor] = pos;
223 (void) memcpy ((char *)(nbtree+pos),
224 (char *)(nbtree+ch), sizeof(neighbor));
225 pos = ch;
226 }
227 nbtree[pos].nbor = i;
228 nbtree[pos].host = new_node;
229 nbtree[pos].cost = cost;
230 intour[i] = pos;
231 }else{ /*---- already neighbor, update it if needed ------------*/
232 if (nbtree[pos = intour[i]].cost > cost){
233 while ((ch=2*pos) < *last){
234 if (nbtree[ch].cost < nbtree[ch+1].cost)
235 ch++;
236 if (cost >= nbtree[ch].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 if (ch == *last){
244 if (cost < nbtree[ch].cost){
245 intour[nbtree[ch].nbor] = pos;
246 (void) memcpy ((char *)(nbtree+pos),
247 (char *)(nbtree+ch), sizeof(neighbor));
248 pos=ch;
249 }
250 }
251 nbtree[pos].nbor = i;
252 nbtree[pos].host = new_node;
253 nbtree[pos].cost = cost;
254 intour[i] = pos;
255 } /*---------- end if{ had to be updated } */
256 } /*-------------- end if{ was not neighbor }else{ was neighbor} */
257 } /*------------------ end if ('i' is not in the tour) */
258 } /*---------------------- end for loop for all nodes */
259 }
260
261 /*===========================================================================*/
262
263 int tsp_insert_into_tour(heur_prob *p, _node *tour, int starter, int size,
264 int new_node)
265 {
266 int change = 0, minchange = MAXINT;
267 int i, iminchange = 0;
268 int v0, v1;
269
270 /*-------------------------------------------------------------------------*\
271 | Here we search for the cheapest place to insert the new customer on the |
272 | tour and insert it in that position. Then tour data structures must be |
273 | updated accordingly |
274 \*-------------------------------------------------------------------------*/
275
276 for (i=0, minchange = MAXINT, v1=starter; i<size; i++){
277 v0 = v1;
278 v1 = tour[v0].next;
279 change = (ICOST(&p->dist, v0,new_node) + ICOST(&p->dist, new_node,v1)) - ICOST(&p->dist, v0,v1);
280 if (change < minchange){
281 minchange = change;
282 iminchange = v0;
283 }
284 }
285 v1 = tour[v0 = iminchange].next;
286 tour[new_node].next = v1;
287 tour[v0].next = new_node;
288 return(minchange);
289 }