A genetic and set partitioning two-phase approach for the vehicle routing problem with time windows

A genetic and set partitioning two-phase approach for the vehicle routing problem with time windows

0.00 Avg rating0 Votes
Article ID: iaor20082524
Country: United Kingdom
Volume: 34
Issue: 6
Start Page Number: 1561
End Page Number: 1584
Publication Date: Jun 2007
Journal: Computers and Operations Research
Authors: , ,
Keywords: heuristics: genetic algorithms
Abstract:

The Vehicle Routing Problem with Time Windows (VRPTW) is a well-known and complex combinatorial problem, which has received considerable attention in recent years. This problem has been addressed using many different techniques including both exact and heuristic methods. The VRPTW benchmark problems of Solomon have been most commonly chosen to evaluate and compare all algorithms. Results from exact methods have been improved considerably because of parallel implementations and modern branch-and-cut techniques. However, 24 out of the 56 high order instances from Solomon’s original test set still remain unsolved. Additionally, in many cases a prohibitive time is needed to find the exact solution. Many of the heuristic methods developed have proved to be efficient in identifying good solutions in reasonable amounts of time. Unfortunately, whilst the research efforts based on exact methods have been focused on the total travel distance, the focus of almost all heuristic attempts has been on the number of vehicles. Consequently, it is more difficult to compare and take advantage of the strong points from each approach. This paper proposes a robust heuristic approach for the VRPTW using travel distance as the main objective through an efficient genetic algorithm and a set partitioning formulation. The tests were produced using real numbers and truncated data type, allowing a direct comparison of its results against previously published heuristic and exact methods. Furthermore, computational results show that the proposed heuristic approach outperforms all previously known and published heuristic methods in terms of the minimal travel distance.

Reviews

Required fields are marked *. Your email address will not be published.