source: branches/DynamicVehicleRouting/HeuristicLab.PDPSimulation/3.3/Optimizers/DynamicPDPOptimization.cs @ 8670

#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.PDPSimulation.DistanceMeasures;
using HeuristicLab.Problems.VehicleRouting.Encodings.Potvin;

namespace HeuristicLab.PDPSimulation {
  [StorableClass]
  public abstract class DynamicPDPOptimization : PickupDeliveryOptimization {
    public ValueParameter<BoolValue> OnlyOptimizedIfRequiredParameter {
      get { return (ValueParameter<BoolValue>)Parameters["OnlyOptimizedIfRequired"]; }
    }

    public DynamicPDPOptimization(): base() {
      optimizationFinshed = true;
      Parameters.Add(new ValueParameter<BoolValue>("OnlyOptimizedIfRequired", "Only optimize if new information is revealed.", new BoolValue(true)));
    }
    [StorableConstructor]
    protected DynamicPDPOptimization(bool deserializing) : base(deserializing) {
    }
    protected DynamicPDPOptimization(DynamicPDPOptimization original, Cloner cloner)
      : base(original, cloner) {
        instance = cloner.Clone<DynamicPDProblemInstance>(original.instance);
        lastUpdateTime = original.lastUpdateTime;
        optimizationFinshed = original.optimizationFinshed;
    }

    [Storable]
    private DynamicPDProblemInstance instance;

    protected DynamicPDProblemInstance Instance {
      get { return instance; }
    }

    [Storable]
    private double lastUpdateTime;

    [Storable]
    private bool optimizationFinshed;

    public override void SetScenario(PickupDeliveryScenario scenario) {
      base.SetScenario(scenario);
      instance = new DynamicPDProblemInstance(scenario, GetResults());
    }

    public override void SetWaitingStrategy(WaitingStrategy waitingStrategy) {
      base.SetWaitingStrategy(waitingStrategy);
      if (instance != null) {
        foreach (IVRPProblemInstance staticInstance in instance.StaticInstances)
          (staticInstance as DynPDPProblemInstance).WaitingStrategy = waitingStrategy;
      }
    }

    public override void Prepare() {
      lastUpdateTime = 0;
      optimizationFinshed = true;
      instance = new DynamicPDProblemInstance(scenario, GetResults());
      foreach (IVRPProblemInstance staticInstance in instance.StaticInstances)
        (staticInstance as DynPDPProblemInstance).WaitingStrategy = waitingStrategy;
      base.Prepare();
    }

    protected virtual void PrepareInstance(DynamicPDProblemInstance instance, ChangeInformation changeInformation) {
      instance.InitializeInstance(changeInformation.CreatedVehicles, changeInformation.CreatedOrders);
    }

    protected virtual void PerformPlan(IVRPEncoding solution) {
      lock (actionLocker) {
        instance.SetCurrentPlan(PotvinEncoding.ConvertFrom(solution, instance.StaticInstance));
        DynPDPEvaluation eval = instance.StaticInstance.Evaluate(solution) as DynPDPEvaluation;

        List<int> vehicles = new List<int>();
        for (int i = 0; i < instance.StaticInstance.Vehicles.Value; i++)
          vehicles.Add(i);

        int tourIdx = 0;
        foreach (Tour tour in solution.GetTours()) {
          List<double> waitingTimes = DynPDPEvaluator.GetWaitingTimes(instance.StaticInstance as DynPDPProblemInstance, tour, solution);

          int vehicleIdx = solution.GetVehicleAssignment(
            solution.GetTourIndex(tour));
          vehicles.Remove(vehicleIdx);
          Guid vehicleId = instance.GetVehicle(vehicleIdx);
          Vehicle vehicle = GetVehicle(vehicleId);

          int stopIdx = 0;
          foreach (int stop in tour.Stops) {
            double coordX = instance.StaticInstance.GetCoordinates(stop)[0];
            double coordY = instance.StaticInstance.GetCoordinates(stop)[1];
            VehicleAction vehicleAction;

            Guid orderId = instance.GetOrder(stop);
            Order order = GetOrder(orderId);
            order.AssignedVehicle = vehicleId;

            if (instance.StaticInstance.GetDemand(stop) >= 0) {
              vehicleAction = VehicleAction.Pickup;
            } else {
              vehicleAction = VehicleAction.Deliver;
            }

            if (instance.StaticInstance.GetDemand(stop) != 0) {
              double waitingTime = waitingTimes[stopIdx];

              PDAction action = new WaitAction(vehicleId, waitingTime);
              if (stopIdx == 0) {
                SetAction(action);
              } else {
                AppendAction(action);
              }

              action = new MoveVehicleAction(
                vehicleId,
                coordX,
                coordY,
                vehicleAction,
                order, 
                scenario.AllowDiversion, 
                scenario.DistanceMeasure);

              AppendAction(action);                            
            }

            stopIdx++;
          }

          tourIdx++;
        }

        foreach (int vehicleIdx in vehicles) {
          Guid vehicleId = instance.GetVehicle(vehicleIdx);
          Vehicle vehicle = GetVehicle(vehicleId);

          double posX, posY;
          lock (vehicle) {
            if (!scenario.AllowDiversion) {
              posX = vehicle.TargetPositionX;
              posY = vehicle.TargetPositionY;
            } else {
              posX = vehicle.PositionX;
              posY = vehicle.PositionY;
            }
          }

          SetAction(new WaitAction(vehicleId, 0));
        }
      }
    }

    private void UpdateInstance(ChangeInformation changeInformation) {
      if (!instance.Initialized) {
        PrepareInstance(instance, changeInformation);
      } else {
        foreach (Vehicle vehicle in changeInformation.CreatedVehicles) {
          lock (vehicle) {
            instance.AddVehicle(vehicle);
          }
        }

        foreach (Order order in changeInformation.CreatedOrders)
          instance.AddOrder(order);

        foreach (Vehicle vehicle in changeInformation.ChangedVehicles) {
          lock (vehicle) {
            instance.UpdateVehicle(vehicle, scenario.AllowDiversion);
          }
        }

        foreach (Order order in changeInformation.ChangedOrders)
          instance.UpdateOrder(order, scenario.AllowDiversion);
      }

      double time = GetSimulationTime();
      double delta = time - lastUpdateTime;
      lastUpdateTime = time;

      instance.UpdateTime(delta);
    }

    protected virtual void BeginInstanceUpdate(DynamicPDProblemInstance instance) {
    }

    protected virtual void EndInstanceUpdate(DynamicPDProblemInstance instance) {
    }

    protected virtual bool OptimizationRequired(ChangeInformation changeInformation) {
      return (!OnlyOptimizedIfRequiredParameter.Value.Value && Instance.StaticInstance != null && Instance.StaticInstance.Cities.Value > 0) || 
        changeInformation.CreatedOrders.Count > 0 || changeInformation.InvalidActions;
    }

    protected virtual void StartOptimization() {
    }

    protected virtual void EndOptimization() {
      SignalWaitHandle();
    }

    protected abstract bool PerformOptimization(DynamicPDProblemInstance instance, ChangeInformation changeInformation);

    protected object myLock = new object();

    public override bool OptimizationRequired() {
      lock (myLock) {
        if (optimizationFinshed) {
          bool optimize = OptimizationRequired(GetChangeInformation(GetChanges(false)));
          if(optimize)
            optimizationFinshed = false;
          
          return optimize;
        } else {
          return true;
        }
      }
    }

    private void RelocateToDepot(Guid vehicleId, double simulationTime, bool finish) {
      Vehicle vehicle = GetVehicle(vehicleId);
      double posX, posY;
      lock (vehicle) {
        posX = vehicle.TargetPositionX;
        posY = vehicle.TargetPositionY;
      }

      bool moveToDepot = finish;
      if (!finish) {
        double length = scenario.DistanceMeasure.GetDistance(posX, posY, vehicle.DepotX, vehicle.DepotY);

        moveToDepot = (simulationTime + length >= vehicle.DueTime);
      }

      if (moveToDepot) {
        bool moved = false;
        PDAction action = GetAction(vehicle);
        while (action != null && action.Successor != null) {
          action = action.Successor;
        }

        moved = action != null && action is MoveVehicleAction &&
          (action as MoveVehicleAction).TargetX == vehicle.DepotX &&
          (action as MoveVehicleAction).TargetY == vehicle.DepotY;

        if (!moved)
          AppendAction(new MoveVehicleAction(vehicleId, vehicle.DepotX, vehicle.DepotY, VehicleAction.Park, null,
                scenario.AllowDiversion, scenario.DistanceMeasure));
      }
    }

    protected virtual void RelocateVehicles(double simulationTime, bool finish) {
      lock (actionLocker) {
        for (int i = 0; i < instance.StaticInstance.Vehicles.Value; i++) {
          Guid vehicleId = instance.GetVehicle(i);
          RelocateToDepot(vehicleId, simulationTime, finish);
        }
      }
    }

    public override void RelocateVehicles() {
      if (scenario.RelocateBackToDepot) {
        double simulationTime = GetSimulationTime() + GetTimeStep();
        RelocateVehicles(simulationTime, false);
      }
    }

    int index = 0;
    protected override void Optimize(CancellationToken token) {
      bool finish = false;
      bool optimize = false;
      bool simulationFinished = false;

      ChangeInformation changeInformation;

      StartOptimization();

      while (!token.IsCancellationRequested && !finish) {
        WaitForSimulation();
        lock (myLock) {
          List<PDChange> changes = GetChanges(true);
          changeInformation = GetChangeInformation(changes);

          BeginInstanceUpdate(instance);
          UpdateInstance(changeInformation);          
          EndInstanceUpdate(instance);

          optimize = OptimizationRequired(changeInformation);
          optimizationFinshed = !optimize;
        }

        double simulationTime = GetSimulationTime();

        if (changeInformation.SimulationFinished)
          simulationFinished = true;

        if (optimize) {
          optimizationFinshed = PerformOptimization(instance, changeInformation);

          /*VehicleRoutingProblem problem = new VehicleRoutingProblem();
            problem.ProblemInstance = instance.StaticInstance;
            index++;
            HeuristicLab.Persistence.Default.Xml.XmlGenerator.Serialize(problem, @"C:\Users\svonolfen\Desktop\tests\i_" + index + ".hl");*/
        }
        
        finish = simulationFinished && optimizationFinshed;

        if(scenario.RelocateBackToDepot)
          RelocateVehicles(simulationTime + GetTimeStep(), finish);

        if (finish)
          running = false;
        else
          SignalWaitHandle();
      }

      EndOptimization();
    }
  }
}