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 Xunit; 16 using Google.OrTools.ConstraintSolver; 17 18 namespace Google.OrTools.Tests 19 { 20 public class RoutingSolverTest 21 { 22 [Theory] 23 [InlineData(false)] 24 [InlineData(true)] SimpleLambdaCallback(bool callGC)25 public void SimpleLambdaCallback(bool callGC) 26 { 27 // Create Routing Index Manager 28 RoutingIndexManager manager = new RoutingIndexManager(5 /*locations*/, 1 /*vehicle*/, 0 /*depot*/); 29 // Create Routing Model. 30 RoutingModel routing = new RoutingModel(manager); 31 // Create a distance callback. 32 int transitCallbackIndex = routing.RegisterTransitCallback((long fromIndex, long toIndex) => { 33 // Convert from routing variable Index to distance matrix NodeIndex. 34 var fromNode = manager.IndexToNode(fromIndex); 35 var toNode = manager.IndexToNode(toIndex); 36 return Math.Abs(toNode - fromNode); 37 }); 38 // Define cost of each arc. 39 routing.SetArcCostEvaluatorOfAllVehicles(transitCallbackIndex); 40 if (callGC) 41 { 42 GC.Collect(); 43 } 44 // Setting first solution heuristic. 45 RoutingSearchParameters searchParameters = 46 operations_research_constraint_solver.DefaultRoutingSearchParameters(); 47 searchParameters.FirstSolutionStrategy = FirstSolutionStrategy.Types.Value.PathCheapestArc; 48 Assignment solution = routing.SolveWithParameters(searchParameters); 49 // 0 --(+1)-> 1 --(+1)-> 2 --(+1)-> 3 --(+1)-> 4 --(+4)-> 0 := +8 50 Assert.Equal(8, solution.ObjectiveValue()); 51 } 52 53 [Fact] TestTransitMatrix()54 public void TestTransitMatrix() 55 { 56 // Create Routing Index Manager 57 RoutingIndexManager manager = new RoutingIndexManager(5 /*locations*/, 1 /*vehicle*/, 0 /*depot*/); 58 // Create Routing Model. 59 RoutingModel routing = new RoutingModel(manager); 60 // Create a distance callback. 61 long[][] matrix = new long[][] { 62 new long[] {1, 1, 1, 1, 1}, 63 new long[] {1, 1, 1, 1, 1}, 64 new long[] {1, 1, 1, 1, 1}, 65 new long[] {1, 1, 1, 1, 1}, 66 new long[] {1, 1, 1, 1, 1}, 67 }; 68 int transitCallbackIndex = routing.RegisterTransitMatrix(matrix); 69 // Define cost of each arc. 70 routing.SetArcCostEvaluatorOfAllVehicles(transitCallbackIndex); 71 // Setting first solution heuristic. 72 RoutingSearchParameters searchParameters = 73 operations_research_constraint_solver.DefaultRoutingSearchParameters(); 74 searchParameters.FirstSolutionStrategy = FirstSolutionStrategy.Types.Value.PathCheapestArc; 75 Assignment solution = routing.SolveWithParameters(searchParameters); 76 // 0 --(+1)-> 1 --(+1)-> 2 --(+1)-> 3 --(+1)-> 4 --(+1)-> 0 := +5 77 Assert.Equal(5, solution.ObjectiveValue()); 78 } 79 80 [Fact] TestTransitCallback()81 public void TestTransitCallback() 82 { 83 // Create Routing Index Manager 84 RoutingIndexManager manager = new RoutingIndexManager(5 /*locations*/, 1 /*vehicle*/, 0 /*depot*/); 85 // Create Routing Model. 86 RoutingModel routing = new RoutingModel(manager); 87 // Create a distance callback. 88 int transitCallbackIndex = routing.RegisterTransitCallback( 89 (long fromIndex, long toIndex) => { 90 // Convert from routing variable Index to distance matrix NodeIndex. 91 var fromNode = manager.IndexToNode(fromIndex); 92 var toNode = manager.IndexToNode(toIndex); 93 return Math.Abs(toNode - fromNode); 94 }); 95 // Define cost of each arc. 96 routing.SetArcCostEvaluatorOfAllVehicles(transitCallbackIndex); 97 // Setting first solution heuristic. 98 RoutingSearchParameters searchParameters = 99 operations_research_constraint_solver.DefaultRoutingSearchParameters(); 100 searchParameters.FirstSolutionStrategy = FirstSolutionStrategy.Types.Value.PathCheapestArc; 101 Assignment solution = routing.SolveWithParameters(searchParameters); 102 Assert.Equal(8, solution.ObjectiveValue()); 103 } 104 105 [Fact] TestMatrixDimension()106 public void TestMatrixDimension() 107 { 108 // Create Routing Index Manager 109 RoutingIndexManager manager = new RoutingIndexManager(5 /*locations*/, 1 /*vehicle*/, 0 /*depot*/); 110 // Create Routing Model. 111 RoutingModel routing = new RoutingModel(manager); 112 // Create a distance callback. 113 long[][] matrix = new long[][] { 114 new long[] {1, 1, 1, 1, 1}, 115 new long[] {1, 1, 1, 1, 1}, 116 new long[] {1, 1, 1, 1, 1}, 117 new long[] {1, 1, 1, 1, 1}, 118 new long[] {1, 1, 1, 1, 1}, 119 }; 120 IntBoolPair result = routing.AddMatrixDimension( 121 matrix, 122 /*capacity=*/10, 123 /*fix_start_cumul_to_zero=*/true, 124 "Dimension"); 125 // Define cost of each arc. 126 routing.SetArcCostEvaluatorOfAllVehicles(result.first); 127 // Setting first solution heuristic. 128 RoutingSearchParameters searchParameters = 129 operations_research_constraint_solver.DefaultRoutingSearchParameters(); 130 searchParameters.FirstSolutionStrategy = FirstSolutionStrategy.Types.Value.PathCheapestArc; 131 Assignment solution = routing.SolveWithParameters(searchParameters); 132 // 0 --(+1)-> 1 --(+1)-> 2 --(+1)-> 3 --(+1)-> 4 --(+1)-> 0 := +5 133 Assert.Equal(5, solution.ObjectiveValue()); 134 } 135 136 [Fact] TestUnaryTransitVector()137 public void TestUnaryTransitVector() 138 { 139 // Create Routing Index Manager 140 RoutingIndexManager manager = new RoutingIndexManager(5 /*locations*/, 1 /*vehicle*/, 0 /*depot*/); 141 // Create Routing Model. 142 RoutingModel routing = new RoutingModel(manager); 143 // Create a distance callback. 144 long[] vector = {1, 1, 1, 1, 1}; 145 int transitCallbackIndex = routing.RegisterUnaryTransitVector(vector); 146 // Define cost of each arc. 147 routing.SetArcCostEvaluatorOfAllVehicles(transitCallbackIndex); 148 // Setting first solution heuristic. 149 RoutingSearchParameters searchParameters = 150 operations_research_constraint_solver.DefaultRoutingSearchParameters(); 151 searchParameters.FirstSolutionStrategy = FirstSolutionStrategy.Types.Value.PathCheapestArc; 152 Assignment solution = routing.SolveWithParameters(searchParameters); 153 // 0 --(+1)-> 1 --(+1)-> 2 --(+1)-> 3 --(+1)-> 4 --(+1)-> 0 := +5 154 Assert.Equal(5, solution.ObjectiveValue()); 155 } 156 157 [Fact] TestUnaryTransitCallback()158 public void TestUnaryTransitCallback() 159 { 160 // Create Routing Index Manager 161 RoutingIndexManager manager = new RoutingIndexManager(5 /*locations*/, 1 /*vehicle*/, 0 /*depot*/); 162 // Create Routing Model. 163 RoutingModel routing = new RoutingModel(manager); 164 // Create a distance callback. 165 int transitCallbackIndex = routing.RegisterUnaryTransitCallback( 166 (long fromIndex) => { 167 // Convert from routing variable Index to distance matrix NodeIndex. 168 var fromNode = manager.IndexToNode(fromIndex); 169 return fromNode + 1; 170 }); 171 // Define cost of each arc. 172 routing.SetArcCostEvaluatorOfAllVehicles(transitCallbackIndex); 173 // Setting first solution heuristic. 174 RoutingSearchParameters searchParameters = 175 operations_research_constraint_solver.DefaultRoutingSearchParameters(); 176 searchParameters.FirstSolutionStrategy = FirstSolutionStrategy.Types.Value.PathCheapestArc; 177 Assignment solution = routing.SolveWithParameters(searchParameters); 178 // 0 --(+1)-> 1 --(+2)-> 2 --(+3)-> 3 --(+4)-> 4 --(+5)-> 0 := +15 179 Assert.Equal(15, solution.ObjectiveValue()); 180 } 181 182 [Fact] TestVectorDimension()183 public void TestVectorDimension() 184 { 185 // Create Routing Index Manager 186 RoutingIndexManager manager = new RoutingIndexManager(5 /*locations*/, 1 /*vehicle*/, 0 /*depot*/); 187 // Create Routing Model. 188 RoutingModel routing = new RoutingModel(manager); 189 // Create a distance callback. 190 long[] vector = new long[] {1, 1, 1, 1, 1}; 191 IntBoolPair result = routing.AddVectorDimension( 192 vector, 193 /*capacity=*/10, 194 /*fix_start_cumul_to_zero=*/true, 195 "Dimension"); 196 // Define cost of each arc. 197 routing.SetArcCostEvaluatorOfAllVehicles(result.first); 198 // Setting first solution heuristic. 199 RoutingSearchParameters searchParameters = 200 operations_research_constraint_solver.DefaultRoutingSearchParameters(); 201 searchParameters.FirstSolutionStrategy = FirstSolutionStrategy.Types.Value.PathCheapestArc; 202 Assignment solution = routing.SolveWithParameters(searchParameters); 203 // 0 --(+1)-> 1 --(+1)-> 2 --(+1)-> 3 --(+1)-> 4 --(+1)-> 0 := +5 204 Assert.Equal(5, solution.ObjectiveValue()); 205 } 206 } 207 } // namespace Google.OrTools.Tests 208