LKHWin-3.0.6_optimization_

#include "LKH.h" #include "Heap.h" /* * The ReadProblem function reads the problem data in TSPLIB format from the * file specified in the parameter file (PROBLEM_FILE). * * The following description of the file format is extracted from the TSPLIB * documentation. * * The file consists of a specification part and a data part. The specification * part contains information on the file format and on its contents. The data * part contains explicit data. * * (1) The specification part * * All entries in this section are of the form <keyword> : <value>, where * <keyword> denotes an alphanumerical keyword and <value> denotes * alphanumerical or numerical data. The terms <string>, <integer> and <real> * denote character string, integer or real data, respectively. The order of * specification of the keywords in the data file is arbitrary (in principle), * but must be consistent, i.e., whenever a keyword is specified, all * necessary information for the correct interpretation of the keyword has to * be known. * * Below is given a list of all available keywords. * * NAME : <string>e * Identifies the data file. * * TYPE : <string> * Specifies the type of data. Possible types are * TSP Data for a symmetric traveling salesman problem * ATSP Data for an asymmetric traveling salesman problem * SOP Data for a sequence ordering problem * HCP Hamiltonian cycle problem data * HPP Hamiltonian path problem data (not available in TSPLIB) * TSPTW Data for a TSP instance with time windows * CCVRP Data for a cumulative capacitated vehicle routing problem * CVRP Data for a symmetric capacitated vehicle routing problem * ACVRP Data for an asymmetric capacitated vehicle routing problem * CVRPTW Data for a capacitated vehicle routing problem with * time windows * VRPMPD Data for a mixed pickup and delivery problem with backhauls * 1-PDTSP Data for a one-commodity pickup-and-delivery traveling * salesman problem * MLP Data for a minimum latency problem * m-PDTSP Data for a mulity-commodity pickup-and-delivery traveling * salesman problem * m1-PDTSP Data for a mulity-commodity one-to-one pickup-and-delivery * traveling salesman problem * OVRP Data for an open vehicle routing problem * PDTSP Data for a pickup and delivery traveling salesman problem * PDTSPF Data for a pickup and delivery traveling salesman problem * with FIFO loading * PDTSPL Data for a pickup and delivery traveling salesman problem * with LIFO loading * PDPTW Data for a pickup and delivery problem with time windows * RCTVRP Data for a risk-constrained cash-in-transit vehicle * routing problem * RCTVRPTW Data for a risk-constrained cash-in-transit vehicle * routing problem with time windows * TRP Data for a traveling repairman problem * TSPDL Dara for a traveling salesman problem with draft limits * TSPPD Data for a pickup and delivery travling salesman problem * TSTSP Data for a Steiner traveling salesman problem * VRPB Data for a vehicle routing problem with backhauls * VRPBTW Data for a vehicle routing problem with backhauls and * time windows * CTSP Data for a colored traveling salesman problem * * COMMENT : <string> * Additional comments (usually the name of the contributor or the creator of * the problem instance is given here). * * DIMENSION : < integer> * The number of nodes. * * CAPACITY : <integer> * Specifies the truck capacity in a CVRP. * * DISTANCE : <real> * The maximum length allowed for each route in a CVRP. * * EDGE_WEIGHT_TYPE : <string> * Specifies how the edge weights (or distances) are given. The values are: * ATT Special distance function for problem att48 and att532 * CEIL_2D Weights are Euclidean distances in 2-D rounded up * CEIL_3D Weights are Euclidean distances in 3-D rounded up * EUC_2D Weights are Euclidean distances in 2-D * EUC_3D Weights are Euclidean distances in 3-D * EXACT_2D Weights are EUC_2D distances (SCALE = 1000 as default) * EXACT_3D Weights are EUC_3D distances (SCALE = 1000 as default) * EXPLICIT Weights are listed explicitly in the corresponding section * FLOOR_2D Weights are Euclidean distances in 2-D rounded down * FLOOR_3D Weights are Euclidean distances in 3-D rounded down * GEO Weights are geographical distances in kilometers (TSPLIB) * Coordinates are given in the form DDD.MM where DDD are the * degrees and MM the minutes * GEOM Weights are geographical distances in meters (used for the * world TSP). Coordinates are given in decimal form * GEO_MEEUS Weights are geographical distances in kilometers, computed * according to Meeus' formula. Coordinates are given in the * form DDD.MM where DDD are the degrees and MM the minutes * GEOM_MEEUS Weights are geographical distances, computed according to * Meeus' formula. Coordinates are given in decimal form * MAN_2D Weights are Manhattan distances in 2-D * MAN_3D Weights are Manhattan distances in 3-D * MAX_2D Weights are maximum distances in 2-D * MAX_3D Weights are maximum distances in 3-D * TOR_2D Wirghes are toroidal distances in 2-D * TOR_3D Wirghes are toroidal distances in 3-D * XRAY1 Distance function for crystallography problems (Version 1) * XRAY2 Distance function for crystallography problems (Version 2) * SPECIAL There is a special distance function implemented in * the Distance_SPECIAL function. * * EDGE-WEIGHT_FORMAT : <string> * Describes the format of the edge weights if they are given explicitly. * The values are * FUNCTION Weights are given by a function (see above) * FULL_MATRIX Weights are given by a full matrix * UPPER_ROW Upper triangular matrix * (row-wise without diagonal entries) * LOWER_ROW Lower triangular matrix * (row-wise without diagonal entries) * UPPER_DIAG_ROW Upper triangular matrix * (row-wise including diagonal entries) * LOWER_DIAG_ROW Lower triangular matrix * (row-wise including diagonal entries) * UPPER_COL Upper triangular matrix * (column-wise without diagonal entries) * LOWER_COL Lower triangular matrix * (column-wise without diagonal entries) * UPPER_DIAG_COL Upper triangular matrix * (column-wise including diagonal entries) * LOWER_DIAG_COL Lower triangular matrix * (column-wise including diagonal entries) * * EDGE_DATA_FORMAT : <string> * Describes the format in which the edges of a graph are given, if the * graph is not complete. The values are * EDGE_LIST The graph is given by an edge list * ADJ_LIST The graph is given by an adjacency list * * NODE_COORD_TYPE : <string> * Specifies whether the coordinates are associated with each node * (which, for example may be used for either graphical display or * distance computations. * The values are * TWOD_COORDS Nodes are specified by coordinates in 2-D * THREED_COORDS Nodes are specified by coordinates in 3-D * NO_COORDS The nodes do not have associated coordinates * The default value is NO_COORDS. In the current implementation, however, * the value has no significance. * * DISPLAY_DATA_TYPE : <string> * Specifies how a graphical display of the nodes can be obt