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