This is SUSTech AI lab about Capacitated Arc Routing Problem
This project is how to solve and optimize the CARP problem within a limited time. In this project, this type of carp problem is a vehicle routing problem with capacity limitations. The purpose of this project is to solve the problem of several arc-based tasks for known needs, to find out how to plan the vehicle route under the condition of meeting the vehicle capacity constraints, so that the service cost is minimum. The CARP problem is proposed by Golden. And the problem has been proven to be an NP problem[1]. For this problem, there are two algorithmic approaches, one is the precise algorithm for small-scale CARP problems, and the other is for large-scale CARP problem heuristics, such as simulated annealing, evolutionary computation, and Tubu-scatter algorithm. In this project, I will use the path-scanning greedy algorithm and genetic algorithm to get the initial solution and optimize the algorithm respectively.