MANG6313
MANG6313 16-17
MANG6313 Computational Methods for Logistics
Coursework 2016 2017
ASSIGNMENT: THE VEHICLE ROUTING PROBLEM WITH TIME WINDOWS (VRPTW)
In the Vehicle Routing Problem with Time Windows (VRPTW) we are given a directed complete graph with node set and arc set . Every node has a demand for service and a time window such that service must begin at this node no sooner than and no later than . One of the nodes is called the depot and its demand is zero and it has no time window.
Every arc between two nodes and has a non-negative time . This time is the sum of the visit time at node and the travel time from to .
A set of homogeneous vehicles, each with capacity is available. A feasible solution to the problem is a set of vehicle routes such that every node, excluding the depot, is visited once and at a time within the time window of each node; every route starts and ends at the depot; and total demand serviced by a vehicle route does not exceed . The objective is hierarchical: the number of routes is to be minimised first, and then, for a given number of routes, the total time needed by the vehicles is minimised.
The nature of this coursework is to demonstrate your ability to research and report on the literature on the above formulation of the VRPTW 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 VRPTW. 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 VRPTW; and
2. heuristics for the VRPTW.
You do not need to go into detail about how the methods actually work. It is expected that you will discuss more than one optimal algorithm as well as more than 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 VRPTW <100 words>
Use the internet to find the data of three instances for the VRPTW 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 and the number of vehicles used in the optimal solution should be at least two. At least one of the instances should have at least 40 nodes.
Note that you will have to test the algorithms you will develop on these three instances. So you hence must select instances of which you also know the all the necessary data (the time of the arcs, the vehicle capacity, which arc is the depot, etc) .
In this section of your report, you give details which will allow another researcher to find this data too. You will want to include the name of the instance, the values of the number of vehicles used and the total time needed of the known optimal solution, and the web-address where you have found it.
You do not need to include all the data of an instance in your report! Please don’t list e.g. the times on each of the arcs, or the sequence of optimal vehicle routes in the known optimal solution. However, all the data of each instance should be included in your Excel VBA programme(s), see also Section 3 and Section 4.
Section 3: Construction heuristic <700 words>
Select from the literature a construction heuristic that you will also programme in Excel VBA. 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 VBA 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 VBA algorithm, the total cost of the solution obtained, number of vehicles used, fill rate of each vehicle when leaving the depot. Compare with the known optimal solution.
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 Excel VBA. 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.
References
You must provide the list of references you have cited in your report using the Harvard format.
Appendices
You do not need to have any appendices, but 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, I don’t want to see very long lists. 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 I will be unhappy and this may then negatively affect your mark.
Further Guidelines
This assessment is an individual piece of work; it counts for 50% of the total.
Respect the due date for submission; failure to meet the dead line is subject to the standard penalties.
If you think you can’t complete this work in time due to valid circumstances (sickness, …), talk to your personal tutor immediately and prior to the due date.
The University is very strict regarding copying and plagiarism, and any issues identified during the marking of your work may lead to penalties.
SUBMISSION FORMAT and DUE DATE
You must write your code in Microsoft Excel VBA. You cannot submit a file that can only be read on Mac, for example, as I have a Microsoft PC and I need to be able to inspect and test your codes.
Use the University computers if you don’t have a Microsoft PC yourself.
1. Save your Excel file as “MANG6313_X.xlsm” where X is your STUDENT NR. Put in onto a memory stick, put the memory stick in a sealed envelope with your student nr on it, and attached it to your written report.
2. Submit a printed version of your report with envelope above attached to the Admin Office no later than 4pm on 10 January, 2017.
3. Submit an electronic version of your report on the blackboard site of MANG6313 no later than 4pm on 10 January, 2017.
RESEARCH ADVICE
4. The web is a useful resource, and you are allowed to search for open-access codes of algorithms for the VRPTW 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.
5. 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 VBA.
6. 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 VBA 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 e.g. your code is slower than the “state-of-the-art” implementations, which is very likely the case!)
7. 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”.
8. You don’t want to run the codes for too long. My advice is that if an algorithm does not halt before 10 minutes, that you simply press the Esc button and report this.
FORMAT OF REPORT
9. Preferably, follow the format suggested in this assignment. Number sections. You can introduce subsections as deemed appropriate.
10. Tables and figures can be included and don’t 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
11. Use proper academic English, i.e. it is important to be clear and concise.
12. Cite references using the Harvard system. Information can be found on the web, see e.g. the Library webpages.
NEED HELP?
13. You know my contact details and office hours.
Marking scheme: see following pages.
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
17
Clarity of description. Properly referenced.
Section 4
17
Clarity of description. Properly referenced.
References
3
Harvard style, no type errors.
Total report
60
Marking Scheme EXCEL VBA CODE
Point
Marks
Criteria
Section 3
17
Code implements the heuristic from the literature; code compiles free of errors
Tests
3
Code of Section 3 runs on instances and produces required output
Section 4
17
Code implements the heuristic from the literature; code compiles free of errors
Tests
6
Code of Section 3 runs on instances and produces required output
Total code
40
Total report and code
100
2 | Page