首页 >
> 详细

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.

联系我们

- QQ：99515681
- 邮箱：99515681@qq.com
- 工作时间：8:00-23:00
- 微信：codinghelp

- 代写cs3014 Google Analytics Customer Rev 2020-01-21
- 代写cmpsc121 Structs代写留学生c/C++实验... 2020-01-21
- 代写mis6326 Data Management调试存储过程作业、数据库编 2020-01-21
- 代写msci 581作业、代做marketing Analytics作业、P 2020-01-20
- Software课程作业代做、代写java，C/C++程序设计作业、Pyth 2020-01-20
- Tcss 372作业代做、代写python，Java编程语言作业、代做c/C 2020-01-20
- Emergency Facilities作业代写、代写r编程设计作业、R课程 2020-01-18
- Cis 413/513作业代做、代写data Structures作业、Ja 2020-01-18
- 代写ia626留学生作业、Python程序设计作业调试、代做data课程作业 2020-01-18
- Mat00027i作业代写、Java程序语言作业调试、Mathematica 2020-01-17
- 代做kt Model作业、代写java，Python编程设计作业、代做c/C 2020-01-17
- Data Set课程作业代做、代写r程序语言作业、Ltcret留学生作业代做 2020-01-17
- 代写rstudio留学生作业、代做r编程设计作业、代写r课程设计作业代做数据 2020-01-17
- 代写cs2250 Delimiter Matching代做数据结... 2020-01-16
- 代写cs12b Edit Distance帮写java实验作业... 2020-01-16
- 代写mins325 Filereader And Filewriter代... 2020-01-16
- 代写cosi131 Tunnels帮写java实验作业 2020-01-16
- 代写inm312 Balancebit Software代写留学... 2020-01-16
- 代写cs61b Maze Solver代写java课程设计 2020-01-16
- Program留学生作业代做、C/C++编程语言作业代写、代做java，Py 2020-01-14