Capacitated Vehicle Routing Problem With Windows (Cvrptw): A Case Study Of Phu Si Distribute

Abstract

Capacitated Vehicle Routing Problem with Time Windows (CVRPTW) is considered to be a NP-hard problem and multi-objective problem with a time window, the capacity and the number of vehicles are limited, which is a complex transportation issue. In this study, multi objective CVRPTW is considered in which the cost of total distance travelled by the vehicles, cost of number of vehicles used to serve the customers and penalty cost for violating the time window are minimized. Each customer has different demand and time window. Then a mathematical method is proposed and IBM CPLEX OPTIMIZER is used as an exact method using small scale dataset. After that, Multi Objective Genetic Algorithm (MOGA) is implemented for solving the problem. The proposed algorithm employs a fitness aggregation technique and dedicated operators, such as selection based on aggregate fitness value, partially mapped crossover, and inverse operation for solving the constraints. Then, the process is repeated until the convergence of genetic algorithm. The algorithm was tested using real company data of 35 customers/ day with different time window and demand in order to improve the result’s performance of the proposed method. The results show that the suggested MOGA method achieved the study goal of minimizing overall transportation costs by selecting the best choice of routes for a fleet of vehicles.