VehicleRouting

This repository contins the code written for my adventures into solving vehicle routing problems with Reinforcement Learning, Competitive Coevolution, the Clarke-Wright Savings Algorithm, a Nearest Neighbour Heuristic, and the PULP Linear Programming library.

The contents of the files are as follows:

1. CVRPEnv.py - This file contains an environment for generating instances of the Capacitated Vehicle Routing Problem (CVRP) written in the style of the OpenAI gym library to facilitate easy implementation with Reinforcement Learning
2. Coevolution.py - This file contains the required functions to train a NN using competitive coevolution based on a Particle Swarm Optimisation approach, all with the aim of the NN being able to solve a CVRP as generated with CVRPEnv.py
3. FFSNeuralNetwork - This file contains a feedforward neural network class which is used in the competitive coevoution implementation
4. OR-Tools_CVRP - This file contains an implementation of Google OR-Tools for solving instances of the CVRP as generated by the CVRPEnv.py environment
5. Optimal,Savings,NearestNeighbour.ipynb - This notbook contains the implementations of the linear program in PULP, the Clarke-Wright Savings Algorithm and the implementation of my very simple Nearest Neighbour Heuristic
6. RLAttempt_V3.ipynb - This file contains my interpretation of a delayed Actor-Critic model based on the implementation of the paper by Nazari et al.[1]. This file is still a work in progress, I am not sure yet if it works as expected, training times have been painfully long
7. ReinforceAttempt_V1.ipynb - This file contains my interpretation of the REINFORCE algorithm implementation of the paper by Nazari et al.[1]. This file is still a work in progress, I am not sure yet if it works as expected, training times have been painfully long
8. main.py - Run the competitive coevolution algorithm from here

[1]. Nazari, M, Oroojlooy, A, Takáˇc, M, Snyder, L V, Reinforcement Learning for Solving the Vehicle Routing Problem, arXiv:1802.04240v2 [cs.AI] 21 May 2018