3
$\begingroup$

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()
$\endgroup$
6
  • 5
    $\begingroup$ 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. $\endgroup$
    – Sune
    Apr 26, 2021 at 13:04
  • $\begingroup$ 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] ] } $\endgroup$
    – dev21
    Apr 26, 2021 at 14:22
  • $\begingroup$ 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. $\endgroup$
    – Sune
    Apr 26, 2021 at 18:53
  • $\begingroup$ Hi @Sune I think its working now. I provided the wrong input to the algorithm. Thanks for your help. $\endgroup$
    – dev21
    Apr 27, 2021 at 5:18
  • $\begingroup$ 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 $\endgroup$
    – Sune
    Apr 27, 2021 at 6:09

2 Answers 2

7
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.