### MANG6313. 16-17. Computational Methods for Logistics. A

Added on - 16 Sep 2019

5

pages

1597

words

46

views

0

downloads

MANG631316-17Computational Methods for LogisticsASSIGNMENT: THE VEHICLE ROUTING PROBLEM WITH TIME WINDOWS (VRPTW)In the Vehicle Routing Problem with Time Windows (VRPTW) we are given a directed completegraphG(N,A)with node setNand arc setA. Every nodev∈Nhas a demand for servicedvanda time window(l¿¿v,uv)¿such that service mustbeginat this node no sooner thanlvand no laterthanuv. One of the nodes is called the depot and its demand is zero and it has no time window.Every arcaij={vi,vj}∈Abetween two nodesviandvjhas a non-negativetimecij. This time is thesum of the visit time at nodeviand the travel time fromvitovj.A set of homogeneous vehicles, each with capacityQis available. A feasible solution to the problemis a set ofmvehicle routes such that every node, excluding the depot, is visited once and at a timewithin the time window of each node; every route starts and ends at the depot; and total demandserviced by a vehicle route does not exceedQ. The objective is hierarchical: the number of routesmis to be minimised first, and then, for a given number of routes, the total time needed by thevehicles is minimised.The nature of this coursework is to demonstrate your ability to research and report on the literatureon the above formulation of the VRPTW and on your ability to programme two heuristic approachesfrom 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 theorigin of this problem and its complexity, but the focus should be on discussing what you think is thestate-of-the-art today of:1.optimal algorithms for the VRPTW; and2.heuristics for the VRPTW.You donotneed to go into detail about how the methods actually work. It is expected that you willdiscuss more than one optimal algorithm as well as more than one heuristic method, since it is quitehard 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 haveidentified either an optimal solution or a best known feasible solution. The number of nodes in eachinstance should be at least 20 and the number of vehicles used in the optimal solution should be atleast 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 youhence 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) .1|P a g e

MANG631316-17In this section of your report, you give details which will allow another researcher to find this datatoo. You will want to include the name of the instance, the values of the number of vehicles usedand the total time needed of the known optimal solution, and the web-address where you havefound it.You donotneed to include all the data of an instance in yourreport! Please don’t list e.g. the timeson each of the arcs, or the sequence of optimal vehicle routes in the known optimal solution.However, all the data of each instance should beincluded in your Excel VBA programme(s), see alsoSection 3 and Section 4.Section 3: Construction heuristic<700 words>Selectfrom the literaturea construction heuristic that you will also programme in Excel VBA. You willthen 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 ahigher-level description of how it works using pseudo-code. Refer to the literature you haveused.2.The results you get on each of the instances: running time of you VBA algorithm, the totalcost of the solution obtained, number of vehicles used, fill rate of each vehicle when leavingthe depot. Compare with the known optimal solution.Section 4: Another heuristic that is not a construction heuristic<700 words>Selectfrom the literatureone heuristic that is not a construction heuristic and that you will alsoprogramme in Excel VBA. You could consider a heuristic based on local search (where you may wishto start from the solution obtained with the method you have selected in Section 3), or a heuristic ofthe class of so-called meta-heuristics. You will then test the algorithm on each of the three instancesselected in Section 2.Explain in this section of the report, following the guidelines set –out in Section 3, the details of howthe algorithm works and the results from running the code on the instances.ReferencesYou must provide the list of references you have cited in your report using the Harvard format.<END OF PAPER> Further guidelines & Marking scheme: See following pages.2|P a g e

**You’re reading a preview**

To View Complete Document

Become a Desklib Library Member.

Subscribe to our plans