Debian Codegraph @

SYMPHONY/Applications/VRP/src/Heuristics/savings_rout3.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 <stddef.h>
18
19 #include "sym_constants.h"
20 #include "binomial.h"
21 #include "savings3.h"//lazimmi dene
22 #include "ins_routines2.h"
23 #include "vrp_const.h"
24 #include "compute_cost.h"
25
26 /*------------------------------------------------------------------*\
27 | This function inserts cust_num into the current route between node1|
28 | and node2. |
29 \*------------------------------------------------------------------*/
30 int find_new_ins_route3(heur_prob *p, int ins_node,
31 _node *tour, int *node1, int *node2,
32 route_data *route_info);
33 #ifndef _SAV
34 #define _SAV
35 #define SAV(d, a, b, c) (p->par.savings_par.lamda) * ICOST(d, 0, c) - \
36 (ICOST(d,a,c) + ICOST(d,b,c) - \
37 (p->par.savings_par.mu) * ICOST(d,a,b))
38 #endif
39
40 void insert_cust3(int cust_num, _node *tour, int node1, int node2,
41 int cur_route, int *demand, route_data *route_info)
42 {
43 if (node1 == 0){
44 route_info[cur_route].first = cust_num;
45 tour[cust_num].next = node2;
46 }else if (node2 == 0){
47 route_info[cur_route].last = cust_num;
48 tour[node1].next = cust_num;
49 }else{
50 tour[node1].next = cust_num;
51 tour[cust_num].next = node2;
52 }
53 tour[cust_num].route = cur_route;
54 route_info[cur_route].weight += demand[cust_num];
55 return;
56 }
57
58 /*===========================================================================*/
59
60 /*-----------------------------------------------------------------------*\
61 | This function updates the savings number of a node following the |
62 | insertion of a new node onto the current route. If the old insertion |
63 | point of the node still exists (i.e. if the new node was not inserted |
64 | there, then we need only calculate the savings for the two possible new |
65 | insertion points created by the addition of the new node to the route. |
66 | Otherwise, we need to start from scratch and recalculate the savings for|
67 | all possible insertion points. |
68 \*-----------------------------------------------------------------------*/
69
70 int new_savings3(heur_prob *p, tree_node *max_ptr, tree_node *head, _node *tour,
71 int *node1, int *node2, route_data *route_info)
72 {
73 int savings, max_savings;
74 int ins_route = max_ptr->node1 ? tour[max_ptr->node1].route :
75 tour[max_ptr->node2].route;
76
77 if (((head->node1 == max_ptr->node1) && (head->node2 == max_ptr->node2)) ||
78 (route_info[ins_route].weight + p->demand[max_ptr->cust_num] >=
79 p->capacity)){
80 max_savings = find_new_ins_route3(p, head->cust_num, tour, node1, node2,
81 route_info);
82 return(max_savings);
83 }
84
85 if ((savings = (int) (SAV(&p->dist, max_ptr->node1, max_ptr->cust_num,
86 head->cust_num))) > head->savings){
87 *node1 = max_ptr->node1;
88 *node2 = max_ptr->cust_num;
89 max_savings = savings;
90 }
91 else if ((savings = (int) (SAV(&p->dist, max_ptr->cust_num, max_ptr->node2,
92 head->cust_num))) > head->savings){
93 *node1 = max_ptr->cust_num;
94 *node2 = max_ptr->node2;
95 max_savings = savings;
96 }
97 else{
98 *node1 = head->node1;
99 *node2 = head->node2;
100 max_savings = head->savings;
101 }
102 return(max_savings);
103 }
104
105 /*===========================================================================*/
106
107 /*---------------------------------------------------------------------------*\
108 | This function updates the heap after a new node has been addded to the |
109 | solution. It walks through the current heap, recalculates the savings |
110 | numbers and merges each node into a new heap. |
111 \*---------------------------------------------------------------------------*/
112
113 tree_node *update_savings3(heur_prob *p, tree_node *head, tree_node *max_ptr,
114 _node *tour, route_data *route_info)
115 {
116 tree_node *temp1, *temp2;
117 int savings;
118 int degree;
119 tree_node *new_head;
120 int node1, node2;
121
122 if (head == NULL) return(NULL);
123
124 temp1 = head->child;
125 temp2 = head->sibling;
126 savings = new_savings3(p, max_ptr, head, tour, &node1, &node2, route_info);
127 if (savings == -MAXINT)
128 return(NULL);
129 new_head = make_heap(head->cust_num, savings, node1, node2);
130 degree = head->degree;
131 free(head);
132
133 if (degree >0){
134 temp1 = update_savings3(p, temp1, max_ptr, tour, route_info);
135 if (!temp1)
136 return(NULL);
137 new_head = merge_heaps(temp1, new_head);
138 }
139
140 if (temp2!=NULL){
141 temp2 = update_savings3(p, temp2, max_ptr, tour, route_info);
142 if (!temp2)
143 return(NULL);
144 new_head = merge_heaps(temp2, new_head);
145 }
146 if(!degree && !temp2 &&!new_head) return(NULL);
147 else return(new_head);
148 }
149
150 /*===========================================================================*/
151
152 int find_new_ins_route3(heur_prob *p, int ins_node,
153 _node *tour, int *node1, int *node2,
154 route_data *route_info)
155 {
156 int max_savings, savings;
157 int cur_route, cur_node, prev_node;
158 int weight = p->demand[ins_node];
159
160 for (max_savings = -MAXINT, cur_route = 1; cur_route <= p->numroutes;
161 cur_route++){
162 if (route_info[cur_route].weight + weight > p->capacity)
163 continue;
164 cur_node = route_info[cur_route].first;
165 prev_node = 0;
166 for (; cur_node; prev_node = cur_node, cur_node = tour[cur_node].next){
167 if ((savings = (int) (SAV(&p->dist, prev_node, cur_node, ins_node)))
168 > max_savings){
169 max_savings = savings;
170 *node1 = prev_node;
171 *node2 = cur_node;
172 }
173 }
174 }
175
176 return(max_savings);
177 }