[4362] | 1 | #region License Information
|
---|
| 2 | /* HeuristicLab
|
---|
| 3 | * Copyright (C) 2002-2010 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
|
---|
| 4 | *
|
---|
| 5 | * This file is part of HeuristicLab.
|
---|
| 6 | *
|
---|
| 7 | * HeuristicLab is free software: you can redistribute it and/or modify
|
---|
| 8 | * it under the terms of the GNU General Public License as published by
|
---|
| 9 | * the Free Software Foundation, either version 3 of the License, or
|
---|
| 10 | * (at your option) any later version.
|
---|
| 11 | *
|
---|
| 12 | * HeuristicLab is distributed in the hope that it will be useful,
|
---|
| 13 | * but WITHOUT ANY WARRANTY; without even the implied warranty of
|
---|
| 14 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
---|
| 15 | * GNU General Public License for more details.
|
---|
| 16 | *
|
---|
| 17 | * You should have received a copy of the GNU General Public License
|
---|
| 18 | * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
|
---|
| 19 | */
|
---|
| 20 | #endregion
|
---|
| 21 |
|
---|
| 22 | using System;
|
---|
| 23 | using System.Collections.Generic;
|
---|
| 24 | using System.Linq;
|
---|
| 25 | using System.Text;
|
---|
| 26 | using HeuristicLab.Problems.VehicleRouting.Interfaces;
|
---|
| 27 | using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
|
---|
| 28 | using HeuristicLab.Core;
|
---|
| 29 | using HeuristicLab.Parameters;
|
---|
| 30 | using HeuristicLab.Data;
|
---|
| 31 | using HeuristicLab.Optimization;
|
---|
| 32 | using HeuristicLab.PluginInfrastructure;
|
---|
[4752] | 33 | using HeuristicLab.Common;
|
---|
[5867] | 34 | using HeuristicLab.Problems.VehicleRouting.Encodings.General;
|
---|
[4362] | 35 |
|
---|
| 36 | namespace HeuristicLab.Problems.VehicleRouting.ProblemInstances {
|
---|
| 37 | [Item("VRPProblemInstance", "Represents a VRP instance.")]
|
---|
| 38 | [StorableClass]
|
---|
[6711] | 39 | public abstract class VRPProblemInstance : ParameterizedNamedItem, IVRPProblemInstance, IStatefulItem {
|
---|
[5867] | 40 | IVRPEvaluator moveEvaluator;
|
---|
| 41 |
|
---|
| 42 | public IVRPEvaluator MoveEvaluator {
|
---|
| 43 | get {
|
---|
[7852] | 44 | if (evaluator == null)
|
---|
[5867] | 45 | return null;
|
---|
| 46 | else {
|
---|
| 47 | if (moveEvaluator == null) {
|
---|
[7852] | 48 | moveEvaluator = evaluator.Clone() as IVRPEvaluator;
|
---|
[5867] | 49 |
|
---|
| 50 | foreach (IParameter parameter in moveEvaluator.Parameters) {
|
---|
| 51 | if (parameter is ILookupParameter
|
---|
| 52 | && parameter != moveEvaluator.ProblemInstanceParameter
|
---|
| 53 | && parameter != moveEvaluator.VRPToursParameter) {
|
---|
| 54 | (parameter as ILookupParameter).ActualName =
|
---|
| 55 | VRPMoveEvaluator.MovePrefix +
|
---|
| 56 | (parameter as ILookupParameter).ActualName;
|
---|
| 57 | }
|
---|
| 58 | }
|
---|
| 59 | }
|
---|
| 60 |
|
---|
| 61 | return moveEvaluator;
|
---|
| 62 | }
|
---|
| 63 | }
|
---|
| 64 | }
|
---|
| 65 |
|
---|
[4374] | 66 | protected abstract IEnumerable<IOperator> GetOperators();
|
---|
| 67 | protected abstract IEnumerable<IOperator> GetAnalyzers();
|
---|
| 68 |
|
---|
| 69 | public IEnumerable<IOperator> Operators {
|
---|
| 70 | get {
|
---|
| 71 | return GetOperators().Union(GetAnalyzers());
|
---|
| 72 | }
|
---|
| 73 | }
|
---|
[4362] | 74 |
|
---|
| 75 | protected ValueParameter<DoubleMatrix> CoordinatesParameter {
|
---|
| 76 | get { return (ValueParameter<DoubleMatrix>)Parameters["Coordinates"]; }
|
---|
| 77 | }
|
---|
[4380] | 78 | protected OptionalValueParameter<DoubleMatrix> DistanceMatrixParameter {
|
---|
| 79 | get { return (OptionalValueParameter<DoubleMatrix>)Parameters["DistanceMatrix"]; }
|
---|
| 80 | }
|
---|
[4362] | 81 | protected ValueParameter<BoolValue> UseDistanceMatrixParameter {
|
---|
| 82 | get { return (ValueParameter<BoolValue>)Parameters["UseDistanceMatrix"]; }
|
---|
| 83 | }
|
---|
| 84 | protected ValueParameter<IntValue> VehiclesParameter {
|
---|
| 85 | get { return (ValueParameter<IntValue>)Parameters["Vehicles"]; }
|
---|
| 86 | }
|
---|
| 87 | protected ValueParameter<DoubleArray> DemandParameter {
|
---|
| 88 | get { return (ValueParameter<DoubleArray>)Parameters["Demand"]; }
|
---|
| 89 | }
|
---|
| 90 |
|
---|
| 91 | protected IValueParameter<DoubleValue> FleetUsageFactorParameter {
|
---|
| 92 | get { return (IValueParameter<DoubleValue>)Parameters["EvalFleetUsageFactor"]; }
|
---|
| 93 | }
|
---|
| 94 | protected IValueParameter<DoubleValue> DistanceFactorParameter {
|
---|
| 95 | get { return (IValueParameter<DoubleValue>)Parameters["EvalDistanceFactor"]; }
|
---|
| 96 | }
|
---|
| 97 |
|
---|
| 98 | public DoubleMatrix Coordinates {
|
---|
| 99 | get { return CoordinatesParameter.Value; }
|
---|
| 100 | set { CoordinatesParameter.Value = value; }
|
---|
| 101 | }
|
---|
[4380] | 102 |
|
---|
| 103 | public DoubleMatrix DistanceMatrix {
|
---|
| 104 | get { return DistanceMatrixParameter.Value; }
|
---|
| 105 | set { DistanceMatrixParameter.Value = value; }
|
---|
| 106 | }
|
---|
[4362] | 107 | public BoolValue UseDistanceMatrix {
|
---|
| 108 | get { return UseDistanceMatrixParameter.Value; }
|
---|
| 109 | set { UseDistanceMatrixParameter.Value = value; }
|
---|
| 110 | }
|
---|
| 111 | public IntValue Vehicles {
|
---|
| 112 | get { return VehiclesParameter.Value; }
|
---|
| 113 | set { VehiclesParameter.Value = value; }
|
---|
| 114 | }
|
---|
| 115 | public DoubleArray Demand {
|
---|
| 116 | get { return DemandParameter.Value; }
|
---|
| 117 | set { DemandParameter.Value = value; }
|
---|
| 118 | }
|
---|
[4365] | 119 | public virtual IntValue Cities {
|
---|
[4362] | 120 | get { return new IntValue(Demand.Length); }
|
---|
| 121 | }
|
---|
| 122 |
|
---|
| 123 | public DoubleValue FleetUsageFactor {
|
---|
| 124 | get { return FleetUsageFactorParameter.Value; }
|
---|
| 125 | set { FleetUsageFactorParameter.Value = value; }
|
---|
| 126 | }
|
---|
| 127 | public DoubleValue DistanceFactor {
|
---|
| 128 | get { return DistanceFactorParameter.Value; }
|
---|
| 129 | set { DistanceFactorParameter.Value = value; }
|
---|
| 130 | }
|
---|
| 131 |
|
---|
[6885] | 132 | protected virtual double CalculateDistance(int start, int end) {
|
---|
[4362] | 133 | double distance = 0.0;
|
---|
| 134 |
|
---|
| 135 | distance =
|
---|
| 136 | Math.Sqrt(
|
---|
| 137 | Math.Pow(Coordinates[start, 0] - Coordinates[end, 0], 2) +
|
---|
| 138 | Math.Pow(Coordinates[start, 1] - Coordinates[end, 1], 2));
|
---|
| 139 |
|
---|
| 140 | return distance;
|
---|
| 141 | }
|
---|
| 142 |
|
---|
| 143 | private DoubleMatrix CreateDistanceMatrix() {
|
---|
| 144 | DoubleMatrix distanceMatrix = new DoubleMatrix(Coordinates.Rows, Coordinates.Rows);
|
---|
| 145 |
|
---|
| 146 | for (int i = 0; i < distanceMatrix.Rows; i++) {
|
---|
[7543] | 147 | for (int j = 0; j < distanceMatrix.Columns; j++) {
|
---|
[4362] | 148 | double distance = CalculateDistance(i, j);
|
---|
| 149 |
|
---|
| 150 | distanceMatrix[i, j] = distance;
|
---|
| 151 | }
|
---|
| 152 | }
|
---|
| 153 |
|
---|
| 154 | return distanceMatrix;
|
---|
| 155 | }
|
---|
[6607] | 156 |
|
---|
[6851] | 157 | public virtual double[] GetCoordinates(int city) {
|
---|
| 158 | double[] coordinates = new double[Coordinates.Columns];
|
---|
| 159 |
|
---|
| 160 | for (int i = 0; i < Coordinates.Columns; i++) {
|
---|
| 161 | coordinates[i] = Coordinates[city, i];
|
---|
| 162 | }
|
---|
| 163 |
|
---|
| 164 | return coordinates;
|
---|
| 165 | }
|
---|
| 166 |
|
---|
| 167 | public virtual double GetDemand(int city) {
|
---|
| 168 | return Demand[city];
|
---|
| 169 | }
|
---|
| 170 |
|
---|
[6607] | 171 | //cache for performance improvement
|
---|
| 172 | private DoubleMatrix distanceMatrix = null;
|
---|
| 173 | private IVRPEvaluator evaluator = null;
|
---|
| 174 |
|
---|
[7852] | 175 | public IVRPEvaluator SolutionEvaluator {
|
---|
| 176 | get {
|
---|
| 177 | return evaluator;
|
---|
| 178 | }
|
---|
| 179 | }
|
---|
| 180 |
|
---|
[6851] | 181 | public virtual double GetDistance(int start, int end, IVRPEncoding solution) {
|
---|
[4362] | 182 | double distance = 0.0;
|
---|
[4380] | 183 | if (distanceMatrix == null && UseDistanceMatrix.Value) {
|
---|
| 184 | distanceMatrix = DistanceMatrix = CreateDistanceMatrix();
|
---|
| 185 | }
|
---|
| 186 |
|
---|
| 187 | if (distanceMatrix != null)
|
---|
| 188 | distance = distanceMatrix[start, end];
|
---|
[4377] | 189 | else
|
---|
[4362] | 190 | distance = CalculateDistance(start, end);
|
---|
| 191 |
|
---|
| 192 | return distance;
|
---|
| 193 | }
|
---|
| 194 |
|
---|
[6854] | 195 | public virtual double GetInsertionDistance(int start, int customer, int end, IVRPEncoding solution,
|
---|
| 196 | out double startDistance, out double endDistance) {
|
---|
[6851] | 197 | double distance = GetDistance(start, end, solution);
|
---|
| 198 |
|
---|
[6854] | 199 | startDistance = GetDistance(start, customer, solution);
|
---|
| 200 | endDistance = GetDistance(customer, end, solution);
|
---|
| 201 |
|
---|
| 202 | double newDistance = startDistance + endDistance;
|
---|
| 203 |
|
---|
[6851] | 204 | return newDistance - distance;
|
---|
| 205 | }
|
---|
| 206 |
|
---|
[4362] | 207 | public bool Feasible(IVRPEncoding solution) {
|
---|
[6607] | 208 | return evaluator.Feasible(
|
---|
| 209 | evaluator.Evaluate(
|
---|
[4378] | 210 | this, solution));
|
---|
[4362] | 211 | }
|
---|
| 212 |
|
---|
[6838] | 213 | public bool TourFeasible(Tour tour, IVRPEncoding solution) {
|
---|
[6607] | 214 | return evaluator.Feasible(
|
---|
[6838] | 215 | evaluator.EvaluateTour(
|
---|
| 216 | this, tour, solution));
|
---|
[4362] | 217 | }
|
---|
| 218 |
|
---|
[6607] | 219 | public VRPEvaluation Evaluate(IVRPEncoding solution) {
|
---|
| 220 | return evaluator.Evaluate(this, solution);
|
---|
[4362] | 221 | }
|
---|
| 222 |
|
---|
[6838] | 223 | public VRPEvaluation EvaluateTour(Tour tour, IVRPEncoding solution) {
|
---|
| 224 | return evaluator.EvaluateTour(this, tour, solution);
|
---|
[4362] | 225 | }
|
---|
| 226 |
|
---|
[6607] | 227 | public bool Feasible(VRPEvaluation eval) {
|
---|
| 228 | return evaluator.Feasible(eval);
|
---|
| 229 | }
|
---|
| 230 |
|
---|
[6851] | 231 | public double GetInsertionCosts(VRPEvaluation eval, IVRPEncoding solution, int customer, int tour, int index, out bool feasible) {
|
---|
| 232 | return evaluator.GetInsertionCosts(this, solution, eval, customer, tour, index, out feasible);
|
---|
[6752] | 233 | }
|
---|
| 234 |
|
---|
[7852] | 235 |
|
---|
| 236 | public event EventHandler EvaluationChanged;
|
---|
| 237 |
|
---|
[4860] | 238 | protected void EvalBestKnownSolution() {
|
---|
[7852] | 239 | EventHandler tmp = EvaluationChanged;
|
---|
| 240 | if (tmp != null)
|
---|
| 241 | tmp(this, null);
|
---|
[4860] | 242 | }
|
---|
| 243 |
|
---|
[4362] | 244 | protected abstract IVRPEvaluator Evaluator { get; }
|
---|
| 245 | protected abstract IVRPCreator Creator { get; }
|
---|
| 246 |
|
---|
| 247 | [StorableConstructor]
|
---|
| 248 | protected VRPProblemInstance(bool deserializing) : base(deserializing) { }
|
---|
| 249 |
|
---|
| 250 | public VRPProblemInstance()
|
---|
| 251 | : base() {
|
---|
| 252 | Parameters.Add(new ValueParameter<DoubleMatrix>("Coordinates", "The x- and y-Coordinates of the cities.", new DoubleMatrix()));
|
---|
[4380] | 253 | Parameters.Add(new OptionalValueParameter<DoubleMatrix>("DistanceMatrix", "The matrix which contains the distances between the cities."));
|
---|
[4362] | 254 | Parameters.Add(new ValueParameter<BoolValue>("UseDistanceMatrix", "True if a distance matrix should be calculated and used for evaluation, otherwise false.", new BoolValue(true)));
|
---|
| 255 | Parameters.Add(new ValueParameter<IntValue>("Vehicles", "The number of vehicles.", new IntValue(0)));
|
---|
| 256 | Parameters.Add(new ValueParameter<DoubleArray>("Demand", "The demand of each customer.", new DoubleArray()));
|
---|
| 257 |
|
---|
[5127] | 258 | Parameters.Add(new ValueParameter<DoubleValue>("EvalFleetUsageFactor", "The fleet usage factor considered in the evaluation.", new DoubleValue(0)));
|
---|
[4362] | 259 | Parameters.Add(new ValueParameter<DoubleValue>("EvalDistanceFactor", "The distance factor considered in the evaluation.", new DoubleValue(1)));
|
---|
| 260 |
|
---|
[7852] | 261 | evaluator = Evaluator;
|
---|
[4860] | 262 | AttachEventHandlers();
|
---|
[4362] | 263 | }
|
---|
[4752] | 264 |
|
---|
| 265 | protected VRPProblemInstance(VRPProblemInstance original, Cloner cloner)
|
---|
| 266 | : base(original, cloner) {
|
---|
[7852] | 267 | evaluator = Evaluator;
|
---|
| 268 | AttachEventHandlers();
|
---|
[4752] | 269 | }
|
---|
[4860] | 270 |
|
---|
| 271 | [StorableHook(HookType.AfterDeserialization)]
|
---|
| 272 | private void AfterDeserializationHook() {
|
---|
[7852] | 273 | evaluator = Evaluator;
|
---|
[4860] | 274 | AttachEventHandlers();
|
---|
| 275 | }
|
---|
| 276 |
|
---|
| 277 | private void AttachEventHandlers() {
|
---|
| 278 | DistanceFactorParameter.ValueChanged += new EventHandler(DistanceFactorParameter_ValueChanged);
|
---|
| 279 | DistanceFactorParameter.Value.ValueChanged += new EventHandler(DistanceFactor_ValueChanged);
|
---|
| 280 | FleetUsageFactorParameter.ValueChanged += new EventHandler(FleetUsageFactorParameter_ValueChanged);
|
---|
| 281 | FleetUsageFactorParameter.Value.ValueChanged += new EventHandler(FleetUsageFactor_ValueChanged);
|
---|
| 282 | DistanceMatrixParameter.ValueChanged += new EventHandler(DistanceMatrixParameter_ValueChanged);
|
---|
| 283 | if (DistanceMatrix != null) {
|
---|
| 284 | DistanceMatrix.ItemChanged += new EventHandler<EventArgs<int, int>>(DistanceMatrix_ItemChanged);
|
---|
| 285 | DistanceMatrix.Reset += new EventHandler(DistanceMatrix_Reset);
|
---|
| 286 | }
|
---|
| 287 | UseDistanceMatrixParameter.ValueChanged += new EventHandler(UseDistanceMatrixParameter_ValueChanged);
|
---|
| 288 | UseDistanceMatrix.ValueChanged += new EventHandler(UseDistanceMatrix_ValueChanged);
|
---|
| 289 | }
|
---|
| 290 |
|
---|
[6711] | 291 | public virtual void InitializeState() {
|
---|
| 292 | }
|
---|
| 293 |
|
---|
| 294 | public virtual void ClearState() {
|
---|
| 295 | }
|
---|
| 296 |
|
---|
[4860] | 297 | #region Event handlers
|
---|
| 298 | void DistanceFactorParameter_ValueChanged(object sender, EventArgs e) {
|
---|
| 299 | DistanceFactorParameter.Value.ValueChanged += new EventHandler(DistanceFactor_ValueChanged);
|
---|
| 300 | EvalBestKnownSolution();
|
---|
| 301 | }
|
---|
| 302 | void DistanceFactor_ValueChanged(object sender, EventArgs e) {
|
---|
| 303 | EvalBestKnownSolution();
|
---|
| 304 | }
|
---|
| 305 | void FleetUsageFactorParameter_ValueChanged(object sender, EventArgs e) {
|
---|
| 306 | FleetUsageFactorParameter.Value.ValueChanged += new EventHandler(FleetUsageFactor_ValueChanged);
|
---|
| 307 | EvalBestKnownSolution();
|
---|
| 308 | }
|
---|
| 309 | void FleetUsageFactor_ValueChanged(object sender, EventArgs e) {
|
---|
| 310 | EvalBestKnownSolution();
|
---|
| 311 | }
|
---|
| 312 | void DistanceMatrixParameter_ValueChanged(object sender, EventArgs e) {
|
---|
| 313 | if (DistanceMatrix != null) {
|
---|
| 314 | DistanceMatrix.ItemChanged += new EventHandler<EventArgs<int, int>>(DistanceMatrix_ItemChanged);
|
---|
| 315 | DistanceMatrix.Reset += new EventHandler(DistanceMatrix_Reset);
|
---|
| 316 | }
|
---|
[6607] | 317 | distanceMatrix = DistanceMatrix;
|
---|
[4860] | 318 | EvalBestKnownSolution();
|
---|
| 319 | }
|
---|
| 320 | void DistanceMatrix_Reset(object sender, EventArgs e) {
|
---|
| 321 | EvalBestKnownSolution();
|
---|
| 322 | }
|
---|
| 323 | void DistanceMatrix_ItemChanged(object sender, EventArgs<int, int> e) {
|
---|
[6607] | 324 | distanceMatrix = DistanceMatrix;
|
---|
[4860] | 325 | EvalBestKnownSolution();
|
---|
| 326 | }
|
---|
| 327 | void UseDistanceMatrixParameter_ValueChanged(object sender, EventArgs e) {
|
---|
| 328 | UseDistanceMatrix.ValueChanged += new EventHandler(UseDistanceMatrix_ValueChanged);
|
---|
[6607] | 329 | if (!UseDistanceMatrix.Value)
|
---|
| 330 | distanceMatrix = null;
|
---|
[4860] | 331 | EvalBestKnownSolution();
|
---|
| 332 | }
|
---|
| 333 | void UseDistanceMatrix_ValueChanged(object sender, EventArgs e) {
|
---|
[6607] | 334 | if (!UseDistanceMatrix.Value)
|
---|
| 335 | distanceMatrix = null;
|
---|
[4860] | 336 | EvalBestKnownSolution();
|
---|
| 337 | }
|
---|
| 338 | #endregion
|
---|
[4362] | 339 | }
|
---|
| 340 | } |
---|