tspcyber.py

# Travelling Salesman Problem Cyberjaya
#
# Usage:
# python tspcyber.py [<destination> ...]
# 
#   If no destination is passed in, it's assumed that rider
#   will travel to all destinations.
#
# destination can be:
#   dpulze, mmu, cyberia, mutiaraville, mdec, ntt,
#   lkw, magic, domain, shell, mcmc, serin

import sys
from ortools.constraint_solver import pywrapcp
from ortools.constraint_solver import routing_enums_pb2

# Distance callback
class CreateDistanceCallback(object):
  """Create callback to calculate distances between points."""
  def __init__(self, chosen_dest_names):
    """Array of distances between points."""

    # Cities
    self.all_dest_name = ["dpulze", "mmu", "cyberia", "mutiaraville", "mdec", "ntt",
                          "lkw", "magic", "domain", "shell", "mcmc", "serin"]

    self.matrix = [
    [   0,    5,    6,    8,    4,    7,   12,    6,    4,    2,    5,    9], # DPulze
    [   5,    0,    2,    4,    7,    7,   10,    9,    6,    5,    7,    4], # MMU
    [   6,    2,    0,    2,    6,    7,   15,    7,    2,    6,    9,    6], # Cyberia
    [   8,    4,    2,    0,    7,    9,   15,    8,    5,   10,   10,    5], # Mutiara Ville
    [   4,    7,    6,    7,    0,    2,    6,    4,    6,    5,    3,   10], # MDEC
    [   7,    7,    7,    9,    2,    0,    5,    4,    6,    4,    4,   12], # NTT
    [  12,   10,   15,   15,    6,    5,    0,   12,    8,    5,    8,   15], # Limkokwing
    [   6,    9,    7,    8,    4,    4,   12,    0,    5,   10,    5,    4], # MaGIC
    [   4,    6,    2,    5,    6,    6,    8,    5,    0,    7,    6,    2], # Domain
    [   2,    5,    6,   10,    5,    4,    5,   10,    7,    0,    2,   10], # Shell
    [   5,    7,    9,   10,    3,    4,    8,    5,    6,    2,    0,   12], # MCMC
    [   9,    4,    6,    5,   10,   12,   15,    4,    2,   10,   12,    0]] # Serin

    # Build a lookup index
    if len(chosen_dest_names) > 1:
      self.lookup_index = [0]
      for dest in chosen_dest_names:
        try:
          self.lookup_index.append(self.all_dest_name.index(dest))
        except ValueError as err:
          print("Destination not recognized: {0}".format(err))
          exit(0)
    else:
      self.lookup_index = [i for i in range(len(self.all_dest_name))]

  def Distance(self, from_node, to_node):
    return self.matrix[self.lookup_index[from_node]][self.lookup_index[to_node]]

def main():
  # Get the delivery destinations from user inputs
  if len(sys.argv) > 1:
    chosen_dest_names = sys.argv[1:]
    tsp_size = len(chosen_dest_names) + 1
    print("Chosen delivery destinations: {0}".format(chosen_dest_names))
  else:
    chosen_dest_names = ["mmu", "cyberia", "mutiaraville", "mdec", "ntt",
                         "lkw", "magic", "domain", "shell", "mcmc", "serin"]
    tsp_size = 12
 
  # Dpulze isnt in args
  
  print("TSP size: {0}".format(tsp_size))

  # Create routing model
  if tsp_size > 0:
    # TSP of size tsp_size
    # Second argument = 1 to build a single tour (it's a TSP).
    # Nodes are indexed from 0 to tsp_size - 1. By default the start of
    # the route is node 0.
    routing = pywrapcp.RoutingModel(tsp_size, 1, 0)
    search_parameters = pywrapcp.RoutingModel.DefaultSearchParameters()

    # Setting first solution heuristic: the
    # method for finding a first solution to the problem.
    # Find the enums here: https://github.com/google/or-tools/blob/master/src/constraint_solver/routing_enums.proto
    search_parameters.first_solution_strategy = (
        routing_enums_pb2.FirstSolutionStrategy.GLOBAL_CHEAPEST_ARC)
        # routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)

    # Create the distance callback, which takes two arguments (the from and to node indices)
    # and returns the distance between these nodes.

    dist_between_nodes = CreateDistanceCallback(chosen_dest_names)
    dist_callback = dist_between_nodes.Distance
    routing.SetArcCostEvaluatorOfAllVehicles(dist_callback)
    # Solve, returns a solution if any.
    assignment = routing.SolveWithParameters(search_parameters)

    # Hack!!
    chosen_dest_names.insert(0, 'dpulze')

    if assignment:
      # Solution cost.
      print("Total time required: " + str(assignment.ObjectiveValue()) + " minutes\n")
      # Inspect solution.
      # Only one route here; otherwise iterate from 0 to routing.vehicles() - 1
      route_number = 0
      index = routing.Start(route_number) # Index of the variable for the starting node.
      route = ''
      while not routing.IsEnd(index):
        # Convert variable indices to node indices in the displayed route.
        route += str(chosen_dest_names[routing.IndexToNode(index)]) + ' -> '
        index = assignment.Value(routing.NextVar(index))
      route += str(chosen_dest_names[routing.IndexToNode(index)])
      print("Route:\n\n" + route)
    else:
      print('No solution found.')
  else:
    print('Specify an instance greater than 0.')

if __name__ == '__main__':
  main()