Debian Codegraph @

SYMPHONY/Applications/VRP/src/Master/Heuristics/collect_solutions.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 <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 }