Debian Codegraph @

SYMPHONY/Applications/VRP/src/Heuristics/savings.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 <stdlib.h>
18 #include <stdio.h>
19 #include "heur_routines.h"
20 #include "savings.h"
21 #ifndef _SAV
22 #define _SAV
23 #define SAV(d, a, b, c) (p->par.savings_par.lamda) * ICOST(d, 0, c) - \
24 (ICOST(d,a,c) + ICOST(d,b,c) - \
25 (p->par.savings_par.mu) * ICOST(d,a,b))
26 #endif
27
28 int new_start PROTO((int *intour, heur_prob *p,
29 int start, int num_cust));
30 void insert_cust PROTO((int cust_num, _node *tour, int node1,
31 int node2, int cur_route,
32 int prev_route_end));
33 void find_max(int *ins_cust, int *savings, int *node1,
34 int *node2, _node *tour, int *intour,
35 int prev_route_end, heur_prob *p);
36
37 void savings(int parent, heur_prob *p)
38 {
39 printf("\nIn savings....\n\n");
40 _node *tour;
41 int mytid, info, r_bufid;
42 int i, capacity;
43 int vertnum;
44 int cur_route=1;
45 int weight, *demand;
46 int savings, start, *intour;
47 int node1, node2, ins_cust, starter;
48 int cur_route_end = 0, prev_route_end = 0;
49 double t=0;
50
51 mytid = pvm_mytid();
52 (void) used_time(&t);
53
54 /*-----------------------------------------------------------------------*\
55 | Receive the parameters |
56 \*-----------------------------------------------------------------------*/
57 PVM_FUNC(r_bufid, pvm_recv(-1, SAVINGS_DATA));
58 PVM_FUNC(info, pvm_upkfloat(&p->par.savings_par.mu, 1, 1));
59 PVM_FUNC(info, pvm_upkfloat(&p->par.savings_par.lamda, 1, 1));
60 PVM_FUNC(info, pvm_upkint(&start, 1, 1));
61 capacity = p->capacity;
62 demand = p->demand;
63 vertnum = p->vertnum;
64
65 if (start != FAR_INS) srand(start);
66
67 p->cur_tour = (best_tours *) calloc (1, sizeof(best_tours));
68 tour = p->cur_tour->tour = (_node *) calloc (vertnum, sizeof(_node));
69 intour = (int *) calloc (vertnum, sizeof(int));
70
71 /*------------------------------------------------------------------*\
72 | Initiate the first route by placing the initial starter (either |
73 | the farthest node from the depot of a random node) and the depot |
74 | on the first route |
75 \*------------------------------------------------------------------*/
76 starter = new_start(intour, p, start, vertnum - 1);
77 tour[0].next = starter;
78 tour[starter].route = cur_route;
79 intour[starter] = IN_TOUR;
80 intour[0] = IN_TOUR;
81 cur_route_end = starter;
82 weight = demand[starter];
83
84 /*------------------------------------------------------------------*\
85 | The following loop first finds the customer with the maximum |
86 | savings among all customers not yet put on routes and returns the |
87 | the position in which to insert the customer in order to achieve |
88 | that savings. It then checks the feasibility of inserting that |
89 | that customer on the current route and if it is infeasible, starts|
90 | a new route. |
91 \*------------------------------------------------------------------*/
92 for (i=0; i<vertnum - 2; i++){
93 find_max(&ins_cust, &savings, &node1, &node2,
94 tour, intour, prev_route_end, p);
95 if (weight + demand[ins_cust] <= capacity){
96 intour[ins_cust] = IN_TOUR;
97 weight += demand[ins_cust];
98 insert_cust(ins_cust, tour, node1, node2,
99 cur_route, prev_route_end);
100 if (node2 == 0)
101 cur_route_end = ins_cust;
102 }
103 else{
104 cur_route++;
105 tour[cur_route_end].next = new_start(intour, p, start, vertnum - 2 - i);
106 prev_route_end = cur_route_end;
107 cur_route_end = tour[prev_route_end].next;
108 tour[cur_route_end].route = cur_route;
109 intour[cur_route_end] = IN_TOUR;
110 weight = demand[cur_route_end];
111 }
112 }
113
114 p->cur_tour->cost = compute_tour_cost(&p->dist, tour);
115 p->cur_tour->numroutes = cur_route;
116
117 /*-----------------------------------------------------------------------*\
118 | Transmit the tour back to the parent |
119 \*-----------------------------------------------------------------------*/
120
121 send_tour(tour, p->cur_tour->cost, p->cur_tour->numroutes, SAVINGS,
122 used_time(&t),
123 parent, vertnum, 0, NULL);
124
125 if (intour) free ((char *) intour);
126
127 free_heur_prob(p);
128
129 }