Changeset 4317 for branches/VRP/HeuristicLab.Problems.VehicleRouting

Timestamp:

08/25/10 16:29:06 (14 years ago)

Author:

svonolfe

Message:

Improved the parsers (#1039)

Location:

branches/VRP/HeuristicLab.Problems.VehicleRouting/3.3

Files:

• ORLIBParser.cs (modified) (2 diffs)
• TSPLIBParser.cs (modified) (16 diffs)
• VehicleRoutingProblem.cs (modified) (2 diffs)

branches/VRP/HeuristicLab.Problems.VehicleRouting/3.3/ORLIBParser.cs

@@ -25 +25 @@
 using System.Text;
 using System.IO;
+using System.Globalization;
 
 namespace HeuristicLab.Problems.VehicleRouting {
   class ORLIBParser {
     private StreamReader source;
+    CultureInfo culture = new CultureInfo("en-US");
     
     private string name;
@@ -101 +103 @@
         line = source.ReadLine();
         tokens = line.Split(new string[] { " " }, StringSplitOptions.RemoveEmptyEntries);
-        vertices[0, 0] = double.Parse(tokens[0]);
-        vertices[0, 1] = double.Parse(tokens[1]);
+        vertices[0, 0] = double.Parse(tokens[0], culture.NumberFormat);
+        vertices[0, 1] = double.Parse(tokens[1], culture.NumberFormat);
 
         for (int i = 0; i < customers; i++) {
           line = source.ReadLine();
           tokens = line.Split(new string[] { " " }, StringSplitOptions.RemoveEmptyEntries);
-          vertices[i + 1, 0] = double.Parse(tokens[0]);
-          vertices[i + 1, 1] = double.Parse(tokens[1]);
-          demands[i + 1] = double.Parse(tokens[2]);
+          vertices[i + 1, 0] = double.Parse(tokens[0], culture.NumberFormat);
+          vertices[i + 1, 1] = double.Parse(tokens[1], culture.NumberFormat);
+          demands[i + 1] = double.Parse(tokens[2], culture.NumberFormat);
         }
       }

branches/VRP/HeuristicLab.Problems.VehicleRouting/3.3/TSPLIBParser.cs

@@ -26 +26 @@
 namespace HeuristicLab.Problems.VehicleRouting {
   /// <summary>
-  /// Parses a *.tsp file in TSPLIB format and extracts its information about a TSP.
+  /// Parses a *.vrp file in TSPLIB format and extracts its information about a VRP.
   /// </summary>
   public class TSPLIBParser {
@@ -43 +43 @@
     private const int DIM = 4;
     private const int WEIGHTTYPE = 5;
+    private const int WEIGHTFORMAT = 11;
     private const int NODETYPE = 6;
     private const int NODESECTION = 7;
     private const int CAPACITY = 8;
+    private const int DISTANCE = 12;
+    private const int VEHICLES = 13;
     private const int DEPOTSECTION = 9;
     private const int DEMANDSECTION = 10;
 
     private StreamReader source;
+    private bool alternateFormat;
+    CultureInfo culture = new CultureInfo("en-US");
 
     private string name;
     /// <summary>
-    /// Gets the name of the parsed TSP.
+    /// Gets the name of the parsed VRP.
     /// </summary>
     public string Name {
@@ -60 +65 @@
     private string comment;
     /// <summary>
-    /// Gets the comment of the parsed TSP.
+    /// Gets the comment of the parsed VRP.
     /// </summary>
     public string Comment {
@@ -67 +72 @@
     private double[,] vertices;
     /// <summary>
-    /// Gets the vertices of the parsed TSP.
+    /// Gets the vertices of the parsed VRP.
     /// </summary>
     public double[,] Vertices {
@@ -74 +79 @@
     private TSPLIBEdgeWeightType weightType;
     /// <summary>
-    /// Gets the weight type of the parsed TSP.
+    /// Gets the weight format of the parsed VRP.
     /// </summary>
     public TSPLIBEdgeWeightType WeightType {
@@ -87 +92 @@
     }
 
+    private double distance;
+    public double Distance {
+      get {
+        return distance;
+      }
+    }
+
+    private int vehicles;
+    public int Vehicles {
+      get {
+        return vehicles;
+      }
+    }
+
     private int depot;
     public int Depot {
@@ -104 +123 @@
     /// Initializes a new instance of <see cref="TSPLIBParser"/> with the given <paramref name="path"/>.
     /// </summary>
-    /// <exception cref="ArgumentException">Thrown if the input file is not a TSPLIB TSP file (*.tsp)
+    /// <exception cref="ArgumentException">Thrown if the input file is not a TSPLIB TSP file (*.vrp)
     /// </exception>
-    /// <param name="path">The path where the TSP is stored.</param>
+    /// <param name="path">The path where the VRP is stored.</param>
     public TSPLIBParser(String path) {
       if (!path.EndsWith(".vrp"))
-        throw new ArgumentException("Input file has to be a TSPLIB CVRP file (*.tsp).");
-
-      source = new StreamReader(path);
+        throw new ArgumentException("Input file has to be a TSPLIB CVRP file (*.vrp, *.txt).");
+
+      source = null;
       name = path;
       comment = string.Empty;
@@ -117 +136 @@
       weightType = TSPLIBEdgeWeightType.UNDEFINED;
       capacity = -1;
+      distance = -1;
+      vehicles = -1;
       depot = -1;
       demands = null;
-    }
-
-    /// <summary>
-    /// Reads the TSPLIB TSP file and parses the elements.
+      alternateFormat = false;
+    }
+
+    /// <summary>
+    /// Reads the TSPLIB VRP file and parses the elements.
     /// </summary>
     /// <exception cref="InvalidDataException">Thrown if the file has an invalid format or contains invalid data.</exception>
     public void Parse() {
-      int section = -1;
-      string str = null;
-      bool typeIsChecked = false;
-      bool weightTypeIsChecked = false;
-
-      do {
-        str = source.ReadLine();
-        section = GetSection(str);
-
-        if (section != -1) {
-          switch (section) {
-            case NAME:
-              ReadName(str);
-              break;
-            case TYPE:
-              CheckType(str);
-              typeIsChecked = true;
-              break;
-            case COMMENT:
-              ReadComment(str);
-              break;
-            case DIM:
-              InitArrays(str);
-              break;
-            case WEIGHTTYPE:
-              ReadWeightType(str);
-              weightTypeIsChecked = true;
-              break;
-            case NODETYPE:
-              CheckNodeType(str);
-              break;
-            case NODESECTION:
-              ReadVertices();
-              break;
-            case CAPACITY:
-              ReadCapacity(str);
-              break;
-            case DEPOTSECTION:
-              ReadDepot();
-              break;
-            case DEMANDSECTION:
-              ReadDemands();
-              break;
+      using (source = new StreamReader(name)) {
+        int section = -1;
+        string str = null;
+        bool typeIsChecked = false;
+        bool weightTypeIsChecked = false;
+        bool weightFormatIsChecked = false;
+
+        do {
+          str = source.ReadLine();
+          section = GetSection(str);
+
+          if (section != -1) {
+            switch (section) {
+              case NAME:
+                ReadName(str);
+                break;
+              case TYPE:
+                CheckType(str);
+                typeIsChecked = true;
+                break;
+              case COMMENT:
+                ReadComment(str);
+                break;
+              case DIM:
+                InitArrays(str);
+                break;
+              case WEIGHTTYPE:
+                ReadWeightType(str);
+                weightTypeIsChecked = true;
+                break;
+              case WEIGHTFORMAT:
+                ReadWeightFormat(str);
+                weightFormatIsChecked = true;
+                break;
+              case NODETYPE:
+                CheckNodeType(str);
+                break;
+              case NODESECTION:
+                ReadVertices();
+                break;
+              case CAPACITY:
+                ReadCapacity(str);
+                break;
+              case DISTANCE:
+                ReadDistance(str);
+                break;
+              case VEHICLES:
+                ReadVehicles(str);
+                break;
+              case DEPOTSECTION:
+                ReadDepot();
+                break;
+              case DEMANDSECTION:
+                ReadDemands();
+                break;
+            }
           }
-        }
-      } while (!((section == EOF) || (str == null)));
-
-      if (!(typeIsChecked && weightTypeIsChecked))
-        throw new InvalidDataException("Input file does not contain type or edge weight type information.");
+        } while (!((section == EOF) || (str == null)));
+
+        if (!typeIsChecked || !weightTypeIsChecked || 
+          (alternateFormat && !weightFormatIsChecked) || 
+          weightType == TSPLIBEdgeWeightType.UNDEFINED)
+          throw new InvalidDataException("Input file does not contain format or edge weight format information.");
+      }
+      source = null;
     }
 
@@ -198 +236 @@
       if (token.Equals("edge_weight_type", StringComparison.OrdinalIgnoreCase))
         return WEIGHTTYPE;
+      if (token.Equals("edge_weight_format", StringComparison.OrdinalIgnoreCase))
+        return WEIGHTFORMAT;
       if (token.Equals("node_coord_type", StringComparison.OrdinalIgnoreCase))
         return NODETYPE;
@@ -204 +244 @@
       if (token.Equals("capacity", StringComparison.OrdinalIgnoreCase))
         return CAPACITY;
+      if (token.Equals("distance", StringComparison.OrdinalIgnoreCase))
+        return DISTANCE;
+      if (token.Equals("vehicles", StringComparison.OrdinalIgnoreCase))
+        return VEHICLES;
       if (token.Equals("depot_section", StringComparison.OrdinalIgnoreCase))
         return DEPOTSECTION;
@@ -222 +266 @@
       string type = tokens[tokens.Length - 1].Trim();
       if (!type.Equals("cvrp", StringComparison.OrdinalIgnoreCase))
-        throw new InvalidDataException("Input file type is not \"CVRP\"");
+        throw new InvalidDataException("Input file format is not \"CVRP\"");
     }
 
@@ -247 +291 @@
       else if (type.Equals("geo", StringComparison.OrdinalIgnoreCase))
         weightType = TSPLIBEdgeWeightType.GEO;
+      else if (type.Equals("function", StringComparison.OrdinalIgnoreCase)) {
+        weightType = TSPLIBEdgeWeightType.UNDEFINED;
+        alternateFormat = true;
+      } else
+        throw new InvalidDataException("Input file contains an unsupported edge weight format (only \"EUC_2D\" and \"GEO\" are supported).");
+    }
+
+    private void ReadWeightFormat(string str) {
+      string[] tokens = str.Split(new string[] { ":" }, StringSplitOptions.None);
+      string format = tokens[tokens.Length - 1].Trim();
+
+      if (alternateFormat && format.Equals("euc_2d", StringComparison.OrdinalIgnoreCase))
+        weightType = TSPLIBEdgeWeightType.EUC_2D;
+      else if (format.Equals("geo", StringComparison.OrdinalIgnoreCase))
+        weightType = TSPLIBEdgeWeightType.GEO;
       else
-        throw new InvalidDataException("Input file contains an unsupported edge weight type (only \"EUC_2D\" and \"GEO\" are supported).");
+        throw new InvalidDataException("Input file contains an unsupported edge weight format.");
     }
 
@@ -256 +315 @@
 
       if (!type.Equals("twod_coords", StringComparison.OrdinalIgnoreCase))
-        throw new InvalidDataException("Input file contains an unsupported node coordinates type (only \"TWOD_COORDS\" is supported).");
+        throw new InvalidDataException("Input file contains an unsupported node coordinates format (only \"TWOD_COORDS\" is supported).");
     }
 
@@ -264 +323 @@
 
       for (int i = 0; i < (vertices.Length / 2); i++) {
-        string str = source.ReadLine();
-        string[] tokens = str.Split(new string[] { " " }, StringSplitOptions.RemoveEmptyEntries);
-
-        if (tokens.Length != 3)
-          throw new InvalidDataException("Input file contains invalid node coordinates.");
-
-        CultureInfo culture = new CultureInfo("en-US");
-        vertices[i, 0] = double.Parse(tokens[1], culture.NumberFormat);
-        vertices[i, 1] = double.Parse(tokens[2], culture.NumberFormat);
+        if (!(alternateFormat && i == 0)) {
+          string str = source.ReadLine();
+          string[] tokens = str.Split(new string[] { " " }, StringSplitOptions.RemoveEmptyEntries);
+
+          if (tokens.Length != 3)
+            throw new InvalidDataException("Input file contains invalid node coordinates.");
+
+          vertices[i, 0] = double.Parse(tokens[1], culture.NumberFormat);
+          vertices[i, 1] = double.Parse(tokens[2], culture.NumberFormat);
+        }
       }
     }
@@ -278 +338 @@
     private void ReadCapacity(string str) {
       string[] tokens = str.Split(new string[] { ":" }, StringSplitOptions.None);
-      capacity = double.Parse(tokens[tokens.Length - 1].Trim());
+      capacity = double.Parse(tokens[tokens.Length - 1].Trim(), culture.NumberFormat);
+    }
+
+    private void ReadDistance(string str) {
+      string[] tokens = str.Split(new string[] { ":" }, StringSplitOptions.None);
+      distance = double.Parse(tokens[tokens.Length - 1].Trim(), culture.NumberFormat);
+    }
+
+    private void ReadVehicles(string str) {
+      string[] tokens = str.Split(new string[] { ":" }, StringSplitOptions.None);
+      vehicles = int.Parse(tokens[tokens.Length - 1].Trim());
     }
 
     private void ReadDepot() {
-      int read;
-
-      do {
-        string str = source.ReadLine();
-        read = int.Parse(str);
-        if (read != -1)
-          depot = read;
-      } while (read != -1);
+      if (alternateFormat) {
+        string[] tokens;
+        do { 
+          string str = source.ReadLine();
+          tokens = str.Split(new string[] { " " }, StringSplitOptions.RemoveEmptyEntries);
+
+          if (tokens.Length == 2) {
+            vertices[0, 0] = double.Parse(tokens[0], culture.NumberFormat);
+            vertices[0, 1] = double.Parse(tokens[1], culture.NumberFormat);
+            depot = 1;
+          }
+        } while(tokens.Length == 2);
+      } else {
+        int read;
+        do {
+          string str = source.ReadLine();
+          read = int.Parse(str);
+          if (read != -1)
+            depot = read;
+        } while (read != -1);
+      }
     }
 
@@ -297 +380 @@
 
       for (int i = 0; i < demands.Length; i++) {
-        string str = source.ReadLine();
-        string[] tokens = str.Split(new string[] { " " }, StringSplitOptions.RemoveEmptyEntries);
-
-        if (tokens.Length != 2)
-          throw new InvalidDataException("Input file contains invalid demands.");
-
-        int index = int.Parse(tokens[0]);
-        double value = double.Parse(tokens[1]);
-
-        demands[index - 1] = value;
+        if (!(alternateFormat && i == 0)) {
+          string str = source.ReadLine();
+          string[] tokens = str.Split(new string[] { " " }, StringSplitOptions.RemoveEmptyEntries);
+
+          if (tokens.Length != 2)
+            throw new InvalidDataException("Input file contains invalid demands.");
+
+          int index = int.Parse(tokens[0]);
+          double value = double.Parse(tokens[1]);
+
+          if (alternateFormat)
+            demands[index] = value;
+          else
+            demands[index - 1] = value;
+        } else {
+          demands[0] = 0;
+        }
       }
     }

branches/VRP/HeuristicLab.Problems.VehicleRouting/3.3/VehicleRoutingProblem.cs

@@ -461 +461 @@
 
       Coordinates = new DoubleMatrix(parser.Vertices);
-      Vehicles.Value = problemSize - 1;
+      if (parser.Vehicles != -1)
+        Vehicles.Value = parser.Vehicles;
+      else 
+        Vehicles.Value = problemSize - 1;
       Capacity.Value = parser.Capacity;
       Demand = new DoubleArray(parser.Demands);
@@ -472 +475 @@
         DueTime[i] = int.MaxValue;
         ServiceTime[i] = 0;
+      }
+
+      if (parser.Distance != -1) {
+        DueTime[0] = parser.Distance;
       }