DotNet Reference

DotNet Reference

VrpTimeWindows.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.Collections.Generic;
19 // [END import]
20 
21 // [START program_part1]
25 public class VrpTimeWindows {
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  {16, 18}, // 3
52  {10, 13}, // 4
53  {0, 5}, // 5
54  {5, 10}, // 6
55  {0, 4}, // 7
56  {5, 10}, // 8
57  {0, 3}, // 9
58  {10, 16}, // 10
59  {10, 15}, // 11
60  {0, 5}, // 12
61  {5, 10}, // 13
62  {7, 8}, // 14
63  {10, 15}, // 15
64  {11, 15}, // 16
65  };
66  public int VehicleNumber = 4;
67  public int Depot = 0;
68  };
69  // [END data_model]
70 
71  // [START solution_printer]
75  static void PrintSolution(
76  in DataModel data,
77  in RoutingModel routing,
78  in RoutingIndexManager manager,
79  in Assignment solution) {
80  RoutingDimension timeDimension = routing.GetMutableDimension("Time");
81  // Inspect solution.
82  long totalTime = 0;
83  for (int i = 0; i < data.VehicleNumber; ++i) {
84  Console.WriteLine("Route for Vehicle {0}:", i);
85  var index = routing.Start(i);
86  while (routing.IsEnd(index) == false) {
87  var timeVar = timeDimension.CumulVar(index);
88  Console.Write("{0} Time({1},{2}) -> ",
89  manager.IndexToNode(index),
90  solution.Min(timeVar),
91  solution.Max(timeVar));
92  index = solution.Value(routing.NextVar(index));
93  }
94  var endTimeVar = timeDimension.CumulVar(index);
95  Console.WriteLine("{0} Time({1},{2})",
96  manager.IndexToNode(index),
97  solution.Min(endTimeVar),
98  solution.Max(endTimeVar));
99  Console.WriteLine("Time of the route: {0}min", solution.Min(endTimeVar));
100  totalTime += solution.Min(endTimeVar);
101  }
102  Console.WriteLine("Total time of all routes: {0}min", totalTime);
103  }
104  // [END solution_printer]
105 
106  public static void Main(String[] args) {
107  // Instantiate the data problem.
108  // [START data]
109  DataModel data = new DataModel();
110  // [END data]
111 
112  // Create Routing Index Manager
113  // [START index_manager]
115  data.TimeMatrix.GetLength(0),
116  data.VehicleNumber,
117  data.Depot);
118  // [END index_manager]
119 
120  // Create Routing Model.
121  // [START routing_model]
122  RoutingModel routing = new RoutingModel(manager);
123  // [END routing_model]
124 
125  // Create and register a transit callback.
126  // [START transit_callback]
127  int transitCallbackIndex = routing.RegisterTransitCallback(
128  (long fromIndex, long toIndex) => {
129  // Convert from routing variable Index to distance matrix NodeIndex.
130  var fromNode = manager.IndexToNode(fromIndex);
131  var toNode = manager.IndexToNode(toIndex);
132  return data.TimeMatrix[fromNode, toNode]; }
133  );
134  // [END transit_callback]
135 
136  // Define cost of each arc.
137  // [START arc_cost]
138  routing.SetArcCostEvaluatorOfAllVehicles(transitCallbackIndex);
139  // [END arc_cost]
140 
141  // Add Distance constraint.
142  // [START time_constraint]
143  routing.AddDimension(
144  transitCallbackIndex, // transit callback
145  30, // allow waiting time
146  30, // vehicle maximum capacities
147  false, // start cumul to zero
148  "Time");
149  RoutingDimension timeDimension = routing.GetMutableDimension("Time");
150  // Add time window constraints for each location except depot.
151  for (int i = 1; i < data.TimeWindows.GetLength(0); ++i) {
152  long index = manager.NodeToIndex(i);
153  timeDimension.CumulVar(index).SetRange(
154  data.TimeWindows[i, 0],
155  data.TimeWindows[i, 1]);
156  }
157  // Add time window constraints for each vehicle start node.
158  for (int i = 0; i < data.VehicleNumber; ++i) {
159  long index = routing.Start(i);
160  timeDimension.CumulVar(index).SetRange(
161  data.TimeWindows[0, 0],
162  data.TimeWindows[0, 1]);
163  }
164  // [END time_constraint]
165 
166  // Instantiate route start and end times to produce feasible times.
167  // [START depot_start_end_times]
168  for (int i = 0; i < data.VehicleNumber; ++i) {
170  timeDimension.CumulVar(routing.Start(i)));
172  timeDimension.CumulVar(routing.End(i)));
173  }
174  // [END depot_start_end_times]
175 
176  // Setting first solution heuristic.
177  // [START parameters]
178  RoutingSearchParameters searchParameters =
180  searchParameters.FirstSolutionStrategy =
181  FirstSolutionStrategy.Types.Value.PathCheapestArc;
182  // [END parameters]
183 
184  // Solve the problem.
185  // [START solve]
186  Assignment solution = routing.SolveWithParameters(searchParameters);
187  // [END solve]
188 
189  // Print solution on console.
190  // [START print_solution]
191  PrintSolution(data, routing, manager, solution);
192  // [END print_solution]
193  }
194 }
195 // [END program_part1]
196 // [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
global::Google.OrTools.ConstraintSolver.FirstSolutionStrategy.Types.Value FirstSolutionStrategy
First solution strategies, used as starting point of local search.
void AddVariableMinimizedByFinalizer(IntVar var)
long NodeToIndex(int node)
Definition: Assignment.cs:11
int IndexToNode(long index)
Value
long Start(int vehicle)
IntVar CumulVar(long index)
Definition: RoutingModel.cs:18
static void Main(String[] args)
First solution strategies, used as starting point of local search.
Vehicles Routing Problem (VRP) with Time Windows.
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
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.