Decision Optimization

 View Only
Expand all | Collapse all

travelling salesman problem

  • 1.  travelling salesman problem

    Posted Tue January 13, 2015 07:15 AM

    Originally posted by: max__x


    


in 
OPL model and script for Symmetric Travelling Salesman Problem, there is code:

tuple 
Subtour { 
int 
size; 
int 
subtour[Cities]; }
{Subtour} subtours = ...;

     

    but after I input the code, it says not defined subtours, can any one tell me how to define it.

    Is that means I need to define the subtours in the data, file ?

    Many thanks.

     

    ‹


    #DecisionOptimization
    #OPLusingCPLEXOptimizer


  • 2.  Re: travelling salesman problem

    Posted Tue January 13, 2015 02:32 PM

    Hi

    you should have a look at the example in

    CPLEX_Studio1261\opl\examples\opl\models\TravelingSalesmanProblem

    regards


    #DecisionOptimization
    #OPLusingCPLEXOptimizer


  • 3.  Re: travelling salesman problem

    Posted Tue January 13, 2015 05:57 PM

    Originally posted by: max__x


    Dear AlexFleischer, I cannot find the example you give, since the website of the attached cannot be found.

    can you tell me directly ?

    my code is: 
    // Cities
     int     n       = ...;
     range   cities  = 1..n;
     range i =1..n;
     range j =1..n;
     
     // Edges -- sparse set
     tuple       edge        {int i; int j;}
     setof(edge) Edges       = {<i,j> | ordered i,j in cities};
     int         distance[i][j] = ...; 
     // Decision variables
     dvar boolean x[i][j];
     
     tuple Subtour { int size; int subtour[cities]; }
     {Subtour} subtours = ...;
     
     
     
    // Objective
     minimize sum (i in cities, j in cities) distance[i][j]*x[i][j];
     subject to {
        
        // Each city is linked with two other cities
       forall (j in cities)
             flow_in:
             sum (i in cities : i!=j) x[i][j] ==1;
             
           forall (i in cities)
             flow_out:
             sum (j in cities : j!=i) x[i][j] ==1;
             
       // Subtour elimination constraints.
        forall (s in subtours)
            sum (i in cities : s.subtour[i] != 0)
               x[minl(i, s.subtour[i]), maxl(i, s.subtour[i])]
               <= s.size-1;
               
     };

    Actually I want to solved when n=10, and all the distance between each pair of cities has been defined: distance[i][j]. The problem of this code is said the subtour is not defined, can you tell me how to define it??

     


    #DecisionOptimization
    #OPLusingCPLEXOptimizer


  • 4.  Re: travelling salesman problem

    Posted Wed January 14, 2015 09:21 AM

    Hi

    CPLEX_Studio1261\opl\examples\opl\models\TravelingSalesmanProblem is not a web link but a folder in the CPLEX product.

    To make your example work if the only error is about subtours then in the .dat you may write

    subtours={};

    regards


    #DecisionOptimization
    #OPLusingCPLEXOptimizer


  • 5.  Re: travelling salesman problem

    Posted Wed January 14, 2015 10:34 AM

    Originally posted by: max__x


    Yes, it was just the error of subtours, and the I was wrong to write the format of subtours. And now I have fixed it.

    Another question is when the city number get larger, there are so many suboturs need to define, do you know any convenient way to define subours? Because, when the city number is 10, there are so many subtours in this case.

    thank you

     


    #DecisionOptimization
    #OPLusingCPLEXOptimizer


  • 6.  Re: travelling salesman problem

    Posted Thu July 21, 2016 12:36 PM