logo

Vehicle Routing Problem with Time Windows (VRPTW) - Literature Review and Heuristic Approaches

5 Pages1597 Words204 Views
   

Added on  2019-09-16

About This Document

This assignment focuses on the Vehicle Routing Problem with Time Windows (VRPTW) and requires a literature review on its optimal algorithms and heuristic methods. It also requires the implementation and testing of a construction heuristic and a non-construction heuristic on three instances of the VRPTW in Excel VBA. The report must follow specific guidelines and include proper references in Harvard format. The marking scheme includes evaluation of the report and the Excel VBA code.

Vehicle Routing Problem with Time Windows (VRPTW) - Literature Review and Heuristic Approaches

   Added on 2019-09-16

ShareRelated Documents
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 complete graph G(N,A) with node set N and arc set A. Every node v∈N has a demand for service dv and a time window(l¿¿v,uv)¿ such that service must begin at this node no sooner than lv and no later than uv. One of the nodes is called the depot and its demand is zero and it has no time window.Every arc aij={vi,vj}∈A between two nodes vi and vj has a non-negative timecij. This time is the sum of the visit time at node vi and the travel time from vi to vj.A set of homogeneous vehicles, each with capacity Q is available. A feasible solution to the problem is a set of mvehicle 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 Q. The objective is hierarchical: the number of routes mis 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; and2.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) .1 | P a g e
Vehicle Routing Problem with Time Windows (VRPTW) - Literature Review and Heuristic Approaches_1
MANG631316-17In 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 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 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. 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
Vehicle Routing Problem with Time Windows (VRPTW) - Literature Review and Heuristic Approaches_2

End of preview

Want to access all the pages? Upload your documents or become a member.

Related Documents
Study on the Vehicle Routing Problem
|12
|4924
|51

Leadership in Business
|9
|2083
|135