Debian Codegraph @

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