Ensure that exactly one tour exits each node
\(\sum_ x_ = 1, \forall i \in V\)

Include subtour elimination constraints (Miller-Tucker-Zemlin)
\(u_i — u_j + p \cdot x_ \leq p-1, \forall 2 \leq i \neq j \leq n\)

The literature includes a number of alternative formulations. Some of the alternatives to the two-index variable, assignment-based formulation are a two-index variable formulation with the original subtour elimination constraints (see Laporte and Nobert, 1980), a three-index variable formulation (see Bektas, 2006), and a \(k\)-degree center tree-based formulation (see Christofides et al., 1981 and Laporte, 1992).

To solve this integer linear programming problem, we can use one of the NEOS Server solvers in the Mixed Integer Linear Programming (MILP) category. Each MILP solver has one or more input formats that it accepts.

GAMS Model

Click here for a GAMS model for the bayg29 instance from the TSPLIB. The formulation was provided by Erwin Kalvelagen in a blog post here.

If we submit this model to XpressMP with a CPU time limit of 1 hour, we obtain a solution with a total cost of 2176 (gap of 4.3%) and the following tours:

• Tour 1: i13 — i4 — i10 — i20 — i2 — i13
  cost = 60 + 39 + 25 + 49 + 87 = 260
• Tour 2: i13 — i18 — i14 — i17 — i22 — i11 — i15 — i13
  cost = 128 + 32 + 51 + 47 + 63 + 68 + 86 = 475
• Tour 3: i13 — i24 — i8 — i28 — i12 — i6 — i1 — i13
  cost = 56 + 48 + 64 + 71 + 46 + 60 + 82 = 427
• Tour 4: i13 — i29 — i3 — i26 — i9 — i5 — i21 — i13
  cost =160 + 60 + 78 + 57 + 42 + 50 + 82 = 529
• Tour 5: i13 — i19 — i25 — i7 — i23 — i27 — i16 — i13
  cost = 71 + 52 + 72 + 111 + 74 + 48 + 57 = 485

Multiple traveling salesman problem with time windows

The Multiple Traveling Salesman Problem

The Multiple Traveling Salesman Problem (mTSP) in which more than one salesman is allowed is a generalization of the Traveling Salesman Problem (TSP). Given a set of cities, one depot (where m salesmen are located), and a cost metric, the objective of the mTSP is to determine a set of routes for m salesmen so as to minimize the total cost of the m routes. The cost metric can represent cost, distance, or time. The requirements on the set of routes are:

• All of the routes must start and end at the (same) depot.
• There must be at least one city (except depot) in each route.
• Each city must be visited exactly once by only one salesman.

Multiple depots: Instead of one depot, the multi-depot mTSP has a set of depots, with m_j salesmen at each depot j. In the fixed destination version, a salesman returns to the same depot from which he started.

Please keep in mind that this project is based on the 81 cities of Turkey while examining sample solutions given below.

In this part of the homework, we will generate 100,000 random solutions to the fixed destination version of the multi-depot mTSP. The number of depots and salesman per depot will be our parameters. The cost metric will be total distance in kilometers. At the end, we will print the best solution that has the minimum cost among 100,000 random solutions.

Your project must be a valid maven project. mvn clean package must produce an executable jar file named mTSP.jar under the target directory. This can be done via maven plugins such as shade or assembly plugin. Optional parameter finalName can be used to change the name of the shaded artifactId. To parse command line arguments, you must use JewelCLI library.

For example, java -jar target/mTSP.jar -d 5 -s 2 -v would produce something like below. Notice that the last line includes the cost metric: the total distance travelled by all salesmen.

Non-verbose example java -jar target/mTSP.jar -d 2 -s 5 will print city indices instead of city names:

❗ If you don’t follow the aforementioned conventions, you will receive grade of zero (even if you think that your code works perfectly).

In the second part of the homework, we will apply a heuristic algorithm to our fixed destination version of the multi-depot mTSP.

The term heuristic is used for algorithms which find solutions among all possible ones, but they do not guarantee that the optimal will be found. Heuristic algorithms often times used to solve NP-complete problems.

The heuristic will iteratively work on the solution (best of the 100,000 random solutions) obtained from the Part-I. In Part-II, we will define five different move operations, which will be detailed in the following subsections. In each iteration, one move operation will be selected (among five) based on a random manner, and then it will be applied to the current solution. If the move improves the solution (i.e., lessen the total distance travelled) then, we will update the best solution at hand. If not, next iteration will be continued. To implement this logic, you need to devise a strategy to somehow backup the current solution. So that if the subsequent move operation does not improve the solution, it should be possible to rollback to a previous state. It is recommended to do a reach on the Internet using the following keywords: copy constructor, deep cloning, shallow cloning, and marshalling. It is totally up to you to how to implement this logic, you can even write an method that calculates a cost function without applying the move!

Some of the the move operation will involve a process where you need to generate two different random numbers from a given interval. Please write a method to generate two random numbers that are different from each other. Here comes the five move operations that the heuristic will be using.

Swap two nodes in a route. Here, both the route and the two nodes are randomly chosen. In this move we select a random route among all routes and then we swap two nodes. Remember to avoid no-operation, we need to select two nodes that are different from each other. Example of the move: random node indices are 1 and 7, which are shown in bold.

Notice that bold nodes are swapped with each other after the move.

Swap hub with a randomly chosen node in a route. Here, both the route and the node are randomly chosen. In this move we select a random route among all routes and then we replace the hub with a random node. Here it is crucial to update the hub in the remaining routes of the initial hub.

Example of the move: random node index is 10, which is shown in bold.

Notice that bold node is replaced with the hub in the first route. Notice also that hub of the second route is updated. Nodes of the second route remain intact.

This is similar to swapNodesInRoute, but this time we will be using two different routes. In this move we select two random routes (that are different) among all routes. Then, we select a random node in each route and then swap them. Here it is important to select two routes that are different from each other, otherwise this move will be identical to swapNodesInRoute.

Example of the move: random node indices are 6 and 7, which are shown in bold.

Notice that bold nodes are swapped with each other after the move. Notice also that this is a cross-route operation.

This is similar to swapNodesInRoute: instead of swapping, we delete the source node, and then insert it to right of the destination node. Note that this operation is only valid on a route having more than two nodes.

Example of the move: random node indices are 2 and 6, which are shown in bold.

Notice that first bold node (source) is deleted and then inserted right after the second bold node (destination).

This is similar to swapNodesBetweenRoutes: instead of swapping, we delete the source node, and then insert it to right of the destination node.

Example of the move: random node indices are 11 and 4, which are shown in bold.

Notice that first bold node (source) is deleted and then inserted right after the second bold node (destination). Notice also that this is a cross-route operation. The number of nodes of the first route is decreased by one. The number of nodes of the second route is increased by one. Thus, first node must have more than two nodes. Otherwise, solution will be invalid after the deletion.

Do 5,000,000 iterations. At the end you will obtain a much better solution than that those of Part-I. Here is one of the solutions that I obtained.

Notice that 14,399km is less than 51,631km. Also print counts of the moves that caused gains:

Which move does the heuristic algorithm benefit the most?

Submit your solution -d 4 -s 2 🆕

Save your best solution (for numDepots=4 and numSalesmen=2) in a file named solution.json and save it at the top-level directory (near the pom.xml and the README.md files). Commit and push your solution.json file to your repository. Here it does not matter how you obtain best solution. It can be be obtained from any heuristic algorithm (random or hill climbing). Or you can use commercial solvers if you want to: GAMS, Gurobi, CPLEX etc. You can even construct it manually!! An example of a solution rendered in JSON format is as follows:

The grading system will checkout your solution.json file and will calculate its cost function. Of course the solution must be valid. Some sanity checks will be performed. Any solution violating one of the rules will be rejected by the scoring system.

Other than that, we will run your program on the server. The solution that your program will find/produce will be saved into a json file too (same format). But this time the name of the json file will include the parameters. If the program ran with -d 4 -s 2 , the result will be saved into solution_d4s2.json

Checkout the Leaderboard

See which solutions have the best scores. Coming soon, stay tuned!

❗ For Part-II you will be teaming up with students of Industrial Engineering Department. Prepare yourselves.