Travelling salesman problem¶

/********** Tsp.java **********/

import java.util.*;
import java.io.*;
import localsolver.*;

public class Tsp {
	// Number of cities
	int nbCities;

	// Vector of distance between two cities
	long[][] distanceWeight;

	// LocalSolver.
    LocalSolver localsolver;

	// Decision variables.
	LSExpression cities;

    // Objective
	LSExpression obj;

    /* Reads instance data. */
    void readInstance(String fileName) {
        try {
            Scanner input = new Scanner(new File(fileName));
            
            // The input files follow the TSPLib "explicit" format.
		    String str = new String();
		    String[] pch = new String[2];
            int i = 0;
		    while (true) {
		        str = input.nextLine();
			    pch = str.split(":");
			    if  (pch[0].compareTo("DIMENSION")==0){
		            nbCities = Integer.parseInt(pch[1].trim());
		            System.out.println("Number of cities = " + nbCities);
		        } else if (pch[0].compareTo("EDGE_WEIGHT_SECTION")==0){
				    break;
                }
            }

            // Distance from i to j
		    distanceWeight = new long[nbCities][nbCities];
		    for(i = 0; i < nbCities; i++) {
                for (int j = 0; j < nbCities; j++) {
			        distanceWeight[i][j] = input.nextInt();
                }
		    }
            input.close();
                        
        } catch (IOException ex) {
            ex.printStackTrace();
        }
    }

    void solve(int limit) {
        try {
            localsolver = new LocalSolver();

            /* Declares the optimization model. */
            LSModel model = localsolver.getModel();

            // A list variable: cities[i] is the index of the ith city in the tour
			cities = model.listVar(nbCities);

            // All cities must be visited
			model.constraint(model.eq(model.count(cities), nbCities));

            // Create a LocalSolver array for the distance matrix in order to be able to 
            // access it with "at" operators.
            LSExpression distanceArray = model.array();
            for(int i = 0; i < nbCities; i++){
                LSExpression row = model.array(distanceWeight[i]);
                distanceArray.addOperand(row);
            }
	
			// As the operator [] is not overloaded, create the explicit list of cities
            LSExpression[] explicitCities = new LSExpression[nbCities];
            for(int i = 0; i < nbCities; i++){
                explicitCities[i] = model.at(cities, i);
			}

			// Distance of the arc reaching the ith city 
			LSExpression[] distance = new LSExpression[nbCities];
            distance[0] = model.at(distanceArray, explicitCities[nbCities-1], explicitCities[0]);
			for(int i = 1; i < nbCities; i++){
                distance[i] = model.at(distanceArray, explicitCities[i-1], explicitCities[i]);
			}

            // Minimize the total distance
			obj = model.sum(distance);
			model.minimize(obj);

            model.close();

            /* Parameterizes the solver. */
            LSPhase phase = localsolver.createPhase();
            phase.setTimeLimit(limit);

            localsolver.solve();

        } catch (LSException e) {
            System.out.println("LSException:" + e.getMessage());
            System.exit(1);
        }

    }

    /* Writes the solution in a file */
    void writeSolution(String fileName) {
        try {
            BufferedWriter output = new BufferedWriter(new FileWriter(fileName));

		    output.write(obj.getValue() + "\n");
            LSCollection citiesCollection = cities.getCollectionValue();
            for (int i = 0; i < nbCities; i++) {
                output.write(citiesCollection.get(i) + " ");
            }
            output.write("\n");
            output.close();
	    } catch (IOException ex) {
            ex.printStackTrace();
        }
    }
    
    public static void main(String[] args) {
        if (args.length < 1) {
            System.out.println("Usage: Tsp inputFile [outputFile] [timeLimit]");
            System.exit(1);
        }

        String instanceFile = args[0];
        String outputFile = args.length > 1 ? args[1] : null;
        String strTimeLimit = args.length > 2 ? args[2] : "5";

        Tsp model = new Tsp();
        model.readInstance(instanceFile);
        model.solve(Integer.parseInt(strTimeLimit));
        if(outputFile != null) {
            model.writeSolution(outputFile);
        }
    }

}