| 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 |
|