source: branches/DynamicVehicleRouting/HeuristicLab.PDPSimulation/3.3/Optimizers/LocalUpdate/BestInsertion.cs @ 8815

#region License Information
/* HeuristicLab
 * Copyright (C) 2002-2011 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
 *
 * This file is part of HeuristicLab.
 *
 * HeuristicLab is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * HeuristicLab is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
 */
#endregion

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using HeuristicLab.Core;
using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
using HeuristicLab.Common;
using HeuristicLab.PDPSimulation.DomainModel;
using System.Threading;
using HeuristicLab.Problems.VehicleRouting.Interfaces;
using HeuristicLab.Problems.VehicleRouting;
using HeuristicLab.Problems.VehicleRouting.Variants;
using HeuristicLab.Problems.VehicleRouting.ProblemInstances;
using HeuristicLab.PDPSimulation.Operators;
using HeuristicLab.Parameters;
using HeuristicLab.Data;
using System.Threading.Tasks;
using HeuristicLab.Problems.VehicleRouting.Encodings.Potvin;

namespace HeuristicLab.PDPSimulation {
  [Item("BestInsertion", "A best insertion local update optimization.")]
  [StorableClass]
  public class BestInsertion : DynamicPDPOptimization {    
    public BestInsertion(): base() {
    }
    [StorableConstructor]
    private BestInsertion(bool deserializing) : base(deserializing) {
    }
    private BestInsertion(BestInsertion original, Cloner cloner)
      : base(original, cloner) {
    }
    public override IDeepCloneable Clone(Cloner cloner) {
      return new BestInsertion(this, cloner);
    }

    public static void RouteUnrouted(IVRPProblemInstance instance, PotvinEncoding solution) {
      DynPDPProblemInstance pdp = instance as DynPDPProblemInstance;
      
      while (solution.Unrouted.Count > 0) {
        int city = solution.Unrouted[0];
        int dest = pdp.GetPickupDeliveryLocation(city);

        int source, target;
        if (instance.GetDemand(city) >= 0) {
          source = city;
          target = dest;
        } else {
          source = dest;
          target = city;
        }

        //consider creating new tours
        int tours = solution.Tours.Count;
        
        for (int i = tours; i < solution.VehicleAssignment.Length; i++) {
          Tour newTour = new Tour();
          solution.Tours.Add(newTour);
        }

        double minCosts = double.MaxValue;
        Tour insertTour = null;
        int sourceLocation = -1;
        int targetLocation = -1;  

        foreach (Tour tour in solution.Tours) {
          VRPEvaluation eval = instance.Evaluate(solution);

          for (int i = 0; i <= tour.Stops.Count; i++) {
            tour.Stops.Insert(i, source);
            VRPEvaluation tourEval = instance.Evaluate(solution);
            double sourceCosts = tourEval.Quality - eval.Quality;

            if (tour.Stops.Count == 1) {
              int vehicle = solution.VehicleAssignment[solution.Tours.IndexOf(tour)];
              if (!pdp.VehicleUsed[vehicle])
                sourceCosts += instance.FleetUsageFactor.Value;
            }


            if (source != target) {
              for (int j = i + 1; j <= tour.Stops.Count; j++) {
                bool feasible;
                double targetCosts = instance.GetInsertionCosts(tourEval, solution, target, solution.Tours.IndexOf(tour), j, out feasible);

                double costs = sourceCosts + targetCosts;
                if (costs < minCosts) {
                  minCosts = costs;
                  insertTour = tour;
                  sourceLocation = i;
                  targetLocation = j;
                }
              }
            } else {
              double costs = sourceCosts;
              if (costs < minCosts) {
                minCosts = costs;
                insertTour = tour;
                sourceLocation = i;
                targetLocation = -1;
              }
            }
            tour.Stops.Remove(source);
          }
        }

        insertTour.Stops.Insert(sourceLocation, source);
        if (source != target) {
          insertTour.Stops.Insert(targetLocation, target);
        }

        solution.Unrouted.Remove(source);
        if (source != target) {
          solution.Unrouted.Remove(target);
        }

        solution.Repair();
      }
    }

    protected override void PrepareInstance(DynamicPDProblemInstance instance, ChangeInformation changeInformation) {
      instance.StaticInstance.Vehicles.Value = changeInformation.CreatedVehicles.Count;
      instance.SetCurrentPlan(new PotvinEncoding(instance.StaticInstance));
      instance.InitializeInstance(changeInformation.CreatedVehicles, changeInformation.CreatedOrders);
    }

    protected override bool PerformOptimization(DynamicPDProblemInstance instance, ChangeInformation changeInformation) {
     PotvinEncoding solution = instance.Solutions.First();

     RouteUnrouted(instance.StaticInstance, solution);

     PerformPlan(solution);

     return true;
    }
  }
}