Solving Travelling Salesman Problem with JgraphT and JGAP libraries

Recently, I came across a real life problem of TSP. In this problem, user is assigned a list of cities to visit, but is not required to come back. At end point, he is again assigned to visit new set of cities.

This turns out to be a Hamiltonian path problem and not Hamiltonian cycle. I evaluated 2 different libraries for it namely JgraphtT and JGAP.

JgraphT seems to use MST-prim based approximation algorithm, where Cost of tour in worst case is 2*optimalCost. It computes in polynomial time and is very fast. To solve Hamiltonian path problem, you can add an extra vertex say city 0. Next add edges from all vertices to city 0 with weight 0 (Remember input graph has to be a complete graph). After computation remove the city 0 and all the corresponding edges.

Code for this is: 

import java.util.ArrayList;
import java.util.List;
import java.util.Set;

import org.jgrapht.alg.HamiltonianCycle;
import org.jgrapht.graph.DefaultWeightedEdge;
import org.jgrapht.graph.SimpleWeightedGraph;


/**
 * Using jgrpaht library
 * 
 * @author pratyush
 * 
 */
public class HamiltonianCycleHelper {

 private SimpleWeightedGraph<Long, DefaultWeightedEdge> g = new SimpleWeightedGraph<Long, DefaultWeightedEdge>(
   DefaultWeightedEdge.class);

 public void addVertex(Long id) {
  g.addVertex(id);
 }

 public void addVertex(List<Long> ids) {
  for (Long id : ids) {
   g.addVertex(id);
  }
 }

 public void addEdge(Long source, Long destination, Long weight) {
  DefaultWeightedEdge edge = g.addEdge(source, destination);
  g.setEdgeWeight(edge, weight);
 }

 public List<Long> execute() {
  Set<Long> vertices = g.vertexSet();
  addVertex(0l);
  System.out.println(vertices);
  for (Long v : vertices) {
   if (v.longValue() == 0)
    continue;
   DefaultWeightedEdge edge = g.addEdge(0l, v);
   g.setEdgeWeight(edge, 0);
  }
  List<Long> output = HamiltonianCycle
    .getApproximateOptimalForCompleteGraph(g);
  output.remove(Long.valueOf(0l));
  return output;
 }

 public static void main(String args[]) {
  List<Long> vertices = new ArrayList<Long>();
  vertices.add(1l);
  vertices.add(2l);
  vertices.add(3l);
  HamiltonianCycleHelper h = new HamiltonianCycleHelper();
  h.addVertex(vertices);
  h.addEdge(1l, 2l, 1l);
  h.addEdge(1l, 3l, 5l);
  h.addEdge(2l, 3l, 3l);
  List<Long> output = h.execute();
  System.out.println(output);
 }
}

JgraphT results were good, but I wanted worst case cost to be better. Even though, I don’t know about genetic algorithms, I tried out JGAP library examples and it worked pretty well. If you check the example source code, you can modify the SalesmanFitnessFunction.java by commenting the return path:

protected double evaluate(final IChromosome a_subject) {
  double s = 0;
  Gene[] genes = a_subject.getGenes();
  for (int i = 0; i < genes.length - 1; i++) {
   s += m_salesman.distance(genes[i], genes[i + 1]);
  }
  // add cost of coming back:
  //s += m_salesman.distance(genes[genes.length - 1], genes[0]);
  return Integer.MAX_VALUE / 2 - s;
}

Also, modify TravellingSalesman.java, instead of just

TravellingSalesman t = new TravellingSalesman();
IChromosome optimal = t.findOptimalPath(null);

Try something like:

public List<Long> compute() throws Exception {
  IChromosome tempChromosome=null;
  int maxEvolution = 12;
  int maxPopulation = 12;
  int steps = 10;
  List<Long> output = new ArrayList<Long>();
  double currentFitness = 0;
  //Give few tries to find avg best path
  while (maxEvolution <= 512) {
   Configuration.reset();
   setMaxEvolution(maxEvolution);
   setPopulationSize(maxPopulation);
   tempChromosome = findOptimalPath(null);
   if (tempChromosome.getFitnessValue() > currentFitness) {
    currentFitness = tempChromosome.getFitnessValue();
    output = new ArrayList<Long>();
    int geneVal;
    Gene g[] = tempChromosome.getGenes();
    for (int i = 0; i < g.length; i++) {
     IntegerGene geneA = (IntegerGene) g[i];
     geneVal = geneA.intValue();
     output.add(geneVal);
    }
   }
   maxEvolution += steps;
   maxPopulation += steps;   
  }
  return output;
 }

Increasing the chromosome population makes computation slow, but results much better. Happy TSP solving !