Travelling salesman problem variant without returning to the starting point

Question

I tried the code provided on the link : https://developers.google.com/optimization/routing/tsp

The actual requirement is to traverse all paths without returning to the start point with minimum distance to travel.

Then I found this link on stackoverflow https://stackoverflow.com/a/7158721/3016453

I added a dummy point and run the first algorithm but not get the expected output. But this is upvoted more than 35 times. I don't know where I am wrong.

I ran the below code with both above-mentioned method:

import json

import flask
import numpy as np
from flask import request, jsonify
from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp

app = flask.Flask(__name__)
app.config["DEBUG"] = True


def create_data_model(distance_input_matrix):
    """Stores the data for the problem."""
    data = {'distance_matrix': distance_input_matrix, 'num_vehicles': 1, 'depot': 0}
    # data['distance_matrix'] = [
    #     [0, 2451, 713, 1018, 1631, 1374, 2408, 213, 2571, 875, 1420, 2145, 1972],
    #     [2451, 0, 1745, 1524, 831, 1240, 959, 2596, 403, 1589, 1374, 357, 579],
    #     [713, 1745, 0, 355, 920, 803, 1737, 851, 1858, 262, 940, 1453, 1260],
    #     [1018, 1524, 355, 0, 700, 862, 1395, 1123, 1584, 466, 1056, 1280, 987],
    #     [1631, 831, 920, 700, 0, 663, 1021, 1769, 949, 796, 879, 586, 371],
    #     [1374, 1240, 803, 862, 663, 0, 1681, 1551, 1765, 547, 225, 887, 999],
    #     [2408, 959, 1737, 1395, 1021, 1681, 0, 2493, 678, 1724, 1891, 1114, 701],
    #     [213, 2596, 851, 1123, 1769, 1551, 2493, 0, 2699, 1038, 1605, 2300, 2099],
    #     [2571, 403, 1858, 1584, 949, 1765, 678, 2699, 0, 1744, 1645, 653, 600],
    #     [875, 1589, 262, 466, 796, 547, 1724, 1038, 1744, 0, 679, 1272, 1162],
    #     [1420, 1374, 940, 1056, 879, 225, 1891, 1605, 1645, 679, 0, 1017, 1200],
    #     [2145, 357, 1453, 1280, 586, 887, 1114, 2300, 653, 1272, 1017, 0, 504],
    #     [1972, 579, 1260, 987, 371, 999, 701, 2099, 600, 1162, 1200, 504, 0],
    # ]  # yapf: disable
    return data


def print_solution(manager, routing, solution):
    """Prints solution on console."""
    # print('Objective: {} miles'.format(solution.ObjectiveValue()))
    index = routing.Start(0)
    # plan_output = 'Route for vehicle 0:\n'
    plan_output = ''
    route_distance = 0
    while not routing.IsEnd(index):
        plan_output += '{}->'.format(manager.IndexToNode(index))
        previous_index = index
        index = solution.Value(routing.NextVar(index))
        route_distance += routing.GetArcCostForVehicle(previous_index, index, 0)
    plan_output += '{}'.format(manager.IndexToNode(index))
    return plan_output
    # print(plan_output)
    # plan_output += 'Route distance: {}miles\n'.format(route_distance)


def main(distance_input_matrix=None):
    """Entry point of the program."""
    # Instantiate the data problem.
    data = create_data_model(distance_input_matrix)

    # Create the routing index manager.
    manager = pywrapcp.RoutingIndexManager(len(data['distance_matrix']),
                                           data['num_vehicles'], data['depot'])

    # Create Routing Model.
    routing = pywrapcp.RoutingModel(manager)

    def distance_callback(from_index, to_index):
        """Returns the distance between the two nodes."""
        # Convert from routing variable Index to distance matrix NodeIndex.
        from_node = manager.IndexToNode(from_index)
        to_node = manager.IndexToNode(to_index)
        return data['distance_matrix'][from_node][to_node]

    transit_callback_index = routing.RegisterTransitCallback(distance_callback)

    # Define cost of each arc.
    routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

    # Setting first solution heuristic.
    search_parameters = pywrapcp.DefaultRoutingSearchParameters()
    search_parameters.first_solution_strategy = (
        routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)

    # Solve the problem.
    solution = routing.SolveWithParameters(search_parameters)

    # Print solution on console.
    if solution:
        return print_solution(manager, routing, solution)


@app.route('/', methods=['GET'])
def home():
    return main()


@app.route('/optimize', methods=['POST'])
def optimize():
    if request.json:
        data_matrix = request.json['data']
        narrows = len(data_matrix)  # 3 rows in your example
        narcs = len(data_matrix[0])
        a = np.zeros((narrows + 1, narcs + 1), dtype='int32').tolist()
        for i in range(len(data_matrix)):
            for j in range(len(data_matrix[i])):
                a[i][j] = data_matrix[i][j]
        #result = main(a)
        result = main(data_matrix)
        r_l = result.split('->')
        #r_l.remove(str(narrows))
        return jsonify({'data': r_l})


app.run()

Answer 1

A TSP with a fixed starting point and no return to start, can be solved as an ordinary TSP with all the in-going arcs to the starting point having a cost of zero. That way the return to the starting point is "for free" and the TSP solver only focuses on the remaining part of the tour, giving you an optimal "open TSP".

Answer 2

The examples on https://developers.google.com/optimization/routing/tsp seem, I believe, to be based on SYMMETRIC TSPs (i.e., distance between nodes are equal regardless of direction).

If you want it to act like as @Sune points out, you'll need an ASYMMETRIC TSP SOLVER which yet adds another higher level of complexity to the problem.