Algorithms for the multi-objective vehicle routing problem with time windows

Abstract

This paper focuses on an algorithm for the vehicle routing problem with time windows (VRPTW). It involves servicing a set of customers, with earliest and latest time deadlines, a constant service time including when the vehicle arrives to the customers. The demands are served by capacitated vehicles with limited travel times to return to the depot. The purpose of this research is to develop a hybrid algorithm that includes a heuristic, a local search and a meta-heuristic algorithm to solve optimization problems with multiple objectives. The first priority aims to find the minimum number of vehicles required and the second priority aims to search for the solution that minimizes the total travel time. The algorithm performances are measured with two criteria: quality of solution and running time. A set of well-known benchmark data and the genetic algorithm are used to compare the quality of solution and running time of the algorithm, respectively. The algorithm is applied to solve the Solomon’s 56 VRPTW benchmarking problems which have 100-customer instances. The results show that 22 solutions are better than or competitive as compared to the best solutions of the Solomon benchmark problem instances. The running time results display that the hybrid algorithm has higher performance than the genetic algorithm when the number of customers less than 25 nodes.