Travelling salesman problem variant without returning to the starting point

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()

• I am not completely sure about what your problem is. But if it is a "TSP with a fixed starting point and no return to start" you can solve an ordinary TSP with all in-going arcs to the starting point having zero cost.
– Sune
Apr 26 at 13:04
• I have updated the Input Martix as you said . but still not getting the corrected result. here the updated matrix. { "data" : [ [0, 2451, 713, 200, 16310, 1374, 2408], [0, 0, 1745, 1524, 831, 1240, 959], [0, 1745, 0, 355, 920, 803, 1737], [0, 1524, 355, 0, 700, 862, 1395], [0, 831, 920, 700, 0, 663, 1021], [0, 1240, 803, 862, 663, 0, 1681], [0, 959, 1737, 1395, 1021, 1681, 0] ] } Apr 26 at 14:22
• I think a methematical model, or a more detailed description of the problem, would help. As I said in the comment before, I am not completely sure what problem you want to solve.
– Sune
Apr 26 at 18:53
• Hi @Sune I think its working now. I provided the wrong input to the algorithm. Thanks for your help. Apr 27 at 5:18
• that's good you figured it out. Did my comment answer your question. If so, I will turn it into an answer for future visiters
– Sune
Apr 27 at 6:09

1 Answer

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".