Heuristics and Reinforcement Learning for Solving the Vehicle Routing Problem

Zhang Ruiwen

Abstract

In the realization of smart cities, the most important component is the smart logistics in which the vehicle routing problem (VRP) plays a significant role. The VRP plays a key role in many areas, such as the location of logistics centers, the optimization of logistics and distribution sequences, and the path planning of intelligent vehicles. Due to the gradual development of the logistics industry and related markets, the simple VRP can no longer satisfy the market demand, which leads to many variants of the VRP problem, such as Capacitated Vehicle Routing Problem (CVRP), Capacitated Vehicle Routing Problem with Time Window (CVRPTW), and Capacitated Vehicle Routing Problem with Pickup and Delivery and Time Window (CVRPPDTW) and so on.  The purpose of this report is to solve CVRP of the points which were isolated from the map of National University of Singapore (NUS) by OSM, using the Gurobi solver and three heuristic reinforcement learning algorithms: the Clarke-Wright Savings Heuristic Algorithm, the Sweep Algorithm, and the Nearest Neighbors Algorithm, and to compare the strengths and weaknesses of the four algorithms, as well as to provide comments on the improvement of the algorithms.