Capacitated vehicle routing problem with column generation and reinforcement learning techniques

Capacitated vehicle routing problem is one of the variants of the vehicle routing problem which was studied in this research. In this research we applied a reinforcement learning algorithm to find set of routes from a depot to the set of customers while also considering the capacity of the vehicles, in order to reduce the cost of transportation of goods and services. Each vehicle originates from a depot, service the customers and return to the depot. We compare the reinforcement learning model with an exact method; column generation and Google’s OR-tool. Our objective is to solve a large-size of problem to near-optimality. We were able to use reinforcement learning to solve upto 101 nodes to near-optimality.