Debian Codegraph @

SYMPHONY/Applications/VRP/src/Heuristics/savings2.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 #include "savings2.h"
20
21 #include "sym_constants.h"
22 #include "heur_routines.h"
23 #include "binomial.h"
24 #include "vrp_common_types.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 void insert_cust2 PROTO((int cust_num, _node *tour, int node1,
35 int node2, int cur_route,
36 int prev_route_end));
37 tree_node *start_new_route2 PROTO((heur_prob *p, tree_node *head,
38 int starter));
39 tree_node *update_savings2 PROTO(( heur_prob *p, tree_node *head,
40 tree_node *mav_ptr, _node *tour,
41 int prev_route_end));
42 int new_start2 PROTO((int *intour, heur_prob *p,
43 int start, int num_cust));
44 void update PROTO((tree_node *cur_node, int savings, int node1,
45 int node2));
46 void savings2(int parent, heur_prob *p)
47 {
48 printf("\nIn savings2....\n\n");
49 _node *tour;
50 int mytid, info, r_bufid;
51 int i, capacity;
52 int vertnum;
53 int cur_route=1;
54 int weight = 0, *demand;
55 int starter;
56 tree_node *head, *max_ptr;
57 int savings, start, *intour;
58 int node1, node2, cust_num, num_cust = 0;
59 int cur_route_end = 0, prev_route_end = 0;
60 double t=0;
61
62 mytid = pvm_mytid();
63
64 (void) used_time(&t);
65
66
67 /*-----------------------------------------------------------------------*\
68 | Receive the parameters |
69 \*-----------------------------------------------------------------------*/
70 PVM_FUNC(r_bufid, pvm_recv(-1, SAVINGS2_DATA));
71 PVM_FUNC(info, pvm_upkfloat(&p->par.savings_par.mu, 1, 1));
72 PVM_FUNC(info, pvm_upkfloat(&p->par.savings_par.lamda, 1, 1));
73 PVM_FUNC(info, pvm_upkint(&start, 1, 1));
74 capacity = p->capacity;
75 vertnum = p->vertnum;
76 demand = p->demand;
77
78 if (start != FAR_INS) srand(start);
79
80 p->cur_tour = (best_tours *) calloc (1, sizeof(best_tours));
81 tour = p->cur_tour->tour = (_node *) calloc (vertnum, sizeof(_node));
82 intour = (int *) calloc (vertnum, sizeof(int));
83
84 /*------------------------------------------------------------------*\
85 | Initiate the first route by placing the initial starter (either |
86 | the farthest node from the depot of a random node) and the depot |
87 | on the first route |
88 \*------------------------------------------------------------------*/
89 starter = new_start2(intour, p, start, vertnum - 1);
90 tour[0].next = starter;
91 tour[starter].next = 0;
92 tour[0].route = 0;
93 tour[starter].route = cur_route;
94 intour[0] = IN_TOUR;
95 intour[starter] = IN_TOUR;
96 cur_route_end = starter;
97 weight += demand[starter];
98
99 /*------------------------------------------------------------------*\
100 | Initialize the heap with node 1 or node 2, whichever is not the |
101 | starter. |
102 \*------------------------------------------------------------------*/
103
104 if (starter != 1){
105 savings = (int) (SAV(&p->dist, 0, starter, 1));
106 node1 = 0;
107 node2 = starter;
108 cust_num = 1;
109 }
110 else{
111 savings = (int) (SAV(&p->dist, 0, 1, 2));
112 node1 = 0;
113 node2 = 1;
114 cust_num = 2;
115 }
116
117 head = make_heap(cust_num, savings, node1, node2);
118
119 /*----------------------------------------------------------*\
120 | Make the initial heap |
121 \*----------------------------------------------------------*/
122
123 if (cust_num == 1){
124 for (i=2; i<vertnum; i++){
125 if (i != starter){
126 savings = (int) (SAV(&p->dist, 0, starter, i));
127 cust_num = i;
128 head = heap_insert(head, cust_num, savings, node1, node2);
129 }
130 }
131 }
132 else{
133 for (i=3; i<vertnum; i++){
134 savings = (int) (SAV(&p->dist, 0, 1, i));
135 cust_num = i;
136 head = heap_insert(head, cust_num, savings, node1, node2);
137 }
138 }
139
140 /*------------------------------------------------------------------*\
141 | The following loop first finds the customer with the maximum |
142 | savings among all customers not yet put on routes and returns the |
143 | the position in which to insert the customer in order to achieve |
144 | that savings. It then checks the feasibility of inserting that |
145 | that customer on the current route and if it is infeasible, starts|
146 | a new route. |
147 \*------------------------------------------------------------------*/
148
149 while (head != NULL){
150 max_ptr = find_max(head);
151 if (weight + demand[max_ptr->cust_num] <= capacity){
152 head = extract_max(head, max_ptr);
153 intour[max_ptr->cust_num] = IN_TOUR;
154 weight += demand[max_ptr->cust_num];
155 insert_cust2(max_ptr->cust_num, tour, max_ptr->node1,
156 max_ptr->node2, cur_route, prev_route_end);
157 if (max_ptr->node2 == 0)
158 cur_route_end = max_ptr->cust_num;
159 head = update_savings2(p, head, max_ptr, tour, prev_route_end);
160 free(max_ptr);
161 num_cust++;
162 }
163 else{
164 cur_route++;
165 tour[cur_route_end].next = new_start2(intour, p,
166 start, vertnum-2-num_cust);
167 prev_route_end = cur_route_end;
168 cur_route_end = tour[prev_route_end].next;
169 tour[cur_route_end].route = cur_route;
170 intour[cur_route_end] = IN_TOUR;
171 head = start_new_route2(p, head, cur_route_end);
172 weight = demand[cur_route_end];
173 num_cust++;
174 }
175 }
176
177 p->cur_tour->cost = compute_tour_cost(&p->dist, tour);
178 p->cur_tour->numroutes = cur_route;
179
180 /*-----------------------------------------------------------------------*\
181 | Transmit the tour back to the parent |
182 \*-----------------------------------------------------------------------*/
183
184 send_tour(tour, p->cur_tour->cost, p->cur_tour->numroutes, SAVINGS2,
185 used_time(&t), parent, vertnum, 0, NULL);
186
187 if (intour) free ((char *) intour);
188
189 free_heur_prob(p);
190
191 }
192