Study On The Algorithms Of The CVRP And The Distribution Network Flow Problem

The VRP and the network flow problem are all famous network optimization problems. The VRP can be regarded as an extension of the TSP and it is NP-complete. It calls for the determination of the optimal routes used by a fleet of vehicles, based at a depot, to serve a set of customers. The flow network is mainly studied in the network flow problem and it calls for the determination of the maximum flow or the minimum cost flow of the flow network.In this paper, we summarize the important algorithms including exact algorithms and heuristic algorithms of the CVRP and put forward two kinds of new heuristic algorithms. One is presented by extending an ACVRP'method and the other is based on Lagrangian relaxation. We described the distribution network flow and get an algorithm of minimum cost flow about a special distribution network flow problem by extending the network simplex method.