Debian Codegraph @

SYMPHONY/Applications/VRP/src/Heuristics/farnear_ins.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 "farnear_ins.h"
18 #include <stdio.h>
19 #ifndef COMPAR
20 #define COMPAR
21 static int compar(const void *elem1, const void *elem2){
22 return(((neighbor *)elem1)->cost - ((neighbor *)elem2)->cost);
23 }
24 #endif
25 void farnear_ins(int parent, heur_prob *p)
26 {
27 printf("\nIn farnear_ins....\n\n");
28 int mytid, info, r_bufid;
29 int farnode, *starter;
30 int *intour;
31 int i, last, cost, numroutes;
32 neighbor *nbtree;
33 _node *tour;
34 route_data *route_info;
35 int cur_route, start;
36 best_tours *tours;
37 double t=0;
38
39 mytid = pvm_mytid();
40 (void) used_time(&t);
41
42 tours = p->cur_tour = (best_tours *) calloc (1, sizeof(best_tours));
43
44
45 /*-----------------------------------------------------------------------*\
46 | Receive the VRP data |
47 \*-----------------------------------------------------------------------*/
48
49 PVM_FUNC(r_bufid, pvm_recv(-1, ROUTE_FNINS_VRP_DATA));
50 PVM_FUNC(info, pvm_upkbyte((char *)tours, sizeof(best_tours), 1));
51 tour = p->cur_tour->tour = (_node *) calloc (p->vertnum, sizeof(_node));
52 PVM_FUNC(info, pvm_upkbyte((char *)tour, (p->vertnum)*sizeof(_node), 1));
53 numroutes = p->cur_tour->numroutes;
54 starter = (int *) calloc (numroutes, sizeof(int));
55 route_info = tours->route_info
56 = (route_data *) calloc (numroutes+1, sizeof(route_data));
57
58 PVM_FUNC(r_bufid, pvm_recv(-1, ROUTE_FNINS_START_RULE));
59 PVM_FUNC(info, pvm_upkint(&start, 1, 1));/*receive the start
60 rule*/
61
62 PVM_FUNC(r_bufid, pvm_recv(parent, FINI_RATIO));
63 PVM_FUNC(info, pvm_upkfloat(&p->par.fini_ratio, 1, 1));
64
65 if (start != FAR_INS) srand(start); /*if the start rule is random, then*\
66 \*initialize the random number gen.*/
67 starters(p, starter, route_info, start);/*generate the route starters for*\
68 \*all the clusters. */
69 /*-----------------------------------------------------------------------*\
70 | Allocate arrays |
71 \*-----------------------------------------------------------------------*/
72
73 nbtree = (neighbor *) malloc (p->vertnum * sizeof(neighbor));
74 intour = (int *) calloc (p->vertnum, sizeof(int));
75
76 for(cur_route = 1; cur_route<=numroutes; cur_route++){
77 /*---------------------------------------------------------------------*\
78 | Find the first 'farside node with farthest insertion from 'starter' |
79 \*---------------------------------------------------------------------*/
80 if (route_info[cur_route].numcust <= 1) continue;
81 cost = 0;
82 last = 0;
83 intour[0] = 0;
84 intour[starter[cur_route-1]] = IN_TOUR;
85 fi_insert_edges(p, starter[cur_route-1], nbtree, intour, &last, tour,
86 cur_route);
87 farnode = farthest(nbtree, intour, &last);
88 intour[farnode] = IN_TOUR;
89 fi_insert_edges(p, farnode, nbtree, intour, &last, tour, cur_route);
90 tour[starter[cur_route-1]].next = farnode;
91 tour[farnode].next = starter[cur_route-1];
92 if (starter[cur_route - 1] == 0)
93 route_info[cur_route].first = route_info[cur_route].last = farnode;
94 if (farnode == 0)
95 route_info[cur_route].first = route_info[cur_route].last
96 = starter[cur_route-1];
97
98 cost = 2 * ICOST(&p->dist, starter[cur_route-1], farnode);
99 cost = farthest_ins_from_to(p, tour, cost,
100 2, (int)ceil(route_info[cur_route].
101 numcust * p->par.fini_ratio)+1,
102 starter[cur_route-1], nbtree, intour,
103 &last, route_info, cur_route);
104
105 /*---------------------------------------------------------------------*\
106 | Order the elements in nbtree (and fix the intour values) so after that|
107 | nbtree is suitable to continue with nearest insertion. |
108 \*---------------------------------------------------------------------*/
109 qsort((char *)(nbtree+1), last, sizeof(neighbor), compar);
110 for (i=1; i<=last; i++)
111 intour[nbtree[i].nbor] = i;
112
113 /*---------------------------------------------------------------------*\
114 | Continue with nearest insertion |
115 \*---------------------------------------------------------------------*/
116 cost = nearest_ins_from_to(p, tour, cost,
117 MAX(((int)ceil(route_info[cur_route].numcust*
118 p->par.fini_ratio)+1), 2),
119 route_info[cur_route].numcust+1,
120 starter[cur_route-1],
121 nbtree, intour, &last, route_info, cur_route);
122
123 route_info[cur_route].cost = cost;
124 }
125
126 tour[0].next = route_info[1].first;
127
128 /*------------------------------------------------------------------------*\
129 | This loop points the last node of each route to the first node of the |
130 | next route. At the end of this procedure, the last node of each route is |
131 | pointing at the depot, which is not what we want. |
132 \*------------------------------------------------------------------------*/
133 for (cur_route = 1; cur_route< numroutes; cur_route++)
134 tour[route_info[cur_route].last].next = route_info[cur_route+1].first;
135
136 cost = compute_tour_cost(&p->dist, tour);
137
138 /*-----------------------------------------------------------------------*\
139 | Transmit the tour back to the parent |
140 \*-----------------------------------------------------------------------*/
141
142 send_tour(tour, cost, numroutes, tours->algorithm, used_time(&t), parent,
143 p->vertnum, 1, route_info);
144
145 if ( nbtree ) free ((char *) nbtree);
146 if ( intour ) free ((char *) intour);
147 if ( starter ) free ((char *) starter);
148
149 free_heur_prob(p);
150
151 }