| 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 |
|
| 18 |
#include <memory.h> |
| 19 |
#include <stdio.h> |
| 20 |
|
| 21 |
#include "BB_constants.h" |
| 22 |
#include "BB_macros.h" |
| 23 |
#include "start_heurs.h" |
| 24 |
#include "cluster_heur.h" |
| 25 |
#include "route_heur.h" |
| 26 |
#include "exchange_heur.h" |
| 27 |
#include "small_graph.h" |
| 28 |
#include "receive_rout.h" |
| 29 |
#include "collect_solutions.h" |
| 30 |
#include "lower_bound.h" |
| 31 |
#include "sym_timemeas.h" |
| 32 |
#include "vrp_const.h" |
| 33 |
#include "sym_dg_params.h" |
| 34 |
#include "vrp_sym_dg.h" |
| 35 |
#include "sym_proccomm.h" |
| 36 |
#include "vrp_master_functions.h" |
| 37 |
|
| 38 |
void start_heurs(vrp_problem *vrp, heur_params *heur_par, lb_params *lb_par, |
| 39 |
double *ub, char windows) |
| 40 |
{ |
| 41 |
int pos, last, mytid; |
| 42 |
int *tids, *sent, dummy; |
| 43 |
int trials = 0, i, jobs = 0; |
| 44 |
best_tours *tours = NULL; |
| 45 |
best_tours *solutions = NULL; |
| 46 |
int *tourorder = NULL, ub_pos; |
| 47 |
heurs *heur_out = NULL; |
| 48 |
double heurtime = 0, lbtime = 0, t = 0; |
| 49 |
|
| 50 |
mytid = pvm_mytid(); |
| 51 |
(void)used_time(&t); |
| 52 |
|
| 53 |
tids = (int *) malloc((heur_par->no_of_machines)*sizeof(int)); |
| 54 |
|
| 55 |
/*-----------------------------------------------------------------------*\ |
| 56 |
| start parallel processes & send common data | |
| 57 |
\*-----------------------------------------------------------------------*/ |
| 58 |
|
| 59 |
jobs = spawn(vrp->par.executables.heuristics, (char **)NULL, |
| 60 |
vrp->par.debug.heuristics, (char *)NULL, |
| 61 |
heur_par->no_of_machines, tids); |
| 62 |
sent = (int *) calloc(jobs, sizeof(int)); |
| 63 |
printf("\nHello, jobs %i %i %i are spawned\n", tids[0],tids[1], tids[2]); |
| 64 |
|
| 65 |
broadcast(vrp, tids, jobs); |
| 66 |
|
| 67 |
/*-----------------------------------------------------------------------*\ |
| 68 |
| start the cluster heuristics | |
| 69 |
\*-----------------------------------------------------------------------*/ |
| 70 |
|
| 71 |
heur_out = (heurs *) calloc (1, sizeof(heurs)); |
| 72 |
|
| 73 |
if (vrp->par.do_heuristics){ |
| 74 |
if (heur_par->sweep_trials && vrp->dist.coordx && vrp->dist.coordy){ |
| 75 |
trials += 1; |
| 76 |
} |
| 77 |
if (heur_par->savings3_par.savings_trials && (vrp->numroutes || |
| 78 |
(!vrp->numroutes && vrp->dist.coordx && vrp->dist.coordy))){ |
| 79 |
trials += heur_par->savings3_par.grid_size |
| 80 |
* heur_par->savings3_par.grid_size; |
| 81 |
} |
| 82 |
if (heur_par->near_cluster_trials && (vrp->numroutes || |
| 83 |
(!vrp->numroutes && vrp->dist.coordx && vrp->dist.coordy))){ |
| 84 |
trials += 1; |
| 85 |
} |
| 86 |
|
| 87 |
trials += ((heur_par->savings_par.savings_trials + |
| 88 |
heur_par->savings_par.savings2_trials) |
| 89 |
* (heur_par->savings_par.grid_size * |
| 90 |
heur_par->savings_par.grid_size) + |
| 91 |
heur_par->tsp.ni_trials + heur_par->tsp.fi_trials + |
| 92 |
heur_par->tsp.fini_trials); |
| 93 |
}else{ |
| 94 |
trials = 0; |
| 95 |
} |
| 96 |
|
| 97 |
printf("\nname of p_process = %s \n\n", vrp->par.executables.heuristics); |
| 98 |
if (trials){ |
| 99 |
|
| 100 |
cluster_heur(vrp, heur_par, heur_out, trials, jobs, tids, sent); |
| 101 |
|
| 102 |
printf("\nNo jobs: %i \n\n", jobs); |
| 103 |
/*-----------------------------------------------------------------------*\ |
| 104 |
| receive the heuristical tours | |
| 105 |
\*-----------------------------------------------------------------------*/ |
| 106 |
|
| 107 |
if (trials){ |
| 108 |
tours = vrp->tours; |
| 109 |
vrp->tours[0].cost = MAXINT; |
| 110 |
vrp->tours[0].tour = (_node *) calloc |
| 111 |
(vrp->par.tours_to_keep, vrp->vertnum * sizeof(_node)); |
| 112 |
for (pos=1; pos<vrp->par.tours_to_keep; pos++){ |
| 113 |
tours[pos].tour = tours[pos-1].tour + vrp->vertnum; |
| 114 |
tours[pos].cost = MAXINT; |
| 115 |
} |
| 116 |
tourorder = vrp->tourorder = (int *) |
| 117 |
calloc(vrp->par.tours_to_keep+1, sizeof(int)); |
| 118 |
vrp->tournum = -1; /*status of |
| 119 |
heuristics*/ |
| 120 |
heurtime += receive_tours(vrp, heur_out, &last, TRUE, FALSE, FALSE, |
| 121 |
windows, jobs, sent); |
| 122 |
/*receives the tours output by *\ |
| 123 |
| the clustering processes and | |
| 124 |
| orders them , keeping the | |
| 125 |
| best "vrp->par.tours_to_keep" | |
| 126 |
\*of them at hand. */ |
| 127 |
} |
| 128 |
|
| 129 |
/*-----------------------------------------------------------------------*\ |
| 130 |
| Start the route heuristics | |
| 131 |
\*-----------------------------------------------------------------------*/ |
| 132 |
|
| 133 |
trials = trials ? MIN(vrp->tournum+1, heur_par->route_opt1) : 0; |
| 134 |
solutions = (best_tours *) malloc(trials*sizeof(best_tours)); |
| 135 |
if (trials){ |
| 136 |
route_heur(vrp, heur_par, heur_out, trials, jobs, tids, sent, solutions); |
| 137 |
// printf("\nTids after route_heur %i % i%i", tids[0], tids[1], tids[2]); |
| 138 |
heurtime += collect_solutions(vrp, trials, &last, FALSE, solutions); |
| 139 |
} |
| 140 |
|
| 141 |
/*-----------------------------------------------------------------------*\ |
| 142 |
| Start the exchange heuristics | |
| 143 |
\*-----------------------------------------------------------------------*/ |
| 144 |
|
| 145 |
trials = trials ? MIN(vrp->tournum+1, heur_par->exchange) : 0; |
| 146 |
if (trials){ |
| 147 |
exchange_heur(vrp, heur_out, trials, jobs, FIRST_SET, tids, sent); |
| 148 |
heurtime += receive_tours(vrp, heur_out, &last, TRUE, FALSE, FALSE, |
| 149 |
windows, jobs, sent); |
| 150 |
} |
| 151 |
|
| 152 |
/*-----------------------------------------------------------------------*\ |
| 153 |
| Run the route heuristics again | |
| 154 |
\*-----------------------------------------------------------------------*/ |
| 155 |
trials = trials ? MIN(vrp->tournum+1, heur_par->route_opt2) : 0; |
| 156 |
if (trials){ |
| 157 |
solutions = (best_tours *) malloc(trials*sizeof(best_tours)); |
| 158 |
route_heur(vrp, heur_par, heur_out, trials, jobs, tids, sent, solutions); |
| 159 |
heurtime += collect_solutions(vrp, trials, &last, FALSE, solutions); |
| 160 |
} |
| 161 |
|
| 162 |
/*-----------------------------------------------------------------------*\ |
| 163 |
| Start the second set of exchange heuristics | |
| 164 |
\*-----------------------------------------------------------------------*/ |
| 165 |
|
| 166 |
trials = trials ? MIN(vrp->tournum+1, heur_par->exchange2) : 0; |
| 167 |
if (trials){ |
| 168 |
exchange_heur(vrp, heur_out, trials, jobs, SECOND_SET, tids, sent); |
| 169 |
heurtime += receive_tours(vrp, heur_out, &last, TRUE, FALSE, FALSE, |
| 170 |
windows, jobs, sent); |
| 171 |
} |
| 172 |
/*-----------------------------------------------------------------------*\ |
| 173 |
| Run route heuristics once more | |
| 174 |
\*-----------------------------------------------------------------------*/ |
| 175 |
|
| 176 |
trials = trials ? MIN(vrp->tournum+1, heur_par->route_opt3) : 0; |
| 177 |
solutions = (best_tours *) malloc(trials*sizeof(best_tours)); |
| 178 |
if (trials){ |
| 179 |
route_heur(vrp, heur_par, heur_out, trials, jobs, tids, sent, solutions); |
| 180 |
make_small_graph(vrp, 2*heur_out->jobs*vrp->vertnum); |
| 181 |
heurtime += collect_solutions(vrp, trials, &last, TRUE, solutions); |
| 182 |
} |
| 183 |
|
| 184 |
/*-----------------------------------------------------------------------*\ |
| 185 |
| Compute the upper and lower bounds | |
| 186 |
\*-----------------------------------------------------------------------*/ |
| 187 |
vrp->lb->lower_bound = (double) 0; |
| 188 |
ub_pos = -1; |
| 189 |
|
| 190 |
if (vrp->tournum>=0 && *ub <= 0){ |
| 191 |
if (!vrp->numroutes){ |
| 192 |
vrp->numroutes = tours[tourorder[0]].numroutes; |
| 193 |
*ub = (double) tours[tourorder[0]].cost; |
| 194 |
ub_pos = 0; |
| 195 |
} |
| 196 |
else{ |
| 197 |
for (i=0; i<= vrp->tournum; i++) |
| 198 |
if (tours[tourorder[i]].numroutes == vrp->numroutes){ |
| 199 |
*ub = (double) tours[tourorder[i]].cost; |
| 200 |
ub_pos = i; |
| 201 |
break; |
| 202 |
} |
| 203 |
} |
| 204 |
if (ub_pos >= 0){ |
| 205 |
/*vrp->cur_tour = &tours[tourorder[ub_pos]];*/ |
| 206 |
vrp->cur_tour->numroutes = tours[tourorder[ub_pos]].numroutes; |
| 207 |
vrp->cur_tour->cost = tours[tourorder[ub_pos]].cost; |
| 208 |
memcpy((char *)vrp->cur_tour->tour, |
| 209 |
(char *)tours[tourorder[ub_pos]].tour, |
| 210 |
vrp->vertnum*sizeof(_node)); |
| 211 |
vrp->cur_tour->algorithm = 0; |
| 212 |
vrp->cur_tour->solve_time = 0; |
| 213 |
FREE(vrp->cur_tour->route_info); |
| 214 |
}else{ |
| 215 |
printf("No tours found with %i routes -- no upper bound found\n\n", |
| 216 |
vrp->numroutes); |
| 217 |
} |
| 218 |
} |
| 219 |
|
| 220 |
vrp->bd_time.ub_overhead = used_time(&t); |
| 221 |
vrp->bd_time.ub_heurtime = heurtime; |
| 222 |
|
| 223 |
if (vrp->numroutes && lb_par->lower_bound){ |
| 224 |
lower_bound(vrp, lb_par, heur_out, (int)(*ub), jobs, tids, sent); |
| 225 |
lbtime += receive_lbs(vrp, heur_out, 1, vrp->numroutes, jobs, sent); |
| 226 |
} |
| 227 |
|
| 228 |
vrp->bd_time.lb_overhead += used_time(&t); |
| 229 |
vrp->bd_time.lb_heurtime = lbtime; |
| 230 |
|
| 231 |
if (heur_out) free((char *)heur_out); |
| 232 |
|
| 233 |
if (ub_pos>=0 && vrp->par.verbosity>0){ |
| 234 |
printf("\nThe best upper bound found with %i trucks is %i\n\n", |
| 235 |
vrp->numroutes, (int)(*ub)); |
| 236 |
if (vrp->par.verbosity >1){ |
| 237 |
if (windows){ |
| 238 |
/*if (!vrp->window) |
| 239 |
vrp->window = init_win(vrp->par.executables.winprog, |
| 240 |
vrp->par.debug.winprog, |
| 241 |
vrp->posx, vrp->posy, vrp->vertnum); |
| 242 |
vrp->window->windata.draw = TRUE; |
| 243 |
disp_tour(vrp->window, tours[tourorder[ub_pos]].tour, TRUE);*/ |
| 244 |
} |
| 245 |
} |
| 246 |
} |
| 247 |
else if (*ub && vrp->par.verbosity > 2){ |
| 248 |
printf("\nUsing upper bound of %i given in parameter file\n\n", |
| 249 |
(int)(*ub)); |
| 250 |
} |
| 251 |
|
| 252 |
if (vrp->lb->lower_bound && vrp->par.verbosity>0){ |
| 253 |
printf("\nThe best lower bound found with %i trucks is %.1f\n\n", |
| 254 |
vrp->numroutes, vrp->lb->lower_bound); |
| 255 |
#if 0 |
| 256 |
if (vrp->par.verbosity >1 && vrp->dg_id){ |
| 257 |
char name[20] = {"Lower Bound"}; |
| 258 |
disp_lb(vrp->dg_id, TRUE, name, vrp->lb->tree, vrp->lb->best_edges, |
| 259 |
vrp->vertnum, vrp->numroutes, CTOI_WAIT_FOR_CLICK_AND_REPORT); |
| 260 |
} |
| 261 |
#endif |
| 262 |
} |
| 263 |
|
| 264 |
/* |
| 265 |
p->comp_times.bc_overhead = used_time(&t); |
| 266 |
*/ |
| 267 |
init_send(DataInPlace); |
| 268 |
send_int_array(&dummy, 1); |
| 269 |
msend_msg(tids, jobs, STOP); |
| 270 |
for(i=0; i<jobs; kill_proc(tids[i++])); |
| 271 |
} |
| 272 |
} |