Python定制 | MANG6313 Assessment Electronic via Blackboard Turnitin ONLY

这个作业是用python实现利润旅行商问题
SEMESTER 1 2019/20
COURSEWORK BRIEF:
Module Code: MANG6313 Assessment: Coursework Weighting: 50
Module Title: Computational Methods for logistics
Module Leader: Antonio Martinez-Sykora
Submission Due Date: @ 16:00 8
th January 2020 Word Count: 2500
Method of Submission: Electronic via Blackboard Turnitin ONLY
(Please ensure that your name does not appear on any part of your work)
Any submitted after 16:00 on the deadline date will be subject to the standard University late penalties (see below),
unless an extension has been granted, in writing by the Senior Tutor, in advance of the deadline.
University Working Days Late: Mark:
1 (final agreed mark) * 0.9
2 (final agreed mark) * 0.8
3 (final agreed mark) * 0.7
4 (final agreed mark) * 0.6
5 (final agreed mark) * 0.5
More than 5 0
This assessment relates to the following module learning outcomes:
A. Knowledge and Understanding
B. Subject Specific Intellectual and Research Skills
C. Transferable and Generic Skills
3
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 programme 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
SEMESTER 1 2019/20
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. FORMAT OF REPORT 6. Preferably, follow the format suggested in this assignment. Number sections. You can introduce subsections as deemed appropriate. SEMESTER 1 2019/20 7. Tables and figures can be included and do not count towards the word count. Make sure they are clearly readable and also make sense when printed in black and white. Tables receive their description at the top of the table, figures at the bottom. Number all tables and figures. STYLE OF WRITING 8. Use proper academic English, i.e. it is important to be clear and concise. 9. Cite references using the Harvard system. Information can be found on the web, see for example the Library webpages. NEED HELP? 10. You know my contact details and office hours. Marking Scheme REPORT Point Marks Criteria Section 1 20 Fair reflection of state-of-the-art. Proper references. No plagiarism. Clarity of discussion. Section 2 3 Clear description. Section 3 37 Clarity of description. Properly referenced. Python code working implies 20/37 marks Section 4 37 Clarity of description. Properly referenced. Python code working implies 20/37 marks References 3 Harvard style, no type errors. Total report 100

SEMESTER 1 2019/20

Nature of Assessment: This is a SUMMATIVE ASSESSMENT. See ‘Weighting’ section above for the percentage that this

assignment counts towards your final module mark.

Word Limit: +/-10% either side of the word count (see above) is deemed to be acceptable. Any text that exceeds an

additional 10% will not attract any marks. The relevant word count includes items such as cover page, executive

summary, title page, table of contents, tables, figures, in-text citations and section headings, if used. The relevant word

count excludes your list of references and any appendices at the end of your coursework submission.

You should always include the word count (from Microsoft Word, not Turnitin), at the end of your coursework

submission, before your list of references.

Title/Cover Page: You must include a title/ cover page that includes: your Student ID, Module Code, Assignment Title,

Word Count. This assignment will be marked anonymously, please ensure that your name does not appear on any part

of your assignment.

References: You should use the Harvard style to reference your assignment. The library provide guidance on how to

reference in the Harvard style and this is available from: http://library.soton.ac.uk/sash/referencing

Submission Deadline: Please note that the submission deadline for Southampton Business School is 16.00 for ALL

assessments.

You must write your code in Python. I need to be able to inspect and test your codes.

Use the University computers if you do not have a Microsoft PC yourself. Submit an electronic version of your report

on the blackboard site of MANG6313 no later than 4pm on 8 January, 2020.

Turnitin Submission: The assignment MUST be submitted electronically via Turnitin, which is accessed via the

individual module on Blackboard. Further guidance on submitting assignments is available on the Blackboard support

pages.

It is important that you allow enough time prior to the submission deadline to ensure your submission is processed

on time as all late submissions are subject to a late penalty. We would recommend you allow 30 minutes to upload

your work and check the submission has been processed and is correct. Please make sure you submit to the correct

assignment link.

You will know that your submission has completed successfully when you see a message stating ‘Congratulations –

your submission is complete…’. It is vital that you make a note of your Submission ID (Digital Receipt Number). This

is a unique receipt number for your submission, and is proof of successful submission. You may be required to

provide this number at a later date. We recommend that you take a screenshot of this page, or note the number

down on a piece of paper. You should also receive an email receipt containing this number, and the number can be

found after submitting by following this guide. This method of checking your submission is particularly useful in the

event that you don’t receive an email receipt.

You are allowed to test submit your assignment via Turnitin before the due date. You can use Turnitin to check your

assignment for plagiarism before you submit your final version. See “Viewing Your Originality Report” for guidance.

Please see the Module Leader/lecturer on your module if you would like advice on the Turnitin Originality report.

The last submission prior to the deadline will be treated as the final submission and will be the copy that is

assessed by the marker.

It is your responsibility to ensure that the version received by the deadline is the final version, resubmissions after

the deadline will not be accepted in any circumstances.

Important: If you have any problems during the submission process you should contact ServiceLine immediately by

email at Serviceline@soton.ac.uk or by phone on +44 (0)23 8059 5656.

Late Penalties: Further information on penalties for work submitted after the deadline can be found here.

SEMESTER 1 2019/20

Special Considerations: If you believe that illness or other circumstances have adversely affected your academic

performance, information regarding the regulations governing Special Considerations can be accessed via the

Calendar: http://www.calendar.soton.ac.uk/sectionIV/special-considerations.html

Extension Requests: : Extension requests along with supporting evidence should be submitted to the Student Office

as soon as possible before the submission date. Information regarding the regulations governing extension requests

can be accessed via the Calendar: http://www.calendar.soton.ac.uk/sectionIV/special-considerations.html

Academic Integrity Policy: Please note that you can access Academic Integrity Guidance for Students via the Quality

Handbook: http://www.southampton.ac.uk/quality/assessment/academic_integrity.page?. Please note any

suspected cases of Academic Integrity will be notified to the Academic Integrity Officer for investigation.

Feedback: Southampton Business School is committed to providing feedback within 4 weeks(University working days).

Once the marks are released and you have received your feedback, you can meet with your Module Leader / Module

Lecturer / Personal Academic Tutor to discuss the feedback within 4 weeks from the release of marks date. Any

additional arrangements for feedback are listed in the Module Profile.

Student Support: Study skills and language support for Southampton Business School students is available at:

http://www.sbsaob.soton.ac.uk/study-skills-and-language-support/.