Debian Codegraph @

SYMPHONY/Applications/VRP/src/Master/Heuristics/route_heur.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 Common Public License. Please see */
13 /* accompanying file for terms. */
14 /* */
15 /*===========================================================================*/
16
17 #include <math.h>
18 #include <memory.h>
19 #include <string.h>
20 #include "BB_constants.h"
21 #include "BB_macros.h"
22 #include "sym_messages.h"
23 #include "vrp_const.h"
24 #include "route_heur.h"
25 #include "sym_timemeas.h"
26 #include <pvm3.h>
27 #include <stdio.h>
28 #include "compute_cost.h"
29 #include "sym_proccomm.h"
30 #include "heur_routines.h"
31 #include "receive_rout.h"
32 /*----------------------------------------------------------------------*\
33 | This program takes clusterings of nodes (determined by the initial |
34 | solution which is given to the program) and tries to improve their |
35 | routings using simple TSP heuristics such as far insert and near insert|
36 | For each cluster of customers, it takes the cheapest routing found by |
37 | any of the heuristics and adds it to the tour to be sent back to the |
38 | parent. |
39 \*----------------------------------------------------------------------*/
40
41 void route_heur(vrp_problem *vrp, heur_params *heur_par,
42 heurs *rh, int trials, int jobs, int *tids,
43 int *sent, best_tours *solutions)
44 {
45
46 int i, mintour = 0;
47 int mytid, info, s_bufid, r_bufid, bytes, msgtag, parent;
48 int cur_node, cur_route, numroutes;
49 int pos, cost, last = 0;
50 _node *tour;
51 int mincost, temp_cost, temp, dummy = 0;
52 route_data *route_info;
53 double routing_time = 0, t=0;
54 int round, index =0;
55 (void) used_time(&t);
56 best_tours *tours;
57 heurs *ro;
58 mytid = pvm_mytid();
59
60 if (vrp->par.verbosity>1)
61 printf("\nNow beginning routing heuristics ....\n\n");
62
63
64 /*-----------------------------------------------------------------------*\
65 | Initialize the heur_params data |
66 \*-----------------------------------------------------------------------*/
67
68 float fini_ratio = heur_par->fini_ratio;
69 int ni_trials = heur_par->ni_trials;
70 int fi_trials = heur_par->fi_trials;
71 int fini_trials = heur_par->fini_trials;
72
73 rh->tids = tids;
74 rh->jobs = trials;//this indicates how many batches will run
75
76
77 /*-----------------------------------------------------------------------*\
78 | Initialize the starting tour |
79 \*-----------------------------------------------------------------------*/
80
81 for(round=0; round < rh->jobs; round++){/*---------------------------------*\
82 |in each round one batch is received|
83 |a solution is synthesised and sent |
84 |to start_heur. |
85 \*---------------------------------*/
86 ro = (heurs *)calloc(1, sizeof(heurs));
87 ro->tids = tids;
88 ro->jobs = fi_trials + fini_trials + ni_trials;
89 vrp_problem *p = (vrp_problem *) calloc(1, sizeof(vrp_problem));
90 memcpy((char *)p, (char *)vrp,sizeof(vrp_problem));
91 p->edgenum = p->vertnum*(p->vertnum-1)/2;
92 tours = p->cur_tour = (best_tours *) calloc (1, sizeof(best_tours));
93 memcpy((char *)p->cur_tour, (char *)
94 &p->tours[p->tourorder[round%(p->tournum+1)]], sizeof(best_tours)) ;
95 tour = p->cur_tour->tour = (_node *) calloc (p->vertnum, sizeof(_node));
96 memcpy((char *)p->cur_tour->tour, (char *)p->
97 tours[p->tourorder[round%(p->tournum+1)]].tour,p->vertnum*sizeof(_node));
98 numroutes = tours->numroutes;
99 tours->route_info =
100 (route_data *) calloc (numroutes+1, sizeof(route_data));
101 route_calc(&p->dist, tour, numroutes, tours->route_info, p->demand);
102
103 /*--------------------------------------------------------------------*\
104 | Here we broadcast the starting point rules to the various heuristics |
105 | If there is only one trial of that particular heuristic, then we just|
106 | use far insert as the starting point rule. For all the remaining |
107 | trials, we use random starting points. |
108 \*--------------------------------------------------------------------*/
109 /*round robin applied here*/
110 temp = FAR_INS;
111 if (fi_trials){
112 PVM_FUNC(s_bufid, pvm_initsend(PvmDataRaw));
113 PVM_FUNC(info, pvm_pkint(&dummy, 1, 1));
114 PVM_FUNC(info, pvm_send(tids[index%jobs], S_FARTHEST_INS));
115 sent[index%jobs]++;
116 PVM_FUNC(s_bufid, pvm_initsend(PvmDataRaw));
117 PVM_FUNC(info, pvm_pkbyte((char *)tours, sizeof(best_tours), 1));
118 PVM_FUNC(info, pvm_pkbyte((char *)tour, (p->vertnum)*sizeof(_node), 1));
119 PVM_FUNC(info, pvm_send(tids[index%jobs], ROUTE_FINS_VRP_DATA));
120 PVM_FUNC(s_bufid, pvm_initsend(PvmDataRaw));
121 PVM_FUNC(info, pvm_pkint(&temp, 1, 1));
122 PVM_FUNC(info, pvm_send(tids[index%jobs], ROUTE_FINS_START_RULE));
123 index++;
124 }
125 if (ni_trials){
126 PVM_FUNC(s_bufid, pvm_initsend(PvmDataRaw));
127 PVM_FUNC(info, pvm_pkint(&dummy, 1, 1));
128 PVM_FUNC(info, pvm_send(tids[index%jobs], S_NEAREST_INS));
129 sent[index%jobs]++;
130 PVM_FUNC(s_bufid, pvm_initsend(PvmDataRaw));
131 PVM_FUNC(info, pvm_pkbyte((char *)tours, sizeof(best_tours), 1));
132 PVM_FUNC(info, pvm_pkbyte((char *)tour, (p->vertnum)*sizeof(_node), 1));
133 PVM_FUNC(info, pvm_send(tids[index%jobs], ROUTE_NINS_VRP_DATA));
134 PVM_FUNC(s_bufid, pvm_initsend(PvmDataRaw));
135 PVM_FUNC(info, pvm_pkint(&temp, 1, 1));
136 PVM_FUNC(info, pvm_send(tids[index%jobs], ROUTE_NINS_START_RULE));
137 index++;
138 }
139 if (fini_trials){
140 PVM_FUNC(s_bufid, pvm_initsend(PvmDataRaw));
141 PVM_FUNC(info, pvm_pkint(&dummy, 1, 1));
142 PVM_FUNC(info, pvm_send(tids[index%jobs], S_FARNEAR_INS));
143 sent[index%jobs]++;
144 PVM_FUNC(s_bufid, pvm_initsend(PvmDataRaw));
145 PVM_FUNC(info, pvm_pkbyte((char *)tours, sizeof(best_tours), 1));
146 PVM_FUNC(info, pvm_pkbyte((char *)tour, (p->vertnum)*sizeof(_node), 1));
147 PVM_FUNC(info, pvm_send(tids[index%jobs], ROUTE_FNINS_VRP_DATA));
148 PVM_FUNC(s_bufid, pvm_initsend(PvmDataRaw));
149 PVM_FUNC(info, pvm_pkint(&temp, 1, 1));
150 PVM_FUNC(info, pvm_send(tids[index%jobs], ROUTE_FNINS_START_RULE));
151 PVM_FUNC(s_bufid, pvm_initsend(PvmDataRaw));
152 PVM_FUNC(info, pvm_pkfloat(&fini_ratio, 1, 1));
153 PVM_FUNC(info, pvm_send(tids[index%jobs], FINI_RATIO));
154 index++;
155 }
156 temp = MAX(fi_trials, ni_trials);
157 temp = MAX(temp, fini_trials);
158 for (i=1; i<temp; i++){
159 if (fi_trials>i){
160 PVM_FUNC(s_bufid, pvm_initsend(PvmDataRaw));
161 PVM_FUNC(info, pvm_pkint(&dummy, 1, 1));
162 PVM_FUNC(info, pvm_send(tids[index%jobs], S_FARTHEST_INS));
163 sent[index%jobs]++;
164 PVM_FUNC(s_bufid, pvm_initsend(PvmDataRaw));
165 PVM_FUNC(info, pvm_pkbyte((char *)tours, sizeof(best_tours), 1));
166 PVM_FUNC(info, pvm_pkbyte((char *)tour, (p->vertnum)*sizeof(_node),1));
167 PVM_FUNC(info, pvm_send(tids[index%jobs], ROUTE_FINS_VRP_DATA));
168 PVM_FUNC(s_bufid, pvm_initsend(PvmDataRaw));
169 PVM_FUNC(info, pvm_pkint(&p->par.rand_seed[(i-1)%NUM_RANDS], 1, 1));
170 PVM_FUNC(info, pvm_send(tids[index%jobs], ROUTE_FINS_START_RULE));
171 index++;
172 }
173 if (ni_trials>i){
174 PVM_FUNC(s_bufid, pvm_initsend(PvmDataRaw));
175 PVM_FUNC(info, pvm_pkint(&dummy, 1, 1));
176 PVM_FUNC(info, pvm_send(tids[index%jobs], S_NEAREST_INS));
177 sent[index%jobs]++;
178 PVM_FUNC(s_bufid, pvm_initsend(PvmDataRaw));
179 PVM_FUNC(info, pvm_pkbyte((char *)tours, sizeof(best_tours), 1));
180 PVM_FUNC(info, pvm_pkbyte((char *)tour, (p->vertnum)*sizeof(_node),1));
181 PVM_FUNC(info, pvm_send(tids[index%jobs], ROUTE_NINS_VRP_DATA));
182 PVM_FUNC(s_bufid, pvm_initsend(PvmDataRaw));
183 PVM_FUNC(info, pvm_pkint(&p->par.rand_seed[(i-1)%NUM_RANDS], 1, 1));
184 PVM_FUNC(info, pvm_send(tids[index%jobs], ROUTE_NINS_START_RULE));
185 index++;
186 }
187 if (fini_trials>i){
188 PVM_FUNC(s_bufid, pvm_initsend(PvmDataRaw));
189 PVM_FUNC(info, pvm_pkint(&dummy, 1, 1));
190 PVM_FUNC(info, pvm_send(tids[index%jobs], S_FARNEAR_INS));
191 sent[index%jobs]++;
192 PVM_FUNC(s_bufid, pvm_initsend(PvmDataRaw));
193 PVM_FUNC(info, pvm_pkbyte((char *)tours, sizeof(best_tours), 1));
194 PVM_FUNC(info, pvm_pkbyte((char *)tour, (p->vertnum)*sizeof(_node),1));
195 PVM_FUNC(info, pvm_send(tids[index%jobs], ROUTE_FNINS_VRP_DATA));
196 PVM_FUNC(s_bufid, pvm_initsend(PvmDataRaw));
197 PVM_FUNC(info, pvm_pkint(&p->par.rand_seed[(i-1)%NUM_RANDS], 1, 1));
198 PVM_FUNC(info, pvm_send(tids[index%jobs], ROUTE_FNINS_START_RULE));
199 PVM_FUNC(s_bufid, pvm_initsend(PvmDataRaw));
200 PVM_FUNC(info, pvm_pkfloat(&fini_ratio, 1, 1));
201 PVM_FUNC(info, pvm_send(tids[index%jobs], FINI_RATIO));
202 index++;
203 }
204 }
205
206 /*-----------------------------------------------------------------------*\
207 | Receive the tours back from the processes |
208 | [initialize the p->tours[i], and then receive into it] |
209 \*-----------------------------------------------------------------------*/
210
211 tours = p->tours =
212 (best_tours *) calloc (p->par.tours_to_keep, sizeof(best_tours));
213 tours[0].cost = MAXINT;
214 tours[0].tour = (_node *) malloc ((int)p->par.tours_to_keep * p->vertnum
215 * sizeof(_node));
216 for (pos=1; pos<p->par.tours_to_keep; pos++){
217 tours[pos].tour = p->tours[pos-1].tour + p->vertnum;
218 tours[pos].cost = MAXINT;
219 }
220 p->tourorder = (int *) calloc((int)p->par.tours_to_keep+1,
221 sizeof(int));
222
223 routing_time = receive_tours(p, ro, &last, TRUE, TRUE, FALSE, FALSE,
224 jobs, sent);
225
226 /*-----------------------------------------------------------------------*\
227 | Form the final tour |
228 \*-----------------------------------------------------------------------*/
229
230 /*--------------------------------------------------------------------*\
231 | This section of the program compares all the routings for a |
232 | particular cluster and chooses the best one to be in the final |
233 | solution. |
234 \*--------------------------------------------------------------------*/
235 route_info = p->cur_tour->route_info;
236
237 cost = 0;
238 cur_node = 0;
239 for (cur_route=1; cur_route<=numroutes; cur_route++){
240 mincost = MAXINT;
241 //choose the mincost tour for the current route as mintour.
242 for (i = 0; i<=p->tournum; i++)
243 if ((temp_cost = tours[i].route_info[cur_route].cost) < mincost){
244 mincost = temp_cost;
245 mintour = i;
246 }
247 //if that is cheaper than current tour's current route
248 if (mincost < route_info[cur_route].cost){
249 //then append that route to current tour's current node.
250 tour[cur_node].next = tours[mintour].route_info[cur_route].first;
251 do{
252 //update current node.
253 cur_node = tour[cur_node].next;
254 tour[cur_node].next = tours[mintour].tour[cur_node].next;
255 }while(cur_node != tours[mintour].route_info[cur_route].last);
256 cost += tours[mintour].route_info[cur_route].cost;
257 }
258 else{
259 tour[cur_node].next = route_info[cur_route].first;
260 cost += route_info[cur_route].cost;
261 cur_node = route_info[cur_route].last;
262 }
263 }
264 printf("\nFinal tour ready.\n\n");
265 /*-----------------------------------------------------------------------*\
266 | Store the final tour |
267 \*-----------------------------------------------------------------------*/
268
269 solutions[round].tour = (_node *) calloc (p->vertnum, sizeof(_node));
270 memcpy((char *)solutions[round].tour, (char *)tour, p->vertnum*sizeof(_node));
271 solutions[round].cost = cost;
272 solutions[round].numroutes = numroutes;
273 solutions[round].solve_time = used_time(&t)+routing_time;
274 solutions[round].algorithm = p->cur_tour->algorithm;
275
276 if (p->tourorder) free ((int *) p->tourorder);
277 if (p->cur_tour->tour) free((_node *) p->cur_tour->tour);
278 if (p->cur_tour->route_info) free ((route_data *) p->cur_tour->route_info);
279 if (p->cur_tour) free ((best_tours *) p->cur_tour);
280 if (p->tours) free ((best_tours *) p->tours);
281 if(p) free ((vrp_problem *) p);
282 if (ro) free((char *) ro);
283 }// for(round=0; round < rh->jobs; round++)
284 }
285
286
287
288
289
290
291
292