How to find the cycles which, together, involve the biggest number of non-shared edges in a directed graph? I am not a computer science theorist, but think this real world problem belongs here.

The problem

My company have several units accross the country.

We offered to employees the possibility to work on another unit. But there is a condition: The total number of workers on a unit cannot change.

That means: We'll allow a employee to left his unit if someone wants his place.

Example (ficticious) request data:

Name            Origin    Destination
Maria              1  -&gt;  2
Marcos             2  -&gt;  3
Jones              3  -&gt;  4
Terry              4  -&gt;  5
Joe                5  -&gt;  6
Rodrigo            6  -&gt;  1
Barbara            6  -&gt;  1
Marylin            1  -&gt;  4
Brown              4  -&gt;  6
Benjamin           1  -&gt;  3
Lucas              4  -&gt;  1


The above, plotted:


See how we have to choose between the red, blue or black options?

The real problem is a little more complex, because we have 27 units and 751 requests. Please take a look at the visualization 

The goal

Having collected all the requests, how to satisfy most of them?

Theory(?) application

Having graph $G(V, E)$, let every unit be a vertex $V$ and a request be a directed edge $E$, a successful exchange will take the form of a directed cyle.

Each cycle must use $E$ only once (a worker cannot leave his unit twice), but can visit $V$ several times (a unit can have many workers wanting to leave).

The question

If this problem is expressed as


  "How to find the cycles which, together, involve the biggest number of
  non-shared edges in a directed graph"?


Will we satisfy most of the requesters?

That being true, there is an algorithm to find that optimal set of cycles?

Will this greddy approach solve the problem?


Find the biggest directed cycle on $G$;
Remove it's edges from $G$;
Repeat 1 until there is not a directed cycle on $G$;


Can you help me?

Do you know another way to describe the original problem (making most of requesters happy)?

Edit: changed department to unit, to better describe the problem.
This is a standard minimum-cost circulation problem.  Give each directed edge capacity $1$ and cost $-1$.  Then a feasible circulation is a sum (ie, union) of edge-disjoint directed cycles, and the cost of the circulation is the negation of the number of edges.

Because all the costs and capacities are bounded by constants, a simple cycle-cancelling algorithm will find the required circulation in polynomial time.  This is almost the same as the obvious greedy algorithm:

while G has any negative-cost directed cycles
    γ = arbitrary negative-cost directed cycle
    reverse every edge in γ
    negate the cost of every edge in γ
return the subgraph of reversed edges


Here, the cost of a cycle is the sum of the costs of its edges.  Negative-cost cycles can be found using the Bellman-Ford shortest-path algorithm in $O(VE)$ time.  Each iteration reduces the cost of the current circulation by at least 1.  The initial (empty) circulation has cost $0$, and the final circulation has cost at least $-E$.  Thus, the algorithm ends after at most $E$ iterations, so its total running time is at most $O(VE^2)$.

This is not the fastest algorithm known.