Debian Codegraph @

SYMPHONY/Applications/VRP/src/Heuristics/mst_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 <math.h>
18 #include <stddef.h>
19
20 #include "sym_constants.h"
21 #include "mst_ins_rout.h"
22 #include "vrp_const.h"
23 #include "compute_cost.h"
24 #include <string.h>
25 /*--------------------------------------------------------------------------*\
26 | This first routine creates a minimum k-degree-centre-tree based on the |
27 | penalized costs. It first dreates a regular spanning tree and then either |
28 | forces edges adjacent to the depot either in or out in order to make the |
29 | degree of the depot correct. Edges are forced in and out by subtracting or |
30 | adding a constant to all the depot edge costs and forming a new minimum |
31 | spanning tree. |
32 \*--------------------------------------------------------------------------*/
33
34 int make_k_tree(lb_prob *p, int *tree, int *lamda, int k)
35 {
36 int nearnode, size;
37 int host, vertnum = p->vertnum, break_node = 0, new_depot_node = 0, i;
38 int depot_degree = 0, cur_node, prev_node, next_node, max_node = 0;
39 int mu = 0, next_mu, cost = 0, last = 0;
40 int *intree = NULL, max_cost;
41 neighbor *nbtree = NULL;
42
43 while (TRUE){
44 intree = (int *) calloc (vertnum, sizeof(int));
45 nbtree = (neighbor *) calloc (vertnum, sizeof(neighbor ));
46 cost = 0;
47 last = 0;
48 intree[0] = IN_TREE;
49 ni_insert_edges(p, 0, nbtree, intree, &last, lamda, mu);
50
51 /*-----------------------------------------------------------------------*\
52 | Calculate the minimum spanning tree by adding in the nearest node to the|
53 | current tree as long as it does not form a cycle. |
54 \*-----------------------------------------------------------------------*/
55
56 for (size = 1; size < vertnum ; size++){
57 nearnode = closest(nbtree, intree, &last, &host);
58 intree[nearnode] = IN_TREE;
59 tree[nearnode] = host;
60 cost += MCOST(&p->dist, host, nearnode, lamda);
61 ni_insert_edges(p, nearnode, nbtree, intree, &last, lamda, mu);
62 }
63
64 /*----------------------------------------------------------------------*\
65 | Calculate the degree of the depot in the current tree |
66 \*----------------------------------------------------------------------*/
67
68 for (depot_degree = 0, cur_node = 1; cur_node < vertnum; cur_node++){
69 if (!tree[cur_node])
70 depot_degree++;
71 }
72
73 /*-----------------------------------------------------------------------*\
74 | If the degree of the depot is as desired, then we are done. If it is too|
75 | small, then we can easily determine the next edge to add adjacent to the|
76 | depot in order to increase the degree of the depot. We add the edge that|
77 | increase the cost of the tree the least by determining which other edge |
78 | in the tree would be forced out. In this case, we don't need to |
79 | recompute the tree from scratch. We simply make the appropriate switch. |
80 | If the degree is too large, we cannot |
81 | compute the leaving edge so easily. Then we simply raise the cost of all|
82 | edges asjacent to the depot by an amount sufficient to force enough |
83 | edges out of the solution. In this case, we do have to recompute the |
84 | tree |
85 \*-----------------------------------------------------------------------*/
86
87 if (depot_degree == k) break;
88
89 if (depot_degree < k){
90 while (depot_degree < k){
91 next_mu = MAXINT;
92 for (i = 1; i<vertnum; i++)
93 if (tree[i]){
94 max_cost = -MAXINT;
95 for (cur_node = i; tree[cur_node]; cur_node = tree[cur_node])
96 if ((cost = MCOST(&p->dist, tree[cur_node], cur_node, lamda)) >
97 max_cost){
98 max_cost = cost;
99 max_node = cur_node;
100 }
101 if ((cost = MCOST(&p->dist, 0, i, lamda) - max_cost) < next_mu){
102 next_mu = cost;
103 new_depot_node = i;
104 break_node = max_node;
105 }
106 }
107 for (prev_node = new_depot_node, cur_node = tree[new_depot_node],
108 next_node = tree[cur_node]; prev_node != break_node;
109 tree[cur_node] = prev_node, prev_node = cur_node,
110 cur_node = next_node, next_node = tree[next_node]);
111
112 tree[new_depot_node] = 0;
113
114 for (depot_degree = 0, cur_node = 1; cur_node < vertnum; cur_node++)
115 if (!tree[cur_node])
116 depot_degree++;
117
118 }
119 for (cost = 0, cur_node = 1; cur_node < vertnum; cur_node++)
120 cost += MCOST(&p->dist, cur_node, tree[cur_node], lamda);
121
122 break;
123 }
124 else{ /*depot_degree > k*/
125
126 mu -= ICOST(&p->dist, 0,1);
127
128 if (intree) free((char *) intree);
129 if (nbtree) free((char *) nbtree);
130 }
131 }
132
133 free ((char *)intree);
134 free ((char *)nbtree);
135 return(cost);
136 }
137
138 /*===========================================================================*/
139
140 int closest(neighbor *nbtree, int *intree, int *last, int *host)
141 {
142 int closest_node;
143 int pos, ch;
144 int cost;
145 neighbor temp;
146
147 /*-----------------------------------------------------------------------*\
148 | This routine deletes the item from the top of the binary tree where the |
149 | distances are stored and adjusts the tree accordingly |
150 \*-----------------------------------------------------------------------*/
151
152 closest_node = nbtree[1].nbor;
153 *host = nbtree[1].host;
154 (void) memcpy ((char *)&temp, (char *)(nbtree+*last), sizeof(neighbor));
155 cost = nbtree[*last].cost;
156 --*last;
157 pos = 1;
158 while ((ch=2*pos) < *last){
159 if ((nbtree[ch].cost > nbtree[ch+1].cost)||
160 ((nbtree[ch].cost == nbtree[ch+1].cost) && !nbtree[ch+1].host))
161 ch++;
162 if (cost <= nbtree[ch].cost)
163 break;
164 intree[nbtree[ch].nbor] = pos;
165 (void) memcpy ((char *)(nbtree+pos),
166 (char *)(nbtree+ch), sizeof(neighbor));
167 pos = ch;
168 }
169 if (ch == *last){
170 if (cost > nbtree[ch].cost){
171 intree[nbtree[ch].nbor] = pos;
172 (void) memcpy ((char *)(nbtree+pos),
173 (char *)(nbtree+ch), sizeof(neighbor));
174 pos=ch;
175 }
176 }
177 intree[temp.nbor] = pos;
178 (void) memcpy ((char *)(nbtree+pos), (char *)&temp, sizeof(neighbor));
179 return(closest_node);
180 }
181
182 /*===========================================================================*/
183
184 void ni_insert_edges(lb_prob *p, int new_node, neighbor *nbtree, int *intree,
185 int *last, int *lamda, int mu)
186
187 /*--------------------------------------------------------------------------*\
188 | Scan through the edges incident to 'new_node' - the new node in the set. |
189 | If the other end 'i' is in the set, do nothing. |
190 | If the other end is not in nbtree then insert it. |
191 | Otherwise update its distance if necessary: |
192 | If the previous closest point of the set to 'i' is closer then |
193 | 'new_node' then we don't have to do anything, otherwise update. |
194 | (update: the min element is on the top of the tree |
195 | Therefore the insertion and the update parts can be done |
196 | with the same code, not like in fi_insert_edges.) |
197 \*--------------------------------------------------------------------------*/
198 {
199 int cost = 0, prevcost;
200 int pos = 0, ch;
201 int i;
202 int vertnum = p->vertnum;
203
204 for (i=0; i<vertnum; i++){
205 if (intree[i] != IN_TREE){
206 cost = TCOST(&p->dist, new_node, i, lamda, mu);
207 if (intree[i] == NOT_NEIGHBOR){
208 pos = ++(*last);
209 prevcost = cost+1;
210 }else{
211 prevcost = nbtree[pos = intree[i]].cost;
212 }
213 if (prevcost > cost){
214 while ((ch=pos/2) != 0){
215 if ((nbtree[ch].cost < cost)||
216 ((nbtree[ch].cost == cost) && !nbtree[ch].host))
217 break;
218 intree[nbtree[ch].nbor] = pos;
219 (void) memcpy ((char *)(nbtree+pos),
220 (char *)(nbtree+ch), sizeof(neighbor));
221 pos = ch;
222 }
223 nbtree[pos].nbor = i;
224 nbtree[pos].host = new_node;
225 nbtree[pos].cost = cost;
226 intree[i] = pos;
227 }
228 }
229 }
230 }
231
232 /*--------------------------------------------------------------------------*\
233 | This routine computes the new penaltie for use in computing the lower bound|
234 | The penalties are based on the amount of violation of the degree |
235 | constraints in the current lower bound. |
236 \*--------------------------------------------------------------------------*/
237
238 int new_lamda(lb_prob *p, int upper_bound, int cur_bound, int *lamda,
239 int numroutes, int *tree, edge_data *cur_edges,
240 int alpha)
241 {
242 int gap = upper_bound-cur_bound, multiplier;
243 int denom = 0;
244 int cur_node1, cur_node2, vertnum = p->vertnum, i;
245 int *degrees;
246
247 degrees = (int *) calloc (vertnum, sizeof(int));
248
249 for (cur_node1 = 0; cur_node1 < vertnum; cur_node1++){
250 for (cur_node2 = 0; cur_node2 < vertnum; cur_node2++)
251 if ((cur_node1 != cur_node2) && (tree[cur_node2] == cur_node1))
252 degrees[cur_node1]++;
253 }
254
255 for (i = 0; i < numroutes; i++){
256 degrees[cur_edges[i].v0]++;
257 degrees[cur_edges[i].v1]++;
258 }
259
260 for (cur_node1 = 0; cur_node1 < vertnum; cur_node1++)
261 denom += cur_node1 ? (degrees[cur_node1]-1)*(degrees[cur_node1]-1) : \
262 (degrees[cur_node1]-2*numroutes)*(degrees[cur_node1]-2*numroutes);
263
264 denom = (int) sqrt((double)denom);
265
266 if (!denom) return(1);
267
268 multiplier = (int) (gap/(denom*alpha));
269
270 for (cur_node1 = 0; cur_node1 < vertnum; cur_node1++)
271 lamda[cur_node1] += (degrees[cur_node1] -
272 (cur_node1 ? 1: 2*numroutes));
273
274 if (degrees) free((char *) degrees);
275
276 return(0);
277 }