Google OrTools Sample showing SetSpanUpperBoundForVehicle() behaviour depending on orders' disjunctions set up.

cscvrptw-question.cs

using Google.OrTools.ConstraintSolver;
using System;

/// <summary>
///   Google OrTools Sample showing SetSpanUpperBoundForVehicle() behaviour
///   depending on orders' disjunctions.
/// </summary>
public class VehicleRoutingProblemWithTimeWindows {

    /// <summary>
    ///   A callback that computes driving time plus service time
    /// </summary>
    class TotalTime : NodeEvaluator2{
        long[,] matrix_; 
        long[,] tw_;
        public TotalTime(long[,] matrix, long[,] tw) {
            matrix_ = matrix;
            tw_ = tw;
        }
        public override long Run(int first_index, int second_index) {
            if (first_index >= tw_.GetLength(0) || second_index >= tw_.GetLength(0)) {
                return 0;
            }
            return matrix_[first_index, second_index] + tw_[first_index, SRVTIME];
        }
    };

    /// <summary>
    ///   A callback that computes driving time 
    /// </summary>
    class DriveTime : NodeEvaluator2 {
        long[,] matrix_; 
        public DriveTime(long[,] matrix) {
            matrix_ = matrix;
        }
        public override long Run(int first_index, int second_index) {
            if (first_index >= matrix_.GetLength(0) || second_index >= matrix_.GetLength(0)) {
                return 0;
            }
            return matrix_[first_index, second_index] ;
        }
    };

    static readonly int 
          SRVTIME = 0
        , SRVSTART = 1
        , SRVEND = 2;
 
    long[,] costMx_;
    long[,] timeSrvWindows_;

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

  private  int CreateOrders() {
     // Index 0 == depot
     Console.WriteLine("Creating orders.");
     costMx_ = new long[,] {
         {0,2827,521,521,521,460,460,1341,1686,1686,602,1613,3031}
        ,{2822,0,2899,2899,2899,2839,2839,3529,3720,3720,3425,3770,3676}
        ,{568,2749,0,0,0,585,585,1466,1810,1810,1171,1737,3090}
        ,{568,2749,0,0,0,585,585,1466,1810,1810,1171,1737,3090}
        ,{568,2749,0,0,0,585,585,1466,1810,1810,1171,1737,3090}
        ,{391,2913,607,607,607,0,0,1138,1482,1482,994,1409,3029}
        ,{391,2913,607,607,607,0,0,1138,1482,1482,994,1409,3029}
        ,{1168,3467,1384,1384,1384,1149,1149,0,614,614,1474,541,3806}
        ,{1684,3690,1900,1900,1900,1665,1665,639,0,0,1990,262,3994}
        ,{1684,3690,1900,1900,1900,1665,1665,639,0,0,1990,262,3994}
        ,{589,3361,1055,1055,1055,995,995,1559,1903,1903,0,1830,3200}
        ,{1540,3792,1757,1757,1757,1522,1522,479,224,224,1847,0,4097}
        ,{3028,3608,3160,3160,3160,2984,2984,3858,4013,4013,3200,4063,0}
    };
     timeSrvWindows_ = new long[,] { 
           { 0, 0, 0 }
         , { 0, 25200, 28800 }
         , { 0, 25200, 28800 }
         , { 600, 64800, 72000 }
         , { 600, 39600, 43200 }
         , { 0, 25200, 0 }
         , { 600, 61200, 64800 }
         , { 0, 25200, 0 }
         , { 0, 25200, 0 }
         , { 36000, 32640, 36000 }
         , { 3540, 25200, 0 }
         , { 0, 25200, 28800 }
         , { 0, 25200, 28800 }
     };

     return timeSrvWindows_.GetLength(0) - 1;
  }

    /// <summary>
    ///   Solves the current routing problem. 
    /// </summary>
    /// <param name="number_of_orders"></param>
    /// <param name="number_of_vehicles"></param>
    /// <param name="spanUpperBoundForVehicle"> -1 == do not apply a span</param>
    /// <param name="orderPenalty"> -1 == no disjunctions</param>
  private void Solve(
        int number_of_orders
      , int number_of_vehicles
      , int spanUpperBoundForVehicle
      , int orderPenalty) {
    Console.WriteLine("Creating model with " + number_of_orders +
                      " orders and " + number_of_vehicles + " vehicles,");
    Console.WriteLine("SpanUpperBoundForVehicle = " + spanUpperBoundForVehicle + ", OrderPenalty = " + orderPenalty +" .");
    // Finalizing model
    int number_of_locations = number_of_orders + 1;
    // Single depot at last  location
    RoutingModel model =
        new RoutingModel(number_of_locations, number_of_vehicles, 0);

    // Using matrix to set up cost
    NodeEvaluator2 arc_cost_callback = new DriveTime(costMx_);
    model.SetArcCostEvaluatorOfAllVehicles(arc_cost_callback);

    // Setting up total time dimension
    const int big_number = 1000000;
    NodeEvaluator2 totalTime = new TotalTime(costMx_, timeSrvWindows_);
    model.AddDimension(
        totalTime, big_number, big_number, false, "time");
    var time_dimension = model.GetDimensionOrDie("time");

    // Setting up vehicles span conditionally
    if (spanUpperBoundForVehicle > 0) 
        for (int vehicle = 0; vehicle < number_of_vehicles; ++vehicle) {
            time_dimension.SetSpanUpperBoundForVehicle(spanUpperBoundForVehicle, vehicle);
        }

    // Setting up orders, skip depot at 0
    for (int order = 1; order < number_of_locations; ++order)
    {
      IntExpr exp = time_dimension.CumulVar(order); 
      if (timeSrvWindows_[order, SRVSTART] > 0)
          exp.SetMin(timeSrvWindows_[order, SRVSTART]);
      if (timeSrvWindows_[order, SRVEND] > 0)
          exp.SetMax(timeSrvWindows_[order, SRVEND]);

      if (orderPenalty > 0) {
          int[] orders = { order };
          model.AddDisjunction(orders, orderPenalty);
      }
    }

    // Solving
    RoutingSearchParameters search_parameters =
        RoutingModel.DefaultSearchParameters();
    search_parameters.FirstSolutionStrategy = 
        FirstSolutionStrategy.Types.Value.PathCheapestArc;
        // NOTE: AllUnperformed will FAIL without disjunctions
        //FirstSolutionStrategy.Types.Value.AllUnperformed;
    search_parameters.TimeLimitMs = 60000;
    Console.WriteLine("Search");
    Assignment solution = model.SolveWithParameters(search_parameters);

    if (solution == null) {
        Console.WriteLine("No solution, status =" + model.Status() +"\n");
        return;
    }
   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_time = model.CumulVar(order, "time");
         route += model.IndexToNode((int)order) +
               " Time(" + solution.Min(local_time) + ", " +
               solution.Max(local_time) + ") -> ";
         }
         IntVar time = model.CumulVar(order, "time");
         route += model.IndexToNode((int)order) +
            " Time(" + solution.Min(time) + ", " + solution.Max(time) + ")";
      }
      output += route + "\n";
   }
   Console.WriteLine(output);
  }

  
  public static void Main(String[] args)
  {
    Console.WriteLine("** "+typeof(RoutingModel).Assembly.FullName +" **");

    VehicleRoutingProblemWithTimeWindows problem =
        new VehicleRoutingProblemWithTimeWindows();

    int span = 20 * 60 * 60;
    int vehicles = 3;
    int orders = problem.CreateOrders();

    int order_penalty = -1;
    problem.Solve(orders, vehicles, span, order_penalty);

    order_penalty = 80 ;
    problem.Solve(orders, vehicles, span, order_penalty);

    order_penalty = 8000;
    problem.Solve(orders, vehicles, span, order_penalty);

    Console.ReadLine();
  }
}

Output

** Google.OrTools, Version=6.0.4217.18304, Culture=neutral, PublicKeyToken=e5e5a
4177ad79658 **
Creating orders.
Creating model with 12 orders and 3 vehicles,
SpanUpperBoundForVehicle = 72000, OrderPenalty = -1 .
Search
No solution, status =3

Creating model with 12 orders and 3 vehicles,
SpanUpperBoundForVehicle = 72000, OrderPenalty = 80 .
Search
Total cost: 5710
Dropped orders: 1 7 10 11
Vehicle 0: 0 Time(0, 34314) -> 9 Time(32640, 36000) -> 8 Time(68640, 104630) ->
0 Time(70324, 106314)
Vehicle 1: 0 Time(0, 28279) -> 2 Time(25200, 28800) -> 4 Time(39600, 43200) -> 3
 Time(64800, 72000) -> 0 Time(65968, 100279)
Vehicle 2: 0 Time(0, 64340) -> 6 Time(61200, 64800) -> 5 Time(61800, 135949) ->
0 Time(62191, 136340)

Creating model with 12 orders and 3 vehicles,
SpanUpperBoundForVehicle = 72000, OrderPenalty = 8000 .
Search
Total cost: 17239
Vehicle 0: 0 Time(2882, 27187) -> 11 Time(25200, 28800) -> 9 Time(32640, 36000)
-> 8 Time(68640, 92945) -> 7 Time(69279, 93584) -> 10 Time(70753, 95058) -> 0 Ti
me(74882, 99187)
Vehicle 1: 0 Time(0, 23074) -> 1 Time(25200, 25901) -> 2 Time(28099, 28800) -> 4
 Time(39600, 43200) -> 3 Time(64800, 72000) -> 0 Time(65968, 95074)
Vehicle 2: 0 Time(0, 25769) -> 12 Time(25200, 28800) -> 6 Time(61200, 64800) ->
5 Time(61800, 97378) -> 0 Time(62191, 97769)