Capacitated Arc Routing Problem

Published:

The Open Capacitated Arc Routing Problem (OCARP) is a NP-hard combinatorial optimization problem where, given an undirected graph, the objective is to find a minimum cost set of tours that services a subset of edges with positive demand under capacity constraints. In this paper, a path-scanning algorithm with local searching function is implemented based on Python to solve this problem. Based on path-scanning as a framework, the algorithm adopts random path scanning and genetic scanning to solve the optimal solutions of NP-hard problems.

In order to solve capacitated arc routing problem, I first used the Dijkstra algorithm to find the shortest path two-dimensional array of the whole graph. Then, path-scanning algorithm is used to search for the Path that meets the conditions and is closest to the current point each time, combined with random algorithm and genetic mutation to find a short path in capacitated arc routing problem which is a NP problem.

You May Also Enjoy

MCM/ICM Math Model

Published:

The value of a sailboat is determined by time and its attributes. In order to help brokers better understand the sailing market, we searched for more data about sailing ships and countries, and finally trained a mathematical model to explain the impact of various data on sailing prices.

Path-Scanning Algorithm for the Capacitated Arc Routing Problem

Published:

The Capacitated Arc Routing Problem (CARP) is a NP-hard combinatorial optimization problem. When given an undirected graph, the objective need to find a minimum cost set of tours that services a subset of edges with positive demand under capacity constraints. In this paper, path-scanning algorithm with local searching function is implemented based on Python to solve this problem. Based on path-scanning as main framework, the algorithm adopts random path scanning and flip to solve the optimal solutions of NP-hard problems.