| 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 <memory.h> |
| 18 |
#include <stdio.h> |
| 19 |
#include <stdlib.h> |
| 20 |
#include <unistd.h> |
| 21 |
#include "BB_constants.h" |
| 22 |
#include "sym_messages.h" |
| 23 |
#include "collect_solutions.h" |
| 24 |
#include "compute_cost.h" |
| 25 |
#include "vrp_master_functions.h" |
| 26 |
#include "network.h" |
| 27 |
#include "vrp_const.h" |
| 28 |
#include "vrp_macros.h" |
| 29 |
|
| 30 |
/*--------------------------------------------------------------------*\ |
| 31 |
| The receive_tours function is used to receive the tours | |
| 32 |
| output by various heuristic processes running in parallel and keep | |
| 33 |
| an ordered list of them in a binary tree. It checks about once every | |
| 34 |
| second to see if any tours have come into the recieve buffer and if | |
| 35 |
| so, it updates the binary tree and stores the tour if it is one of | |
| 36 |
| the lowest (vrp->par.tours_to_keep) cost tours | |
| 37 |
\*--------------------------------------------------------------------*/ |
| 38 |
|
| 39 |
double collect_solutions(vrp_problem *vrp, int trials, int *last, |
| 40 |
char add_edges, best_tours *solutions) |
| 41 |
{ |
| 42 |
printf("in get_rh_solutions... \n"); |
| 43 |
int pos; |
| 44 |
int i, round; |
| 45 |
int *tourorder = vrp->tourorder, tournum = -1; |
| 46 |
best_tours *tours = vrp->tours;/*-------------------------------------*\ |
| 47 |
| new best tours are put in this tours* | |
| 48 |
\*-------------------------------------*/ |
| 49 |
int v0, v1, vertnum = vrp->vertnum; |
| 50 |
double total_solve_time = 0; |
| 51 |
edge_data *next_edge = NULL; |
| 52 |
small_graph *g = NULL; |
| 53 |
int newedgenum=0; |
| 54 |
|
| 55 |
if (add_edges){ |
| 56 |
g = vrp->g; |
| 57 |
next_edge = g->edges+g->edgenum; |
| 58 |
} |
| 59 |
|
| 60 |
|
| 61 |
|
| 62 |
for (round=0; round<trials; round++){ |
| 63 |
|
| 64 |
if (tournum + 1 < vrp->par.tours_to_keep){ |
| 65 |
*last = ++tournum; |
| 66 |
tours[*last].cost = MAXINT; |
| 67 |
} |
| 68 |
else{ |
| 69 |
*last = tourorder[tournum]; |
| 70 |
} |
| 71 |
|
| 72 |
if (tours[*last].cost >solutions[round].cost){ /*check to see if tour is one of *\ |
| 73 |
|the (vrp->par.tours_to_keep) | |
| 74 |
|cheapest and if so, update | |
| 75 |
\*binary tree */ |
| 76 |
tours[*last].cost = solutions[round].cost; |
| 77 |
tours[*last].numroutes = solutions[round].numroutes; |
| 78 |
tours[*last].algorithm = solutions[round].algorithm; |
| 79 |
tours[*last].solve_time += solutions[round].solve_time; |
| 80 |
total_solve_time += solutions[round].solve_time;//solution time of one batch |
| 81 |
|
| 82 |
memcpy((char *)tours[*last].tour, (char *)solutions[round].tour, |
| 83 |
(vertnum) * sizeof(_node)); |
| 84 |
for (pos = tournum -1; |
| 85 |
pos >=0 &&tours[tourorder[pos]].cost >solutions[round].cost; pos--){ |
| 86 |
tourorder[pos+1]=tourorder[pos]; |
| 87 |
} |
| 88 |
tourorder[pos+1]=*last; |
| 89 |
} |
| 90 |
|
| 91 |
if (add_edges){ |
| 92 |
v0 = 0; |
| 93 |
v1 = solutions[round].tour[0].next; |
| 94 |
for (pos = 0; pos<vertnum; pos++){ |
| 95 |
v1 = solutions[round].tour[v0=v1].next; |
| 96 |
if(solutions[round].tour[v0].route == solutions[round].tour[v1].route){ |
| 97 |
if (v0 < v1){ |
| 98 |
next_edge->v0 = v0; |
| 99 |
next_edge->v1 = v1; |
| 100 |
} |
| 101 |
else{ |
| 102 |
next_edge->v0 = v1; |
| 103 |
next_edge->v1 = v0; |
| 104 |
} |
| 105 |
if (!bsearch((char *)next_edge, (char *)g->edges, |
| 106 |
g->edgenum, sizeof(edge_data), is_same_edge)){ |
| 107 |
(next_edge++)->cost = ICOST(&vrp->dist, v0, v1); |
| 108 |
newedgenum++; |
| 109 |
} |
| 110 |
} |
| 111 |
}//for |
| 112 |
}//if |
| 113 |
|
| 114 |
}//for |
| 115 |
|
| 116 |
if (add_edges && newedgenum){ |
| 117 |
g->edgenum += newedgenum; |
| 118 |
delete_dup_edges(g); |
| 119 |
} |
| 120 |
vrp->tournum = tournum; |
| 121 |
for (i=0; i<trials; i++) |
| 122 |
free ((char *)solutions[i].tour); |
| 123 |
free((char *)solutions); |
| 124 |
return(total_solve_time); |
| 125 |
} |