Vehicle routing problem with time constraints

Abstract

This paper addresses the Vehicle Routing Problem (VRP) with time constraints which been solved by several heuristic algorithms. The problem starting at the depot where the customer orders which associated with due date determined by customer, are released with different point of time. Ideally, to avoid any lateness in delivery process, the orders need to be delivered as soon as it released and available at the depot. However, this may increase the traveling cost because one vehicle needs to go and come back to depot for the other deliveries which this can be saved by batching the deliveries. Therefore, the study will focus on minimizing the tradeoff between traveling and tardiness costs.  Literatures show that implementing the heuristic algorithms for solving various instances of VRPs manage to minimize the distribution cost within the reasonable computing times. An initial feasible solution was generated using a constructive heuristic. The solution then was improved by several metaheuristic algorithms were developed for solving the problem studied; Variable Neighborhood Search, Large Neighborhood Search and Tabu Search. To cater with the problem studied, a modification to the benchmark problems of Solomon has been done. The performance of the algorithms can be seen through the comparison of the solution obtained.  The results showed that there is a significant saving in producing the least cost solution and manually constructed routes are very ineffective.