1 // Copyright 2010-2021 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 using System; 15 using System.Collections.Generic; 16 using Google.OrTools.ConstraintSolver; 17 18 class Tsp 19 { 20 class RandomManhattan 21 { RandomManhattan(RoutingIndexManager manager, int size, int seed)22 public RandomManhattan(RoutingIndexManager manager, int size, int seed) 23 { 24 this.xs_ = new int[size]; 25 this.ys_ = new int[size]; 26 this.manager_ = manager; 27 Random generator = new Random(seed); 28 for (int i = 0; i < size; ++i) 29 { 30 xs_[i] = generator.Next(1000); 31 ys_[i] = generator.Next(1000); 32 } 33 } 34 Call(long first_index, long second_index)35 public long Call(long first_index, long second_index) 36 { 37 int first_node = manager_.IndexToNode(first_index); 38 int second_node = manager_.IndexToNode(second_index); 39 return Math.Abs(xs_[first_node] - xs_[second_node]) + Math.Abs(ys_[first_node] - ys_[second_node]); 40 } 41 42 private readonly int[] xs_; 43 private readonly int[] ys_; 44 private readonly RoutingIndexManager manager_; 45 }; 46 Solve(int size, int forbidden, int seed)47 static void Solve(int size, int forbidden, int seed) 48 { 49 RoutingIndexManager manager = new RoutingIndexManager(size, 1, 0); 50 RoutingModel routing = new RoutingModel(manager); 51 52 // Setting the cost function. 53 // Put a permanent callback to the distance accessor here. The callback 54 // has the following signature: ResultCallback2<int64_t, int64_t, int64_t>. 55 // The two arguments are the from and to node inidices. 56 RandomManhattan distances = new RandomManhattan(manager, size, seed); 57 routing.SetArcCostEvaluatorOfAllVehicles(routing.RegisterTransitCallback(distances.Call)); 58 59 // Forbid node connections (randomly). 60 Random randomizer = new Random(); 61 long forbidden_connections = 0; 62 while (forbidden_connections < forbidden) 63 { 64 long from = randomizer.Next(size - 1); 65 long to = randomizer.Next(size - 1) + 1; 66 if (routing.NextVar(from).Contains(to)) 67 { 68 Console.WriteLine("Forbidding connection {0} -> {1}", from, to); 69 routing.NextVar(from).RemoveValue(to); 70 ++forbidden_connections; 71 } 72 } 73 74 // Add dummy dimension to test API. 75 routing.AddDimension(routing.RegisterUnaryTransitCallback((long index) => { return 1; }), size + 1, size + 1, 76 true, "dummy"); 77 78 // Solve, returns a solution if any (owned by RoutingModel). 79 RoutingSearchParameters search_parameters = 80 operations_research_constraint_solver.DefaultRoutingSearchParameters(); 81 // Setting first solution heuristic (cheapest addition). 82 search_parameters.FirstSolutionStrategy = FirstSolutionStrategy.Types.Value.PathCheapestArc; 83 84 Assignment solution = routing.SolveWithParameters(search_parameters); 85 Console.WriteLine("Status = {0}", routing.GetStatus()); 86 if (solution != null) 87 { 88 // Solution cost. 89 Console.WriteLine("Cost = {0}", solution.ObjectiveValue()); 90 // Inspect solution. 91 // Only one route here; otherwise iterate from 0 to routing.vehicles() - 1 92 int route_number = 0; 93 for (long node = routing.Start(route_number); !routing.IsEnd(node); 94 node = solution.Value(routing.NextVar(node))) 95 { 96 Console.Write("{0} -> ", node); 97 } 98 Console.WriteLine("0"); 99 } 100 } 101 Main(String[] args)102 public static void Main(String[] args) 103 { 104 int size = 10; 105 if (args.Length > 0) 106 { 107 size = Convert.ToInt32(args[0]); 108 } 109 int forbidden = 0; 110 if (args.Length > 1) 111 { 112 forbidden = Convert.ToInt32(args[1]); 113 } 114 int seed = 0; 115 if (args.Length > 2) 116 { 117 seed = Convert.ToInt32(args[2]); 118 } 119 120 Solve(size, forbidden, seed); 121 } 122 } 123