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