source: branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Manipulators/PotvinCustomerRelocationManipulator.cs @ 6753

#region License Information
/* HeuristicLab
 * Copyright (C) 2002-2010 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 HeuristicLab.Core;
using HeuristicLab.Encodings.PermutationEncoding;
using HeuristicLab.Parameters;
using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
using HeuristicLab.Data;
using System.Collections.Generic;
using HeuristicLab.Common;
using HeuristicLab.Problems.VehicleRouting.Variants;

namespace HeuristicLab.Problems.VehicleRouting.Encodings.Potvin {
  [Item("PotvinCustomerRelocationMainpulator", "A customer relocation operator")]
  [StorableClass]
  public sealed class PotvinCustomerRelocationMainpulator : PotvinManipulator, IPickupAndDeliveryOperator {
    [StorableConstructor]
    private PotvinCustomerRelocationMainpulator(bool deserializing) : base(deserializing) { }

    public PotvinCustomerRelocationMainpulator() : base() { }

    public override IDeepCloneable Clone(Cloner cloner) {
      return new PotvinCustomerRelocationMainpulator(this, cloner);
    }

    private PotvinCustomerRelocationMainpulator(PotvinCustomerRelocationMainpulator original, Cloner cloner)
      : base(original, cloner) {
    }

    protected override void Manipulate(IRandom random, PotvinEncoding individual) {
      bool allowInfeasible = AllowInfeasibleSolutions.Value.Value;
      bool performed = false;

      int selectedIndex;
      Tour route1;

      int mode = random.Next(0,3);

      //Try pickup and delivery first
      IPickupAndDeliveryProblemInstance pdp = ProblemInstance as IPickupAndDeliveryProblemInstance;
      if (pdp != null && mode == 0) {
        selectedIndex = SelectRandomTourBiasedByLength(random, individual);
        route1 =
          individual.Tours[selectedIndex];

        List<int> deliveryViolations = new List<int>();

        Dictionary<int, bool> visited = new Dictionary<int, bool>();
        for (int i = 0; i < route1.Stops.Count; i++) {
          int stop = route1.Stops[i];
          if (ProblemInstance.Demand[stop] < 0) {
            int source = pdp.PickupDeliveryLocation[stop];

            if (!visited.ContainsKey(source))
              deliveryViolations.Add(stop);
          }

          visited.Add(stop, true);
        }

        if (deliveryViolations.Count > 0) {
          int selected =
            deliveryViolations[random.Next(deliveryViolations.Count)];

          int source = pdp.PickupDeliveryLocation[selected];

          //find route of source
          Tour found = null;
          foreach (Tour tour in individual.Tours) {
            if (tour.Stops.Contains(source)) {
              found = tour;
              break;
            }
          }

          if (found != null) {
            double rand = random.NextDouble();
            if (rand < 0.33) {
              route1.Stops.Remove(selected);

              int index = individual.FindBestInsertionPlace(found, selected);
              found.Stops.Insert(index, selected);
              performed = true;

              if (route1.Stops.Count == 0)
                individual.Tours.Remove(route1);
            } else if (rand < 0.66) {
              found.Stops.Remove(source);

              int index = individual.FindBestInsertionPlace(route1, source);
              route1.Stops.Insert(index, source);
              performed = true;

              if (found.Stops.Count == 0)
                individual.Tours.Remove(found);
            } else {
              found.Stops.Remove(source);
              route1.Stops.Remove(selected);

              int chosenRoute = random.Next(individual.Tours.Count);
              Tour tour = individual.Tours[chosenRoute];

              int index = individual.FindBestInsertionPlace(tour, source);
              tour.Stops.Insert(index, source);
              index = individual.FindBestInsertionPlace(tour, selected);
              tour.Stops.Insert(index, selected);

              if (found.Stops.Count == 0)
                individual.Tours.Remove(found);
              if (route1.Stops.Count == 0)
                individual.Tours.Remove(route1);
            }
          }
        }
      }

      //then try tw
      if (!performed && mode == 1) {
        ITimeWindowedProblemInstance vrptw = ProblemInstance as ITimeWindowedProblemInstance;

        if (vrptw != null) {
          selectedIndex = SelectRandomTourBiasedByLength(random, individual);
          route1 =
            individual.Tours[selectedIndex];

          DoubleArray dueTime = vrptw.DueTime;
          DoubleArray readyTime = vrptw.ReadyTime;
          DoubleArray serviceTimes = vrptw.ServiceTime;

          List<int> timeWindowViolations = new List<int>();
          double time = 0;

          for (int i = 0; i < route1.Stops.Count; i++) {
            int start = 0;
            if (i > 0)
              start = route1.Stops[i - 1];
            int end = 0;
            if (i < route1.Stops.Count)
              end = route1.Stops[i];

            //drive there
            double currentDistace = vrptw.GetDistance(start, end);
            time += currentDistace;

            //check if it was serviced on time
            if (time > dueTime[end]) {
              timeWindowViolations.Add(end);
            }

            //wait
            double currentWaitingTime = 0.0;
            if (time < readyTime[end])
              currentWaitingTime = readyTime[end] - time;
            time += currentWaitingTime;

            //service
            double currentServiceTime = serviceTimes[end];
            time += currentServiceTime;
          }

          if (timeWindowViolations.Count > 0) {
            int selected =
              timeWindowViolations[random.Next(timeWindowViolations.Count)];

            int oldIndex = route1.Stops.IndexOf(selected);
            route1.Stops.Remove(selected);

            int route, place;
            if (FindInsertionPlace(individual, selected, selectedIndex, allowInfeasible, out route, out place)) {
              Tour newTour = individual.Tours[route];
              newTour.Stops.Insert(place, selected);
              performed = true;
            } else {
              route1.Stops.Insert(oldIndex, selected);
            }

            if (route1.Stops.Count == 0)
              individual.Tours.Remove(route1);
          }
        }
      }

      //finally relocate random customer
      if (!performed) {
        selectedIndex = SelectRandomTourBiasedByLength(random, individual);
        route1 =
          individual.Tours[selectedIndex];

        int selected = route1.Stops[random.Next(route1.Stops.Count)];
        int oldIndex = route1.Stops.IndexOf(selected);
        route1.Stops.Remove(selected);

        int route, place;
        if (FindInsertionPlace(individual, selected, selectedIndex, allowInfeasible, out route, out place)) {
          Tour tour = individual.Tours[route];
          tour.Stops.Insert(place, selected);
          performed = true;
        } else {
          route1.Stops.Insert(oldIndex, selected);
        }

        if (route1.Stops.Count == 0)
          individual.Tours.Remove(route1);
      }
    }
  }
}