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