Debian Codegraph @

SYMPHONY/Applications/VRP/src/Heuristics/exchange.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 "exchange.h"
18 #include <stdio.h>
19
20 void exchange (int parent, heur_prob *p)
21 {
22 _node *tour;
23 int numroutes;
24 int mytid, info, r_bufid;
25 int prev_node, cur_node, next_node;
26 int v0, v1, insert0 = 0, insert1 = 0, delete0 = 0;
27 int delete1 = 0, max_node = 0;
28 best_tours *tours;
29 int max_savings = 0, savings;
30 int cur_route1, cur_route2, insert_route = 0, delete_route = 0;
31 route_data *route_info;
32 int cont = TRUE, capacity;
33 int *demand, count = 0;
34 double t = 0;
35
36 (void) used_time(&t);
37 mytid = pvm_mytid();
38
39 tours = p->cur_tour = (best_tours *) calloc (1, sizeof(best_tours));
40
41
42 /*-----------------------------------------------------------------------*\
43 | Receive the starting tour |
44 \*-----------------------------------------------------------------------*/
45
46 PVM_FUNC(r_bufid, pvm_recv(-1, EXCHANGE_HEUR_TOUR));
47 PVM_FUNC(info, pvm_upkbyte((char *)tours, sizeof(best_tours), 1));
48 tour = p->cur_tour->tour = (_node *) calloc (p->vertnum, sizeof(_node));
49 PVM_FUNC(info, pvm_upkbyte((char *)tour, (p->vertnum)*sizeof(_node), 1));
50 numroutes = tours->numroutes;
51 route_info = tours->route_info
52 = (route_data *) calloc (numroutes+1, sizeof(route_data));
53 route_calc(&p->dist, tour, numroutes, route_info, p->demand);
54 demand = p->demand;
55 capacity = p->capacity;
56
57 /*------------------------------------------------------------------------*\
58 | This loop takes every customer and considers inserting it between every |
59 | other pair of customers on all other routes. After considering all these |
60 | moves, the one that is feasible and results in the greatest cost savings |
61 | is made. This is iterated until no more cost saving moves can be found. |
62 \*------------------------------------------------------------------------*/
63
64 while (cont){ /* while the last iteration produced a savings */
65 max_savings = 0;
66
67 /*----------------------------------------------------------------------*\
68 | In these nested loops, cur_node is the node being considered for |
69 | relocation. cur_route1 is the route on which that node is located. |
70 | prev_node and next_node are the neighbors of that node in the solution |
71 | cur_route2 is the route being considered for relocation. v0 and v1 are |
72 | the two nodes between which we are considering inserting cur_node. |
73 | max_savings denotes the greatest savings found so far. max_node denotes|
74 | the node whose relocation gives that savings. insert0 and insert1 |
75 | denote where that node should be inserted in order to achieve that |
76 | savings. delete0 and delete1 denote the neighbors of max_node in its |
77 | original position. Since the depot is not included in the node list for|
78 | the routes, we must always make sure to include node zero as a neighbor|
79 | at the beginning and end of each route (see comments below) |
80 \*----------------------------------------------------------------------*/
81
82 for (cur_route1 = 1; cur_route1 <= numroutes; cur_route1++){
83 for (cur_node = route_info[cur_route1].first,
84 prev_node = 0,
85 next_node = tour[cur_node].next;
86 cur_node != route_info[cur_route1].last;
87 prev_node = cur_node, cur_node = tour[cur_node].next,
88 next_node = tour[cur_node].next){
89 for (cur_route2 = 1; cur_route2 <= numroutes; cur_route2++){
90 for (v0 = 0, v1 = route_info[cur_route2].first;
91 v0 != route_info[cur_route2].last; v0=v1, v1=tour[v1].next)
92 if (((savings = -((ICOST(&p->dist, v0, cur_node) + ICOST(&p->dist,
93 cur_node, v1) - ICOST(&p->dist, v0, v1))
94 + (ICOST(&p->dist, prev_node, next_node) -
95 (ICOST(&p->dist, prev_node, cur_node) +
96 ICOST(&p->dist, cur_node, next_node))))) > max_savings )
97 && (v0 != cur_node) && (v1 != cur_node)
98 && (demand[cur_node] + route_info[cur_route2].weight <=
99 capacity)){
100 max_savings = savings;
101 max_node = cur_node;
102 insert0 = v0;
103 insert1 = v1;
104 delete0 = prev_node;
105 delete1 = next_node;
106 insert_route = cur_route2;
107 delete_route = cur_route1;
108 }
109
110 /*-----------------------------------------------------------------*\
111 | We have now reached the end of cur_route2 and must set v1 to be |
112 | zero and repeat the inner loop |
113 \*-----------------------------------------------------------------*/
114
115 v1 = 0;
116 if (((savings = -((ICOST(&p->dist, v0, cur_node) +
117 ICOST(&p->dist, cur_node, v1) -
118 ICOST(&p->dist, v0, v1))
119 + (ICOST(&p->dist, prev_node, next_node) -
120 (ICOST(&p->dist, prev_node, cur_node) +
121 ICOST(&p->dist, cur_node, next_node)))))
122 > max_savings )
123 && (v0 != cur_node) & (v1 != cur_node)
124 && (demand[cur_node] + route_info[cur_route2].weight <=
125 capacity)){
126 max_savings = savings;
127 max_node = cur_node;
128 insert0 = v0;
129 insert1 = v1;
130 delete0 = prev_node;
131 delete1 = next_node;
132 insert_route = cur_route2;
133 delete_route = cur_route1;
134 }
135 }
136 }
137
138 /*---------------------------------------------------------------------*\
139 | We have now reached the end of cur_route1 and must set next_node to |
140 | be 0 and repeat the outer loop |
141 \*---------------------------------------------------------------------*/
142
143 next_node = 0;
144 for (cur_route2 = 1; cur_route2 <= numroutes; cur_route2++){
145 for (v0 = 0, v1 = route_info[cur_route2].first;
146 v0 != route_info[cur_route2].last; v0=v1, v1=tour[v1].next)
147 if (((savings = -((ICOST(&p->dist, v0, cur_node) + ICOST(&p->dist,
148 cur_node, v1) - ICOST(&p->dist, v0, v1))
149 + (ICOST(&p->dist, prev_node, next_node) -
150 (ICOST(&p->dist, prev_node, cur_node) +
151 ICOST(&p->dist, cur_node, next_node))))) > max_savings )
152 && (v0 != cur_node) & (v1 != cur_node)
153 && (demand[cur_node] + route_info[cur_route2].weight <=
154 capacity)){
155 max_savings = savings;
156 max_node = cur_node;
157 insert0 = v0;
158 insert1 = v1;
159 delete0 = prev_node;
160 delete1 = next_node;
161 insert_route = cur_route2;
162 delete_route = cur_route1;
163 }
164 v1 = 0;
165 if (((savings = -((ICOST(&p->dist, v0, cur_node) +
166 ICOST(&p->dist, cur_node, v1) -
167 ICOST(&p->dist, v0, v1))
168 + (ICOST(&p->dist, prev_node, next_node) -
169 (ICOST(&p->dist, prev_node, cur_node) +
170 ICOST(&p->dist, cur_node, next_node))))) > max_savings )
171 && (v0 != cur_node) & (v1 != cur_node)
172 && (demand[cur_node] + route_info[cur_route2].weight <=
173 capacity)){
174 max_savings = savings;
175 max_node = cur_node;
176 insert0 = v0;
177 insert1 = v1;
178 delete0 = prev_node;
179 delete1 = next_node;
180 insert_route = cur_route2;
181 delete_route = cur_route1;
182 }
183 }
184 }
185
186 if (max_savings){ /* If we found any cost saving moves, then make the
187 best one */
188
189 /* Update the route costs */
190
191 count++;
192 route_info[delete_route].cost += (ICOST(&p->dist, delete0, delete1) -
193 (ICOST(&p->dist, delete0, max_node) +
194 ICOST(&p->dist, max_node, delete1)));
195 route_info[insert_route].cost += (ICOST(&p->dist, insert0, max_node) +
196 ICOST(&p->dist, max_node, insert1) -
197 ICOST(&p->dist, insert0, insert1));
198
199 /*---------------------------------------------------------------------*\
200 | If max_node is the only customer left on the route, then we must |
201 | delete the route We must also reset delete0 and delete1 so that the |
202 | correct updates are made |
203 \*-----------------------------------_---------------------------------*/
204
205 if ((!delete0) && (!delete1)){
206 delete0 = route_info[(delete_route)-1].last;
207 if (delete_route != numroutes)
208 delete1 = route_info[delete_route+1].first;
209 numroutes -= 1;
210 for (cur_route1 = delete_route; cur_route1 <= numroutes; cur_route1++){
211 route_info[cur_route1] = route_info[cur_route1+1];
212 }
213 for (cur_node = route_info[delete_route].first; cur_node !=0;
214 cur_node = tour[cur_node].next)
215 tour[cur_node].route -= 1;
216 if (insert_route > tour[max_node].route)
217 insert_route -= 1;
218 }
219 else{
220
221 /*-------------------------------------------------------------------*\
222 | If delete0 or delete1 are 0, we must reset their values so that the |
223 | correct updates in the data structure are made. Also, the first or |
224 | last nodes of the route my have to be updated |
225 \*-------------------------------------------------------------------*/
226
227 if (!delete0){
228 delete0 = route_info[(delete_route)-1].last;
229 route_info[delete_route].first = delete1;
230 }
231 if (!delete1)
232 route_info[delete_route].last = delete0;
233 if ((!delete1) && (delete_route != numroutes))
234 delete1 = route_info[(delete_route)+1].first;
235 route_info[delete_route].numcust -=1;
236 route_info[delete_route].weight -= demand[max_node];
237 }
238
239 /*---------------------------------------------------------------------*\
240 | Here, we might also have to reset insert0 and insert1 and the first |
241 | and last nodes of the route where max_node is to be inserted |
242 \*---------------------------------------------------------------------*/
243
244 if (!insert0){
245 insert0 = route_info[insert_route-1].last;
246 route_info[insert_route].first = max_node;
247 }
248 if (!insert1)
249 route_info[insert_route].last = max_node;
250 if ((!insert1) && (insert_route != numroutes))
251 insert1 = route_info[insert_route+1].first;
252
253 /* Update the tour and route_info data structures */
254
255 tour[delete0].next = delete1;
256 tour[insert0].next = max_node;
257 tour[max_node].next = insert1;
258 route_info[insert_route].weight += demand[max_node];
259 route_info[insert_route].numcust += 1;
260 tour[max_node].route = insert_route;
261 tours->cost -= max_savings;
262 }
263 else cont = FALSE; /* If no savings is found, exit */
264 }
265
266 /*-----------------------------------------------------------------------*\
267 | Transmit the final tour back to the parent |
268 \*-----------------------------------------------------------------------*/
269
270 send_tour (tour, tours->cost, numroutes, tours->algorithm, used_time(&t),
271 parent, p->vertnum, 0, NULL);
272
273 free_heur_prob(p);
274
275 }
276
277
278