Debian Codegraph @

SYMPHONY/Applications/VRP/src/Heuristics/near_cluster.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 "near_cluster.h"
18 #include <stdio.h>
19 void near_cluster(int parent, heur_prob *p)
20 {
21 printf("\nIn near_cluster....\n\n");
22 int vertnum;
23 int mytid, info, r_bufid;
24 int cost, zero_cost = 0;
25 int *intour, last = 0;
26 int numroutes, i;
27 neighbor *nbtree;
28 _node *tour;
29 route_data *route_info;
30 int cur_route;
31 best_tours *tours;
32 double t=0;
33
34 (void) used_time(&t);
35
36 mytid = pvm_mytid();
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, NC_NUMROUTES));
45 PVM_FUNC(info, pvm_upkint(&p->numroutes, 1, 1));
46
47 vertnum = p->vertnum;
48 numroutes = p->numroutes;
49
50 /*-----------------------------------------------------------------------*\
51 | Allocate arrays |
52 \*-----------------------------------------------------------------------*/
53
54 nbtree = (neighbor *) malloc (vertnum * sizeof(neighbor));
55 intour = (int *) calloc (vertnum, sizeof(int));
56 tour = p->cur_tour->tour
57 = (_node *) calloc (vertnum, sizeof(_node));
58
59 /*-----------------------------------------------------------------------*\
60 | First we generate seed customers for all the routes |
61 \*-----------------------------------------------------------------------*/
62
63 seeds2(p, &numroutes, intour, nbtree);
64
65 route_info = p->cur_tour->route_info;
66
67 p->cur_tour->numroutes = numroutes;
68
69 /*-----------------------------------------------------------------------*\
70 | This algorithm builds all routes simultaneously. For each customer not |
71 | already in the solution, it keeps track of the route that it is closest |
72 | to (i.e. the route # of the customer already in the solution that it is |
73 | closest to). At each step, the customer in closest proximity to its host|
74 | route is added to that route and all distances are updated. If it is |
75 | found to be infeasible to add the customer to the route, then a new host|
76 | is found and we start the process again. Note that as we go through the |
77 | algorithm, the last node of each route always points towards the depot |
78 \*-----------------------------------------------------------------------*/
79
80 if (nbtree) free ((char *) nbtree);
81
82 nbtree = (neighbor *) calloc (vertnum, sizeof(neighbor));
83
84 for( i = 0; i<vertnum; i++){
85 if (intour[i] != IN_TOUR)
86 intour[i] = 0;
87 tour[i].next = 0;
88 }
89
90 for (cur_route = 1; cur_route<=numroutes; cur_route++)
91 ni_insert_edges2(p, route_info[cur_route].first, nbtree, intour, &last,
92 tour, route_info);
93
94 /* Form the routes by nearest insertion as described above */
95
96 nearest_ins2(p, tour, route_info, numroutes+1, vertnum,
97 nbtree, intour, &last, &zero_cost);
98 if(!zero_cost){
99 tour[0].next = route_info[1].first;
100
101
102 /*-------------------------------------------------------------------------*\
103 | This loop points the last node of each route to the first node of the next|
104 | route. At the end of this procedure, the last node of each route is |
105 | pointing at the depot, which is not what we want. |
106 \*-------------------------------------------------------------------------*/
107
108 for (cur_route = 1; cur_route < numroutes; cur_route++)
109 tour[route_info[cur_route].last].next = route_info[cur_route+1].first;
110
111 cost = compute_tour_cost(&p->dist, tour);
112
113 /*-----------------------------------------------------------------------*\
114 | Transmit the tour back to the parent |
115 \*-----------------------------------------------------------------------*/
116
117 send_tour(tour, cost, numroutes, NEAR_CLUSTER, used_time(&t), parent,
118 vertnum, 1, route_info);
119
120 if ( nbtree ) free ((char *) nbtree);
121 if ( intour ) free ((char *) intour);
122
123 free_heur_prob(p);
124 }
125 }