00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016 #ifndef _VRP_CG_H
00017 #define _VRP_CG_H
00018
00019
00020 #include <stdio.h>
00021
00022
00023 #include "sym_types.h"
00024 #include "sym_proto.h"
00025
00026
00027 #include "network.h"
00028 #include "vrp_cg_params.h"
00029
00030 typedef struct VRP_CG_PROBLEM{
00031 vrp_cg_params par;
00032 int dg_id;
00033 int vertnum;
00034
00035 int *demand;
00036 int capacity;
00037 int numroutes;
00038
00039 int *edges;
00040
00041 network *n;
00042 int orig_edgenum;
00043 int *cost;
00044 int *ref;
00045 char *in_set;
00046 int *new_demand;
00047 double *cut_val;
00048 char *cut_list;
00049
00050
00051 #ifdef CHECK_CUT_VALIDITY
00052 int feas_sol_size;
00053 int *feas_sol;
00054 #endif
00055 }vrp_cg_problem;
00056
00057
00058
00059
00060
00061 void check_connectivity PROTO((network *n, double etol, int capacity,
00062 int numroutes, cut_data ***cuts,
00063 int *num_cuts, int *alloc_cuts));
00064
00065
00066
00067
00068
00069 void reduce_graph PROTO((network *n, double etol, int *demand));
00070 int greedy_shrinking1 PROTO((network *n, double truck_cap, double etol,
00071 int max_num_cuts, cut_data *new_cut,
00072 int *compnodes, int *compmembers, int compnum,
00073 char *in_set, double *cut_val,int *ref,
00074 char *cut_list, int *demand, cut_data ***cuts,
00075 int *num_cuts, int *alloc_cuts));
00076 int greedy_shrinking6 PROTO((network *n, double truck_cap,
00077 double etol, cut_data *new_cut,
00078 int *compnodes,
00079 int *compmembers, int compnum, char *in_set,
00080 double *cut_val,int *ref, char *cut_list,
00081 int max_num_cuts, int *demand, int trial_num,
00082 double prob, cut_data ***cuts, int *num_cuts,
00083 int *alloc_cuts));
00084 int greedy_shrinking1_one PROTO((network *n, double truck_cap,
00085 double etol, int max_num_cuts,
00086 cut_data *new_cut, char *in_set,
00087 double *cut_val, char *cut_list,
00088 int num_routes, int *demand, cut_data ***cuts,
00089 int *num_cuts, int *alloc_cuts));
00090 int greedy_shrinking6_one PROTO((network *n, double truck_cap,
00091 double etol, cut_data *new_cut,
00092 char *in_set, double *cut_val, int num_routes,
00093 char *cut_list, int max_num_cuts,
00094 int *demand,int trial_num, double prob,
00095 cut_data ***cuts, int *num_cuts,
00096 int *alloc_cuts));
00097 int greedy_shrinking2_one PROTO((network *n, double truck_cap,
00098 double etol, cut_data *new_cut,
00099 char *in_set, double *cut_val, int num_routes,
00100 int *demand, cut_data ***cuts, int *num_cuts,
00101 int *alloc_cuts));
00102
00103
00104
00105
00106
00107 void depth_first_search PROTO((vertex *v, int *count1, int *count2));
00108 int biconnected PROTO((network *n, int *compnodes, int
00109 *compdemands, double *compcuts));
00110 void compute_comp_nums PROTO((vertex *v, int parent_comp, int *num_comps,
00111 char parent_is_art_point));
00112
00113
00114
00115
00116
00117 int tsp_cuts PROTO((network *n, int verbosity, char tsp_prob, int which_cuts,
00118 cut_data ***cuts, int *num_cuts, int *alloc_cuts));
00119
00120 #endif