| 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 |
/* Capacitated Network Routing Problems. */ |
| 6 |
/* */ |
| 7 |
/* (c) Copyright 2000-2007 Ted Ralphs. All Rights Reserved. */ |
| 8 |
/* */ |
| 9 |
/* This application was developed by Ted Ralphs ([email protected]) */ |
| 10 |
/* */ |
| 11 |
/* This software is licensed under the Eclipse Public License. Please see */ |
| 12 |
/* accompanying file for terms. */ |
| 13 |
/* */ |
| 14 |
/*===========================================================================*/ |
| 15 |
|
| 16 |
/* system include files */ |
| 17 |
#include <stdio.h> |
| 18 |
#include <stdlib.h> |
| 19 |
#include <math.h> |
| 20 |
|
| 21 |
/* CNRP include files */ |
| 22 |
#include "compute_cost.h" |
| 23 |
#include "cnrp_macros.h" |
| 24 |
#include "cnrp_const.h" |
| 25 |
|
| 26 |
/*===========================================================================*/ |
| 27 |
|
| 28 |
/*===========================================================================*\ |
| 29 |
* This file contains functions for computing costs. |
| 30 |
\*===========================================================================*/ |
| 31 |
|
| 32 |
/*===========================================================================*\ |
| 33 |
* This function computes the cost of the edge from va to vb |
| 34 |
\*===========================================================================*/ |
| 35 |
|
| 36 |
int compute_icost(distances *dist, int va, int vb) |
| 37 |
{ |
| 38 |
double q1, q2, q3, dx, dy, dz; |
| 39 |
int cost = 0; |
| 40 |
|
| 41 |
if (dist->wtype == _GEO){ |
| 42 |
q1 = cos( dist->coordy[va] - dist->coordy[vb] ); |
| 43 |
q2 = cos( dist->coordx[va] - dist->coordx[vb] ); |
| 44 |
q3 = cos( dist->coordx[va] + dist->coordx[vb] ); |
| 45 |
cost = (int) (RRR*acos(0.5*((1.0+q1)*q2-(1.0-q1)*q3))+1.0); |
| 46 |
} |
| 47 |
else{ |
| 48 |
dx = dist->coordx[va] - dist->coordx[vb]; |
| 49 |
dy = dist->coordy[va] - dist->coordy[vb]; |
| 50 |
switch (dist->wtype){ |
| 51 |
case _EUC_2D : cost = (int) floor( sqrt( dx*dx + dy*dy ) + 0.5); |
| 52 |
break; |
| 53 |
case _EUC_3D : dz = dist->coordz[va] - dist->coordz[vb]; |
| 54 |
cost = (int) floor( sqrt( dx*dx + dy*dy + dz*dz) + 0.5); |
| 55 |
break; |
| 56 |
case _MAX_2D : cost = (int) fabs(dx); |
| 57 |
if (cost < fabs(dy)) cost = (int) fabs(dy); |
| 58 |
break; |
| 59 |
case _MAX_3D : dz = dist->coordz[va] - dist->coordz[vb]; |
| 60 |
cost = (int) fabs(dx); |
| 61 |
if (cost < fabs(dy)) cost = (int) fabs(dy); |
| 62 |
if (cost < fabs(dz)) cost = (int) fabs(dz); |
| 63 |
break; |
| 64 |
case _MAN_2D : cost = (int) floor( dx+dy+0.5 ); |
| 65 |
break; |
| 66 |
case _MAN_3D : dz = dist->coordz[va] - dist->coordz[vb]; |
| 67 |
cost = (int) floor( dx+dy+dz+0.5 ); |
| 68 |
break; |
| 69 |
case _CEIL_2D : cost = (int)ceil( sqrt( dx*dx + dy*dy ) + 0.5); |
| 70 |
break; |
| 71 |
case _ATT : cost = (int)( sqrt( (dx*dx + dy*dy ) / 10 ) + 1); |
| 72 |
break; |
| 73 |
} |
| 74 |
} |
| 75 |
return( cost ); |
| 76 |
} |
| 77 |
|
| 78 |
/*===========================================================================*\ |
| 79 |
* This function computes the canonical tour and puts it into the field |
| 80 |
* p->cur_tour. It adds the nodes to routes in order until capacity is |
| 81 |
* exceeded, and then it starts a new route, |
| 82 |
\*===========================================================================*/ |
| 83 |
|
| 84 |
void canonical_tour(distances *dist, best_tours *cur_tour, int vertnum, |
| 85 |
double capacity, double *demand) |
| 86 |
{ |
| 87 |
register int i, j = 1; |
| 88 |
double weight = 0; |
| 89 |
_node *tour = cur_tour->tour; |
| 90 |
|
| 91 |
if (demand[1] > capacity){ |
| 92 |
fprintf(stderr, "Error: weight greater than truck capacity\n"); |
| 93 |
exit(1); /*check whether any of the weights exceed capacity*/ |
| 94 |
} |
| 95 |
|
| 96 |
tour[0].next = 1; |
| 97 |
tour[0].route = 0; |
| 98 |
|
| 99 |
for ( i=1; i < vertnum-1; i++){ |
| 100 |
if (weight + demand[i] <= capacity){ |
| 101 |
weight += demand[i]; |
| 102 |
tour[i].next=i+1; /*keep adding customers to routes until */ |
| 103 |
tour[i].route=j; /*capacity is exceeded*/ |
| 104 |
} |
| 105 |
else{ |
| 106 |
weight = demand[i]; /*start new route*/ |
| 107 |
if (weight > capacity){ |
| 108 |
fprintf(stderr, "Error: weight greater than truck capacity\n"); |
| 109 |
exit(1); |
| 110 |
} |
| 111 |
j++; |
| 112 |
tour[i].next=i+1; |
| 113 |
tour[i].route=j; |
| 114 |
} |
| 115 |
} |
| 116 |
if (weight + demand[i] <= capacity){ |
| 117 |
tour[i].next=0; |
| 118 |
tour[i].route=j; /*add the final customer to the route and */ |
| 119 |
} /* mark the next customer as customer as the*/ |
| 120 |
else{ /*depot or start a new route as necessary */ |
| 121 |
weight = demand[i]; |
| 122 |
if (weight > capacity){ |
| 123 |
fprintf(stderr, "Error: weight greater than truck capacity\n"); |
| 124 |
exit(1); |
| 125 |
} |
| 126 |
j++; |
| 127 |
tour[i].next=0; |
| 128 |
tour[i].route=j; |
| 129 |
} |
| 130 |
|
| 131 |
cur_tour->cost = compute_tour_cost (dist, tour); |
| 132 |
cur_tour->numroutes = j; |
| 133 |
} |
| 134 |
|
| 135 |
/*===========================================================================*\ |
| 136 |
* This function computes the route information pertaining to a given |
| 137 |
* tour. It just traces out the routes, counting the customers on each |
| 138 |
* route. When it reaches a new route, |
| 139 |
* it records the last cutomer on the previous route and the first |
| 140 |
* customer on the current route, and also the cost of the previous |
| 141 |
* route. It knows whether it has reached the end of a route by |
| 142 |
* checking whether the next customer has the same route number as it |
| 143 |
* does. |
| 144 |
\*===========================================================================*/ |
| 145 |
|
| 146 |
int route_calc(distances *dist, _node *tour, int numroutes, |
| 147 |
route_data *route_info, int *demand) |
| 148 |
{ |
| 149 |
register int cur_node = 0; |
| 150 |
register int cur_route = 1; |
| 151 |
int cost = 0; |
| 152 |
|
| 153 |
for (cur_route = 1; cur_route<=numroutes; cur_route++){ |
| 154 |
cur_node = tour[cur_node].next; |
| 155 |
route_info[cur_route].numcust++; |
| 156 |
route_info[cur_route].weight += demand[cur_node]; |
| 157 |
route_info[cur_route].cost = ICOST(dist, 0, cur_node); |
| 158 |
route_info[cur_route].first = cur_node; |
| 159 |
while (tour[cur_node].route == tour[tour[cur_node].next].route){ |
| 160 |
route_info[cur_route].cost += ICOST(dist, cur_node, tour[cur_node].next); |
| 161 |
cur_node = tour[cur_node].next; |
| 162 |
route_info[cur_route].numcust++; |
| 163 |
route_info[cur_route].weight += demand[cur_node]; |
| 164 |
} |
| 165 |
route_info[cur_route].cost += ICOST(dist, 0, cur_node); |
| 166 |
route_info[cur_route].last = cur_node; |
| 167 |
cost += route_info[cur_route].cost; |
| 168 |
} |
| 169 |
return(cost); |
| 170 |
} |
| 171 |
|
| 172 |
/*===========================================================================*\ |
| 173 |
* This function computes the cost of the tour held in |
| 174 |
* p->cur_tour. At the end of each route, it automatically |
| 175 |
* adds in the cost of returning to the depot and then |
| 176 |
* travelling back to the next customer. |
| 177 |
\*===========================================================================*/ |
| 178 |
|
| 179 |
int compute_tour_cost(distances *dist, _node *tour) |
| 180 |
{ |
| 181 |
int cost=0; |
| 182 |
int v0, v1; |
| 183 |
|
| 184 |
for ( v1 = tour[0].next, cost = ICOST(dist, 0, tour[0].next);;){ |
| 185 |
v1=tour[v0=v1].next; |
| 186 |
if (tour[v0].route == tour[v1].route) |
| 187 |
cost += ICOST(dist, v0, v1); |
| 188 |
else if (v1 == 0){ |
| 189 |
cost += ICOST(dist, 0, v0); |
| 190 |
break; |
| 191 |
} |
| 192 |
else{ |
| 193 |
cost += ICOST(dist, 0, v0); |
| 194 |
cost += ICOST(dist, 0, v1); |
| 195 |
} |
| 196 |
} |
| 197 |
|
| 198 |
return(cost); |
| 199 |
} |
| 200 |
|
| 201 |
double ECOST(double *cost, int v0, int v1, int vertnum) |
| 202 |
{ |
| 203 |
return((v0 < vertnum && v1 < vertnum) ? (cost[INDEX(v0, v1)]): |
| 204 |
((v0 < vertnum && v0 > 0) ? (cost[INDEX(0, v0)]) : |
| 205 |
((v1 < vertnum && v1 > 0) ? (cost[INDEX(0, v1)]): DEPOT_PENALTY))); |
| 206 |
} |
| 207 |
|
| 208 |
int ICOST(distances *dist, int v0, int v1) |
| 209 |
{ |
| 210 |
return(dist->wtype==_EXPLICIT ? dist->cost[INDEX(v0,v1)] : |
| 211 |
compute_icost(dist,v0,v1)); |
| 212 |
} |
| 213 |
|
| 214 |
int MCOST(distances *dist, int v0, int v1, int *lamda) |
| 215 |
{ |
| 216 |
return(dist->wtype==_EXPLICIT ? |
| 217 |
dist->cost[INDEX(v0,v1)]+lamda[v0]+lamda[v1] : |
| 218 |
(compute_icost(dist,v0,v1)+lamda[v0]+lamda[v1])); |
| 219 |
} |
| 220 |
|
| 221 |
int TCOST(distances *dist, int v0, int v1, int *lamda, int mu) |
| 222 |
{ |
| 223 |
return(v0 ? MCOST(dist, v0, v1, lamda) : MCOST(dist, v0, v1, lamda) - mu); |
| 224 |
} |
| 225 |
|