This mini-project is realized within the course 0S01 - Fondements de la Recherche Opérationnelle (Fundamentals of Operations Research) for student of the Master program Optimisation et Securité des Systèmes (Optimization and Systems Safety), semester Autumn 2012, at University of Technology of Troyes, France.
The original French document Relaxation-lagrangienne-pour-le-probleme-du-voyageur-de-commerce presents the theory foundations, algorithms, as well as task assignments of the project. I selectively translate some important parts of this document into English at Theory-foundation_brief.
The report (in French) of the project is at OS01_Rapport-du-projet.
The algorithms in this project are implemented using Matlab.
We can find all source programs (.m files), that have been optimized for code performance (speed, memory) and clarification, together with a related synthesis note at folder Matlab-code.
There are 5 test files in folder TSPLIB:
| TSPLIB |
|---|
| bier127.tsp |
| eil51.tsp |
| eil76.tsp |
| pr76.tsp |
| st70.tsp |
The number in the filename is the number of nodes. These files, whose types are “.tsp”, are readable with a text editor (notepad, VBA editor, Visual C++ editor, etc.). In these files, notice some important details below:
- The optimal cost is provided on line 1.
- The number of nodes is on line 4. For example, test file eil51.tsp has “DIMENSION: 51” which means there are 51 nodes.
- From line 7 are the node number i and its coordinates (xi, yi).
We can copy these files into Excel sheets and simplify the format. For example, after eliminating the first six line in each file, the simplified versions with extension “.txt” are stored in folder TSPLIB simplified.
-
Task 5 - Evaluation of the method on test problems. For 5 test files in folder TSPLIB, compute the value of LB for rules R1, R2, R3, the value of UB, and the difference between LB and UB in %. For R2, use λj = 1/j. For R3, use σ = 50 and α = 0.9.
-
Task 6 - Statistical evaluation. Generate randomly 100 problems, each contains 30 nodes and specify for each rule the average difference between UB and LB in %, and the number of problems where the algorithm "1_Tree" is an optimal solution of the TSP.