DotNet Reference

DotNet Reference

VrpResources.cs
Go to the documentation of this file.
1 // Copyright 2010-2018 Google LLC
2 // Licensed under the Apache License, Version 2.0 (the "License");
3 // you may not use this file except in compliance with the License.
4 // You may obtain a copy of the License at
5 //
6 // http://www.apache.org/licenses/LICENSE-2.0
7 //
8 // Unless required by applicable law or agreed to in writing, software
9 // distributed under the License is distributed on an "AS IS" BASIS,
10 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11 // See the License for the specific language governing permissions and
12 // limitations under the License.
13 
14 // [START program]
15 // [START import]
16 using System;
17 using System.Linq;
18 using System.Collections.Generic;
20 // [END import]
21 
25 public class VrpResources {
26  // [START data_model]
27  class DataModel {
28  public long[,] TimeMatrix = {
29  {0, 6, 9, 8, 7, 3, 6, 2, 3, 2, 6, 6, 4, 4, 5, 9, 7},
30  {6, 0, 8, 3, 2, 6, 8, 4, 8, 8, 13, 7, 5, 8, 12, 10, 14},
31  {9, 8, 0, 11, 10, 6, 3, 9, 5, 8, 4, 15, 14, 13, 9, 18, 9},
32  {8, 3, 11, 0, 1, 7, 10, 6, 10, 10, 14, 6, 7, 9, 14, 6, 16},
33  {7, 2, 10, 1, 0, 6, 9, 4, 8, 9, 13, 4, 6, 8, 12, 8, 14},
34  {3, 6, 6, 7, 6, 0, 2, 3, 2, 2, 7, 9, 7, 7, 6, 12, 8},
35  {6, 8, 3, 10, 9, 2, 0, 6, 2, 5, 4, 12, 10, 10, 6, 15, 5},
36  {2, 4, 9, 6, 4, 3, 6, 0, 4, 4, 8, 5, 4, 3, 7, 8, 10},
37  {3, 8, 5, 10, 8, 2, 2, 4, 0, 3, 4, 9, 8, 7, 3, 13, 6},
38  {2, 8, 8, 10, 9, 2, 5, 4, 3, 0, 4, 6, 5, 4, 3, 9, 5},
39  {6, 13, 4, 14, 13, 7, 4, 8, 4, 4, 0, 10, 9, 8, 4, 13, 4},
40  {6, 7, 15, 6, 4, 9, 12, 5, 9, 6, 10, 0, 1, 3, 7, 3, 10},
41  {4, 5, 14, 7, 6, 7, 10, 4, 8, 5, 9, 1, 0, 2, 6, 4, 8},
42  {4, 8, 13, 9, 8, 7, 10, 3, 7, 4, 8, 3, 2, 0, 4, 5, 6},
43  {5, 12, 9, 14, 12, 6, 6, 7, 3, 3, 4, 7, 6, 4, 0, 9, 2},
44  {9, 10, 18, 6, 8, 12, 15, 8, 13, 9, 13, 3, 4, 5, 9, 0, 9},
45  {7, 14, 9, 16, 14, 8, 5, 10, 6, 5, 4, 10, 8, 6, 2, 9, 0},
46  };
47  public long[,] TimeWindows = {
48  {0, 5}, // depot
49  {7, 12}, // 1
50  {10, 15}, // 2
51  {5, 14}, // 3
52  {5, 13}, // 4
53  {0, 5}, // 5
54  {5, 10}, // 6
55  {0, 10}, // 7
56  {5, 10}, // 8
57  {0, 5}, // 9
58  {10, 16}, // 10
59  {10, 15}, // 11
60  {0, 5}, // 12
61  {5, 10}, // 13
62  {7, 12}, // 14
63  {10, 15}, // 15
64  {5, 15}, // 16
65  };
66  public int VehicleNumber = 4;
67  // [START resources_data]
68  public int VehicleLoadTime = 5;
69  public int VehicleUnloadTime = 5;
70  public int DepotCapacity = 2;
71  // [END resources_data]
72  public int Depot = 0;
73  };
74  // [END data_model]
75 
76  // [START solution_printer]
80  static void PrintSolution(
81  in DataModel data,
82  in RoutingModel routing,
83  in RoutingIndexManager manager,
84  in Assignment solution) {
85  RoutingDimension timeDimension = routing.GetMutableDimension("Time");
86  // Inspect solution.
87  long totalTime = 0;
88  for (int i = 0; i < data.VehicleNumber; ++i) {
89  Console.WriteLine("Route for Vehicle {0}:", i);
90  var index = routing.Start(i);
91  while (routing.IsEnd(index) == false) {
92  var timeVar = timeDimension.CumulVar(index);
93  Console.Write("{0} Time({1},{2}) -> ",
94  manager.IndexToNode(index),
95  solution.Min(timeVar),
96  solution.Max(timeVar));
97  index = solution.Value(routing.NextVar(index));
98  }
99  var endTimeVar = timeDimension.CumulVar(index);
100  Console.WriteLine("{0} Time({1},{2})",
101  manager.IndexToNode(index),
102  solution.Min(endTimeVar),
103  solution.Max(endTimeVar));
104  Console.WriteLine("Time of the route: {0}min", solution.Min(endTimeVar));
105  totalTime += solution.Min(endTimeVar);
106  }
107  Console.WriteLine("Total time of all routes: {0}min", totalTime);
108  }
109  // [END solution_printer]
110 
111  public static void Main(String[] args) {
112  // Instantiate the data problem.
113  // [START data]
114  DataModel data = new DataModel();
115  // [END data]
116 
117  // Create Routing Index Manager
118  // [START index_manager]
120  data.TimeMatrix.GetLength(0),
121  data.VehicleNumber,
122  data.Depot);
123  // [END index_manager]
124 
125  // Create Routing Model.
126  // [START routing_model]
127  RoutingModel routing = new RoutingModel(manager);
128  // [END routing_model]
129 
130  // Create and register a transit callback.
131  // [START transit_callback]
132  int transitCallbackIndex = routing.RegisterTransitCallback(
133  (long fromIndex, long toIndex) => {
134  // Convert from routing variable Index to distance matrix NodeIndex.
135  var fromNode = manager.IndexToNode(fromIndex);
136  var toNode = manager.IndexToNode(toIndex);
137  return data.TimeMatrix[fromNode, toNode]; }
138  );
139  // [END transit_callback]
140 
141  // Define cost of each arc.
142  // [START arc_cost]
143  routing.SetArcCostEvaluatorOfAllVehicles(transitCallbackIndex);
144  // [END arc_cost]
145 
146  // Add Distance constraint.
147  // [START time_constraint]
148  routing.AddDimension(
149  transitCallbackIndex, // transit callback
150  30, // allow waiting time
151  30, // vehicle maximum capacities
152  false, // start cumul to zero
153  "Time");
154  RoutingDimension timeDimension = routing.GetMutableDimension("Time");
155  // Add time window constraints for each location except depot.
156  for (int i = 1; i < data.TimeWindows.GetLength(0); ++i) {
157  long index = manager.NodeToIndex(i);
158  timeDimension.CumulVar(index).SetRange(
159  data.TimeWindows[i, 0],
160  data.TimeWindows[i, 1]);
161  }
162  // Add time window constraints for each vehicle start node.
163  for (int i = 0; i < data.VehicleNumber; ++i) {
164  long index = routing.Start(i);
165  timeDimension.CumulVar(index).SetRange(
166  data.TimeWindows[0, 0],
167  data.TimeWindows[0, 1]);
168  }
169  // [END time_constraint]
170 
171  // Add resource constraints at the depot.
172  // [START depot_load_time]
173  Solver solver = routing.solver();
174  IntervalVar[] intervals = new IntervalVar[ data.VehicleNumber * 2 ];
175  for (int i = 0; i < data.VehicleNumber; ++i) {
176  // Add load duration at start of routes
177  intervals[2*i] = solver.MakeFixedDurationIntervalVar(
178  timeDimension.CumulVar(routing.Start(i)), data.VehicleLoadTime,
179  "depot_interval");
180  // Add unload duration at end of routes.
181  intervals[2*i+1] = solver.MakeFixedDurationIntervalVar(
182  timeDimension.CumulVar(routing.End(i)), data.VehicleUnloadTime,
183  "depot_interval");
184  }
185  // [END depot_load_time]
186 
187  // [START depot_capacity]
188  long[] depot_usage = Enumerable.Repeat<long>(1, intervals.Length).ToArray();
189  solver.Add(solver.MakeCumulative(intervals, depot_usage,
190  data.DepotCapacity, "depot"));
191  // [END depot_capacity]
192 
193  // Instantiate route start and end times to produce feasible times.
194  // [START depot_start_end_times]
195  for (int i = 0; i < data.VehicleNumber; ++i) {
197  timeDimension.CumulVar(routing.Start(i)));
199  timeDimension.CumulVar(routing.End(i)));
200  }
201  // [END depot_start_end_times]
202 
203  // Setting first solution heuristic.
204  // [START parameters]
205  RoutingSearchParameters searchParameters =
207  searchParameters.FirstSolutionStrategy =
208  FirstSolutionStrategy.Types.Value.PathCheapestArc;
209  // [END parameters]
210 
211  // Solve the problem.
212  // [START solve]
213  Assignment solution = routing.SolveWithParameters(searchParameters);
214  // [END solve]
215 
216  // Print solution on console.
217  // [START print_solution]
218  PrintSolution(data, routing, manager, solution);
219  // [END print_solution]
220  }
221 }
222 // [END program]
virtual void SetRange(long l, long u)
Definition: IntExpr.cs:75
void SetArcCostEvaluatorOfAllVehicles(int evaluator_index)
long End(int vehicle)
virtual long Value()
Definition: IntVar.cs:62
void Add(Constraint c)
global::Google.OrTools.ConstraintSolver.FirstSolutionStrategy.Types.Value FirstSolutionStrategy
First solution strategies, used as starting point of local search.
void AddVariableMinimizedByFinalizer(IntVar var)
static void Main(String[] args)
IntervalVar MakeFixedDurationIntervalVar(long start_min, long start_max, long duration, bool optional, string name)
long NodeToIndex(int node)
Definition: Assignment.cs:11
int IndexToNode(long index)
Value
long Start(int vehicle)
Vehicles Routing Problem (VRP) with Resource Constraints.
Definition: VrpResources.cs:25
IntVar CumulVar(long index)
Definition: RoutingModel.cs:18
Definition: IntervalVar.cs:18
First solution strategies, used as starting point of local search.
virtual long Min()
Definition: IntExpr.cs:51
bool AddDimension(int evaluator_index, long slack_max, long capacity, bool fix_start_cumul_to_zero, string name)
static Google.OrTools.ConstraintSolver.RoutingSearchParameters DefaultRoutingSearchParameters()
Definition: Assignment.cs:18
Solver solver()
Container for nested types declared in the FirstSolutionStrategy message type.
int RegisterTransitCallback(LongLongToLong callback)
Assignment SolveWithParameters(Google.OrTools.ConstraintSolver.RoutingSearchParameters search_parameters)
RoutingDimension GetMutableDimension(string dimension_name)
Parameters defining the search used to solve vehicle routing problems.
Constraint MakeCumulative(IntervalVarVector intervals, long[] demands, long capacity, string name)