Debian Codegraph @

SYMPHONY/Applications/VRP/src/Heuristics/savings3.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 <stdio.h>
18
19 #include "savings3.h"
20 #include "sym_macros.h"
21 #include "sym_constants.h"
22 #include "heur_routines.h"
23 #include "ins_routines2.h"
24 #include "binomial.h"
25 #include "vrp_common_types.h"
26
27 #ifndef _SAV
28 #define _SAV
29 #define SAV(d, a, b, c) (p->par.savings_par.lamda) * ICOST(d, 0, c) - \
30 (ICOST(d,a,c) + ICOST(d,b,c) - \
31 (p->par.savings_par.mu) * ICOST(d,a,b))
32 #endif
33
34 void insert_cust3 PROTO((int cust_num, _node *tour, int node1,
35 int node2, int cur_route, int *demand,
36 route_data *route_info));
37 tree_node *update_savings3 PROTO((heur_prob *p, tree_node *head,
38 tree_node *max_ptr, _node *tour,
39 route_data *route_info));
40 int find_new_ins_route3 PROTO((heur_prob *p, int ins_node, _node *tour,
41 int *node1, int *node2,
42 route_data *route_info));
43
44 void savings3(int parent, heur_prob *p)
45 {
46 printf("\nIn savings3....\n\n");
47 _node *tour;
48 int mytid, info, r_bufid;
49 int i, capacity;
50 int vertnum;
51 int cur_route=1;
52 int *demand;
53 tree_node *head, *max_ptr;
54 int savings, *intour, max_savings;
55 int numroutes, v0, v1, ins_route, cust_num;
56 double t=0;
57 neighbor *nbtree;
58 route_data *route_info;
59
60 mytid = pvm_mytid();
61 (void) used_time(&t);
62
63
64 /*-----------------------------------------------------------------------*\
65 | Receive the parameters |
66 \*-----------------------------------------------------------------------*/
67
68 PVM_FUNC(r_bufid, pvm_recv(-1, S3_NUMROUTES));
69 PVM_FUNC(info, pvm_upkint(&p->numroutes, 1, 1));
70 PVM_FUNC(r_bufid, pvm_recv(-1, SAVINGS3_DATA));
71 printf("\nCheckpoint 1\n");
72 PVM_FUNC(info, pvm_upkfloat(&p->par.savings_par.mu, 1, 1));
73 PVM_FUNC(info, pvm_upkfloat(&p->par.savings_par.lamda, 1, 1));
74 capacity = p->capacity;
75 vertnum = p->vertnum;
76 demand = p->demand;
77 numroutes = p->numroutes;
78
79 p->cur_tour = (best_tours *) calloc (1, sizeof(best_tours));
80 tour = p->cur_tour->tour = (_node *) calloc (vertnum, sizeof(_node));
81 intour = (int *) calloc (vertnum, sizeof(int));
82 nbtree = (neighbor *) malloc (vertnum * sizeof(neighbor));
83
84 seeds2(p, &numroutes, intour, nbtree);
85
86 p->numroutes = numroutes;
87
88 route_info = p->cur_tour->route_info;
89 p->cur_tour->numroutes = numroutes;
90
91 for( i = 0; i<vertnum; i++){
92 if (intour[i] != IN_TOUR)
93 intour[i] = 0;
94 tour[i].next = 0;
95 }
96 printf("\nCheckpoint 2\n");
97 for (i = 0; intour[i] == IN_TOUR; i++);
98 for (max_savings = MAXINT, cur_route = 1; cur_route <= numroutes;
99 cur_route++){
100 if ((savings = (int) (SAV(&p->dist, 0, route_info[cur_route].first, i)))
101 < max_savings){
102 max_savings = savings;
103 v1 = route_info[cur_route].first;
104 }
105 }
106 head = make_heap(i, max_savings, 0, v1);
107
108 /*----------------------------------------------------------*\
109 | Make the initial heap |
110 \*----------------------------------------------------------*/
111
112 for (i++; i<vertnum; i++){
113 if (intour[i] == IN_TOUR)
114 continue;
115 for (max_savings = MAXINT, cur_route = 1; cur_route <= numroutes;
116 cur_route++){
117 if (((savings = (int) (SAV(&p->dist, 0, route_info[cur_route].first, i)))
118 < max_savings) && (route_info[cur_route].weight +
119 demand[i] <= capacity)){
120 max_savings = savings;
121 v1 = route_info[cur_route].first;
122 }
123 }
124 head = heap_insert(head, i, max_savings, 0, v1);
125 }
126 printf("\nCheckpoint 3\n");
127 /*------------------------------------------------------------------*\
128 | The following loop first finds the customer with the maximum |
129 | savings among all customers not yet put on routes and returns the |
130 | the position in which to insert the customer in order to achieve |
131 | that savings. It then checks the feasibility of inserting that |
132 | that customer on the current route and if it is infeasible, starts|
133 | a new route. |
134 \*------------------------------------------------------------------*/
135
136 cust_num = numroutes+1;
137 while (head != NULL){
138 max_ptr = find_max(head);
139 head = extract_max(head, max_ptr);
140 ins_route = max_ptr->node1 ? tour[max_ptr->node1].route :
141 tour[max_ptr->node2].route;
142 if (route_info[ins_route].weight+demand[max_ptr->cust_num] <= capacity){
143 insert_cust3(max_ptr->cust_num, tour, max_ptr->node1,
144 max_ptr->node2, ins_route, demand, route_info);
145 head = update_savings3(p, head, max_ptr, tour, route_info);
146 cust_num++;
147 }else{
148 savings = find_new_ins_route3(p, max_ptr->cust_num, tour, &v0, &v1,
149 route_info);
150 if (savings == -MAXINT){
151 head = NULL;
152 continue;
153 }
154 head = heap_insert(head, max_ptr->cust_num, savings, v0, v1);
155 }
156 FREE(max_ptr);
157 }
158 printf("\nCheckpoint 4\n");
159 tour[0].next = route_info[1].first;
160
161 /*------------------------------------------------------------------------*\
162 | This loop points the last node of each route to the first node of the |
163 | next route. At the end of this procedure, the last node of each route is |
164 | pointing at the depot, which is not what we want. |
165 \*------------------------------------------------------------------------*/
166
167 for (cur_route = 1; cur_route < numroutes; cur_route++)
168 tour[route_info[cur_route].last].next = route_info[cur_route+1].first;
169
170 if (cust_num != vertnum){
171 printf(
172 "\n\nError: customer cannot be inserted on any route .... aborting!\n");
173 p->cur_tour->cost = 0;
174 }else{
175 p->cur_tour->cost = compute_tour_cost(&p->dist, tour);
176 }
177
178 /*-----------------------------------------------------------------------*\
179 | Transmit the tour back to the parent |
180 \*-----------------------------------------------------------------------*/
181
182 send_tour(tour, p->cur_tour->cost, p->cur_tour->numroutes, SAVINGS3,
183 used_time(&t), parent, vertnum, 0, NULL);
184 printf("\nCheckpoint 5\n");
185 FREE(intour);
186 FREE(nbtree);
187
188 free_heur_prob(p);
189 printf("\nCheckpoint 6\n");
190 }
191
192