TITLE:
A Time-Dependent Vehicle Routing Problem with Time Windows for E-Commerce Supplier Site Pickups Using Genetic Algorithm
AUTHORS:
Suresh Nanda Kumar, Ramasamy Panneerselvam
KEYWORDS:
Vehicle Routing Problem, Exact Methods, Heuristics, Metaheuristics, VRPTW, TDVRPTW, Optimization, Genetic Algorithms, Matlab, HeuristicLab, C#, DOT NET
JOURNAL NAME:
Intelligent Information Management,
Vol.7 No.4,
July
10,
2015
ABSTRACT: The VRP is classified as an NP-hard
problem. Hence exact optimization methods may be difficult to solve these
problems in acceptable CPU times, when the problem involves real-world data
sets that are very large. To get solutions in determining routes which are realistic
and very close to the actual solution, we use heuristics and metaheuristics
which are of the combinatorial optimization type. A literature review of VRPTW,
TDVRP, and a metaheuristic such as the genetic algorithm was conducted. In this
paper, the implementation of the VRPTW and its extension, the time-dependent
VRPTW (TDVRPTW) has been carried out using the model as well as metaheuristics
such as the genetic algorithm (GA). The algorithms were implemented, using
Matlab and HeuristicLab optimization software. A plugin was developed using
Visual C# and DOT NET framework 4.5. Results were tested using Solomon’s 56
benchmark instances classified into groups such as C1, C2, R1, R2, RC1, RC2,
with 100 customer nodes, 25 vehicles and each vehicle capacity of 200. The
results were comparable to the earlier algorithms developed and in some cases
the current algorithm yielded better results in terms of total distance
travelled and the average number of vehicles used.