00001 /*===========================================================================*/ 00002 /* */ 00003 /* This file is part of a demonstration application for use with the */ 00004 /* SYMPHONY Branch, Cut, and Price Library. This application is a solver for */ 00005 /* the Vehicle Routing Problem and the Traveling Salesman Problem. */ 00006 /* */ 00007 /* (c) Copyright 2000-2008 Ted Ralphs. All Rights Reserved. */ 00008 /* */ 00009 /* This application was developed by Ted Ralphs (tkralphs@lehigh.edu) */ 00010 /* */ 00011 /* This software is licensed under the Common Public License. Please see */ 00012 /* accompanying file for terms. */ 00013 /* */ 00014 /*===========================================================================*/ 00015 00016 #ifndef _VRP_COMMON_TYPES_H 00017 #define _VRP_COMMON_TYPES_H 00018 00019 /*---------------------------------------------------------------------*\ 00020 | This _node data structure holds information about a customer node in | 00021 | a tour. The next field contains the index of the node that is next | 00022 | on the current route or if the current node is the last on eon its | 00023 | route, it contains the index of the first node on the next route. | 00024 | The route number field contains the number of the route that the | 00025 | node is on. This information is maintained to make reconstruction of | 00026 | the route and calculation of the route cost possible | 00027 \*---------------------------------------------------------------------*/ 00028 00029 typedef struct _NODE{ 00030 int next; 00031 int route; 00032 }_node; 00033 00034 /*--------------------------------------------------------------------*\ 00035 | This data structure contains information about a tour's route | 00036 | structure. Specifically, first and last are the first and last nodes | 00037 | on a particular route, numcust is the number of customers on the | 00038 | route and cost is the cost of that route. The routes are always | 00039 | numbered starting at 1 for convenience in certain calculations so | 00040 | route_info[0] always contains 0 in all fields. | 00041 \*--------------------------------------------------------------------*/ 00042 00043 typedef struct ROUTE_DATA{ 00044 int first; 00045 int last; 00046 int numcust; 00047 int weight; 00048 int cost; 00049 }route_data; 00050 00051 /*--------------------------------------------------------------------*\ 00052 | The best_tours data structure is for storing tours for later use. The| 00053 | cost field contains the total cost of the tour. The numroutes field | 00054 | contains the number of trucks used in the tour and the tour field is | 00055 | a pointer to an array which specifies the order of each of the | 00056 | routes as explained above. The field route_info contains | 00057 | information about the tour's routes as explained above | 00058 \*--------------------------------------------------------------------*/ 00059 typedef struct BEST_TOURS{ 00060 int algorithm; 00061 double solve_time; 00062 int cost; 00063 int numroutes; 00064 route_data *route_info; 00065 _node *tour; 00066 }best_tours; 00067 00068 /*--------------------------------------------------------------------*\ 00069 | Stores the method by which distances should be calculated | 00070 \*--------------------------------------------------------------------*/ 00071 00072 typedef struct DISTANCES{ 00073 int wtype; 00074 int *cost; 00075 double *coordx; 00076 double *coordy; 00077 double *coordz; 00078 }distances; 00079 00080 /*--------------------------------------------------------------------*\ 00081 | This structure contains information about a particular edge | 00082 \*--------------------------------------------------------------------*/ 00083 00084 typedef struct EDGE_DATA{ 00085 int v0; 00086 int v1; 00087 int cost; 00088 }edge_data; 00089 00090 typedef struct DBL_EDGE_DATA{ 00091 int v0; 00092 int v1; 00093 double cost; 00094 }dbl_edge_data; 00095 00096 #endif