Debian Codegraph @

SYMPHONY/Applications/VRP/src/Heuristics/savings_rout.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 <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