Coursework Brief:
ASSIGNMENT: THE TRAVELING SALESMAN PROBLEM WITH PROFITS (TSPP)
In the Traveling Salesman Problem with Profits (TSPP) and time limit we are given an undirected complete graph
𝐺(𝑉, 𝐸) with node set 𝑉 and edge set 𝐸. We assume that node 1 ∈ 𝑉 represents the depot and nodes {2, ... , 𝑛} ∈ 𝑉 are the customers. For each customer 𝑖 ∈ 𝑉\{1} there is a profit 𝑝𝑖 associated. The aim is to find a route starting and finishing at node 1 ∈ 𝑉 in such a way the total distance travelled is less than 𝑇 and the total profit is maximized.
A feasible solution to the problem is one single route starting and finishing at the depot, which visits a subset of customers and the total length of the route is less than 𝑇. This problem arise in last mile logistics, where the porter needs to decide which deliveries is willing to do.
The nature of this coursework is to demonstrate your ability to research and report on the literature on the above problem and on your ability to program me two heuristic approaches from the literature.
Section 1: State-of-the-art? Literature Review <1000 words>
In this part you present a literature review on the TSPP. It must include a short description of the origin of this problem and its complexity, but the focus should be on discussing what you think is the state-of-the-art today of:
1.optimal algorithms for the TSPP; and
2.heuristics for the TSPP.
You do not need to go into detail about how the methods actually work. It is expected that you will discuss at least one optimal algorithm as well as at least one heuristic method, since it is quite hard to identify an approach that outperforms all others. You must refer to the literature.
Section 2: Instances for the CVRP <100 words>
- Use the internet to find the data of three instances for the Traveling Salesman Problem (TSP) of which other researchers have identified either an optimal solution or a best known feasible solution. The number of nodes in each instance should be at least 20 nodes. At least one of the instances should have at least 100 nodes.
- Then, you will need to convert these instances into the TSPP by providing sensible values for 𝑇 and 𝑝𝑖 , 𝑖 ∈ 𝑉. In other words, you will need to provide a T value lower than the optimal solution of the original TSP instance and a vector containing the profits of each customer. Note that you will have to test the algorithms on these three instances. So you hence must select instances of which you also know the all the necessary data (the cost of the edges, the vehicle capacity, and which node is the depot) .
You do not need to include all the data of an instance in your report! Please do not list. For example, the costs on each of the edges, or the sequence of the optimal route in the known optimal solution.
Section 3: Construction heuristic <700 words>
Select from the literature a construction heuristic that you will also programme in Python. You will then test the algorithm on each of the three instances selected in Section 2.
Explain in this section of the report:
1.The details of how the algorithm works. It should not be a print-out of your Python code, but a higher-level description of how it works using pseudo-code. Refer to the literature you have used.
2.The results you get on each of the instances: running time of you Python algorithm and the total profit obtained.
Section 4: Another heuristic that is not a construction heuristic <700 words>
Select from the literature one heuristic that is not a construction heuristic and that you will also programme in Python. You could consider a heuristic based on local search (where you may wish to start from the solution obtained with the method you have selected in Section 3), or a heuristic of the class of so-called meta-heuristics. You will then test the algorithm on each of the three instances selected in Section 2.
Explain in this section of the report, following the guidelines set-out in Section 3, the details of how the algorithm works and the results from running the code on the instances.
Appendices
You have to add your Python code in the appendix. Also, you may include extra material in appropriate sections here as you feel is necessary or desirable. There is no limit on what you provide but avoid excessively long appendices! Think wisely about what to include here. The appendices do not contribute much to the mark you can obtain; a thoughtful use of appendices may help me understand some points in the main text, but if it is too long and contains irrelevant material may then negatively affect your mark.
RESEARCH ADVICE
1.The web is a useful resource, and you are allowed to search for open-access codes of algorithms for the TSP and use these codes to learn from. You will not be penalised if you reuse parts of such code; it may sometimes be better to adopt this approach then to try to write your own codes from scratch. You must refer in this case to the website and authors of these codes carefully in your report and acknowledge precisely which parts you have reused.
2.You are free to choose which heuristics you want to implement, as long as these are methods from the literature. You get marks for writing a good report on these methods, referring properly to the literature, and for implementing them correctly in Python.
3.It is not of such importance that you would use “smart tricks” to speed up the running times of your code. The latter aspect would require a more in-depth knowledge of Python and computer programming than what we can see in this module. The only criteria are: (1) the code implements the method from the literature, (2) it works. Hence the actual running times, while you need to report them, are not that important. (You will not lose marks if, for example, your code is slower than the “state-of-the-art” implementations, which is very likely the case!)
4.Report running times in seconds. Use the method we have seen in the lectures. If you get the result “0 sec” from VBA, report in your table “<1s”.
5.You do not want to run the codes for too long. My advice is that if an algorithm does not halt before 10 minutes, that you simply stop and report it.