| 1 | #region License Information
|
|---|
| 2 | /* HeuristicLab
|
|---|
| 3 | * Copyright (C) 2002-2017 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 HeuristicLab.Analysis;
|
|---|
| 26 | using HeuristicLab.Common;
|
|---|
| 27 | using HeuristicLab.Core;
|
|---|
| 28 | using HeuristicLab.Data;
|
|---|
| 29 | using HeuristicLab.Encodings.IntegerVectorEncoding;
|
|---|
| 30 | using HeuristicLab.Optimization;
|
|---|
| 31 | using HeuristicLab.Optimization.Operators;
|
|---|
| 32 | using HeuristicLab.Parameters;
|
|---|
| 33 | using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
|
|---|
| 34 |
|
|---|
| 35 | namespace HeuristicLab.Problems.FacilityLocation {
|
|---|
| 36 | [Item("Facility Location Problem (FLP)", "Problem that represents the delivery to multiple customers from a set of depots. Solutions to this problem define which depots to open and which customer to serve from which depot.")]
|
|---|
| 37 | [Creatable(CreatableAttribute.Categories.CombinatorialProblems, Priority = 230)]
|
|---|
| 38 | [StorableClass]
|
|---|
| 39 | public sealed class FacilityLocationProblem : SingleObjectiveBasicProblem<IntegerVectorEncoding> {
|
|---|
| 40 | public override bool Maximization {
|
|---|
| 41 | get { return false; }
|
|---|
| 42 | }
|
|---|
| 43 |
|
|---|
| 44 | [Storable]
|
|---|
| 45 | private IValueParameter<DoubleArray> openingCostsParameter;
|
|---|
| 46 | public IValueParameter<DoubleArray> OpeningCostsParameter {
|
|---|
| 47 | get { return openingCostsParameter; }
|
|---|
| 48 | }
|
|---|
| 49 |
|
|---|
| 50 | [Storable]
|
|---|
| 51 | private IValueParameter<DoubleArray> depotCapacitiesParameter;
|
|---|
| 52 | public IValueParameter<DoubleArray> DepotCapacitiesParameter {
|
|---|
| 53 | get { return depotCapacitiesParameter; }
|
|---|
| 54 | }
|
|---|
| 55 |
|
|---|
| 56 | [Storable]
|
|---|
| 57 | private IValueParameter<DoubleArray> customerDemandsParameter;
|
|---|
| 58 | public IValueParameter<DoubleArray> CustomerDemandsParameter {
|
|---|
| 59 | get { return customerDemandsParameter; }
|
|---|
| 60 | }
|
|---|
| 61 |
|
|---|
| 62 | [Storable]
|
|---|
| 63 | private IValueParameter<DoubleMatrix> deliveryCostsParameter;
|
|---|
| 64 | public IValueParameter<DoubleMatrix> DeliveryCostsParameter {
|
|---|
| 65 | get { return deliveryCostsParameter; }
|
|---|
| 66 | }
|
|---|
| 67 |
|
|---|
| 68 | [StorableConstructor]
|
|---|
| 69 | private FacilityLocationProblem(bool deserializing) : base(deserializing) { }
|
|---|
| 70 | private FacilityLocationProblem(FacilityLocationProblem original, Cloner cloner)
|
|---|
| 71 | : base(original, cloner) {
|
|---|
| 72 | openingCostsParameter = cloner.Clone(original.openingCostsParameter);
|
|---|
| 73 | depotCapacitiesParameter = cloner.Clone(original.depotCapacitiesParameter);
|
|---|
| 74 | customerDemandsParameter = cloner.Clone(original.customerDemandsParameter);
|
|---|
| 75 | deliveryCostsParameter = cloner.Clone(original.deliveryCostsParameter);
|
|---|
| 76 | RegisterEventHandlers();
|
|---|
| 77 | }
|
|---|
| 78 | public FacilityLocationProblem() {
|
|---|
| 79 | Parameters.Add(openingCostsParameter = new ValueParameter<DoubleArray>("Opening Costs", "For each possible depot location the costs to open it."));
|
|---|
| 80 | Parameters.Add(depotCapacitiesParameter = new ValueParameter<DoubleArray>("Depot Capacities", "For each depot d in D the capacity value which is used to satisfy the customer demands."));
|
|---|
| 81 | Parameters.Add(customerDemandsParameter = new ValueParameter<DoubleArray>("Customer Demands", "For each customer c in C the demand that has to be delivered."));
|
|---|
| 82 | Parameters.Add(deliveryCostsParameter = new ValueParameter<DoubleMatrix>("Delivery Costs", "A DxC matrix with service costs for each pair (d, c)."));
|
|---|
| 83 |
|
|---|
| 84 | OpeningCostsParameter.Value = new DoubleArray(new double[] { 55929, 53094, 53842, 47865, 47995, 57991, 55903, 51308, 49140, 59082 } );
|
|---|
| 85 | DepotCapacitiesParameter.Value = new DoubleArray(new double[] { 490, 420, 420, 490, 560, 490, 490, 490, 420, 560 });
|
|---|
| 86 | CustomerDemandsParameter.Value = new DoubleArray(new double[] { 14, 19, 16, 18, 16, 14, 18, 12, 14, 20, 19, 20, 19, 18, 19, 18, 20, 20, 19, 15, 19, 18, 12, 19, 20, 19, 11, 16, 20, 17, 15, 19, 19, 11, 20, 12, 14, 19, 12, 20, 12, 20, 15, 16, 13, 15, 18, 19, 12, 19, 18, 20, 13, 17, 17, 11, 16, 16, 17, 16, 18, 16, 18, 19, 18, 17, 16, 13, 16, 15, 11, 15, 13, 16, 18, 15, 11, 14, 12, 16, 17, 17, 12, 14, 14, 15, 19, 16, 19, 12, 16, 11, 11, 14, 17, 15, 17, 20, 15, 12 });
|
|---|
| 87 | DeliveryCostsParameter.Value = new DoubleMatrix(new double[,] {
|
|---|
| 88 | { 29.73, 30.81, 27.07, 25.08, 20.00, 46.23, 4.24, 28.23, 36.22, 27.02, 51.62, 37.66, 12.04, 25.81, 17.46, 10.44, 5.00, 46.04, 35.69, 39.66, 57.80, 48.09, 33.54, 42.06, 41.19, 41.19, 47.38, 45.28, 43.19, 22.02, 30.61, 55.23, 43.60, 28.86, 24.74, 34.00, 38.00, 17.12, 27.20, 39.62, 36.06, 5.66, 47.63, 24.84, 19.31, 25.96, 17.09, 29.15, 8.06, 18.03, 40.11, 18.25, 38.33, 22.80, 53.82, 49.52, 60.61, 41.11, 30.08, 28.02, 42.58, 7.07, 28.02, 47.01, 32.25, 28.07, 14.76, 41.04, 28.65, 43.19, 7.28, 40.01, 32.53, 45.62, 39.60, 52.40, 31.24, 41.59, 20.10, 21.19, 42.64, 32.02, 31.06, 30.68, 47.41, 31.38, 25.32, 25.00, 10.30, 51.89, 21.93, 49.24, 43.01, 48.80, 23.77, 48.66, 44.28, 49.20, 37.11, 44.78, }
|
|---|
| 89 | , { 8.49, 30.41, 33.84, 25.00, 21.26, 13.15, 33.62, 9.43, 42.94, 34.79, 20.22, 9.49, 26.93, 13.04, 38.01, 37.48, 32.70, 23.41, 9.06, 6.08, 30.02, 44.55, 10.05, 31.89, 39.05, 45.49, 50.61, 17.26, 13.15, 20.02, 17.00, 25.18, 20.62, 42.72, 14.14, 4.00, 40.50, 22.02, 18.97, 35.47, 28.43, 39.85, 21.38, 15.00, 41.05, 41.98, 20.59, 8.60, 39.05, 21.93, 14.32, 20.62, 44.78, 16.12, 28.16, 18.11, 32.14, 11.40, 43.97, 35.11, 37.48, 44.38, 19.31, 45.28, 41.23, 34.18, 27.17, 12.65, 9.22, 13.15, 30.41, 16.16, 13.04, 28.65, 13.42, 19.65, 16.12, 4.24, 36.22, 27.29, 11.05, 15.13, 39.00, 27.29, 28.64, 6.40, 15.00, 13.45, 44.38, 33.24, 43.19, 39.41, 42.64, 18.03, 40.61, 41.23, 6.71, 14.87, 47.42, 29.68, }
|
|---|
| 90 | , { 47.63, 19.24, 20.40, 26.83, 51.89, 42.05, 44.28, 45.61, 11.18, 20.22, 40.52, 55.87, 39.29, 39.41, 30.07, 37.01, 44.41, 29.41, 54.49, 43.01, 37.01, 5.10, 53.91, 16.55, 8.49, 6.32, 4.00, 35.85, 38.47, 34.00, 31.14, 39.46, 30.46, 19.65, 48.55, 44.55, 9.22, 48.85, 30.81, 12.04, 19.10, 43.05, 33.53, 37.44, 29.43, 22.56, 44.78, 46.23, 40.05, 50.16, 60.83, 48.33, 9.49, 38.59, 33.14, 40.16, 39.01, 38.59, 18.97, 19.24, 10.30, 48.26, 30.00, 3.00, 15.13, 19.42, 35.17, 37.22, 42.64, 38.47, 45.89, 62.29, 34.66, 22.80, 35.51, 42.72, 31.83, 48.01, 27.00, 28.46, 40.31, 57.20, 16.00, 21.63, 24.52, 46.75, 50.77, 47.71, 42.58, 24.00, 27.89, 13.04, 5.00, 39.22, 24.33, 10.05, 50.48, 44.38, 13.04, 20.88, }
|
|---|
| 91 | , { 15.00, 14.42, 17.72, 9.06, 22.02, 18.38, 24.84, 13.04, 26.93, 18.68, 22.80, 23.43, 17.03, 7.28, 23.54, 25.06, 24.21, 17.46, 21.93, 14.00, 28.84, 30.53, 21.26, 18.97, 24.21, 29.83, 35.36, 16.28, 14.76, 7.07, 2.00, 26.17, 14.76, 26.68, 16.76, 12.53, 24.84, 20.10, 3.00, 20.81, 13.89, 29.21, 18.60, 6.00, 26.31, 26.17, 16.28, 13.60, 27.46, 21.02, 28.32, 19.03, 28.84, 8.06, 25.06, 20.81, 31.62, 13.00, 27.89, 18.97, 23.32, 34.71, 3.16, 30.81, 25.08, 18.03, 15.00, 12.53, 10.00, 14.76, 23.32, 29.70, 4.12, 19.03, 10.82, 23.85, 2.24, 18.25, 21.10, 12.17, 14.87, 24.70, 22.85, 11.40, 20.22, 14.14, 18.97, 15.81, 32.76, 25.18, 28.07, 27.20, 27.66, 20.00, 25.02, 28.23, 21.21, 21.54, 31.30, 19.03, }
|
|---|
| 92 | , { 15.23, 15.65, 16.28, 8.06, 17.09, 25.55, 17.03, 13.00, 26.91, 17.03, 30.48, 24.70, 9.22, 7.07, 18.03, 18.03, 16.40, 25.06, 22.85, 19.92, 36.62, 33.84, 21.47, 24.02, 26.93, 30.81, 36.89, 24.04, 22.20, 1.00, 9.43, 33.97, 22.47, 24.19, 14.14, 16.00, 26.08, 14.32, 6.32, 24.04, 18.11, 21.63, 26.40, 5.00, 21.10, 22.85, 10.20, 13.93, 20.12, 15.52, 29.07, 13.60, 29.07, 4.47, 32.76, 28.43, 39.41, 20.25, 25.55, 17.69, 26.93, 27.02, 7.28, 33.62, 24.08, 16.97, 7.62, 20.00, 11.18, 22.20, 15.65, 30.02, 11.40, 25.71, 18.44, 31.40, 10.00, 23.19, 16.49, 8.06, 21.95, 23.43, 21.93, 13.60, 27.20, 15.52, 16.28, 13.45, 25.50, 32.02, 23.35, 32.14, 29.97, 27.66, 21.19, 32.56, 26.17, 28.65, 30.48, 25.32, }
|
|---|
| 93 | , { 26.08, 18.68, 15.00, 13.60, 21.63, 38.01, 9.06, 24.02, 24.74, 15.03, 42.44, 35.36, 6.71, 19.24, 7.81, 5.39, 9.22, 35.38, 33.38, 32.57, 47.38, 36.01, 31.58, 30.08, 29.07, 29.61, 35.90, 35.81, 34.48, 13.00, 20.81, 45.45, 33.24, 18.36, 22.80, 28.28, 26.08, 18.03, 17.20, 27.46, 24.17, 10.00, 37.54, 17.46, 10.82, 15.81, 15.23, 25.02, 7.81, 19.42, 39.05, 18.36, 26.93, 16.12, 43.19, 40.50, 50.21, 32.65, 19.72, 16.03, 30.41, 15.81, 17.80, 35.01, 20.88, 16.00, 5.10, 32.25, 23.09, 34.48, 11.18, 39.56, 23.71, 34.13, 30.53, 43.57, 21.63, 35.69, 8.94, 9.43, 34.44, 31.95, 19.42, 18.79, 36.06, 27.00, 24.35, 22.56, 13.04, 40.31, 13.60, 37.11, 31.02, 39.66, 13.60, 36.50, 38.64, 41.15, 26.40, 33.12, }
|
|---|
| 94 | , { 8.06, 35.61, 36.80, 28.32, 9.22, 27.89, 26.02, 9.49, 47.38, 37.54, 34.93, 9.43, 22.14, 15.26, 36.25, 32.98, 25.02, 36.12, 7.81, 20.40, 44.41, 52.84, 5.66, 41.23, 46.32, 51.09, 57.01, 31.06, 27.17, 21.21, 24.17, 39.81, 33.14, 44.41, 6.40, 14.04, 46.23, 12.00, 23.85, 43.05, 36.24, 33.06, 35.01, 17.20, 39.40, 42.72, 13.60, 9.22, 33.38, 11.05, 11.05, 11.05, 49.52, 16.28, 42.05, 32.76, 46.69, 25.08, 45.80, 38.21, 45.65, 36.12, 24.70, 53.00, 44.60, 37.48, 24.60, 26.02, 12.65, 27.17, 22.00, 11.05, 21.84, 40.02, 26.02, 34.48, 23.77, 18.79, 35.85, 28.43, 25.32, 3.16, 42.45, 33.02, 40.61, 10.00, 4.47, 7.07, 38.12, 45.54, 42.05, 49.40, 49.65, 32.56, 40.82, 50.57, 20.25, 29.73, 50.99, 40.52, }
|
|---|
| 95 | , { 21.54, 13.00, 18.25, 12.21, 30.00, 16.03, 31.91, 19.92, 24.74, 19.24, 18.03, 28.60, 24.19, 15.03, 27.29, 30.48, 31.38, 10.00, 27.46, 15.26, 21.93, 24.76, 27.29, 12.21, 19.42, 26.40, 31.06, 11.40, 12.04, 14.32, 6.08, 20.25, 7.81, 27.07, 24.33, 17.20, 21.54, 28.16, 8.94, 15.81, 8.94, 35.38, 12.21, 14.04, 29.55, 27.46, 24.33, 20.25, 33.24, 29.07, 33.60, 27.07, 26.25, 16.12, 17.80, 16.49, 24.76, 11.40, 28.02, 19.10, 17.69, 41.11, 8.06, 25.50, 24.08, 18.11, 21.40, 10.20, 16.76, 12.04, 30.87, 35.23, 7.62, 11.00, 8.25, 19.65, 6.00, 20.25, 24.17, 16.40, 13.34, 31.38, 22.02, 10.05, 12.17, 20.12, 26.48, 23.35, 38.29, 17.12, 30.68, 20.12, 23.02, 15.52, 26.93, 21.63, 22.83, 19.00, 29.61, 11.18, }
|
|---|
| 96 | , { 10.30, 27.73, 27.80, 20.12, 5.10, 29.41, 16.12, 9.22, 38.60, 28.43, 35.85, 18.11, 11.70, 10.20, 25.94, 22.56, 15.13, 33.73, 16.12, 22.02, 44.01, 45.88, 14.04, 35.51, 39.00, 42.72, 48.88, 30.46, 27.29, 13.00, 19.00, 40.25, 30.81, 34.71, 5.10, 15.56, 38.08, 3.61, 17.26, 36.06, 29.83, 23.02, 33.84, 11.00, 29.07, 32.80, 3.16, 10.00, 23.09, 4.12, 21.10, 2.24, 40.80, 9.06, 40.80, 33.62, 46.62, 25.06, 36.12, 29.21, 38.90, 26.68, 18.25, 45.69, 35.47, 28.60, 14.42, 25.50, 10.82, 27.29, 12.37, 21.38, 18.44, 36.01, 24.70, 36.06, 19.03, 22.80, 25.81, 19.21, 26.08, 13.60, 33.42, 25.63, 37.12, 12.21, 6.08, 5.39, 28.00, 42.11, 31.76, 43.74, 42.05, 33.12, 30.81, 44.38, 25.24, 32.02, 41.77, 36.01, }
|
|---|
| 97 | , { 29.73, 32.02, 37.64, 31.76, 42.05, 9.22, 49.50, 29.55, 42.05, 38.60, 2.24, 31.02, 41.73, 28.60, 46.96, 49.65, 48.80, 12.00, 31.14, 16.76, 8.54, 36.40, 32.39, 25.08, 34.13, 42.11, 44.91, 8.60, 10.82, 31.89, 23.60, 3.16, 12.37, 46.10, 34.93, 23.41, 38.00, 41.68, 27.20, 31.02, 26.31, 54.04, 8.06, 29.07, 49.24, 46.84, 38.83, 29.15, 52.20, 42.06, 35.06, 40.31, 43.00, 31.24, 9.22, 4.47, 10.05, 13.04, 46.87, 38.33, 31.26, 59.55, 26.63, 38.08, 42.43, 37.36, 39.82, 12.81, 27.29, 10.82, 47.51, 37.05, 21.21, 18.25, 14.14, 3.16, 22.80, 19.03, 43.86, 35.85, 12.08, 37.48, 40.61, 29.41, 16.49, 27.51, 36.40, 34.01, 57.43, 18.36, 50.33, 28.79, 37.34, 5.00, 46.49, 31.62, 19.10, 8.06, 47.04, 20.22, }
|
|---|
| 98 | });
|
|---|
| 99 |
|
|---|
| 100 | Encoding.Bounds[0, 0] = 0;
|
|---|
| 101 | Encoding.Bounds[0, 1] = DepotCapacitiesParameter.Value.Length;
|
|---|
| 102 | Encoding.Length = CustomerDemandsParameter.Value.Length;
|
|---|
| 103 |
|
|---|
| 104 | InitializeOperators();
|
|---|
| 105 | RegisterEventHandlers();
|
|---|
| 106 | }
|
|---|
| 107 |
|
|---|
| 108 | public override IDeepCloneable Clone(Cloner cloner) {
|
|---|
| 109 | return new FacilityLocationProblem(this, cloner);
|
|---|
| 110 | }
|
|---|
| 111 |
|
|---|
| 112 | [StorableHook(HookType.AfterDeserialization)]
|
|---|
| 113 | private void AfterDeserialization() {
|
|---|
| 114 | RegisterEventHandlers();
|
|---|
| 115 | }
|
|---|
| 116 |
|
|---|
| 117 | private void InitializeOperators() {
|
|---|
| 118 | Operators.Add(new IntegerVectorHammingSimilarityOperator());
|
|---|
| 119 | Operators.Add(new QualitySimilarityCalculator());
|
|---|
| 120 | Operators.Add(new PopulationSimilarityAnalyzer(Operators.OfType<SingleObjectiveSolutionSimilarityCalculator>()));
|
|---|
| 121 | }
|
|---|
| 122 |
|
|---|
| 123 | private void RegisterEventHandlers() {
|
|---|
| 124 | CustomerDemandsParameter.ValueChanged += CustomerDemandsParameterOnValueChanged;
|
|---|
| 125 | CustomerDemandsParameter.Value.ToStringChanged += CustomerDemandsParameterValueOnToStringChanged;
|
|---|
| 126 | DepotCapacitiesParameter.ValueChanged += DepotCapacitiesParameterOnValueChanged;
|
|---|
| 127 | DepotCapacitiesParameter.Value.ToStringChanged += DepotCapacitiesParameterValueOnToStringChanged;
|
|---|
| 128 | }
|
|---|
| 129 |
|
|---|
| 130 | private void CustomerDemandsParameterOnValueChanged(object sender, EventArgs eventArgs) {
|
|---|
| 131 | CustomerDemandsParameter.Value.ToStringChanged += CustomerDemandsParameterValueOnToStringChanged;
|
|---|
| 132 | Encoding.Length = CustomerDemandsParameter.Value.Length;
|
|---|
| 133 | }
|
|---|
| 134 |
|
|---|
| 135 | private void CustomerDemandsParameterValueOnToStringChanged(object sender, EventArgs eventArgs) {
|
|---|
| 136 | Encoding.Length = CustomerDemandsParameter.Value.Length;
|
|---|
| 137 | }
|
|---|
| 138 |
|
|---|
| 139 | private void DepotCapacitiesParameterOnValueChanged(object sender, EventArgs eventArgs) {
|
|---|
| 140 | DepotCapacitiesParameter.Value.ToStringChanged += DepotCapacitiesParameterValueOnToStringChanged;
|
|---|
| 141 | Encoding.Bounds[0, 0] = 0;
|
|---|
| 142 | Encoding.Bounds[0, 1] = DepotCapacitiesParameter.Value.Length;
|
|---|
| 143 | }
|
|---|
| 144 |
|
|---|
| 145 | private void DepotCapacitiesParameterValueOnToStringChanged(object sender, EventArgs eventArgs) {
|
|---|
| 146 | Encoding.Bounds[0, 0] = 0;
|
|---|
| 147 | Encoding.Bounds[0, 1] = DepotCapacitiesParameter.Value.Length;
|
|---|
| 148 | }
|
|---|
| 149 |
|
|---|
| 150 | public override double Evaluate(Individual individual, IRandom random) {
|
|---|
| 151 | var vec = individual.IntegerVector(Encoding.Name);
|
|---|
| 152 | return Evaluate(vec);
|
|---|
| 153 | }
|
|---|
| 154 |
|
|---|
| 155 | public double Evaluate(IntegerVector depotAssignment) {
|
|---|
| 156 | var openingCosts = OpeningCostsParameter.Value;
|
|---|
| 157 | var capacities = DepotCapacitiesParameter.Value;
|
|---|
| 158 | var demands = CustomerDemandsParameter.Value;
|
|---|
| 159 | var deliveryCosts = DeliveryCostsParameter.Value;
|
|---|
| 160 |
|
|---|
| 161 | double totalOpeningCosts, totalDeliveryCosts;
|
|---|
| 162 | double[] depotUsage;
|
|---|
| 163 |
|
|---|
| 164 | try {
|
|---|
| 165 | return Evaluate(depotAssignment, openingCosts, capacities, demands, deliveryCosts, out totalOpeningCosts, out totalDeliveryCosts, out depotUsage);
|
|---|
| 166 | } catch (IndexOutOfRangeException) {
|
|---|
| 167 | throw new ArgumentException("The solution contains more customers than there are problem data for.");
|
|---|
| 168 | }
|
|---|
| 169 | }
|
|---|
| 170 |
|
|---|
| 171 | public FacilityLocationSolution GetSolution(IntegerVector depotAssignment) {
|
|---|
| 172 | var openingCosts = OpeningCostsParameter.Value;
|
|---|
| 173 | var capacities = DepotCapacitiesParameter.Value;
|
|---|
| 174 | var demands = CustomerDemandsParameter.Value;
|
|---|
| 175 | var deliveryCosts = DeliveryCostsParameter.Value;
|
|---|
| 176 |
|
|---|
| 177 | double totalOpeningCosts, totalDeliveryCosts, fitness;
|
|---|
| 178 | double[] depotUsage;
|
|---|
| 179 |
|
|---|
| 180 | try {
|
|---|
| 181 | fitness = Evaluate(depotAssignment, openingCosts, capacities, demands, deliveryCosts, out totalOpeningCosts, out totalDeliveryCosts, out depotUsage);
|
|---|
| 182 | } catch (IndexOutOfRangeException) {
|
|---|
| 183 | throw new ArgumentException("The solution contains more customers than there are problem data for.");
|
|---|
| 184 | }
|
|---|
| 185 |
|
|---|
| 186 | var overbooking = depotUsage.Zip(capacities, (a, b) => a > b ? a - b : 0).Sum();
|
|---|
| 187 |
|
|---|
| 188 | return new FacilityLocationSolution() {
|
|---|
| 189 | OpeningCosts = (DoubleArray)openingCosts.Clone(),
|
|---|
| 190 | DepotCapacities = (DoubleArray)capacities.Clone(),
|
|---|
| 191 | CustomerDemands = (DoubleArray)demands.Clone(),
|
|---|
| 192 | DeliveryCosts = (DoubleMatrix)deliveryCosts.Clone(),
|
|---|
| 193 | CustomerToDepotAssignmentParameter = { Value = (IntegerVector)depotAssignment.Clone() },
|
|---|
| 194 | FitnessValueParameter = { Value = new DoubleValue(fitness) },
|
|---|
| 195 | TotalOpeningCostsParameter = { Value = new DoubleValue(totalOpeningCosts) },
|
|---|
| 196 | TotalDeliveryCostsParameter = { Value = new DoubleValue(totalDeliveryCosts) },
|
|---|
| 197 | TotalOverbookedCapacityParameter = { Value = new DoubleValue(overbooking) }
|
|---|
| 198 | };
|
|---|
| 199 | }
|
|---|
| 200 |
|
|---|
| 201 | public static double Evaluate(IEnumerable<int> customer2Depot, DoubleArray openingCosts, DoubleArray capacities, DoubleArray demands, DoubleMatrix deliveryCosts, out double totalOpeningCosts, out double totalDeliveryCosts, out double[] capacityDemandsPerDepot) {
|
|---|
| 202 | var D = capacities.Length;
|
|---|
| 203 |
|
|---|
| 204 | capacityDemandsPerDepot = new double[D];
|
|---|
| 205 | totalOpeningCosts = 0.0;
|
|---|
| 206 | totalDeliveryCosts = 0.0;
|
|---|
| 207 |
|
|---|
| 208 | var customer = 0;
|
|---|
| 209 | foreach (var depot in customer2Depot) {
|
|---|
| 210 | if (capacityDemandsPerDepot[depot] == 0) totalOpeningCosts += openingCosts[depot];
|
|---|
| 211 | capacityDemandsPerDepot[depot] += demands[customer];
|
|---|
| 212 | totalDeliveryCosts += deliveryCosts[depot, customer];
|
|---|
| 213 | customer++;
|
|---|
| 214 | }
|
|---|
| 215 |
|
|---|
| 216 |
|
|---|
| 217 | var overbooking = capacityDemandsPerDepot.Zip(capacities, (a, b) => a > b ? a - b : 0).Sum();
|
|---|
| 218 | if (overbooking > 0) // infeasible
|
|---|
| 219 | return openingCosts.Sum() + deliveryCosts.Sum() + overbooking;
|
|---|
| 220 |
|
|---|
| 221 | return totalOpeningCosts + totalDeliveryCosts;
|
|---|
| 222 | }
|
|---|
| 223 |
|
|---|
| 224 | public override void Analyze(Individual[] individuals, double[] qualities, ResultCollection results, IRandom random) {
|
|---|
| 225 | var orderedIndividuals = individuals.Zip(qualities, (i, q) => new { Individual = i, Quality = q }).OrderBy(z => z.Quality);
|
|---|
| 226 | var best = Maximization ? orderedIndividuals.Last() : orderedIndividuals.First();
|
|---|
| 227 | var bestSol = best.Individual.IntegerVector(Encoding.Name);
|
|---|
| 228 |
|
|---|
| 229 | FacilityLocationSolution bestSoFar = null;
|
|---|
| 230 | IResult bestSoFarResult;
|
|---|
| 231 | results.TryGetValue("Best Solution", out bestSoFarResult);
|
|---|
| 232 | if (bestSoFarResult != null) bestSoFar = bestSoFarResult.Value as FacilityLocationSolution;
|
|---|
| 233 |
|
|---|
| 234 | if (bestSoFar == null || bestSoFar.FitnessValueParameter.Value.Value > best.Quality) {
|
|---|
| 235 |
|
|---|
| 236 | var openingCosts = OpeningCostsParameter.Value;
|
|---|
| 237 | var capacities = DepotCapacitiesParameter.Value;
|
|---|
| 238 | var demands = CustomerDemandsParameter.Value;
|
|---|
| 239 | var deliveryCosts = DeliveryCostsParameter.Value;
|
|---|
| 240 |
|
|---|
| 241 | double totalOpeningCosts, totalDeliveryCosts;
|
|---|
| 242 | double[] depotUsage;
|
|---|
| 243 |
|
|---|
| 244 | try {
|
|---|
| 245 | Evaluate(bestSol, openingCosts, capacities, demands, deliveryCosts, out totalOpeningCosts, out totalDeliveryCosts, out depotUsage);
|
|---|
| 246 | } catch (IndexOutOfRangeException) {
|
|---|
| 247 | throw new ArgumentException("The solution contains more customers than there are problem data for.");
|
|---|
| 248 | }
|
|---|
| 249 | var overbooking = depotUsage.Zip(capacities, (a, b) => a > b ? a - b : 0).Sum();
|
|---|
| 250 |
|
|---|
| 251 | if (bestSoFar == null) {
|
|---|
| 252 | bestSoFar = new FacilityLocationSolution() {
|
|---|
| 253 | OpeningCosts = (DoubleArray)openingCosts.Clone(),
|
|---|
| 254 | DepotCapacities = (DoubleArray)capacities.Clone(),
|
|---|
| 255 | CustomerDemands = (DoubleArray)demands.Clone(),
|
|---|
| 256 | DeliveryCosts = (DoubleMatrix)deliveryCosts.Clone(),
|
|---|
| 257 | CustomerToDepotAssignmentParameter = {Value = (IntegerVector)bestSol.Clone()},
|
|---|
| 258 | FitnessValueParameter = {Value = new DoubleValue(best.Quality)},
|
|---|
| 259 | TotalOpeningCostsParameter = {Value = new DoubleValue(totalOpeningCosts)},
|
|---|
| 260 | TotalDeliveryCostsParameter = {Value = new DoubleValue(totalDeliveryCosts)},
|
|---|
| 261 | TotalOverbookedCapacityParameter = {Value = new DoubleValue(overbooking)}
|
|---|
| 262 | };
|
|---|
| 263 | } else {
|
|---|
| 264 | bestSoFar.CustomerToDepotAssignmentParameter.Value = (IntegerVector)bestSol.Clone();
|
|---|
| 265 | bestSoFar.FitnessValueParameter.Value.Value = best.Quality;
|
|---|
| 266 | bestSoFar.TotalOpeningCostsParameter.Value.Value = totalOpeningCosts;
|
|---|
| 267 | bestSoFar.TotalDeliveryCostsParameter.Value.Value = totalDeliveryCosts;
|
|---|
| 268 | bestSoFar.TotalOverbookedCapacityParameter.Value.Value = overbooking;
|
|---|
| 269 | }
|
|---|
| 270 | }
|
|---|
| 271 |
|
|---|
| 272 | if (bestSoFarResult == null) {
|
|---|
| 273 | bestSoFarResult = new Result("Best Solution", bestSoFar);
|
|---|
| 274 | results.Add(bestSoFarResult);
|
|---|
| 275 | }
|
|---|
| 276 | }
|
|---|
| 277 | }
|
|---|
| 278 | }
|
|---|
