Development of Efficient Approaches for Solving the Vehicle Routing Problem with Time Windows

Abstract

Being a key element in logistics distribution, Vehicle Routing Problem becomes an importance research topic in management and computation science. Vehicle Routing Problem with time windows is a specialization of Vehicle Routing Problem. The VRPTW is a fundamental problem underlying many operational challenges in the field of logistics and supply chain management. Most of the researches have generally focused only on the minimization of total transportation cost. Here, the main focus is the bi-objective optimization considering the minimization of the total transportation cost and number of vehicles. The problem is Non Polynomial time (NP) hard. The bi- objective VRPTW is modelled into mathematical set of equations on which optimisation strategies could work upon. First, a Mixed Integer Programming approach, a general methodology for solving a broad class of VRPs, is developed and use this technique to obtain competent results. This technique could work on limited number of customers. Then, a solution strategy based on Lagrangian relaxation using sub gradient approach is proposed. This approach gives optimal solutions for the considered problem. But, this solution is not efficient to compute solutions for most of the instances with 100 customers. Hence, exact approaches are not much efficient when large instances are considered. Therefore, Firefly Algorithm, a metaheuristic technique, which could give approximate results to problem is applied to the VRPTW. A modification is proposed to generate optimum results. A strategy of reducing the population space in each consecutive iteration to reduce the overall computation time is applied. Moreover, a distance method, analysed to give best results among four different distance method is used. The proposed approach has been tested on the well-known Solomon’s benchmark test instances. Extensive results have shown that the proposed approach outperforms the benchmark results and is comparable to optimum results.