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.

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.

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.