| 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 |
#include <stdlib.h> |
| 19 |
|
| 20 |
#include "sym_constants.h" |
| 21 |
#include "savings.h"//lazimmi dene |
| 22 |
#include "vrp_const.h" |
| 23 |
#include "compute_cost.h" |
| 24 |
|
| 25 |
#ifndef _SAV |
| 26 |
#define _SAV |
| 27 |
#define SAV(d, a, b, c) (p->par.savings_par.lamda) * ICOST(d, 0, c) - \ |
| 28 |
(ICOST(d,a,c) + ICOST(d,b,c) - \ |
| 29 |
(p->par.savings_par.mu) * ICOST(d,a,b)) |
| 30 |
#endif |
| 31 |
|
| 32 |
/*------------------------------------------------------------------*\ |
| 33 |
| This function inserts cust_num into the current route between node1| |
| 34 |
| and node2. | |
| 35 |
\*------------------------------------------------------------------*/ |
| 36 |
#ifndef _INSERT_CUST |
| 37 |
#define _INSERT_CUST |
| 38 |
void insert_cust(int cust_num, _node *tour, int node1, |
| 39 |
int node2, int cur_route, |
| 40 |
int prev_route_end) |
| 41 |
{ |
| 42 |
if (node1 == 0){ |
| 43 |
tour[prev_route_end].next = cust_num; |
| 44 |
tour[cust_num].route = cur_route; |
| 45 |
tour[cust_num].next = node2; |
| 46 |
} |
| 47 |
else{ |
| 48 |
tour[node1].next = cust_num; |
| 49 |
tour[cust_num].next = node2; |
| 50 |
tour[cust_num].route = cur_route; |
| 51 |
} |
| 52 |
return; |
| 53 |
} |
| 54 |
#endif |
| 55 |
/*===========================================================================*/ |
| 56 |
|
| 57 |
/*---------------------------------------------------------------------*\ |
| 58 |
| This function prints the current routes to stdout. It is for debugging| |
| 59 |
| purposes only. | |
| 60 |
\*---------------------------------------------------------------------*/ |
| 61 |
#ifndef _PRINT_ROUTES |
| 62 |
#define _PRINT_ROUTES |
| 63 |
void print_routes(_node *tour) |
| 64 |
{ |
| 65 |
int prev_node = 0, node = tour[0].next; |
| 66 |
|
| 67 |
while (node != 0){ |
| 68 |
if (tour[prev_node].route != tour[node].route) |
| 69 |
printf("\nRoute #%i: ", tour[node].route); |
| 70 |
printf("%i ", node); |
| 71 |
prev_node = node; |
| 72 |
node = tour[node].next; |
| 73 |
} |
| 74 |
printf("\n\n"); |
| 75 |
return; |
| 76 |
} |
| 77 |
#endif |
| 78 |
/*===========================================================================*/ |
| 79 |
|
| 80 |
/*--------------------------------------------------------------------*\ |
| 81 |
| This function computes the starter for a new route. It either returns| |
| 82 |
| the farthest customer from the depot that is not yet on a route or it| |
| 83 |
| returns a random node that is not yet on a route, depending on the | |
| 84 |
| value of the variable start. | |
| 85 |
\*--------------------------------------------------------------------*/ |
| 86 |
#ifndef _NEW_START |
| 87 |
#define _NEW_START |
| 88 |
int new_start(int *intour, heur_prob *p, int start, int num_cust) |
| 89 |
{ |
| 90 |
int starter = 0, start_pos, cust, count=0; |
| 91 |
int cost = -MAXINT, temp_cost; |
| 92 |
int vertnum = p->vertnum; |
| 93 |
|
| 94 |
if (start == FAR_INS) |
| 95 |
for (cust=1; cust<vertnum; cust++){ |
| 96 |
if (((temp_cost = ICOST(&p->dist, 0, cust)) > cost) && |
| 97 |
(intour[cust] != IN_TOUR)){ |
| 98 |
starter = cust; |
| 99 |
cost = temp_cost; |
| 100 |
} |
| 101 |
} |
| 102 |
else{ |
| 103 |
start_pos = rand()%num_cust+1; |
| 104 |
for (cust = 1, count = 0; count<start_pos; cust ++) |
| 105 |
if (intour[cust] != IN_TOUR) count ++; |
| 106 |
starter = cust-1; |
| 107 |
} |
| 108 |
return(starter); |
| 109 |
} |
| 110 |
#endif |
| 111 |
/*===========================================================================*/ |
| 112 |
|
| 113 |
/*---------------------------------------------------------------------*\ |
| 114 |
| find-max finds the cutomer with the maximum savings value among all | |
| 115 |
| customers not already on routes and returns that customer along with | |
| 116 |
| the position in which it should be inserted in the current route in | |
| 117 |
| order to achieve that savings. | |
| 118 |
\*---------------------------------------------------------------------*/ |
| 119 |
|
| 120 |
void find_max(int *ins_cust, int *savings, int *node1, |
| 121 |
int *node2, _node *tour, int *intour, |
| 122 |
int prev_route_end, heur_prob *p) |
| 123 |
{ |
| 124 |
int v0 = 0, v1; |
| 125 |
register int i; |
| 126 |
int vertnum = p->vertnum; |
| 127 |
|
| 128 |
*savings = -MAXINT; |
| 129 |
|
| 130 |
for (i = 1; i<vertnum; i++) |
| 131 |
if (intour[i] != IN_TOUR){ |
| 132 |
v0 = 0; |
| 133 |
v1 = tour[prev_route_end].next; |
| 134 |
if (SAV(&p->dist, v0, v1, i) > *savings){ |
| 135 |
*savings = (int) (SAV(&p->dist, v0, v1, i)); |
| 136 |
*node1 = v0; |
| 137 |
*node2 = v1; |
| 138 |
*ins_cust = i; |
| 139 |
} |
| 140 |
do{ |
| 141 |
v1 = tour[v0=v1].next; |
| 142 |
if (SAV (&p->dist, v0, v1, i) > *savings){ |
| 143 |
*savings = (int) (SAV(&p->dist, v0, v1, i)); |
| 144 |
*node1 = v0; |
| 145 |
*node2 = v1; |
| 146 |
*ins_cust = i; |
| 147 |
} |
| 148 |
}while (v1 != 0); |
| 149 |
} |
| 150 |
return; |
| 151 |
} |
| 152 |
|