← BONABEAU APPS

Letting the people who do the work shape how it is divided

A working model of the two-stage method in Funes, Bonabeau, Hervé and Morieux, “Interactive Multi-Participant Tour Allocation” (CEC 2004), with a second example applied to nurse rosters.

1

The computer tunes six plans

Hill climbing on what the planner can measure: efficiency and even loads.

2

Each person ranks only their own piece

Rank 1 is the piece they would most like to get. Nobody rates a whole plan.

3

The rankings choose the parents

The best plan is kept, the top three breed four children, and one newcomer joins.

Both goals at once

Each dot is one tuned plan. Lines join the plans of a round that no other plan beats on both goals, labeled with the round number at their least-dissatisfied end. Lower left is better.

Round by round

Inefficiency, the planner’s cost. 1.00 means even loads with no local advantage.
Dissatisfaction, the mean private cost. The planner never sees this number; it is shown here because the participants are simulated.
best planmean of sixmean with no participant input
How the model works and where it departs from the paper
  • Scores. For one person and one piece, the weights of the marked spots inside the piece are summed and normalized to S between -1 and +1. Cost is load × 0.9S, so local knowledge or preference moves cost by at most about 10 percent. Efficiency weights (diamonds) are public. Preference weights (circles) are private.
  • Stage 1. Six hill climbers each mutate their plan and keep the child only if the planner’s cost drops. That cost is the summed efficiency cost under the best of the 24 possible assignments of people to pieces, multiplied by 1.3variance to penalize uneven loads. It is shown divided by four.
  • Stage 2. Each person ranks the six pieces offered to them. A plan’s score is the sum of its cubed ranks, so one very unhappy person weighs more than several mildly unhappy ones. The best plan is kept, the top three form the parent pool, two children come from crossover, two from mutation, and one plan is random.
  • Your part. The ranks shown are what simulated participants would answer. Use the arrows to overrule any of them before breeding. The dissatisfaction charts keep using the simulated preferences, so rankings that contradict them will show up as higher dissatisfaction.
  • Dashed line. The same problem run in parallel with parents chosen by efficiency alone. The gap between it and the mean line is what participant input contributes.
  • Size of the effect. In test runs on 20 random problems per example, 20 rounds lowered mean dissatisfaction by roughly 1.5 to 2 percent while inefficiency stayed about the same. Single runs are noisy, and the 10 percent cap on score effects keeps differences small.
  • Departures from the paper. Each carrier gets exactly three efficiency spots and three preference spots inside the district (the paper scatters ten and discards those outside). A cut is the line through point c1 at angle 2πφ. Children are assigned by efficiency rather than by lowest dissatisfaction, so the optimizer never reads a private weight. Loads are scaled so a fair share equals 1.
  • The nurse example is not in the paper. A plan splits 21 shifts (7 days, 3 shifts) into four bundles. Mutation moves one shift to another bundle or swaps two shifts. Crossover takes the start of the week from one parent and the rest from the other. Two shifts back to back add half a shift of load. Each nurse has four public efficiency marks and five private preference marks.