Decision Optimization

 View Only
  • 1.  TSP complete trip

    Posted Wed April 14, 2021 06:10 AM
    Dear All,

    I have binary decision variable x[i][j] for TSP problem. it given me value of x in table but I want to get sequence of route (in order) e.g. 1-2-5-3-6-7-4-1.
    how can I do this

    ------------------------------
    Muhammad Usama
    ------------------------------

    #DecisionOptimization


  • 2.  RE: TSP complete trip

    Posted Wed April 14, 2021 08:20 AM
    Hi,

    in https://www.linkedin.com/pulse/how-opl-alex-fleischer/

    you can have a look at

    TSP (Traveling Salesman Problem) in OPL with scheduling, with Constraint Programming, or with remove circuits and MTZ

    ------------------------------
    [Alex] [Fleischer]
    [EMEA CPLEX Optimization Technical Sales]
    [IBM]
    ------------------------------



  • 3.  RE: TSP complete trip

    Posted Fri March 31, 2023 07:50 AM

    o get the sequence of the route for the TSP problem, you can use a simple algorithm to traverse the path starting from node 1 (assuming it is the starting node).

    1. Initialize an empty list to store the sequence of the route. Let's call it 'route'.
    2. Start at node 1 and add it to the 'route' list.
    3. Find the next node j with the highest value of x[i][j] where i is the current node in the 'route' list.
    4. Add j to the 'route' list.
    5. Repeat step 3 and 4 until all nodes have been added to the 'route' list.
    6. Add node 1 to the end of the 'route' list to complete the loop.

    Here is a sample Python code to implement the algorithm:

    This code assumes that the values of x[i][j] are stored in a 2D array x, where x[i][j] is the probability of traveling from node i to node j. The variable n represents the number of nodes.

    n = len(x) # number of nodes
    
    # Initialize the 'route' list with the starting node 1
    route = [1]
    
    # Traverse the path
    while len(route) < n+1:
        i = route[-1] # current node
        j = max(range(n), key=lambda x: x[i-1][x]) + 1 # find the next node with the highest value of x[i][j]
        route.append(j)
    
    # Add node 1 to the end of the 'route' list to complete the loop
    route.append(1)
    
    # Print the sequence of the route
    print('-'.join(map(str, route)))
    


    ------------------------------
    Ashley Roy
    ------------------------------