Debian Codegraph @

SYMPHONY/Applications/VRP/src/Heuristics/tsp_fi.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 <stdio.h>
19 #include "tsp_fi.h"
20 #include "sym_constants.h"
21 #include "tsp_ins_rout.h"
22 #include "s_path.h"
23 #include "heur_routines.h"
24
25 void tsp_fi(int parent, heur_prob *p)
26 {
27 printf("\nIn tsp_fi....\n\n");
28 int mytid, info, r_bufid;
29 int starter, farnode, v0, v1, cur_start;
30 _node *tsp_tour, *tour, *opt_tour;
31 int maxdist;
32 int *intour;
33 int last, cost;
34 int i, j, vertnum;
35 neighbor *nbtree;
36 int trials, interval;
37 best_tours *opt_tours, *tours;
38 double t=0;
39
40 mytid = pvm_mytid();
41 printf("\nthis time, my tid in tsp_fi.c is %i", mytid);
42 (void) used_time(&t);
43
44 /*-----------------------------------------------------------------------*\
45 | Receive the VRP data |
46 \*-----------------------------------------------------------------------*/
47
48
49
50 PVM_FUNC(r_bufid, pvm_recv(-1, TSP_FI_TRIALS));
51 PVM_FUNC(info, pvm_upkint(&trials, 1, 1));
52
53 /*-----------------------------------------------------------------------*\
54 | Receive the starting point |
55 \*-----------------------------------------------------------------------*/
56 PVM_FUNC(r_bufid, pvm_recv(-1, TSP_START_POINT));
57 PVM_FUNC(info, pvm_upkint(&starter, 1, 1));
58 vertnum = p->vertnum;
59
60 if (starter == vertnum)
61 for (starter=v0=1, maxdist=ICOST(&p->dist, 0,1); v0<vertnum-1; v0++)
62 for (v1=v0+1; v1<vertnum; v1++)
63 if (maxdist < ICOST(&p->dist, v0, v1)){
64 maxdist = ICOST(&p->dist, v0, v1);
65 starter = v0;
66 }
67
68 /*-----------------------------------------------------------------------*\
69 | Allocate arrays |
70 \*-----------------------------------------------------------------------*/
71 tsp_tour = (_node *) malloc (vertnum * sizeof(_node));
72 nbtree = (neighbor *) malloc (vertnum * sizeof(neighbor));
73 intour = (int *) calloc (vertnum, sizeof(int));
74 tours = p->cur_tour = (best_tours *) calloc (1, sizeof(best_tours));
75 tour = p->cur_tour->tour = (_node *) calloc (vertnum, sizeof(_node));
76 opt_tours = (best_tours *) malloc (sizeof(best_tours));
77 opt_tour = (_node *) malloc (vertnum*sizeof(_node));
78
79 /*------------------------------------------------------------------------*\
80 | This heuristic is a so-called route-first, cluster-second heuristic. |
81 | We first construct a TSP route by farthest insert and then partition it |
82 | into feasible routes by finding a shortest cycle of a graph with edge |
83 | costs bewtween nodes being defined to be the cost of a route from one |
84 | endpoint of the edge to the other. |
85 \*------------------------------------------------------------------------*/
86
87 /*-----------------------------------------------------------------------*\
88 | Find the farthest insertion tour from 'starter' |
89 \*-----------------------------------------------------------------------*/
90 last = 0;
91 intour[0] = IN_TOUR;
92 intour[starter] = IN_TOUR;
93 tsp_fi_insert_edges(p, starter, nbtree, intour, &last);
94 farnode = tsp_farthest(nbtree, intour, &last);
95 intour[farnode] = IN_TOUR;
96 tsp_fi_insert_edges(p, farnode, nbtree, intour, &last);
97 tsp_tour[starter].next = farnode;
98 tsp_tour[farnode].next = starter;
99
100 cost = 2 * ICOST(&p->dist, starter, farnode);
101 cost = tsp_farthest_ins_from_to(p, tsp_tour, cost,
102 2, vertnum-1, starter, nbtree, intour, &last);
103
104 /*------------------------------------------------------------------------*\
105 | We must arbitrarily choose a node to be the first node on the first |
106 | route in order to start the partitioning algorithm. The trials variable |
107 | tells us how many starting points to try. Its value is contained in |
108 | p->par.tsp.numstarts. |
109 \*------------------------------------------------------------------------*/
110
111 if (trials > vertnum-1) trials = vertnum-1;
112 interval = (vertnum-1)/trials;
113 opt_tours->cost = MAXINT;
114
115 /*------------------------------------------------------------------------*\
116 | Try various partitionings and take the solution that has the least cost |
117 \*------------------------------------------------------------------------*/
118
119 for (i=0, cur_start = starter; i<trials; i++){
120 make_routes(p, tsp_tour, cur_start, tours);
121 if (tours->cost < opt_tours->cost){
122 (void) memcpy ((char *)opt_tours, (char *)tours, sizeof(best_tours));
123 (void) memcpy ((char *)opt_tour, (char *)tour, vertnum*sizeof(_node));
124 }
125 for (j=0; j<interval; j++)
126 cur_start = tsp_tour[cur_start].next;
127 }
128
129
130 /*-----------------------------------------------------------------------*\
131 | Transmit the tour back to the parent |
132 \*-----------------------------------------------------------------------*/
133
134 send_tour(opt_tour, opt_tours->cost, opt_tours->numroutes, TSP_FI,
135 used_time(&t), parent, vertnum, 0, NULL);
136
137 if ( nbtree ) free ((char *) nbtree);
138 if ( intour ) free ((char *) intour);
139 if ( opt_tours ) free ((char *) opt_tours);
140 if ( opt_tour ) free ((char *) opt_tour);
141 if ( tsp_tour ) free ((char *) tsp_tour);
142
143 free_heur_prob(p);
144
145 }