source: branches/DynamicVehicleRouting/HeuristicLab.PDPSimulation/3.3/Optimizers/DynamicPDProblemInstance.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.Problems.VehicleRouting.ProblemInstances;
using HeuristicLab.Problems.VehicleRouting.Interfaces;
using HeuristicLab.PDPSimulation.DomainModel;
using HeuristicLab.Data;
using HeuristicLab.PDPSimulation.Operators;
using HeuristicLab.Problems.VehicleRouting.Encodings.Potvin;
using HeuristicLab.Problems.VehicleRouting;
using HeuristicLab.PDPSimulation.DistanceMeasures;
using HeuristicLab.Optimization;

namespace HeuristicLab.PDPSimulation {
  [Item("DynamicPDProblemInstance", "A dynamic PD instance.")]
  [StorableClass]
  public class DynamicPDProblemInstance: Item {
    [Storable]
    private List<DynPDPProblemInstance> instances;

    [Storable]
    private HashSet<PotvinEncoding> solutions;

    [Storable]
    private List<Item> tabuAttributes;

    [Storable]
    private Dictionary<int, Guid> vehicleAssignment;

    [Storable]
    private Dictionary<int, Guid> orderAssignment;

    [Storable]
    private double timeDelta;

    [Storable]
    private bool initialized;

    public bool Initialized {
      get { return initialized; }
    }

    public List<IVRPProblemInstance> StaticInstances {
      get {
        List<IVRPProblemInstance> result = new List<IVRPProblemInstance>();

        foreach (DynPDPProblemInstance instance in instances)
          result.Add(instance);

        return result;
      }
    }

    public IVRPProblemInstance StaticInstance {
      get {
        return instances[0];
      }
    }

    public HashSet<PotvinEncoding> Solutions {
      get { return solutions;  }
    }

    public List<Item> TabuAttributes {
      get { return tabuAttributes; }
    }

    public void SetInstanceCount(int count) {
      if (count > 0) {
        if (instances.Count > count)
          instances.RemoveRange(0, instances.Count - count);
        else
          while(instances.Count < count)
            instances.Add(instances[0].ShallowClone());
      }
    }

    public DynamicPDProblemInstance(PickupDeliveryScenario scenario, ResultCollection results): base() {
      vehicleAssignment = new Dictionary<int, Guid>();
      orderAssignment = new Dictionary<int, Guid>();
      solutions = new HashSet<PotvinEncoding>();
      tabuAttributes = new List<Item>();
      timeDelta = 0;
      initialized = false;

      instances = new List<DynPDPProblemInstance>();
      instances.Add(new DynPDPProblemInstance(scenario, results));
    }

    [StorableConstructor]
    private DynamicPDProblemInstance(bool deserializing) : base(deserializing) {
    }
    private DynamicPDProblemInstance(DynamicPDProblemInstance original, Cloner cloner)
      : base(original, cloner) {
      instances = new List<DynPDPProblemInstance>();
      foreach (DynPDPProblemInstance instance in original.instances)
        instances.Add(cloner.Clone<DynPDPProblemInstance>(instance));

      vehicleAssignment = new Dictionary<int, Guid>();
      foreach (int key in original.vehicleAssignment.Keys)
        vehicleAssignment.Add(key, original.vehicleAssignment[key]);

      orderAssignment = new Dictionary<int, Guid>();
      foreach (int key in original.orderAssignment.Keys)
        orderAssignment.Add(key, original.orderAssignment[key]);

      solutions = new HashSet<PotvinEncoding>();
      foreach (PotvinEncoding solution in original.solutions)
        solutions.Add(cloner.Clone<PotvinEncoding>(solution));
      
      tabuAttributes = new List<Item>();
      foreach (Item tabuAttribute in original.tabuAttributes)
        tabuAttributes.Add(cloner.Clone<Item>(tabuAttribute));

      timeDelta = original.timeDelta;
      initialized = original.initialized;
    }
    public override IDeepCloneable Clone(Cloner cloner) {
      return new DynamicPDProblemInstance(this, cloner);
    }

    public void SetCurrentPlan(PotvinEncoding plan) {
      foreach (DynPDPProblemInstance instance in instances) {
        if (instance.CurrentPlan != null)
          solutions.Remove(instance.CurrentPlan);

        instance.CurrentPlan = PotvinEncoding.ConvertFrom(plan, instance);
        solutions.Add(instance.CurrentPlan);
      }
    }

    public Guid GetOrder(int stop) {
      return orderAssignment[stop - 1];
    }

    public List<int> GetStops(Guid order) {
      return (from a in orderAssignment where a.Value == order select a.Key).OrderBy(s => s).ToList();
    }

    public Guid GetVehicle(int index) {
      return vehicleAssignment[index];
    }

    public void UpdateTime(double delta) {
      foreach (DynPDPProblemInstance instance in instances) {
        for (int i = 0; i < instance.DueTime.Length; i++) {
          instance.DueTime[i] = Math.Max(0, instance.DueTime[i] - delta);
          instance.ReadyTime[i] = Math.Max(0, instance.ReadyTime[i] - delta);
        }
      }

      timeDelta += delta;
    }

    public void AddVehicle(Vehicle vehicle) {
      throw new NotImplementedException();
    }

    private void AddOrder(DynPDPProblemInstance instance, Order order, ref int customerIdx, ref int depotIdx) {
      orderAssignment[customerIdx] = order.Id;

      instance.Demand[customerIdx] = order.Demand;
      instance.PickupDeliveryLocation[customerIdx] = customerIdx + (order.ServiceRequest ? 1 : 2);
      instance.ServiceTime[customerIdx] = order.PickupServiceTime;
      instance.ReadyTime[customerIdx + depotIdx] = Math.Max(0, order.PickupReadyTime - timeDelta);
      instance.DueTime[customerIdx + depotIdx] = Math.Max(0, order.PickupDueTime - timeDelta);
      instance.Coordinates[customerIdx + depotIdx, 0] = order.PickupXCoord;
      instance.Coordinates[customerIdx + depotIdx, 1] = order.PickupYCoord;
      customerIdx++;

      if (!order.ServiceRequest) {
        orderAssignment[customerIdx] = order.Id;

        instance.Demand[customerIdx] = -order.Demand;
        instance.PickupDeliveryLocation[customerIdx] = customerIdx;
        instance.ServiceTime[customerIdx] = order.DeliveryServiceTime;
        instance.ReadyTime[customerIdx + depotIdx] = Math.Max(0, order.DeliveryReadyTime - timeDelta);
        instance.DueTime[customerIdx + depotIdx] = Math.Max(0, order.DeliveryDueTime - timeDelta);
        instance.Coordinates[customerIdx + depotIdx, 0] = order.DeliveryXCoord;
        instance.Coordinates[customerIdx + depotIdx, 1] = order.DeliveryYCoord;
        customerIdx++;
      }

      foreach (PotvinEncoding solution in solutions) {
        if (!order.ServiceRequest && !solution.Unrouted.Contains(customerIdx - 1))
          solution.Unrouted.Add(customerIdx - 1);

        if (!solution.Unrouted.Contains(customerIdx))
          solution.Unrouted.Add(customerIdx);
      }
    }

    public void AddOrder(Order order) {
      foreach (DynPDPProblemInstance instance in instances) {
        int customerIdx = instance.Demand.Length;
        int depotIdx = instance.Vehicles.Value;

        int added = order.ServiceRequest ? 1 : 2;
        (instance.Coordinates as IStringConvertibleMatrix).Rows += added;
        (instance.ReadyTime as IStringConvertibleArray).Length += added;
        (instance.DueTime as IStringConvertibleArray).Length += added;
        (instance.Demand as IStringConvertibleArray).Length += added;
        (instance.ServiceTime as IStringConvertibleArray).Length += added;
        (instance.PickupDeliveryLocation as IStringConvertibleArray).Length += added;

        AddOrder(instance, order, ref customerIdx, ref depotIdx);

        instance.ResetDistanceMatrix();
      }
    }

    public void UpdateVehicle(Vehicle vehicle, bool diversionAllowed) {
      bool last = false;
      for (int i = 0; i < instances.Count; i++) {
        DynPDPProblemInstance instance = instances[i];
        last = (i == instances.Count - 1);
        int vehicleIdx = vehicleAssignment.First(kvp => kvp.Value == vehicle.Id).Key;

        if (!diversionAllowed && vehicle.VehicleState == VehicleState.Moving)
          instance.VehicleStates[vehicleIdx] = VehicleState.Waiting;
        else
          instance.VehicleStates[vehicleIdx] = vehicle.VehicleState;

        if (diversionAllowed) {
          instance.Coordinates[vehicleIdx, 0] = vehicle.PositionX;
          instance.Coordinates[vehicleIdx, 1] = vehicle.PositionY;

          instance.Capacity[vehicleIdx] = vehicle.Capacity;

          instance.ResetDistanceMatrix();
          if (vehicle.Distance > 0)
            instance.VehicleUsed[vehicleIdx] = true;
        } else {
          var found = orderAssignment.Where(kvp => kvp.Value == vehicle.CurrentOrder).ToList();
          if (found.Count() > 0) {
            instance.Coordinates[vehicleIdx, 0] = vehicle.TargetPositionX;
            instance.Coordinates[vehicleIdx, 1] = vehicle.TargetPositionY;

            int target = -1, source = -1;
            if (found.Count == 2 &&
               (vehicle.CurrentAction == VehicleAction.Pickup || vehicle.CurrentAction == VehicleAction.Deliver)) {
              if (instance.Demand[found[0].Key] >= 0) {
                source = found[0].Key;
                target = found[1].Key;
              } else {
                target = found[0].Key;
                source = found[1].Key;
              }

              int vehicleId = vehicleAssignment.First(
               kvp => kvp.Value == vehicle.Id).Key;
              instance.PickupDeliveryLocation[target] = -vehicleId;
            } else if (found.Count == 1 &&
              (vehicle.CurrentAction == VehicleAction.Deliver)) {
              source = found[0].Key;
            }

            if (source >= 0) {
              if(last)
                RemoveCustomer(source, vehicleIdx, diversionAllowed);
              instance.ResetDistanceMatrix();
            }

            instance.VehicleUsed[vehicleIdx] = true;
          }
        }

        instance.ReadyTime[vehicleIdx] = Math.Max(0, vehicle.ReadyTime - timeDelta);
        vehicleAssignment[vehicleIdx] = vehicle.Id;
      }
    }

    private void RemoveCustomer(int customer, int vehicle, bool diversionAllowed) {
      foreach (DynPDPProblemInstance instance in instances) {
        if (!diversionAllowed) {
          instance.Capacity[vehicle] -= instance.Demand[customer];
        }

        int customers = instance.Cities.Value;
        int depots = instance.Vehicles.Value;

        for (int i = customer; i < customers - 1; i++) {
          instance.Demand[i] = instance.Demand[i + 1];
          instance.ServiceTime[i] = instance.ServiceTime[i + 1];
          instance.PickupDeliveryLocation[i] = instance.PickupDeliveryLocation[i + 1];

          int index = i + depots;
          instance.ReadyTime[index] = instance.ReadyTime[index + 1];
          instance.DueTime[index] = instance.DueTime[index + 1];
          instance.Coordinates[index, 0] = instance.Coordinates[index + 1, 0];
          instance.Coordinates[index, 1] = instance.Coordinates[index + 1, 1];
        }

        for (int i = 0; i < customers; i++) {
          if (instance.PickupDeliveryLocation[i] > customer)
            instance.PickupDeliveryLocation[i] -= 1;
        }

        (instance.Coordinates as IStringConvertibleMatrix).Rows -= 1;
        (instance.ReadyTime as IStringConvertibleArray).Length -= 1;
        (instance.DueTime as IStringConvertibleArray).Length -= 1;
        (instance.Demand as IStringConvertibleArray).Length -= 1;
        (instance.ServiceTime as IStringConvertibleArray).Length -= 1;
        (instance.PickupDeliveryLocation as IStringConvertibleArray).Length -= 1;
      }

      foreach (PotvinEncoding solution in solutions) {
        int i;
        foreach (Tour tour in solution.Tours) {
          i = 0;
          while (i < tour.Stops.Count) {
            if (tour.Stops[i] > (customer + 1)) {
              tour.Stops[i] = tour.Stops[i] - 1;
              i++;
            } else if (tour.Stops[i] < (customer + 1)) {
              i++;
            } else {
              tour.Stops.RemoveAt(i);
            }
          }
        }

        solution.Repair();

        i = 0;
        while (i < solution.Unrouted.Count) {
          if (solution.Unrouted[i] > (customer + 1)) {
            solution.Unrouted[i] = solution.Unrouted[i] - 1;
            i++;
          } else if (solution.Unrouted[i] < (customer + 1)) {
            i++;
          } else {
            solution.Unrouted.RemoveAt(i);
          }
        }
      }

      int j = 0;
      while (j < tabuAttributes.Count) {
        if (tabuAttributes[j] is DynPotvinPDRelocateMoveAttribute) {
          DynPotvinPDRelocateMoveAttribute attr =
            tabuAttributes[j] as DynPotvinPDRelocateMoveAttribute;

          if (attr.City > (customer + 1)) {
            attr.City = attr.City - 1;
            j++;
          } else if (attr.City < (customer + 1)) {
            j++;
          } else {
            attr.City = -1;
            j++;
          }
        } else {
          j++;
        }
      }

      Dictionary<int, Guid> newOrderAssignment = new Dictionary<int, Guid>();
      foreach (int assigned in orderAssignment.Keys) {
        if (assigned > customer)
          newOrderAssignment[assigned - 1] = orderAssignment[assigned];
        else if (assigned != customer)
          newOrderAssignment[assigned] = orderAssignment[assigned];
      }
      orderAssignment = newOrderAssignment;
    }

    public void UpdateOrder(Order order, bool diversionAllowed) {
      bool last = false;
      for(int i = 0; i < instances.Count; i++) {
        DynPDPProblemInstance instance = instances[i];
        last = (i == instances.Count - 1);
        var customers = orderAssignment.Where(
          kvp => kvp.Value == order.Id).ToList();
        int depots = instance.Vehicles.Value;
        int vehicle = vehicleAssignment.First(
              kvp => kvp.Value == order.Vehicle).Key;

        int source = -1;
        int target = -1;

        if (order.OrderState == OrderState.PickingUp || order.OrderState == OrderState.PickedUp) {
          if (!order.ServiceRequest && customers.Count == 2) {
            if (instance.Demand[customers[0].Key] >= 0) {
              source = customers[0].Key;
              target = customers[1].Key;
            } else {
              source = customers[1].Key;
              target = customers[0].Key;
            }

            instance.PickupDeliveryLocation[target] = -vehicle;
            if (last)
              RemoveCustomer(source, vehicle, diversionAllowed);
            instance.ResetDistanceMatrix();
          } else if (order.ServiceRequest && customers.Count == 1) {
            target = customers[0].Key;

            if (last)
              RemoveCustomer(target, vehicle, diversionAllowed);
            instance.ResetDistanceMatrix();
          }
        } else if (order.OrderState == OrderState.Delivering || order.OrderState == OrderState.Delivered) {
          if (customers.Count == 1) {
            target = customers[0].Key;

            if (last)
              RemoveCustomer(target, vehicle, diversionAllowed);
            instance.ResetDistanceMatrix();
          } else if (customers.Count == 2) {
            if (instance.Demand[customers[0].Key] >= 0) {
              source = customers[0].Key;
              target = customers[1].Key;
            } else {
              source = customers[1].Key;
              target = customers[0].Key;
            }

            if (last)
              RemoveCustomer(source, vehicle, diversionAllowed);
            if (last)
              RemoveCustomer(target - 1, vehicle, diversionAllowed);
            instance.ResetDistanceMatrix();
          }
        }
      }
    }

    public void InitializeInstance(List<Vehicle> vehicles, List<Order> orders) {
      if (vehicles.Count > 0) {
        foreach (DynPDPProblemInstance instance in instances) {
          timeDelta = 0;

          instance.Coordinates = new DoubleMatrix(vehicles.Count + orders.Count * 2, 2);
          instance.DepotCoordinates = new DoubleMatrix(vehicles.Count, 2);
          instance.ReadyTime = new DoubleArray(vehicles.Count + orders.Count * 2);
          instance.DueTime = new DoubleArray(vehicles.Count + orders.Count * 2);

          instance.Capacity = new DoubleArray(vehicles.Count);
          instance.VehicleDepotAssignment = new IntArray(vehicles.Count);
          instance.VehicleUsed = new BoolArray(vehicles.Count);
          instance.VehicleStates.Clear();
          for (int i = 0; i < vehicles.Count; i++) {
            instance.VehicleStates.Add(VehicleState.Parked);
          }

          int depotIdx = 0;
          int vehicleIdx = 0;
          foreach (Vehicle vehicle in vehicles) {
            vehicleAssignment[vehicleIdx] = vehicle.Id;

            instance.Coordinates[depotIdx, 0] = vehicle.DepotX;
            instance.Coordinates[depotIdx, 1] = vehicle.DepotY;
            instance.DepotCoordinates[depotIdx, 0] = vehicle.DepotX;
            instance.DepotCoordinates[depotIdx, 1] = vehicle.DepotY;

            instance.ReadyTime[vehicleIdx] = 0;
            instance.DueTime[vehicleIdx] = vehicle.DueTime;

            instance.Capacity[vehicleIdx] = vehicle.Capacity;
            instance.VehicleDepotAssignment[vehicleIdx] = depotIdx;

            depotIdx++;
            vehicleIdx++;
          }

          instance.Depots.Value = depotIdx;
          instance.Vehicles.Value = vehicleIdx;

          foreach (PotvinEncoding solution in solutions) {
            (solution.VehicleAssignment as IStringConvertibleArray).Length = instance.Vehicles.Value;
          }

          instance.Demand = new DoubleArray(orders.Count * 2);
          instance.ServiceTime = new DoubleArray(orders.Count * 2);
          instance.PickupDeliveryLocation = new IntArray(orders.Count * 2);

          int customerIdx = 0;
          foreach (Order order in orders) {
            AddOrder(instance, order, ref customerIdx, ref depotIdx);
          }

          if (customerIdx != orders.Count * 2) {
            (instance.Coordinates as IStringConvertibleMatrix).Rows = vehicles.Count + customerIdx;
            (instance.ReadyTime as IStringConvertibleArray).Length = vehicles.Count + customerIdx;
            (instance.DueTime as IStringConvertibleArray).Length = vehicles.Count + customerIdx;
            (instance.Demand as IStringConvertibleArray).Length = customerIdx;
            (instance.ServiceTime as IStringConvertibleArray).Length = customerIdx;
            (instance.PickupDeliveryLocation as IStringConvertibleArray).Length = customerIdx;
          }

          instance.ResetDistanceMatrix();
          instance.Initialize();
        }
        initialized = true;
      }
    }
  }
}