CODEWITHSUNDEEP
ampl
Hansen2
Hansen2

Reputation: 13

Traveling salesman ampl

I am working on a Traveling salesman problem and can't figure how to solve it. The problem contains ten workers, ten workplaces where they should be driven to and one car driving them one by one. There is a cost of $1.5 per km. Also, all the nodes (both workers and workplaces) are positioned in a 10*10 matrix and the distance between each block in the matrix is 1 km.
The problem should be solved using AMPL.

I have already calculated the distances between each coordinate in excel and have copy pasted the matrix to the dat.file in AMPL. 

 This is my mod.file so far (without the constrains): 

    param D > 0;
    param D > 0;
    set A = 1..W cross 1..D; 

    var x{A};   # 1 if the route goes from person p to work d, 
               # 0 otherwise

    param cost;
    param distance;

    minimize Total_Cost:
        sum {(w,d) in A} cost * x[w,d];

Upvotes: 0

Views: 1590

Answers (1)

G_B
G_B

Reputation: 1573

OK, so your route looks like: start-worker 1-job 1-worker 2-job 2-worker 3-job-3-...-job 10-end (give or take start & end points, depending on how you formulate the problem.

That being the case, the "worker n-job n" parts of your route are predetermined. You don't need to include "worker n-job n" costs in the route optimisation, because there's no choice about those parts of the route (though you do need to remember them for calculating total cost, of course).

So what you have here is really a basic TSP with 10 "destinations" (each representing a single worker and their assigned job) but with an asymmetric cost matrix (because cost of travel from job i to worker j isn't the same as cost of travel from job j to worker i).

If you already have an implementation for the basic TSP, it should be easy to adapt. If not, then you need to write one and make that small change for an asymmetric cost matrix. I've seen two different approaches to this in AMPL.

2-D decision matrix with subtour elimination

Decision variable x{1..10,1..10} is defined as: x[i,j] = 1 if the route goes from job i to job j, and 0 otherwise. Constraints require that every row and column of this matrix has exactly one 1.

The challenging part with this approach is preventing subtours (i.e. the "route" produced is actually two or more separate cycles instead of one large cycle). It sounds like your current attempt is at this stage.

One solution to the problem of subtours is an iterative approach:

  1. Write an implementation that includes all requirements except for subtour prevention.
  2. Solve with this implementation.
  3. Check the resulting solution for subtours.
  4. If no subtours are found, return the solution and end.
  5. If you do find subtours, add a constraint which prevents that particular subtour. (Identify the arcs involved in the subtour, and set a constraint which implies they can't all be selected.) Then go to #2.

For a small exercise you may be able to do the subtour elimination by hand. For a larger exercise, or if your lecturer doesn't like that approach, you can create a .run that automates it. See Bob Fourer's post of 31/7/2013 in this thread for an example of implementation.

3-D decision matrix with time dimension

Under this approach, you set up a decision variable x{1..10,1..10,1..10} where x[i,j,t] = 1 if the route goes from job i to worker j at time t, and 0 otherwise. Your constraints then require that the route goes to and from each job/worker combination exactly once, that if it goes to worker i at time t then it must go from job i at time t+1 (excepting first/last issues), that it's doing exactly one thing at time t, and that the endpoint at time 10 matches the startpoint at time 1 (assuming you want a circuit).

This prevents subtours, because it forces a route that starts at some point at time 1, returns to that point at time 10, and doesn't visit any other point more than once - meaning that it has to go through all of them exactly once.

Upvotes: 2

Related Questions