Microsoft Word – MANG6313 Computational Methods for Logistics 2016 2017.docx
MANG6313 !”-!$
1 | P a g e
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) .
MANG6313 !”-!$
2 | P a g e
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.
MANG6313 !”-!$
3 | P a g e
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”.
MANG6313 !"-!$
4 | P a g e
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.
MANG6313 !"-!$
5 | P a g e
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