Capacitated-Arc-Routing-Problem-CARP-

REPORT FOR CARP_PROBLEMS

@[2017.11.24]

[TOC]

---

1.Preliminaries

Use python2.7 as the coding language. Use dijkstra algorithm to find the shortest distance of the VERTICES. Use Path Scanning to generate the initial solution pool. Use Memetic search as the algorithm to find the best solution.

---

2.Methodology

2.1 Read The Data

Use module re to split the input data and formalize the structure of the data.

    for x in given_file:
        arr.append(re.split(" *:*", x.strip()))

Also save some useful information like CAPACITY DEPOT etc.

2.2 Calculate The Shortest Length Of The Vertices

Use dijkstra algorithm to calculate the path of each two vertices in the problems and store the data into a array.

2.3 Generate The Initial Solution Pool

Use a well-known Path Scanning algorithm¹ heuristic to generate the initial solution pool. Previous Research shows that it has five methods to generate a path efficiently: for a given $arc(i,j)$ and the distance $d(i,j)$, and the depot is $d$ the next node can have:

(1) $d(i,j)$, per unit remaining demand is minimized; (2) $d(i,j)$, per unit remaining demand is maximized; (3) $d(i,d)$ is minimized; (4) $d(j,d)$ is minimized; (5) if the vehicle is less than half-full, $max(d(i,d))$ , otherwise $min(d(i,d))$.

In the programming the weighs for those five are:

0.4, 0.1, 0.1, 0.1, 0.1

Also give the rest 0.2 weigh to the other strategy: randomly choose the near task and add it into the path.

2.4 Route-based Crossover

In this part we use a crossover method called Route-based crossover (RBX)² to create the offspring solution. Given two parent solutions : $S^1 = {R^1_1,R^2_2,\cdots R^1_{m1}} $ with $ m_1 $ routes $S^2 = {R^1_2,R^2_2,\cdots R^2_{m2}} $ with $ m_2 $ routes The steps shows below:

1. Step1: Copy $S^1$ to an offspring solution $S^0$ and randomly choose a route from $S^2$ to replace a random route in $S^0$. Collect the unserved tasks into a set.

2. Step2: Remove duplicate tasks. In this part it will take the cost of the two duplicate tasks into consideration. It will choose a task that will reduce the total cost or choose the task that lead to smaller cost increased.
3. Step3: Insert the unserved task into $S^0$. At first, shuffle the unserved task. For every route that can accommdate the task, it will choose a palce that will reduce the total cost or lead to smaller cost increased. This process is repeated until the set becomes empty.

The steps it is clear that the RBX method could lead to an offspring solution which is structurally different from its parent solutions since that the deletion and insertion is randomly choose and it can also lead the overall cost minimaized.

2.5 Move Operators

In this part we will use four operator³ Inversion(IV), Single insertion(SI), Double insertion(DI), Swap(SW) to start mutation and local search. The introduction of the move operators shows below: Let $u$ and $v$ be a pair of tasks in the current solution $S$, tasks $x$ and $y$ be respectively the successor of $u$ and $v$, $rt(u)$ be the route including task $u$.

Inversion (IV): replace the current arc of task $u$ with its reverse arc in $S$

Single insertion (SI): displace task $u$ after task $v$

Double insertion (DI): displace a sequence $(u; x)$ after task $v$

Swap (SW): exchange task $u$ and task $v$

For all of the move operators, both directions are considered and the best result of the cost will be chosen.

---

3 Processing

st=>start: Input data
op=>operation: Dijkstra algorithm
op2=>operation: Path Scanning algorithm
op3=>operation: Route-based Crossover(RBX)
op4=>operation: Move Operators
op5=>end: Output Data

st->op->op2->op3->op4->op5

Footnotes

1. B. L. Golden†. Computational Experiments with Algorithms for a class of routing problems[J]. Computers & Operations Research, 1983, 10(1):47-59. ↩

2. Chen Y, Hao J K, Glover F. A hybrid metaheuristic approach for the capacitated arc routing problem[J]. European Journal of Operational Research, 2016, 253(1):25-39. ↩

3. 梅一. 基于元启发式方法对限量弧路由问题的求解[D]. 中国科学技术大学, 2010. ↩