Debian Codegraph @

SYMPHONY/Applications/VRP/src/Heuristics/farthest_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 "farthest_ins.h"
18 #include <stdio.h>
19 void farthest_ins(int parent, heur_prob *p)
20 {
21 printf("\nIn farthest_ins....\n\n");
22 int mytid, info, r_bufid;
23 int farnode, *starter;
24 int *intour;
25 int last, cost, numroutes;
26 neighbor *nbtree;
27 _node *tour;
28 route_data *route_info;
29 int cur_route, start;
30 best_tours *tours;
31 double t=0;
32
33 mytid = pvm_mytid();
34
35 (void) used_time(&t);
36
37
38 tours = p->cur_tour = (best_tours *) calloc (1, sizeof(best_tours));
39
40 /*-----------------------------------------------------------------------*\
41 | Receive the VRP data |
42 \*-----------------------------------------------------------------------*/
43
44 PVM_FUNC(r_bufid, pvm_recv(-1, ROUTE_FINS_VRP_DATA));
45 PVM_FUNC(info, pvm_upkbyte((char *)tours, sizeof(best_tours), 1));
46 tour = p->cur_tour->tour = (_node *) calloc (p->vertnum, sizeof(_node));
47 PVM_FUNC(info, pvm_upkbyte((char *)tour, (p->vertnum)*sizeof(_node), 1));
48 numroutes = p->cur_tour->numroutes;
49 starter = (int *) calloc (numroutes, sizeof(int));
50 route_info = p->cur_tour->route_info
51 = (route_data *) calloc (numroutes+1, sizeof(route_data));
52
53 PVM_FUNC(r_bufid, pvm_recv(-1, ROUTE_FINS_START_RULE));
54 PVM_FUNC(info, pvm_upkint(&start, 1, 1));/*receive the start
55 rule*/
56
57 if (start != FAR_INS) srand(start); /*if the start rule is random, then*\
58 \*initialize the random number gen.*/
59 starters(p, starter, route_info, start);/*generate the route starters for*\
60 \*all the clusters. */
61 /*-----------------------------------------------------------------------*\
62 | Allocate arrays |
63 \*-----------------------------------------------------------------------*/
64
65 nbtree = (neighbor *) malloc (p->vertnum * sizeof(neighbor));
66 intour = (int *) calloc (p->vertnum, sizeof(int));
67
68 /*-----------------------------------------------------------------------*\
69 | Find the farthest insertion tour from 'starter' |
70 \*-----------------------------------------------------------------------*/
71
72 for(cur_route = 1; cur_route<=numroutes; cur_route++){
73 /*---------------------------------------------------------------------*\
74 | The first part of this loop adds the starter and the farthest node |
75 | away from it into the route to initialize it. Then a function is |
76 | called which inserts the rest of the nodes into the route in farthest |
77 | insert order. |
78 \*---------------------------------------------------------------------*/
79 if (route_info[cur_route].numcust <= 1) continue;
80 cost = 0;
81 last = 0;
82 intour[0] = 0;
83 intour[starter[cur_route -1]] = IN_TOUR;
84 fi_insert_edges(p, starter[cur_route-1], nbtree, intour, &last, tour, cur_route);
85 farnode = farthest(nbtree, intour, &last);
86 intour[farnode] = IN_TOUR;
87 fi_insert_edges(p, farnode, nbtree, intour, &last, tour, cur_route);
88 tour[starter[cur_route-1]].next = farnode;
89 tour[farnode].next = starter[cur_route-1];
90 if (starter[cur_route - 1] == 0)
91 route_info[cur_route].first = route_info[cur_route].last = farnode;
92 if (farnode == 0)
93 route_info[cur_route].first = route_info[cur_route].last
94 = starter[cur_route-1];
95
96 cost = 2 * ICOST(&p->dist, starter[cur_route-1], farnode);
97 cost = farthest_ins_from_to(p, tour, cost, 2, route_info[cur_route].numcust+1,
98 starter[cur_route-1], nbtree, intour, &last,
99 route_info, cur_route);
100
101 route_info[cur_route].cost = cost;
102 }
103
104 tour[0].next = route_info[1].first;
105
106 /*-------------------------------------------------------------------------*\
107 | This loop points the last node of each route to the first node of the next|
108 | route. At the end of this procedure, the last node of each route is |
109 | pointing at the depot, which is not what we want. |
110 \*-------------------------------------------------------------------------*/
111 for (cur_route = 1; cur_route < numroutes; cur_route++)
112 tour[route_info[cur_route].last].next = route_info[cur_route+1].first;
113
114 cost = compute_tour_cost(&p->dist, tour);
115
116 /*-----------------------------------------------------------------------*\
117 | Transmit the tour back to the parent |
118 \*-----------------------------------------------------------------------*/
119
120 send_tour(tour, cost, numroutes, tours->algorithm, used_time(&t), parent,
121 p->vertnum, 1, route_info);
122
123 if ( nbtree ) free ((char *) nbtree);
124 if ( intour ) free ((char *) intour);
125 if ( starter ) free ((char *) starter);
126
127 free_heur_prob(p);
128
129 }
130