Debian Codegraph @

SYMPHONY/Applications/VRP/src/Heuristics/sweep.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 "sweep.h"
18 #include "qsort.h"
19 #include <string.h>
20 #include <stdio.h>
21 /*-----------------------------------------------------------------------*\
22 | Make_tour receives the nodes in sorted order and performs the algorithm |
23 | described below, starting with a number of equally spaced nodes as |
24 | determined by the parameter p->par.sweep_trials. |
25 \*-----------------------------------------------------------------------*/
26
27 void make_tour(heur_prob *p, sweep_data *data, best_tours *final_tour)
28 {
29 int i, k, weight = 0, j=1, l;
30 int interval, start=0;
31 int cost;
32 _node *tour;
33 int *demand = p->demand;
34 int vertnum = p->vertnum;
35 int capacity = p->capacity;
36
37 if (p->par.sweep_trials>vertnum - 1) p->par.sweep_trials = vertnum-1;
38
39 final_tour->cost = MAXINT;
40
41 tour = (_node *) calloc (vertnum, sizeof(_node));
42
43 interval = vertnum/p->par.sweep_trials;
44
45 for (l=0; l < p->par.sweep_trials; l++){
46
47 tour[0].next = data[start].cust;
48 tour[0].route = 0;
49
50 for (k=1; k < vertnum-1; k++){
51
52 i = (k-1) + start;
53 if (i>vertnum-2) i-=(vertnum-1);
54
55 if (weight + demand[data[i].cust] <= capacity){
56 weight += demand[data[i].cust];
57 if (i != vertnum - 2)
58 tour[data[i].cust].next = data[i+1].cust;
59 else
60 tour[data[i].cust].next = data[0].cust;
61 tour[data[i].cust].route=j;
62 }
63 else{
64 weight = demand[data[i].cust];
65 j++; if (i != vertnum - 2) tour[data[i].cust].next =
66 data[i+1].cust; else tour[data[i].cust].next = data[0].cust;
67 tour[data[i].cust].route=j; } } i = (k-1) + start; if
68 (i>vertnum-2) i-=(vertnum-1); if (weight +
69 demand[data[i].cust] <= capacity){ tour[data[i].cust].next =
70 0; tour[data[i].cust].route = j; } else{
71 j++;
72 tour[data[i].cust].next = 0;
73 tour[data[i].cust].route = j;
74 }
75
76 cost = compute_tour_cost (&p->dist, tour);
77 if (cost < final_tour->cost){
78 memcpy((char *)final_tour->tour,(char *)tour, vertnum*sizeof(_node));
79 final_tour->cost = cost;
80 final_tour->numroutes=j;
81 }
82
83 j=1;
84 weight=0;
85 start += interval;
86
87 }
88 free((char *)tour);
89 }
90
91 /*===========================================================================*/
92
93 /*-----------------------------------------------------------------*\
94 | The sweep algorithm is a very simple heuristic for clustering. |
95 | We simply order the nodes radially about the depot and then add |
96 | to the current route in this order until capacity is exceeded and |
97 | then we start a new route. Depending on where we start in the |
98 | cyclic ordering, we get different solutions. |
99 \*-----------------------------------------------------------------*/
100
101 void sweep(int parent, heur_prob *p)
102 {
103 printf("\nIn sweep....\n\n");
104 int mytid, info, r_bufid;
105 int i;
106 int vertnum;
107 sweep_data *data;
108 float depotx, depoty;
109 float tempx, tempy;
110 double t=0;
111
112 mytid = pvm_mytid();
113
114 (void) used_time(&t);
115
116 printf("mytid in sweep.c= %i", pvm_mytid());
117 /*-----------------------------------------------------------------------*\
118 | Receive the VRP data |
119 \*-----------------------------------------------------------------------*/
120
121 PVM_FUNC(r_bufid, pvm_recv(-1, SWEEP_TRIALS));
122 PVM_FUNC(info, pvm_upkint(&(p->par.sweep_trials), 1, 1));
123 printf("\nCheckpoint 1\n");
124 /*-----------------------------------------------------------------------*/
125
126 vertnum = p->vertnum;
127 p->cur_tour = (best_tours *)calloc(1, sizeof(best_tours));
128 p->cur_tour->tour = (_node *)calloc(vertnum, sizeof(_node));
129 printf("\nCheckpoint 2\n");
130 data = (sweep_data *)calloc(vertnum-1, sizeof(sweep_data));
131 if (p->dist.coordx && p->dist.coordy){
132 depotx = p->dist.coordx[0];
133 depoty = p->dist.coordy[0];
134 printf("\nCheckpoint 3\n");
135 /*calculate angles for sorting*/
136 for (i=0; i<vertnum-1; i++){
137 tempx = p->dist.coordx[i+1] - depotx;
138 tempy = p->dist.coordy[i+1] - depoty;
139 data[i].angle = (float) atan2(tempy, tempx);
140 if (data[i].angle < 0) data[i].angle += 2*M_PI;
141 data[i].cust=i+1;
142 }
143 printf("\nCheckpoint 4\n");
144 quicksort(data, vertnum-1);
145 printf("\nCheckpoint 5\n");
146 make_tour(p, data, p->cur_tour);
147 printf("\nCheckpoint 6\n");
148 /*-----------------------------------------------------------------------*\
149 | Transmit the tour back to the parent |
150 \*-----------------------------------------------------------------------*/
151
152 send_tour(p->cur_tour->tour, p->cur_tour->cost, p->cur_tour->numroutes,
153 SWEEP, used_time(&t), parent, vertnum, 0, NULL);
154 printf("\nCheckpoint 7\n");
155 }
156 if (data) free((char *) data);
157 printf("\nCheckpoint 8\n");
158 free_heur_prob(p);
159
160 }
161
162
163
164
165
166