Description
1 Overview In this project you need to design and implement heuristic search algorithms for CARP, a classical NP-hard arc routing problem. An introduction to CARP (including problem formulation and solution representation) can be found in the slides we provide (CARP.pdf). Overall, CARP is a constrained optimization problem, and you need to design and implement applicable heuristic algorithms to CARP. The scores you get in this project will be given according to your algorithm’s performance in our test.
2 General Rules After you submit your project, we will run some scripts to test your CARP solver on different CARP problem instances. To make this process as smooth as possible, the package you submit must satisfy the following requirements. 1) Algorithm description A solver description (in pdf format) must be submitted, in which you should describe the core idea of your design, entail each component of your algorithm, illustrate the algorithm structure and give the pseudo code. 2) Programming aspects In order to get rid of the operating system related issues and the execution efficiency issues of different programming languages, your algorithm must be implemented using Python 2.7+ (Python 3.0+ not included). The name of your executable CARP solver must be CARP_solver.py 3) Input and output a) Input In the test, we will repeatedly call your CARP solver through scripts. Specifically, the format of the solver call is as follows (the test environment is Unix-like): python CARP_solver.py < CARP instance file -t
