# source:trunk/Applications/VRP/src/Heuristics/farthest_ins.c@397

Last change on this file since 397 was 397, checked in by tkr, 9 years ago

Major upgarde to heuristics by Ali Pilatin. Created a single parallel process that performs all heuristics

• Property svn:eol-style set to native
• Property svn:keywords set to Author Date Id Revision
File size: 5.9 KB
RevLine
[397]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 (tkralphs@lehigh.edu)        */
8/* This file was modified by Ali Pilatin January, 2005 (alp8@lehigh.edu)     */
9/*                                                                           */
11/*                                                                           */
13/* accompanying file for terms.                                              */
14/*                                                                           */
15/*===========================================================================*/
[2]16
[397]17#include "farthest_ins.h"
18#include <stdio.h>
19void farthest_ins(int parent, heur_prob *p)
[2]20{
[397]21  printf("\nIn farthest_ins....\n\n");
22  int mytid, info, r_bufid;
[2]23  int farnode, *starter;
24  int *intour;
25  int last, cost, numroutes;
26  neighbor *nbtree;
27  _node *tour;
28  route_data *route_info;
29  int cur_route, start;
30  best_tours *tours;
[397]31  double t=0;
[2]32
[397]33  mytid = pvm_mytid();
34
[2]35  (void) used_time(&t);
36
37
38  tours = p->cur_tour = (best_tours *) calloc (1, sizeof(best_tours));
[397]39
[2]40  /*-----------------------------------------------------------------------*\
41  |                    Receive the VRP data                                 |
42  \*-----------------------------------------------------------------------*/
43
[397]44  PVM_FUNC(r_bufid, pvm_recv(-1, ROUTE_FINS_VRP_DATA));
[2]45  PVM_FUNC(info, pvm_upkbyte((char *)tours, sizeof(best_tours), 1));
46  tour = p->cur_tour->tour = (_node *) calloc (p->vertnum, sizeof(_node));
47  PVM_FUNC(info, pvm_upkbyte((char *)tour, (p->vertnum)*sizeof(_node), 1));
48  numroutes = p->cur_tour->numroutes;
49  starter = (int *) calloc (numroutes, sizeof(int));
50  route_info = p->cur_tour->route_info
51             = (route_data *) calloc (numroutes+1, sizeof(route_data));
52
[397]53  PVM_FUNC(r_bufid, pvm_recv(-1, ROUTE_FINS_START_RULE));
[2]54  PVM_FUNC(info, pvm_upkint(&start, 1, 1));/*receive the start
55                                                           rule*/
56
57  if (start != FAR_INS) srand(start); /*if the start rule is random, then*\
58                                      \*initialize the random number gen.*/
59  starters(p, starter, route_info, start);/*generate the route starters for*\
60                                          \*all the clusters.              */
61  /*-----------------------------------------------------------------------*\
62  |                    Allocate arrays                                      |
63  \*-----------------------------------------------------------------------*/
64
65  nbtree   = (neighbor *) malloc (p->vertnum * sizeof(neighbor));
66  intour   = (int *)      calloc (p->vertnum, sizeof(int));
67
68  /*-----------------------------------------------------------------------*\
69  |               Find the farthest insertion tour from 'starter'           |
70  \*-----------------------------------------------------------------------*/
71
72  for(cur_route = 1; cur_route<=numroutes; cur_route++){
73    /*---------------------------------------------------------------------*\
74    | The first part of this loop adds the starter and the farthest node    |
75    | away from it into the route to initialize it. Then a function is      |
76    | called which inserts the rest of the nodes into the route in farthest |
77    | insert order.                                                         |
78    \*---------------------------------------------------------------------*/
79    if (route_info[cur_route].numcust <= 1) continue;
80    cost = 0;
81    last = 0;
82    intour[0] = 0;
83    intour[starter[cur_route -1]] = IN_TOUR;
84    fi_insert_edges(p, starter[cur_route-1], nbtree, intour, &last, tour, cur_route);
85    farnode = farthest(nbtree, intour, &last);
86    intour[farnode] = IN_TOUR;
87    fi_insert_edges(p, farnode, nbtree, intour, &last, tour, cur_route);
88    tour[starter[cur_route-1]].next = farnode;
89    tour[farnode].next = starter[cur_route-1];
90    if (starter[cur_route - 1] == 0)
91      route_info[cur_route].first = route_info[cur_route].last = farnode;
92    if (farnode == 0)
93      route_info[cur_route].first = route_info[cur_route].last
94                                  = starter[cur_route-1];
95
96    cost = 2 * ICOST(&p->dist, starter[cur_route-1], farnode);
97    cost = farthest_ins_from_to(p, tour, cost, 2, route_info[cur_route].numcust+1,
98                                starter[cur_route-1], nbtree, intour, &last,
99                                route_info, cur_route);
100
101    route_info[cur_route].cost = cost;
102  }
103
104  tour[0].next = route_info[1].first;
105
106  /*-------------------------------------------------------------------------*\
107  | This loop points the last node of each route to the first node of the next|
108  | route. At the end of this procedure, the last node of each route is       |
109  | pointing at the depot, which is not what we want.                         |
110  \*-------------------------------------------------------------------------*/
111  for (cur_route = 1; cur_route < numroutes; cur_route++)
112    tour[route_info[cur_route].last].next = route_info[cur_route+1].first;
113
114  cost = compute_tour_cost(&p->dist, tour);
115
116  /*-----------------------------------------------------------------------*\
117  |             Transmit the tour back to the parent                        |
118  \*-----------------------------------------------------------------------*/
119
120  send_tour(tour, cost, numroutes, tours->algorithm, used_time(&t), parent,
121            p->vertnum, 1, route_info);
122
123  if ( nbtree ) free ((char *) nbtree);
124  if ( intour ) free ((char *) intour);
125  if ( starter ) free ((char *) starter);
126
127  free_heur_prob(p);
128
129}
130
Note: See TracBrowser for help on using the repository browser.