DotNet Reference

DotNet Reference

Tsp.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 
26 public class Tsp {
27  // [START data_model]
28  class DataModel {
29  // Constructor:
30  public DataModel() {
31  // Convert locations in meters using a city block dimension of 114m x 80m.
32  for (int i=0; i < Locations.GetLength(0); i++) {
33  Locations[i, 0] *= 114;
34  Locations[i, 1] *= 80;
35  }
36  }
37  public int[,] Locations = {
38  {4, 4},
39  {2, 0}, {8, 0},
40  {0, 1}, {1, 1},
41  {5, 2}, {7, 2},
42  {3, 3}, {6, 3},
43  {5, 5}, {8, 5},
44  {1, 6}, {2, 6},
45  {3, 7}, {6, 7},
46  {0, 8}, {7, 8}
47  };
48  public int VehicleNumber = 1;
49  public int Depot = 0;
50  };
51  // [END data_model]
52 
53  // [START manhattan_distance]
59  class ManhattanDistance {
60  public ManhattanDistance(
61  in DataModel data,
62  in RoutingIndexManager manager) {
63  // precompute distance between location to have distance callback in O(1)
64  int locationNumber = data.Locations.GetLength(0);
65  distancesMatrix_ = new long[locationNumber, locationNumber];
66  indexManager_ = manager;
67  for (int fromNode = 0; fromNode < locationNumber; fromNode++) {
68  for (int toNode = 0; toNode < locationNumber; toNode++) {
69  if (fromNode == toNode)
70  distancesMatrix_[fromNode, toNode] = 0;
71  else
72  distancesMatrix_[fromNode, toNode] =
73  Math.Abs(data.Locations[toNode, 0] - data.Locations[fromNode, 0]) +
74  Math.Abs(data.Locations[toNode, 1] - data.Locations[fromNode, 1]);
75  }
76  }
77  }
78 
82  public long Call(long fromIndex, long toIndex) {
83  // Convert from routing variable Index to distance matrix NodeIndex.
84  int fromNode = indexManager_.IndexToNode(fromIndex);
85  int toNode = indexManager_.IndexToNode(toIndex);
86  return distancesMatrix_[fromNode, toNode];
87  }
88  private long[,] distancesMatrix_;
89  private RoutingIndexManager indexManager_;
90  };
91  // [END manhattan_distance]
92 
93  // [START solution_printer]
97  static void PrintSolution(
98  in RoutingModel routing,
99  in RoutingIndexManager manager,
100  in Assignment solution) {
101  Console.WriteLine("Objective: {0}", solution.ObjectiveValue());
102  // Inspect solution.
103  Console.WriteLine("Route for Vehicle 0:");
104  long routeDistance = 0;
105  var index = routing.Start(0);
106  while (routing.IsEnd(index) == false) {
107  Console.Write("{0} -> ", manager.IndexToNode((int)index));
108  var previousIndex = index;
109  index = solution.Value(routing.NextVar(index));
110  routeDistance += routing.GetArcCostForVehicle(previousIndex, index, 0);
111  }
112  Console.WriteLine("{0}", manager.IndexToNode((int)index));
113  Console.WriteLine("Distance of the route: {0}m", routeDistance);
114  }
115  // [END solution_printer]
116 
117  public static void Main(String[] args) {
118  // Instantiate the data problem.
119  // [START data]
120  DataModel data = new DataModel();
121  // [END data]
122 
123  // Create Routing Index Manager
124  // [START index_manager]
126  data.Locations.GetLength(0),
127  data.VehicleNumber,
128  data.Depot);
129  // [END index_manager]
130 
131  // Create Routing Model.
132  // [START routing_model]
133  RoutingModel routing = new RoutingModel(manager);
134  // [END routing_model]
135 
136  // Create and register a transit callback.
137  // [START transit_callback]
138  var distanceCallback = new ManhattanDistance(data, manager);
139  int transitCallbackIndex = routing.RegisterTransitCallback(distanceCallback.Call);
140  // [END transit_callback]
141 
142  // Define cost of each arc.
143  // [START arc_cost]
144  routing.SetArcCostEvaluatorOfAllVehicles(transitCallbackIndex);
145  // [END arc_cost]
146 
147  // Setting first solution heuristic.
148  // [START parameters]
149  RoutingSearchParameters searchParameters =
151  searchParameters.FirstSolutionStrategy =
152  FirstSolutionStrategy.Types.Value.PathCheapestArc;
153  // [END parameters]
154 
155  // Solve the problem.
156  // [START solve]
157  Assignment solution = routing.SolveWithParameters(searchParameters);
158  // [END solve]
159 
160  // Print solution on console.
161  // [START print_solution]
162  PrintSolution(routing, manager, solution);
163  // [END print_solution]
164  }
165 }
166 // [END program]
void SetArcCostEvaluatorOfAllVehicles(int evaluator_index)
global::Google.OrTools.ConstraintSolver.FirstSolutionStrategy.Types.Value FirstSolutionStrategy
First solution strategies, used as starting point of local search.
static void Main(String[] args)
Definition: Tsp.cs:117
Definition: Assignment.cs:11
Value
Definition: RoutingModel.cs:18
Minimal TSP.
Definition: Tsp.cs:26
First solution strategies, used as starting point of local search.
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)
Parameters defining the search used to solve vehicle routing problems.