Debian Codegraph @

SYMPHONY/Applications/VRP/src/Heuristics/tsp_fini.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 Eclipse Public License. Please see */
13 /* accompanying file for terms. */
14 /* */
15 /*===========================================================================*/
16
17 #include <string.h>
18 #include <stdlib.h>
19 #include <stdio.h>
20 #include "tsp_fini.h"
21 #include "sym_constants.h"
22 #include "sym_macros.h"
23 #include "tsp_ins_rout.h"
24 #include "s_path.h"
25 #include "heur_routines.h"
26 #include "qsort.h"
27
28 static int compar(const void *elem1, const void *elem2){
29 return(((neighbor *)elem1)->cost - ((neighbor *)elem2)->cost);
30 }
31
32 void tsp_fini(int parent, heur_prob *p)
33 {
34 printf("\nIn tsp_fini....\n\n");
35 int mytid, info, r_bufid;
36 int starter, farnode, v0, v1, cur_start;
37 _node *tsp_tour, *tour, *opt_tour;
38 int maxdist;
39 int *intour;
40 int last, cost;
41 int i, j;
42 neighbor *nbtree;
43 int trials, interval;
44 int farside, vertnum;
45 best_tours *opt_tours, *tours;
46 double t=0;
47
48 mytid = pvm_mytid();
49
50 (void) used_time(&t);
51
52 /*-----------------------------------------------------------------------*\
53 | Receive the VRP data |
54 \*-----------------------------------------------------------------------*/
55
56
57
58 PVM_FUNC(r_bufid, pvm_recv(-1, TSP_FINI_TRIALS));
59 PVM_FUNC(info, pvm_upkint(&trials, 1, 1));
60
61 PVM_FUNC(r_bufid, pvm_recv(parent, TSP_FINI_RATIO));
62 PVM_FUNC(info, pvm_upkint(&farside, 1, 1));
63
64 /*-----------------------------------------------------------------------*\
65 | Receive the starting point |
66 \*-----------------------------------------------------------------------*/
67 PVM_FUNC(r_bufid, pvm_recv(-1, TSP_START_POINT));
68 PVM_FUNC(info, pvm_upkint(&starter, 1, 1));
69 vertnum = p->vertnum;
70
71 if (starter == vertnum)
72 for (starter=v0=1, maxdist=ICOST(&p->dist, 0,1); v0<vertnum-1; v0++)
73 for (v1=v0+1; v1<vertnum; v1++)
74 if (maxdist < ICOST(&p->dist, v0, v1)){
75 maxdist = ICOST(&p->dist, v0, v1);
76 starter = v0;
77 }
78
79 /*-----------------------------------------------------------------------*\
80 | Allocate arrays |
81 \*-----------------------------------------------------------------------*/
82 tsp_tour = (_node *) malloc (vertnum * sizeof(_node));
83 nbtree = (neighbor *) malloc (vertnum * sizeof(neighbor));
84 intour = (int *) calloc (vertnum, sizeof(int));
85 tours = p->cur_tour = (best_tours *) calloc (1, sizeof(best_tours));
86 tour = p->cur_tour->tour = (_node *) calloc (vertnum, sizeof(_node));
87 opt_tours = (best_tours *) malloc (sizeof(best_tours));
88 opt_tour = (_node *) malloc (vertnum*sizeof(_node));
89
90 /*------------------------------------------------------------------------*\
91 | This heuristic is a so-called route-first, cluster-second heuristic. |
92 | We first construct a TSP route by farnear insert and then partition it |
93 | into feasible routes by finding a shortest cycle of a graph with edge |
94 | costs bewtween nodes being defined to be the cost of a route from one |
95 | endpoint of the edge to the other. |
96 \*------------------------------------------------------------------------*/
97
98 /*-----------------------------------------------------------------------*\
99 | Find the first 'farside node with farthest insertion from 'starter' |
100 \*-----------------------------------------------------------------------*/
101 last = 0;
102 intour[0] = IN_TOUR;
103 intour[starter] = IN_TOUR;
104 tsp_fi_insert_edges(p, starter, nbtree, intour, &last);
105 farnode = tsp_farthest(nbtree, intour, &last);
106 intour[farnode] = IN_TOUR;
107 tsp_fi_insert_edges(p, farnode, nbtree, intour, &last);
108 tsp_tour[starter].next = farnode;
109 tsp_tour[farnode].next = starter;
110
111 cost = 2 * ICOST(&p->dist, starter, farnode);
112 farside = MAX(farside, 2);
113 cost = tsp_farthest_ins_from_to(p, tsp_tour, cost,
114 2, farside, starter, nbtree, intour, &last);
115
116 /*------------------------------------------------------------------------*\
117 | Order the elements in nbtree (and fix the intour values) so after that |
118 | nbtree is suitable to continue with nearest insertion. |
119 \*------------------------------------------------------------------------*/
120
121 qsort((char *)(nbtree+1), last, sizeof(neighbor), compar);
122 for (i=1; i<=last; i++)
123 intour[nbtree[i].nbor] = i;
124
125 /*-----------------------------------------------------------------------*\
126 | Continue with nearest insertion |
127 \*-----------------------------------------------------------------------*/
128 cost = tsp_nearest_ins_from_to(p, tsp_tour, cost,
129 farside, vertnum-1, starter, nbtree, intour,
130 &last);
131
132 /*------------------------------------------------------------------------*\
133 | We must arbitrarily choose a node to be the first node on the first |
134 | route in order to start the partitioning algorithm. The trials variable |
135 | tells us how many starting points to try. Its value is contained in |
136 | p->par.tsp.numstarts. |
137 \*------------------------------------------------------------------------*/
138
139 if (trials > vertnum-1) trials = vertnum-1;
140 interval = (vertnum-1)/trials;
141 opt_tours->cost = MAXINT;
142
143 /*------------------------------------------------------------------------*\
144 | Try various partitionings and take the solution that has the least cost |
145 \*------------------------------------------------------------------------*/
146
147 for (i=0, cur_start = starter; i<trials; i++){
148 make_routes(p, tsp_tour, cur_start, tours);
149 if (tours->cost < opt_tours->cost){
150 (void) memcpy ((char *)opt_tours, (char *)tours, sizeof(best_tours));
151 (void) memcpy ((char *)opt_tour, (char *)tour, vertnum*sizeof(_node));
152 }
153 for (j=0; j<interval; j++)
154 cur_start = tsp_tour[cur_start].next;
155 }
156
157
158 /*-----------------------------------------------------------------------*\
159 | Transmit the tour back to the parent |
160 \*-----------------------------------------------------------------------*/
161
162 send_tour(opt_tour, opt_tours->cost, opt_tours->numroutes, TSP_FINI,
163 used_time(&t), parent, vertnum, 0, NULL);
164
165 if ( nbtree ) free ((char *) nbtree);
166 if ( intour ) free ((char *) intour);
167 if ( opt_tours ) free ((char *) opt_tours);
168 if ( opt_tour ) free ((char *) opt_tour);
169 if ( tsp_tour ) free ((char *) tsp_tour);
170
171 free_heur_prob(p);
172
173 }
174