2025-01-10 11:35:44 +01:00
|
|
|
// Copyright 2010-2025 Google LLC
|
2019-01-09 11:28:14 +01:00
|
|
|
//
|
|
|
|
|
// Licensed under the Apache License, Version 2.0 (the "License");
|
|
|
|
|
// you may not use this file except in compliance with the License.
|
|
|
|
|
// You may obtain a copy of the License at
|
|
|
|
|
//
|
|
|
|
|
// http://www.apache.org/licenses/LICENSE-2.0
|
|
|
|
|
//
|
|
|
|
|
// Unless required by applicable law or agreed to in writing, software
|
|
|
|
|
// distributed under the License is distributed on an "AS IS" BASIS,
|
|
|
|
|
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
|
|
|
|
|
// See the License for the specific language governing permissions and
|
|
|
|
|
// limitations under the License.
|
2022-10-06 21:50:57 +02:00
|
|
|
|
2020-09-11 21:17:23 +02:00
|
|
|
package com.google.ortools.java;
|
2020-06-10 14:36:44 +02:00
|
|
|
|
2020-09-11 21:17:23 +02:00
|
|
|
import com.google.ortools.Loader;
|
2019-01-09 11:28:14 +01:00
|
|
|
import com.google.ortools.constraintsolver.Assignment;
|
|
|
|
|
import com.google.ortools.constraintsolver.FirstSolutionStrategy;
|
|
|
|
|
import com.google.ortools.constraintsolver.RoutingIndexManager;
|
|
|
|
|
import com.google.ortools.constraintsolver.RoutingModel;
|
|
|
|
|
import com.google.ortools.constraintsolver.RoutingSearchParameters;
|
|
|
|
|
import com.google.ortools.constraintsolver.main;
|
2020-09-23 12:10:52 +02:00
|
|
|
// import java.io.*;
|
|
|
|
|
// import java.text.*;
|
|
|
|
|
// import java.util.*;
|
2019-02-06 09:37:26 +01:00
|
|
|
import java.util.Random;
|
|
|
|
|
import java.util.function.LongBinaryOperator;
|
|
|
|
|
import java.util.function.LongUnaryOperator;
|
|
|
|
|
import java.util.logging.Logger;
|
2019-01-09 11:28:14 +01:00
|
|
|
|
2020-09-11 21:17:23 +02:00
|
|
|
public class RandomTsp {
|
2020-09-23 12:10:52 +02:00
|
|
|
private static Logger logger = Logger.getLogger(RandomTsp.class.getName());
|
2019-02-06 09:37:26 +01:00
|
|
|
|
|
|
|
|
static class RandomManhattan implements LongBinaryOperator {
|
2019-01-09 11:28:14 +01:00
|
|
|
public RandomManhattan(RoutingIndexManager manager, int size, int seed) {
|
|
|
|
|
this.xs = new int[size];
|
|
|
|
|
this.ys = new int[size];
|
|
|
|
|
this.indexManager = manager;
|
|
|
|
|
Random generator = new Random(seed);
|
|
|
|
|
for (int i = 0; i < size; ++i) {
|
|
|
|
|
xs[i] = generator.nextInt(1000);
|
|
|
|
|
ys[i] = generator.nextInt(1000);
|
|
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
|
2019-02-06 09:37:26 +01:00
|
|
|
public long applyAsLong(long firstIndex, long secondIndex) {
|
2019-01-09 11:28:14 +01:00
|
|
|
int firstNode = indexManager.indexToNode(firstIndex);
|
|
|
|
|
int secondNode = indexManager.indexToNode(secondIndex);
|
|
|
|
|
return Math.abs(xs[firstNode] - xs[secondNode]) + Math.abs(ys[firstNode] - ys[secondNode]);
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
private int[] xs;
|
|
|
|
|
private int[] ys;
|
|
|
|
|
private RoutingIndexManager indexManager;
|
|
|
|
|
}
|
|
|
|
|
|
2019-02-06 09:37:26 +01:00
|
|
|
static class ConstantCallback implements LongUnaryOperator {
|
|
|
|
|
public long applyAsLong(long index) {
|
2019-01-09 11:28:14 +01:00
|
|
|
return 1;
|
|
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
static void solve(int size, int forbidden, int seed) {
|
|
|
|
|
RoutingIndexManager manager = new RoutingIndexManager(size, 1, 0);
|
|
|
|
|
RoutingModel routing = new RoutingModel(manager);
|
|
|
|
|
|
|
|
|
|
// Setting the cost function.
|
|
|
|
|
// Put a permanent callback to the distance accessor here. The callback
|
2021-04-02 14:58:16 +02:00
|
|
|
// has the following signature: ResultCallback2<int64_t, int64_t, int64_t>.
|
2019-01-09 11:28:14 +01:00
|
|
|
// The two arguments are the from and to node inidices.
|
2019-02-06 09:37:26 +01:00
|
|
|
LongBinaryOperator distances = new RandomManhattan(manager, size, seed);
|
2019-01-09 11:28:14 +01:00
|
|
|
routing.setArcCostEvaluatorOfAllVehicles(routing.registerTransitCallback(distances));
|
|
|
|
|
|
|
|
|
|
// Forbid node connections (randomly).
|
|
|
|
|
Random randomizer = new Random();
|
|
|
|
|
long forbidden_connections = 0;
|
|
|
|
|
while (forbidden_connections < forbidden) {
|
|
|
|
|
long from = randomizer.nextInt(size - 1);
|
|
|
|
|
long to = randomizer.nextInt(size - 1) + 1;
|
|
|
|
|
if (routing.nextVar(from).contains(to)) {
|
2019-02-06 09:37:26 +01:00
|
|
|
logger.info("Forbidding connection " + from + " -> " + to);
|
2019-01-09 11:28:14 +01:00
|
|
|
routing.nextVar(from).removeValue(to);
|
|
|
|
|
++forbidden_connections;
|
|
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
// Add dummy dimension to test API.
|
2020-09-23 12:10:52 +02:00
|
|
|
routing.addDimension(routing.registerUnaryTransitCallback(new ConstantCallback()), size + 1,
|
|
|
|
|
size + 1, true, "dummy");
|
2019-01-09 11:28:14 +01:00
|
|
|
|
|
|
|
|
// Solve, returns a solution if any (owned by RoutingModel).
|
|
|
|
|
RoutingSearchParameters search_parameters =
|
|
|
|
|
RoutingSearchParameters.newBuilder()
|
|
|
|
|
.mergeFrom(main.defaultRoutingSearchParameters())
|
|
|
|
|
.setFirstSolutionStrategy(FirstSolutionStrategy.Value.PATH_CHEAPEST_ARC)
|
|
|
|
|
.build();
|
|
|
|
|
|
|
|
|
|
Assignment solution = routing.solveWithParameters(search_parameters);
|
|
|
|
|
if (solution != null) {
|
|
|
|
|
// Solution cost.
|
2019-02-06 09:37:26 +01:00
|
|
|
logger.info("Objective : " + solution.objectiveValue());
|
2019-01-09 11:28:14 +01:00
|
|
|
// Inspect solution.
|
|
|
|
|
// Only one route here; otherwise iterate from 0 to routing.vehicles() - 1
|
|
|
|
|
int route_number = 0;
|
2019-02-06 09:37:26 +01:00
|
|
|
String route = "";
|
2020-09-23 12:10:52 +02:00
|
|
|
for (long node = routing.start(route_number); !routing.isEnd(node);
|
|
|
|
|
node = solution.value(routing.nextVar(node))) {
|
|
|
|
|
route += "" + node + " -> ";
|
2019-01-09 11:28:14 +01:00
|
|
|
}
|
2019-02-06 09:37:26 +01:00
|
|
|
logger.info(route + "0");
|
2019-01-09 11:28:14 +01:00
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
public static void main(String[] args) throws Exception {
|
2020-09-11 21:17:23 +02:00
|
|
|
Loader.loadNativeLibraries();
|
2019-01-09 11:28:14 +01:00
|
|
|
int size = 10;
|
|
|
|
|
if (args.length > 0) {
|
|
|
|
|
size = Integer.parseInt(args[0]);
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
int forbidden = 0;
|
|
|
|
|
if (args.length > 1) {
|
|
|
|
|
forbidden = Integer.parseInt(args[1]);
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
int seed = 0;
|
|
|
|
|
if (args.length > 2) {
|
|
|
|
|
seed = Integer.parseInt(args[2]);
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
solve(size, forbidden, seed);
|
|
|
|
|
}
|
|
|
|
|
}
|
