cstsp.cs

// Copyright 2010-2018 Google LLC
// 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.

using System;
using System.Collections.Generic;
using Google.OrTools.ConstraintSolver;

class Tsp
{
  class RandomManhattan {
    public RandomManhattan(RoutingIndexManager manager, int size, int seed)
    {
      this.xs_ = new int[size];
      this.ys_ = new int[size];
      this.manager_ = manager;
      Random generator = new Random(seed);
      for (int i = 0; i < size; ++i)
      {
        xs_[i] = generator.Next(1000);
        ys_[i] = generator.Next(1000);
      }
    }

    public long Call(long first_index, long second_index) {
      int first_node = manager_.IndexToNode(first_index);
      int second_node = manager_.IndexToNode(second_index);
      return Math.Abs(xs_[first_node] - xs_[second_node]) +
          Math.Abs(ys_[first_node] - ys_[second_node]);
    }

    private readonly int[] xs_;
    private readonly int[] ys_;
    private readonly RoutingIndexManager manager_;
  };

  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
    // has the following signature: ResultCallback2<int64, int64, int64>.
    // The two arguments are the from and to node inidices.
    RandomManhattan distances = new RandomManhattan(manager, size, seed);
    routing.SetArcCostEvaluatorOfAllVehicles(
        routing.RegisterTransitCallback(distances.Call));

    // Forbid node connections (randomly).
    Random randomizer = new Random();
    long forbidden_connections = 0;
    while (forbidden_connections < forbidden) {
      long from = randomizer.Next(size - 1);
      long to = randomizer.Next(size - 1) + 1;
      if (routing.NextVar(from).Contains(to)) {
        Console.WriteLine("Forbidding connection {0} -> {1}", from, to);
        routing.NextVar(from).RemoveValue(to);
        ++forbidden_connections;
      }
    }

    // Add dummy dimension to test API.
    routing.AddDimension(
        routing.RegisterUnaryTransitCallback((long index) => {return 1;}),
        size + 1,
        size + 1,
        true,
        "dummy");

    // Solve, returns a solution if any (owned by RoutingModel).
    RoutingSearchParameters search_parameters =
        operations_research_constraint_solver.DefaultRoutingSearchParameters();
    // Setting first solution heuristic (cheapest addition).
    search_parameters.FirstSolutionStrategy =
        FirstSolutionStrategy.Types.Value.PathCheapestArc;

    Assignment solution = routing.SolveWithParameters(search_parameters);
    Console.WriteLine("Status = {0}", routing.GetStatus());
    if (solution != null) {
      // Solution cost.
      Console.WriteLine("Cost = {0}", solution.ObjectiveValue());
      // Inspect solution.
      // Only one route here; otherwise iterate from 0 to routing.vehicles() - 1
      int route_number = 0;
      for (long node = routing.Start(route_number);
           !routing.IsEnd(node);
           node = solution.Value(routing.NextVar(node))) {
        Console.Write("{0} -> ", node);
      }
      Console.WriteLine("0");
    }
  }

  public static void Main(String[] args)
  {
    int size = 10;
    if (args.Length > 0) {
      size = Convert.ToInt32(args[0]);
    }
    int forbidden = 0;
    if (args.Length > 1) {
      forbidden = Convert.ToInt32(args[1]);
    }
    int seed = 0;
    if (args.Length > 2) {
      seed = Convert.ToInt32(args[2]);
    }

    Solve(size, forbidden, seed);
  }
}