Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

COURSEWORK BRIEF:

Module Code:

MANG6542

Assessment:

Report (+code)

Weighting:

50

Module Title:

Computational Methods for Logistics

Module Leader:

Antonio Martinez-Sykora

Submission Due Date: @ 16:00

9 Jan 2023

Word Count:

1500

 

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 “Quasi” TRAVELING SALESMAN PROBLEM

In the Quasi Traveling Salesman Problem (QTSP) we are given an undirected complete graph  with node set  and edge set . We assume that node  represents the depot and nodes  are the customers. The aim is to find a route starting and finishing at node  in such a way the total distance travelled is minimised and at least n-2 customers are visited (only one customer may be not visited). A feasible solution to the problem is one single route starting and finishing at the depot, which visits a subset of at least n-2 customers.

 

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 more general and well-known Travelling Salesman Problem (TSP). 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 TSP; and

2. heuristics for the TSP.

You do not need to go into detail about how the methods 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 TSP<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. Report the best known solutions (or the optimal solution if known).

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 <400 words>

Select from the literature of the TSP a construction heuristic and adapt it to solve the QSTP (Quasi-TSP). You will also need to programme in Python. You will then test the algorithm on each of the three instances selected in Section 2 and compare the results with the TSP solutions from the literature.

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 cost obtained.

 

 

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 than to try to write your own codes from scratch. You must clearly 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 Python, report in your table “<1s”.

FORMAT OF REPORT

1. Preferably, follow the format suggested in this assignment. Number sections. You can introduce subsections as deemed appropriate.

2. 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.

 

 

 

 

 

 

 

 


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.

 

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.

 

Email submission receipts are not currently supported with Turnitin Feedback Studio LTI integrations, however following a submission, students are presented with a banner within their assignment dashboard that provides a link to download a submission receipt. You can also access your assignment dashboard at any time to download a copy of the submission receipt using the receipt icon. 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. 

 

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 [email protected] 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.

 

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/.