| 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 |
|