Debian Codegraph @

SYMPHONY/Applications/VRP/src/Heuristics/exchange2.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 "exchange2.h"
18 #include <stdio.h>
19 void exchange2(int parent, heur_prob *p)
20 {
21 printf("\nIn exchange2....\n\n");
22 _node *tour;
23 int numroutes;
24 int mytid, info, r_bufid;
25 int prev_node1, cur_node1, next_node1;
26 int prev_node2, cur_node2, next_node2;
27 int max_prev1 = 0, max_prev2 = 0, max_next1 = 0, max_next2 = 0;
28 int max_node1 = 0, max_node2 = 0;
29 best_tours *tours;
30 int max_savings = 0, savings;
31 int max_route1 = 0, max_route2 = 0, cur_route1, cur_route2;
32 route_data *route_info;
33 int cont = 1, capacity;
34 int *demand;
35 double t=0;
36
37 (void) used_time(&t);
38
39 mytid = pvm_mytid();
40
41 tours = p->cur_tour = (best_tours *) calloc (1, sizeof(best_tours));
42
43 /*-----------------------------------------------------------------------*\
44 | Receive the starting tour |
45 \*-----------------------------------------------------------------------*/
46
47 PVM_FUNC(r_bufid, pvm_recv(-1, EXCHANGE_HEUR_TOUR));
48 PVM_FUNC(info, pvm_upkbyte((char *)tours, sizeof(best_tours), 1));
49 tour = p->cur_tour->tour = (_node *) calloc (p->vertnum, sizeof(_node));
50 PVM_FUNC(info, pvm_upkbyte((char *)tour, (p->vertnum)*sizeof(_node), 1));
51 numroutes = tours->numroutes;
52 route_info = tours->route_info
53 = (route_data *) calloc (numroutes+1, sizeof(route_data));
54 route_calc(&p->dist, tour, numroutes, tours->route_info, p->demand);
55 capacity = p->capacity;
56 demand = p->demand;
57
58 /*------------------------------------------------------------------------*\
59 | This loop takes every pair of customers that are on different routes and |
60 | considers the savings obtained by switching their positions. After |
61 | considering all possible switches, the switch that is feasible and |
62 | produces the greatest savings is made. This is iterated until no more |
63 | savings can be obtained. |
64 \*------------------------------------------------------------------------*/
65
66 while (cont){
67 max_savings = 0;
68
69 /*----------------------------------------------------------------------*\
70 | In these nested loops, cur_node1 and cur_node2 are the nodes being |
71 | considered for switching. prev_node1, prev_node2, next_node1, and |
72 | next_node2 are the neighbors of these nodes on their current routes, |
73 | which are denoted by cur_route1 and cur_route2. The current best nodes |
74 | to switch are held in max_node1 and max_node2. Their neighbors are |
75 | denoted max_prev1, max_next, max_prev2, and max_next2 respectively |
76 | Since the depot is not included in the node list for the routes, we |
77 | must always be sure to include node zero as a neighbor at the beginning|
78 | and end of the routes (see comments below) |
79 \*----------------------------------------------------------------------*/
80
81 for (cur_route1 = 1; cur_route1 <= numroutes; cur_route1++){
82 for (cur_node1 = route_info[cur_route1].first, prev_node1 = 0,
83 next_node1 = tour[cur_node1].next;
84 cur_node1 != route_info[cur_route1].last;
85 prev_node1 = cur_node1, cur_node1 = tour[cur_node1].next,
86 next_node1 = tour[cur_node1].next){
87 for (cur_route2 = cur_route1+1; cur_route2 <= numroutes; cur_route2++){
88 for (cur_node2 = route_info[cur_route2].first, prev_node2 = 0,
89 next_node2 = tour[cur_node2].next;
90 cur_node2 != route_info[cur_route2].last;
91 prev_node2 = cur_node2, cur_node2 = tour[cur_node2].next,
92 next_node2 = tour[cur_node2].next){
93 if ((savings = - (ICOST(&p->dist, prev_node1, cur_node2) +
94 ICOST(&p->dist, cur_node2, next_node1) +
95 ICOST(&p->dist, prev_node2, cur_node1) +
96 ICOST(&p->dist, cur_node1, next_node2) -
97 ICOST(&p->dist, prev_node1, cur_node1) -
98 ICOST(&p->dist, cur_node1, next_node1) -
99 ICOST(&p->dist, prev_node2, cur_node2) -
100 ICOST(&p->dist, cur_node2, next_node2))) >
101 max_savings){
102 if ((route_info[cur_route1].weight - demand[cur_node1]
103 +demand[cur_node2] <= capacity) &&
104 (route_info[cur_route2].weight - demand[cur_node2]
105 +demand[cur_node1] <= capacity)){
106 max_savings = savings;
107 max_node1 = cur_node1;
108 max_node2 = cur_node2;
109 max_prev1 = prev_node1;
110 max_prev2 = prev_node2;
111 max_next1 = next_node1;
112 max_next2 = next_node2;
113 max_route1 = cur_route1;
114 max_route2 = cur_route2;
115 }
116 }
117 }
118
119 /*-----------------------------------------------------------------*\
120 | We have now reached the end of cur_route2 and must set next_node2 |
121 | to be zero and repeat the inner loop |
122 \*-----------------------------------------------------------------*/
123
124 next_node2 = 0;
125 if ((savings = - (ICOST(&p->dist, prev_node1, cur_node2) +
126 ICOST(&p->dist, cur_node2, next_node1) +
127 ICOST(&p->dist, prev_node2, cur_node1) +
128 ICOST(&p->dist, cur_node1, next_node2) -
129 ICOST(&p->dist, prev_node1, cur_node1) -
130 ICOST(&p->dist, cur_node1, next_node1) -
131 ICOST(&p->dist, prev_node2, cur_node2) -
132 ICOST(&p->dist, cur_node2, next_node2))) >
133 max_savings){
134 if ((route_info[cur_route1].weight - demand[cur_node1]
135 +demand[cur_node2] <= capacity) &&
136 (route_info[cur_route2].weight - demand[cur_node2]
137 +demand[cur_node1] <= capacity)){
138 max_savings = savings;
139 max_node1 = cur_node1;
140 max_node2 = cur_node2;
141 max_prev1 = prev_node1;
142 max_prev2 = prev_node2;
143 max_next1 = next_node1;
144 max_next2 = next_node2;
145 max_route1 = cur_route1;
146 max_route2 = cur_route2;
147 }
148 }
149 }
150 }
151
152 /*---------------------------------------------------------------------*\
153 | We have now reached the end of cur_route1 and must set next_node1 |
154 | to be 0 and repeat the outer loop |
155 \*---------------------------------------------------------------------*/
156
157 next_node1 = 0;
158 for (cur_route2 = cur_route1+1; cur_route2 <= numroutes; cur_route2++){
159 for (cur_node2 = route_info[cur_route2].first, prev_node2 = 0,
160 next_node2 = tour[cur_node2].next;
161 cur_node2 != route_info[cur_route2].last;
162 prev_node2 = cur_node2, cur_node2 = tour[cur_node2].next,
163 next_node2 = tour[cur_node2].next){
164 if ((savings = - (ICOST(&p->dist, prev_node1, cur_node2) +
165 ICOST(&p->dist, cur_node2, next_node1) +
166 ICOST(&p->dist, prev_node2, cur_node1) +
167 ICOST(&p->dist, cur_node1, next_node2) -
168 ICOST(&p->dist, prev_node1, cur_node1) -
169 ICOST(&p->dist, cur_node1, next_node1) -
170 ICOST(&p->dist, prev_node2, cur_node2) -
171 ICOST(&p->dist, cur_node2, next_node2))) >
172 max_savings){
173 if ((route_info[cur_route1].weight - demand[cur_node1]
174 +demand[cur_node2] <= capacity) &&
175 (route_info[cur_route2].weight - demand[cur_node2]
176 +demand[cur_node1] <= capacity)){
177 max_savings = savings;
178 max_node1 = cur_node1;
179 max_node2 = cur_node2;
180 max_prev1 = prev_node1;
181 max_prev2 = prev_node2;
182 max_next1 = next_node1;
183 max_next2 = next_node2;
184 max_route1 = cur_route1;
185 max_route2 = cur_route2;
186 }
187 }
188 }
189 next_node2 = 0;
190 if ((savings = - (ICOST(&p->dist, prev_node1, cur_node2) +
191 ICOST(&p->dist, cur_node2, next_node1) +
192 ICOST(&p->dist, prev_node2, cur_node1) +
193 ICOST(&p->dist, cur_node1, next_node2) -
194 ICOST(&p->dist, prev_node1, cur_node1) -
195 ICOST(&p->dist, cur_node1, next_node1) -
196 ICOST(&p->dist, prev_node2, cur_node2) -
197 ICOST(&p->dist, cur_node2, next_node2))) >
198 max_savings){
199 if ((route_info[cur_route1].weight - demand[cur_node1]
200 +demand[cur_node2] <= capacity) &&
201 (route_info[cur_route2].weight - demand[cur_node2]
202 +demand[cur_node1] <= capacity)){
203 max_savings = savings;
204 max_node1 = cur_node1;
205 max_node2 = cur_node2;
206 max_prev1 = prev_node1;
207 max_prev2 = prev_node2;
208 max_next1 = next_node1;
209 max_next2 = next_node2;
210 max_route1 = cur_route1;
211 max_route2 = cur_route2;
212 }
213 }
214 }
215 }
216
217 if (max_savings){/* If we found any cost saving switches,
218 then make the best one */
219
220 /* Update the route costs */
221
222 route_info[max_route1].cost += ICOST(&p->dist, max_prev1, max_node2) +
223 ICOST(&p->dist, max_node2, max_next1) -
224 ICOST(&p->dist, max_prev1, max_node1) -
225 ICOST(&p->dist, max_node1, max_next1);
226 route_info[max_route2].cost += ICOST(&p->dist, max_prev2, max_node1) +
227 ICOST(&p->dist, max_node1, max_next2) -
228 ICOST(&p->dist, max_prev2, max_node2) -
229 ICOST(&p->dist, max_node2, max_next2);
230
231 /*--------------------------------------------------------------------*\
232 | This is a special case where we need to do the switching a little |
233 | differently because the nodes are adjacent in the route lists, even |
234 | though they are on different routes. |
235 \*--------------------------------------------------------------------*/
236
237 if ((!max_next1) && (!max_prev2) && (max_route2 == max_route1+1)){
238 route_info[max_route1].last = max_node2;
239 route_info[max_route2].first = max_node1;
240
241 /*-------------------------------------------------------------------*\
242 | If max_next2 or max_prev1 are 0, we must correct their values so |
243 | that the correct updates in the data structures are made |
244 \*-------------------------------------------------------------------*/
245
246 if (!max_prev1){
247 max_prev1 = route_info[max_route1-1].last;
248 route_info[max_route1].first = max_node2;
249 }
250 if (!max_next2)
251 route_info[max_route2].last = max_node1;
252 if ((!max_next2) && (max_route2 != numroutes))
253 max_next2 = route_info[max_route2+1].first;
254 tour[max_prev1].next = max_node2;
255 tour[max_node2].next = max_node1;
256 tour[max_node1].next = max_next2;
257 }
258 else{
259
260 /*-------------------------------------------------------------------*\
261 | Again as above, if any of max_prev1, max_prev2, max_next1, or |
262 | max_next2 are zero, these values must be corrected so that the data |
263 | structure is updated correctly |
264 \*-------------------------------------------------------------------*/
265
266 if (!max_prev1){
267 max_prev1 = route_info[max_route1-1].last;
268 route_info[max_route1].first = max_node2;
269 }
270 if (!max_next1)
271 route_info[max_route1].last = max_node2;
272 if ((!max_next1) && (max_route1 != numroutes))
273 max_next1 = route_info[max_route1+1].first;
274 if (!max_prev2){
275 max_prev2 = route_info[max_route2-1].last;
276 route_info[max_route2].first = max_node1;
277 }
278 if (!max_next2)
279 route_info[max_route2].last = max_node1;
280 if ((!max_next2) && (max_route2 != numroutes))
281 max_next2 = route_info[max_route2+1].first;
282
283 /* Update the tour data structure*/
284
285 tour[max_prev1].next = max_node2;
286 tour[max_node2].next = max_next1;
287 tour[max_prev2].next = max_node1;
288 tour[max_node1].next = max_next2;
289 }
290
291 /* Update the route_info data structure*/
292
293 route_info[max_route1].weight += demand[max_node2] - demand[max_node1];
294 route_info[max_route2].weight += demand[max_node1] - demand[max_node2];
295 tour[max_node1].route = max_route2;
296 tour[max_node2].route = max_route1;
297 tours->cost -= max_savings;
298 }
299 else cont = 0; /* If no more savings found, then exit */
300 }
301
302 /*-----------------------------------------------------------------------*\
303 | Transmit the final tour back to the parent |
304 \*-----------------------------------------------------------------------*/
305
306 send_tour (tour, tours->cost, numroutes, tours->algorithm, used_time(&t),
307 parent, p->vertnum, 0, NULL);
308
309 free_heur_prob(p);
310
311 }