cscvrptw.cs

// Copyright 2010-2018 Google LLC
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

using System;
using System.Collections.Generic;
using Google.OrTools.ConstraintSolver;

/// <summary>
///   Sample showing how to model and solve a capacitated vehicle routing
///   problem with time windows using the swig-wrapped version of the vehicle
///   routing library in src/constraint_solver.
/// </summary>
public class CapacitatedVehicleRoutingProblemWithTimeWindows {

  /// <summary>
  ///   A position on the map with (x, y) coordinates.
  /// </summary>
  class Position {
    public Position() {
      this.x_ = 0;
      this.y_ = 0;
    }

    public Position(int x, int y) {
      this.x_ = x;
      this.y_ = y;
    }

    public int x_;
    public int y_;
  }

  /// <summary>
  ///    A time window with start/end data.
  /// </summary>
  class TimeWindow {
    public TimeWindow() {
      this.start_ = -1;
      this.end_ = -1;
    }

    public TimeWindow(int start, int end) {
      this.start_ = start;
      this.end_ = end;
    }

    public int start_;
    public int end_;
  }

  /// <summary>
  /// Manhattan distance implemented as a callback. It uses an array of
  ///   positions and computes the Manhattan distance between the two
  ///   positions of two different indices.
  /// </summary>
  class Manhattan {
    public Manhattan(
        RoutingIndexManager manager,
        Position[] locations,
        int coefficient) {
      this.manager_ = manager;
      this.locations_ = locations;
      this.coefficient_ = coefficient;
    }

    public long Call(long first_index, long second_index) {
      if (first_index >= locations_.Length ||
          second_index >= locations_.Length) {
        return 0;
      }
      int first_node = manager_.IndexToNode(first_index);
      int second_node = manager_.IndexToNode(second_index);
      return (Math.Abs(locations_[first_node].x_ -
                       locations_[second_node].x_) +
              Math.Abs(locations_[first_node].y_ -
                       locations_[second_node].y_)) * coefficient_;
    }

    private readonly RoutingIndexManager manager_;
    private readonly Position[] locations_;
    private readonly int coefficient_;
  };

  /// <summary>
  ///   A callback that computes the volume of a demand stored in an
  ///   integer array.
  /// </summary>
  class Demand {
    public Demand(
        RoutingIndexManager manager,
        int[] order_demands) {
      this.manager_ = manager;
      this.order_demands_ = order_demands;
    }

    public long Call(long index) {
      if (index < order_demands_.Length) {
        int node = manager_.IndexToNode(index);
        return order_demands_[node];
      }
      return 0;
    }

    private readonly RoutingIndexManager manager_;
    private readonly int[] order_demands_;
  };

  /// Locations representing either an order location or a vehicle route
  /// start/end.
  private Position[] locations_;
  /// Quantity to be picked up for each order.
  private int[] order_demands_;
  /// Time window in which each order must be performed.
  private TimeWindow[] order_time_windows_;
  /// Penalty cost "paid" for dropping an order.
  private int[] order_penalties_;
  /// Capacity of the vehicles.
  private int vehicle_capacity_ = 0;
  /// Latest time at which each vehicle must end its tour.
  private int[] vehicle_end_time_;
  /// Cost per unit of distance of each vehicle.
  private int[] vehicle_cost_coefficients_;
  /// Vehicle start and end indices. They have to be implemented as int[] due
  /// to the available SWIG-ed interface.
  private int[] vehicle_starts_;
  private int[] vehicle_ends_;

  /// Random number generator to produce data.
  private Random random_generator = new Random(0xBEEF);

  /// <summary>
  ///    Constructs a capacitated vehicle routing problem with time windows.
  /// </summary>
  private CapacitatedVehicleRoutingProblemWithTimeWindows() {}

  /// <summary>
  ///   Creates order data. Location of the order is random, as well
  ///   as its demand (quantity), time window and penalty.  ///
  ///   </summary>
  /// <param name="number_of_orders"> number of orders to build. </param>
  /// <param name="x_max"> maximum x coordinate in which orders are located.
  /// </param>
  /// <param name="y_max"> maximum y coordinate in which orders are located.
  /// </param>
  /// <param name="demand_max"> maximum quantity of a demand. </param>
  /// <param name="time_window_max"> maximum starting time of the order time
  /// window. </param>
  /// <param name="time_window_width"> duration of the order time window.
  /// </param>
  /// <param name="penalty_min"> minimum pernalty cost if order is dropped.
  /// </param>
  /// <param name="penalty_max"> maximum pernalty cost if order is dropped.
  /// </param>
  private void BuildOrders(int number_of_orders,
                           int number_of_vehicles,
                           int x_max, int y_max,
                           int demand_max,
                           int time_window_max,
                           int time_window_width,
                           int penalty_min,
                           int penalty_max) {
    Console.WriteLine("Building orders.");
    locations_ = new Position[number_of_orders + 2 * number_of_vehicles];
    order_demands_ = new int[number_of_orders];
    order_time_windows_ = new TimeWindow[number_of_orders];
    order_penalties_ = new int[number_of_orders];
    for (int order = 0; order < number_of_orders; ++order) {
      locations_[order] =
          new Position(random_generator.Next(x_max + 1),
                       random_generator.Next(y_max + 1));
      order_demands_[order] = random_generator.Next(demand_max + 1);
      int time_window_start = random_generator.Next(time_window_max + 1);
      order_time_windows_[order] =
          new TimeWindow(time_window_start,
                         time_window_start + time_window_width);
      order_penalties_[order] =
          random_generator.Next(penalty_max - penalty_min + 1) + penalty_min;
    }
  }

  /// <summary>
  /// Creates fleet data. Vehicle starting and ending locations are
  /// random, as well as vehicle costs per distance unit.
  /// </summary>
  ///
  /// <param name="number_of_orders"> number of orders</param>
  /// <param name="number_of_vehicles"> number of vehicles</param>
  /// <param name="x_max"> maximum x coordinate in which orders are located.
  /// </param>
  /// <param name="y_max"> maximum y coordinate in which orders are located.
  /// </param>
  /// <param name="end_time"> latest end time of a tour of a vehicle. </param>
  /// <param name="capacity"> capacity of a vehicle. </param>
  /// <param name="cost_coefficient_max"> maximum cost per distance unit of a
  /// vehicle (minimum is 1)</param>
  private void BuildFleet(int number_of_orders,
                          int number_of_vehicles,
                          int x_max, int y_max,
                          int end_time,
                          int capacity,
                          int cost_coefficient_max) {
    Console.WriteLine("Building fleet.");
    vehicle_capacity_ = capacity;
    vehicle_starts_ = new int[number_of_vehicles];
    vehicle_ends_ = new int[number_of_vehicles];
    vehicle_end_time_ = new int[number_of_vehicles];
    vehicle_cost_coefficients_ = new int[number_of_vehicles];
    for (int vehicle = 0; vehicle < number_of_vehicles; ++vehicle) {
      int index = 2 * vehicle + number_of_orders;
      vehicle_starts_[vehicle] = index;
      locations_[index] =
          new Position(random_generator.Next(x_max + 1),
                       random_generator.Next(y_max + 1));
      vehicle_ends_[vehicle] = index + 1;
      locations_[index + 1] =
          new Position(random_generator.Next(x_max + 1),
                       random_generator.Next(y_max + 1));
      vehicle_end_time_[vehicle] = end_time;
      vehicle_cost_coefficients_[vehicle] =
          random_generator.Next(cost_coefficient_max) + 1;
    }
  }

  /// <summary>
  ///   Solves the current routing problem.
  /// </summary>
  private void Solve(int number_of_orders, int number_of_vehicles) {
    Console.WriteLine("Creating model with " + number_of_orders +
                      " orders and " + number_of_vehicles + " vehicles.");
    // Finalizing model
    int number_of_locations = locations_.Length;

    RoutingIndexManager manager =
        new RoutingIndexManager(number_of_locations, number_of_vehicles,
                                vehicle_starts_, vehicle_ends_);
    RoutingModel model = new RoutingModel(manager);

    // Setting up dimensions
    const int big_number = 100000;
    Manhattan manhattan_callback = new Manhattan(manager, locations_, 1);
    model.AddDimension(
        model.RegisterTransitCallback(manhattan_callback.Call),
        big_number, big_number, false, "time");
    RoutingDimension time_dimension = model.GetDimensionOrDie("time");

    Demand demand_callback = new Demand(manager, order_demands_);
    model.AddDimension(model.RegisterUnaryTransitCallback(demand_callback.Call),
                       0, vehicle_capacity_, true, "capacity");
    RoutingDimension capacity_dimension = model.GetDimensionOrDie("capacity");

    // Setting up vehicles
    Manhattan[] cost_callbacks = new Manhattan[number_of_vehicles];
    for (int vehicle = 0; vehicle < number_of_vehicles; ++vehicle) {
      int cost_coefficient = vehicle_cost_coefficients_[vehicle];
      Manhattan manhattan_cost_callback =
          new Manhattan(manager, locations_, cost_coefficient);
      cost_callbacks[vehicle] = manhattan_cost_callback;
      int manhattan_cost_index =
          model.RegisterTransitCallback(manhattan_cost_callback.Call);
      model.SetArcCostEvaluatorOfVehicle(manhattan_cost_index, vehicle);
      time_dimension.CumulVar(model.End(vehicle)).SetMax(
          vehicle_end_time_[vehicle]);
    }

    // Setting up orders
    for (int order = 0; order < number_of_orders; ++order) {
      time_dimension.CumulVar(order).SetRange(order_time_windows_[order].start_,
                                              order_time_windows_[order].end_);
      long[] orders = {manager.NodeToIndex(order)};
      model.AddDisjunction(orders, order_penalties_[order]);
    }

    // Solving
    RoutingSearchParameters search_parameters =
        operations_research_constraint_solver.DefaultRoutingSearchParameters();
    search_parameters.FirstSolutionStrategy =
        FirstSolutionStrategy.Types.Value.AllUnperformed;

    Console.WriteLine("Search...");
    Assignment solution = model.SolveWithParameters(search_parameters);

    if (solution != null) {
      String output = "Total cost: " + solution.ObjectiveValue() + "\n";
      // Dropped orders
      String dropped = "";
      for (int order = 0; order < number_of_orders; ++order) {
        if (solution.Value(model.NextVar(order)) == order) {
          dropped += " " + order;
        }
      }
      if (dropped.Length > 0) {
        output += "Dropped orders:" + dropped + "\n";
      }
      // Routes
      for (int vehicle = 0; vehicle < number_of_vehicles; ++vehicle) {
        String route = "Vehicle " + vehicle + ": ";
        long order = model.Start(vehicle);
        if (model.IsEnd(solution.Value(model.NextVar(order)))) {
          route += "Empty";
        } else {
          for (;
               !model.IsEnd(order);
               order = solution.Value(model.NextVar(order))) {
            IntVar local_load = capacity_dimension.CumulVar(order);
            IntVar local_time = time_dimension.CumulVar(order);
            route += order + " Load(" + solution.Value(local_load) + ") " +
                "Time(" + solution.Min(local_time) + ", " +
                solution.Max(local_time) + ") -> ";
          }
          IntVar load = capacity_dimension.CumulVar(order);
          IntVar time = time_dimension.CumulVar(order);
          route += order + " Load(" + solution.Value(load) + ") " +
              "Time(" + solution.Min(time) + ", " + solution.Max(time) + ")";
        }
        output += route + "\n";
      }
      Console.WriteLine(output);
    }
  }


  public static void Main(String[] args)
  {
    CapacitatedVehicleRoutingProblemWithTimeWindows problem =
        new CapacitatedVehicleRoutingProblemWithTimeWindows();
    int x_max = 20;
    int y_max = 20;
    int demand_max = 3;
    int time_window_max = 24 * 60;
    int time_window_width = 4 * 60;
    int penalty_min = 50;
    int penalty_max = 100;
    int end_time = 24 * 60;
    int cost_coefficient_max = 3;

    int orders = 100;
    int vehicles = 20;
    int capacity = 50;

    problem.BuildOrders(orders,
                        vehicles,
                        x_max,
                        y_max,
                        demand_max,
                        time_window_max,
                        time_window_width,
                        penalty_min,
                        penalty_max);
    problem.BuildFleet(orders,
                       vehicles,
                       x_max,
                       y_max,
                       end_time,
                       capacity,
                       cost_coefficient_max);
    problem.Solve(orders, vehicles);
  }
}