Description
(CARP)
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 your algorithm needs to find high-quality feasible solutions to it. 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 to Sakai, 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 3.9.7 and the only allowed library is numpy.
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 <termination> -s <random
seed>
ππππ_π¬π¨π₯π―ππ«. π©π² is your executable CARP solver.
< πππ«π© π’π§π¬πππ§ππ ππ’π₯π > βπ < πππ«π¦π’π§πππ’π¨π§ > βπ¬ < π«ππ§ππ¨π¦ π¬πππ > are the arguments passed to your CARP solver
< πππ«π© π’π§π¬πππ§ππ ππ’π₯π > is the absolute path of the test CARP instance file βπ < πππ«π¦π’π§πππ’π¨π§ > specifies the termination condition of your algorithm. Specifically, <termination> is a positive number which indicates how many seconds (in Wall clock time, range: [60s, 600s]) your algorithm can spend on this instance. Once the time budget is consumed, your algorithm should be terminated immediately.
βπ¬ < π«ππ§ππ¨π¦ π¬πππ > specifies the random seed used in this run. In case that your solver is stochastic, the random seed controls all the stochastic behaviors of your solver, such that the same random seeds will make your solver produce the same results. If your solver is deterministic, it still needs to accept βπ¬ < π«ππ§ππ¨π¦ π¬πππ >, but can just ignore them while solving CARPs.
You can use multithread, but the number of thread shall not exceed 8.
In summary, your CARP solver needs to:
Β handle the arguments passed from our scripts while being called as above
Β measure the runtime, and terminate after the time budget is consumed.
Typically, in python 3 you can measure runtime using time.time(): start = time.time()
β¦solving carp
run_time = (time.time() – start)
Note here although our tests rely on your solverβs internal time measurement, we will still measure your solverβs runtime from external, so make sure that your solverβs internal time measurement is accurate.
Β use random seeds to control all the stochastic behaviors
b) Output
Your solver must print messages to the standard output. These messages will be used to evaluate this solver run. Your solver has to print two lines. Each of them, according to its first char, must belong to one of the categories described below. Lines that do not start with one of the patterns below will be considered a comment and hence ignored.
Solution line begins with a lower case βsβ followed by a space (ASCII code 32). Only one such line is allowed and it is mandatory. The best solution your solver has found for the CARP problem instance must be printed in this line. The format of the solution can be found in the slides we provide (CARP.pdf). For example, for the CARP instance given below, the βsβ line is:
s 0,(1,2),(2,4),(4,1),0,0,(4,3),(3,1),0
Quality line begins with a lower case βqβ followed by a space (ASCII code 32).
Only one such line is allowed and it is mandatory. The solution quality (i.e., the total cost) of your best found solution must be printed in this line. The βqβ line of the above example is:
q 15
4) Format of CARP problem instance
The format of the CARP problem instances can be found in the instruction we provide (CARP_format.txt), and we also provide some CARP instance files as examples (CARP_samples/). 3 Evaluation
We divide the solver evaluation into three parts:
Usability test 50%): In this test we will use some CARP problem instances to check whether your solvers are usable. Here the meanings behind usability are twofold:
a) (25%) Your solvers can satisfy the input and the output requirements (See Section 2). The failure cases include: cannot handle the inputs, the output messages are undesirable (missing βsβ line or βqβ line, the format of the output solution is incorrect or the total cost of the output solution is not correctly calculated), crash.
b) (25%) The best found solution output by your solver is a feasible solution (since CARP is a constrained problem). Infeasible solutions violate at least one constraints of CARP.
Once your solvers have passed a test, you will get all the corresponding scores. Note only those solvers that have been through test a) will be tested in b).
Efficacy test (50%): In this test we will focus on how good your solvers are. Specifically, we will select different CARP instances with different sizes from existing CARP benchmarks to test your solvers. For each instance, we will set a common cutoff time for all participant solvers and compare their solution quality.
The scores you get in this test depend on the rankings your solvers obtain. Note only those solvers that have been through usability test will be tested in efficacy test.
The scores you get in this test depend on the rankings your solvers obtain. Note only those solvers that have been through usability test will be tested in robustness test.
4 Test Environment
1) Operation System: Debian 10
2) Server CPUοΌ2.2GHz*2, 8-core total
3) Python version: 3.9.7
PSοΌ
1) Paper reference link: http://scholar.google.com 2) A website for you to submit your code and online judge: http://10.20.99.199/
Reviews
There are no reviews yet.