DEVELOPING HEURISTIC METHOD FOR PICKUP AND DELIVERY VEHICLE ROUTING PROBLEM WITH TIME WINDOW (PDVRPTW)
Vehicle Routing Problem, commonly abbreviated as VRP, is a globally studied problem on assigning a set of location to vehicles to minimize an objective calculated from routes scheduled on each vehicles. This problem is considered to be NP-Hard and comes with a lot of variants. Relevant to this pa...
Saved in:
| Main Author: | |
|---|---|
| Format: | Final Project |
| Language: | Indonesia |
| Online Access: | https://digilib.itb.ac.id/gdl/view/76887 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Institution: | Institut Teknologi Bandung |
| Language: | Indonesia |
| Summary: | Vehicle Routing Problem, commonly abbreviated as VRP, is a globally studied
problem on assigning a set of location to vehicles to minimize an objective calculated
from routes scheduled on each vehicles. This problem is considered to be NP-Hard
and comes with a lot of variants. Relevant to this paper, the variants contains capacity,
time window, and pickup delivery constraints, combined abbreviated as PDVRPTW.
Studies on VRP variants usually consist of initial solution generation followed by
optimization strategy. In this paper, a heuristic method is developed utilizing balanced
graph clustering and dynamic programming for hierarchically breakdown large
graphs, also reassignments and bipartite matching for incorporating time window.
This solution is then experimented on each optimization strategy, namely steepest hill
climbing, simulated annealing, and tabu search. Results shows that balanced
k-medoids is the best clustering method that generates TSP solution 3-15% worse
than best known solutions. This heuristic method also generates solution with number
of vehicles less than 130% of best known solutions on PDVRPTW instances. |
|---|