The vehicle routing problem with traffic conditions

The Vehicle Routing Problem (VRP) is a combinatorial optimization and integer programming problem seeking to service a number of customers with a fleet of vehicles. The classical VRP aims to find a set of routes at a minimal cost for beginning and ending points of the route at the depot, so that the known demands of all customers are fulfilled. Each customer is visited only once, by only one vehicle, and each vehicle has a limited capacity. It is important that the right amount of product should be transported at the right time to ensure customer satisfaction. So, choosing the right route is very critical for transportation systems. The vehicle routing problem is an NP-Hard problem. When number of customers and vehicles, constraints of capacity, and time increases, the solution of the problem becomes more difficult. In this study, a vehicle routing problem, which is suitable for real-life situation is discussed. In order to establish the best route apart from the traveled total distance, time must be taken into account for customer satisfaction. Traffic volume on the selected route will affect the time which is spent on the route. So, traffic plays an important role in determining the route. In this study, traffic conditions on alternative ways are taken into account to solve VRP. To achieve this aim, literature review is conducted, then integer linear programing formulation and metaheuristic method which is a combination of Genetic Algorithm, Lin-Kernighan Algorithm and 2-opt Algorithm, is developed.