Debian Codegraph @

SYMPHONY/Applications/VRP/src/Heuristics/savings_rout2.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 <stdlib.h>
18 #include <stdio.h>
19
20 #include "sym_constants.h"
21 #include "binomial.h"
22 #include "savings2.h"//lazimmi dene
23 #include "vrp_const.h"
24 #include "compute_cost.h"
25
26 #ifndef _SAV
27 #define _SAV
28 #define SAV(d, a, b, c) (p->par.savings_par.lamda) * ICOST(d, 0, c) - \
29 (ICOST(d,a,c) + ICOST(d,b,c) - \
30 (p->par.savings_par.mu) * ICOST(d,a,b))
31 #endif
32
33 /*------------------------------------------------------------------*\
34 | This function inserts cust_num into the current route between node1|
35 | and node2. |
36 \*------------------------------------------------------------------*/
37
38 void insert_cust2(int cust_num, _node *tour, int node1,
39 int node2, int cur_route, int end_of_route)
40 {
41 if (node1 == 0){
42 tour[end_of_route].next = cust_num;
43 tour[cust_num].route = cur_route;
44 tour[cust_num].next = node2;
45 }
46 else{
47 tour[node1].next = cust_num;
48 tour[cust_num].next = node2;
49 tour[cust_num].route = cur_route;
50 }
51 return;
52 }
53
54 /*===========================================================================*/
55
56 /*-------------------------------------------------------------------*\
57 | This function starts a new heap for the next route by walking |
58 | through the current heap, computing the new savings value for each |
59 | customer encountered and inserting that customer in the new heap |
60 \*-------------------------------------------------------------------*/
61
62 tree_node *start_new_route2(heur_prob *p, tree_node *head, int starter)
63 {
64 tree_node *temp1, *temp2;
65 int savings;
66 int degree;
67 tree_node *new_head = NULL;
68
69 temp1 = head->child;
70 temp2 = head->sibling;
71 degree = head->degree;
72
73 if (head->cust_num == starter){
74 free(head);
75 head = NULL;
76 }
77 else{
78 savings = (int) (SAV(&p->dist, 0, starter, head->cust_num));
79 new_head = make_heap(head->cust_num, savings, 0, starter);
80 degree = head->degree;
81 free(head);
82 }
83
84 if (degree >0){
85 temp1 = start_new_route2 (p, temp1, starter);
86 if (!head)
87 new_head = temp1;
88 else
89 new_head = merge_heaps(temp1, new_head);
90 }
91
92 if (temp2 != NULL){
93 temp2 = start_new_route2 (p, temp2, starter);
94 if (!head && !degree)
95 new_head = temp2;
96 else
97 new_head = merge_heaps(temp2, new_head);
98 }
99 if (!degree && !temp2 && !head) return(NULL);
100 else return(new_head);
101 }
102
103 /*===========================================================================*/
104
105 /*-----------------------------------------------------------------------*\
106 | This function updates the savings number of a node following the |
107 | insertion of a new node onto the current route. If the old insertion |
108 | point of the node still exists (i.e. if the new node was not inserted |
109 | there, then we need only calculate the savings for the two possible new |
110 | insertion points created by the addition of the new node to the route. |
111 | Otherwise, we need to start from scratch and recalculate the savings for|
112 | all possible insertion points. |
113 \*-----------------------------------------------------------------------*/
114
115 int new_savings2(heur_prob *p, tree_node *max_ptr, tree_node *head, _node *tour,
116 int prev_route_end, int *node1, int *node2)
117 {
118 int v0 = 0, v1;
119 int savings, temp_savings;
120
121 if ((head->node1 == max_ptr->node1) && (head->node2 == max_ptr->node2)){
122 v1 = tour[prev_route_end].next;
123 savings = (int) (SAV (&p->dist, 0, v1, head->cust_num));
124 *node1 = v0;
125 *node2 = v1;
126
127 do{
128 v1 = tour[v0=v1].next;
129 if (SAV (&p->dist, v1, v0, head->cust_num) > savings){
130 savings = (int) (SAV(&p->dist, v0, v1, head->cust_num));
131 *node1 = v0;
132 *node2 = v1;
133 }
134 }while (v1 != 0);
135 }
136 else{
137 if ((temp_savings = (int) (SAV(&p->dist, max_ptr->node1,
138 max_ptr->cust_num, head->cust_num)))
139 > head->savings){
140 *node1 = max_ptr->node1;
141 *node2 = max_ptr->cust_num;
142 savings = (int) (SAV(&p->dist, max_ptr->node1,
143 max_ptr->cust_num, head->cust_num));
144 }
145 else if ((temp_savings = (int) (SAV(&p->dist, max_ptr->cust_num,
146 max_ptr->node2, head->cust_num)))
147 > head->savings){
148 *node1 = max_ptr->cust_num;
149 *node2 = max_ptr->node2;
150 savings = (int) (SAV(&p->dist, max_ptr->cust_num,
151 max_ptr->node2, head->cust_num));
152 }
153 else{
154 *node1 = head->node1;
155 *node2 = head->node2;
156 savings = head->savings;
157 }
158 }
159 return(savings);
160 }
161
162 /*===========================================================================*/
163
164 /*---------------------------------------------------------------------------*\
165 | This function updates the heap after a new node has been addded to a route. |
166 | It walks through the current heap, recalculates the savings numbers and |
167 | merges each node into a new heap. |
168 \*---------------------------------------------------------------------------*/
169
170 tree_node *update_savings2(heur_prob *p, tree_node *head, tree_node *max_ptr,
171 _node *tour, int prev_route_end)
172 {
173 tree_node *temp1, *temp2;
174 int savings;
175 int degree;
176 tree_node *new_head;
177 int node1, node2;
178
179 if (head == NULL) return(NULL);
180
181 temp1 = head->child;
182 temp2 = head->sibling;
183 savings = new_savings2(p, max_ptr, head, tour, prev_route_end, &node1, &node2);
184 new_head = make_heap(head->cust_num, savings, node1, node2);
185 degree = head->degree;
186 free(head);
187
188 if (degree >0){
189 temp1 = update_savings2(p, temp1, max_ptr, tour, prev_route_end);
190 new_head = merge_heaps(temp1, new_head);
191 }
192
193 if (temp2!=NULL){
194 temp2 = update_savings2(p, temp2, max_ptr, tour, prev_route_end);
195 new_head = merge_heaps(temp2, new_head);
196 }
197 if(!degree && !temp2 &&!new_head) return(NULL);
198 else return(new_head);
199 }
200
201 /*===========================================================================*/
202
203 /*---------------------------------------------------------------------*\
204 | This function prints the current routes to stdout. It is for debugging|
205 | purposes only. |
206 \*---------------------------------------------------------------------*/
207
208 void print_routes2(_node *tour)
209 {
210 int prev_node = 0, node = tour[0].next;
211
212 while (node != 0){
213 if (tour[prev_node].route != tour[node].route)
214 printf("\nRoute #%i: ", tour[node].route);
215 printf("%i ", node);
216 prev_node = node;
217 node = tour[node].next;
218 }
219 printf("\n\n");
220 return;
221 }
222
223 /*===========================================================================*/
224
225 /*--------------------------------------------------------------------*\
226 | This function computes the starter for a new route. It either returns|
227 | the farthest customer from the depot that is not yet on a route or it|
228 | returns a random node that is not yet on a route, depending on the |
229 | value of the variable start. |
230 \*--------------------------------------------------------------------*/
231
232 int new_start2(int *intour, heur_prob *p, int start,
233 int num_cust)
234 {
235 int starter = 0, start_pos, count=0, i=0;
236 int cost = -MAXINT;
237 int vertnum = p->vertnum;
238
239 if (start == FAR_INS)
240 for (i=1; i<vertnum; i++){
241 if ((ICOST(&p->dist, 0, i) > cost) &&
242 (intour[i] != IN_TOUR)){
243 starter = i;
244 cost = ICOST(&p->dist, 0, i);
245 }
246 }
247 else{
248 start_pos = rand()%num_cust+1;
249 do{
250 i++;
251 if (intour[i] != IN_TOUR) count++;
252 }while (count < start_pos);
253 starter = i;
254 }
255
256 return(starter);
257 }
258