Solving Capacitated Vehicle Routing Problem using Nested Genetic and Sweep algorithm: A Case Study for Raw Milk Transportation

Abstract

Vehicle routing problem (VRP) is one of the important and widely researched topics in the fields of operation research, distribution, transportation and logistics. Various variants of VRP exist in literature, each formulated based on the nature of the problem and type of constraints i.e., time, cost, capacity, distance under consideration. Capacitated Vehicle Routing Problem (CVRP) is one such variant where the objective is to provide optimal routes to a set of vehicles so that the combined cost or distance travelled by all vehicles is as minimum as possible while serving all demand points under the constraints of vehicles’ capacity. This research aims to solve a variant CVRP for a dairy factory that has several area offices. Each area office owns a fixed heterogeneous fleet and is responsible for collecting raw milk from its respective Milk collection Centers (MCC). The objective of this research is to minimize overall cost of milk collection by determining optimum routes for area offices’ fleet considering their fuel economies and capacities. This research uses a popular, two-phased approach i.e., clustering first and then solving TSP, for solving this variant of CVRP. It uses a modified version of sweep algorithm in combination with nested hybrid genetic for assigning suitable MCCs to vehicles and solving TSP for each vehicle. The results show that the vehicles are utilized at their maximum capacities i.e., more than 90%, and improved Genetic Algorithm (GA) provides better and faster results than normal GA. The GA on the top of sweep and improved GA provides optimum routes for vehicles with significant drop in the overall cost.