Debian Codegraph @

SYMPHONY/Applications/VRP/src/Heuristics/s_path.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 "s_path.h"
21 #include "vrp_const.h"
22 #include "compute_cost.h"
23
24 /*----------------------------------------------------------------*\
25 | This next routine computes the shortest path in a graph using |
26 | a naive implementation of Dyjkstra's shortest path algorithm. d |
27 | contains the current best distance to the node in questions and |
28 | pi represents the shortest path tree so that pi[node] is the |
29 | predecessor of node on a shortest path from the origin. An |
30 | adjacency list is the data structure used by the algorithm to |
31 | access the graph.
32 \*----------------------------------------------------------------*/
33
34 int *sp(adj_list **adj, int numnodes, int origin,
35 int dest)
36 {
37 int *d, mincost;
38 register int i, j;
39 int *pi, minindex=0;
40 adj_list *temp;
41
42 d = (int *) malloc (numnodes*sizeof(int));
43 pi = (int *) calloc (numnodes, sizeof(int));
44
45 /* First set all the distances to infinity */
46
47 for (i= 1; i<numnodes; i++)
48 d[i] = MAXINT;
49
50 /* Now set the distances of the nodes adjacent to the origin */
51
52 temp = adj[origin];
53 while (temp != NULL){
54 d[temp->custnum] = temp->cost;
55 temp = temp->next;
56 }
57
58 /*--------------------------------------------------------------*\
59 | In each iteration, we search for the nopde with the smallest |
60 | d-value, set that value to -1 indicating that node is in the |
61 | shortest path tree, and add the node to the shortest path tree |
62 | We stop when we scan the destination node. Note that the last |
63 | node on the path to the origin does not actually point to the |
64 | origin. It points to zero so that we can use this routine to |
65 | find shortest cycles. This is actually what we want to do. |
66 \*--------------------------------------------------------------*/
67
68 for (i=1; i<numnodes; i++){
69 mincost = MAXINT;
70 for (j=1; j<numnodes; j++)
71 if ((d[j]>=0)&&(d[j]<mincost)){
72 mincost = d[j];
73 minindex = j;
74 }
75 temp = adj[minindex];
76 while (temp != NULL){
77 if (d[temp->custnum] > d[minindex] + temp->cost){
78 d[temp->custnum] = d[minindex] +temp->cost;
79 pi[temp->custnum] = minindex;
80 }
81 temp = temp->next;
82 }
83 if (minindex == dest) break;
84 d[minindex] = -1;
85 }
86 return(pi);
87 }
88
89 /*===========================================================================*/
90
91 /*---------------------------------------------------------------------*\
92 | This routine partitions the TSP tour into feasible routes for a VRP |
93 | solution by using a shortest path algorithm to find the optimal points|
94 | to break the TSP tour. |
95 \*---------------------------------------------------------------------*/
96
97 void make_routes(heur_prob *p, _node *tsp_tour, int start,
98 best_tours *new_tour)
99 {
100 int cur_node, prev_node, route_beg, prev_route_beg;
101 int weight, i, capacity = p->capacity;
102 int cur_route = 1;
103 int cost;
104 _node *tour = new_tour->tour;
105 adj_list **adj;
106 adj_list *temp, *path;
107 int *pi, route_end;
108 int vertnum = p->vertnum;
109 int *demand = p->demand;
110
111 adj = (adj_list **) calloc (vertnum, sizeof(adj_list *));
112
113 /*--------------------------------------------------------------------*\
114 | First we must construct the graph to give to the shortest path |
115 | algorithm. In this graph, the edge costs are as follows. The cost of |
116 | edge between nodes i and j is the cost of a route beginning with i's |
117 | successor on the TSP tour and ending with j (in bewtween, the route |
118 | follows the same ordering as the TSP tour itself) if this is a |
119 | feasible route and infinity otherwise. Now if we find a |
120 | shortest cycle in this graph, then the nodes in the cycle will be the|
121 | endpoints of the routes in an optimal partition. This is what I do. |
122 | We need to arbitrarily specify the fist endpoint in advance. |
123 | This is the value contained the start variable. The tsp_tour |
124 | structure contains the original TSP tour. |
125 \*--------------------------------------------------------------------*/
126
127 for (prev_route_beg = start, route_beg = tsp_tour[start].next, i=0;
128 i<vertnum-1; prev_route_beg = route_beg,
129 route_beg = tsp_tour[route_beg].next, i++){
130 cur_node = route_beg;
131 prev_node = 0;
132 temp = adj[prev_route_beg] = (adj_list *) calloc (1, sizeof(adj_list));
133 weight = demand[cur_node];
134 cost = ICOST(&p->dist, prev_node, cur_node);
135 temp->cost = cost + ICOST(&p->dist, 0, cur_node);
136 temp->custnum = cur_node;
137 prev_node = cur_node;
138 cur_node = tsp_tour[cur_node].next;
139 while (weight + demand[cur_node] <= capacity){
140 weight += demand[cur_node];
141 cost += ICOST(&p->dist, prev_node, cur_node);
142 temp->next = (adj_list *) calloc (1, sizeof(adj_list));
143 temp = temp->next;
144 temp->cost = cost + ICOST(&p->dist, 0, cur_node);
145 temp->custnum = cur_node;
146 prev_node = cur_node;
147 cur_node = tsp_tour[cur_node].next;
148 }
149 }
150
151 /* The graph is constructed. Now find a shortest cycle in it */
152
153 pi = sp(adj, vertnum, start, start);
154
155 /*--------------------------------------------------------------------*\
156 | Now the shortest cycle information is contained in pi. However, using|
157 | pi, we can only trace the shortest cycle in one direction since it is|
158 | actually stored as a directed path from the start node to itself. |
159 | Also, we can only trace the TSp tour in one direction since it is |
160 | stored in the same way. So we must store the cycle in the reverse |
161 | direction in order to break up the TSP tour. That is what this piece |
162 | of code does. It stores the nodes on the cycle in opposite order in a|
163 | linked list to be used in the next part of the code. |
164 \*--------------------------------------------------------------------*/
165
166 path = (adj_list *) calloc (1, sizeof(adj_list));
167 path->custnum = start;
168 cur_node = pi[start];
169 while (cur_node){
170 temp = (adj_list *) calloc (1, sizeof(adj_list));
171 temp->custnum = cur_node;
172 temp->next = path;
173 path = temp;
174 cur_node = pi[cur_node];
175 }
176 temp = path;
177
178 /*--------------------------------------------------------------------*\
179 | Now we have the optimal break points stored in order in a liked list.|
180 | We trace the TSP tour, copying each node into the VRP tour until we |
181 | reach the endpoint of a route and then we change the route number. |
182 \*--------------------------------------------------------------------*/
183
184 tour[0].next = tsp_tour[start].next;
185 cur_node = tour[0].next;
186 route_end = temp->custnum;
187 for (i=1; i<vertnum-1; i++){
188 tour[cur_node].next = tsp_tour[cur_node].next;
189 tour[cur_node].route = cur_route;
190 if (cur_node == route_end){
191 cur_route++;
192 if (temp->next){
193 temp = temp->next;
194 route_end = temp->custnum;
195 }
196 else break;
197 }
198 cur_node = tsp_tour[cur_node].next;
199 }
200 tour[cur_node].next = 0;
201 tour[cur_node].route = cur_route;
202
203 new_tour->cost = compute_tour_cost(&p->dist, tour);
204 new_tour->numroutes = cur_route;
205 }
206
207
208
209
210
211
212
213