Hvilket problem løser dette?

Se for deg at du både har nykommere som ønsker plass på grupper, samt personer som allerede har plass og potensielt ønsker å bytte mellom grupper. Slike problemer oppstår ofte, og noen konkrete eksempler er:

  • Fastlegebytter
  • Studentboliger og studenter
  • Bytte av barnehageplasser
  • Bytter mellom prosjekter i et internt jobbmarked i en stor organisasjon

Vi skal bruke fastlegebytter som eksempel for å forklare denne algoritmen. Det er en aktuell problemstilling med stor samfunnsøkonomisk gevinst. Som beskrevet i leserinnlegget “Enkelt å forbedre fastlegeordningen - med en algoritme” i Dagens Næringsliv i 2024 så tillater ikke dagens algoritme bytter. Den tillater heller ikke at man kan stille seg i kø hos mer enn én lege. I beskrivelsen av denne algoritmen skal vi løse begge disse problemene.

I eksempelet nedenfor har vi to leger D1 og D2 som begge totalt har to plasser på listen sin, men bare én pasient. Nummerene på pilene angir rekkefølgen på byttekøen, altså når pasientene meldte inn ønske om bytte.

Diagram som viser reallokering av personer mellom grupper

  • Dersom rekkefølgen på innmeldt bytte er som ovenfor (Emil, Emma, Ola og til slutt Kari), så vil Emil og Emma fylle opp listene. Ettersom det ikke er ledig plass kan verken Ola eller Kari bytte fastlege etterpå i dagens system.
  • Hadde rekkefølgen vært Ola, Kari, Emil og til slutt Emma, så ville alle fått ønsket fastlege.

Dette problemet kan modelleres ved hjelp av en kø, og input-data for APIet er vist nedenfor. Merk at kapasiteten er total kapasitet, ikke ledig kapasitet. Lege D1 nedenfor har to plasser totalt, der en er tatt av Ola og den andre er ledig.

{"data": {"groups": [{"id": "D1", "capacity": 2, "current": ["Ola"]}, 
                     {"id": "D2", "capacity": 2, "current": ["Kari"]}], 
          "queue": [{"person": "Emil", "group": "D1", "preference": 1},
                    {"person": "Emma", "group": "D2", "preference": 1},
                    {"person": "Ola",  "group": "D2", "preference": 1}, 
                    {"person": "Kari", "group": "D1", "preference": 1}]}, 
 "parameters": {"algorithm": "top_trading_cycles", "priority": "queue"}}

I løsningen er byttet mulig og alle fire personene blir fornøyde:

{"Emil": "D1", "Emma": "D2", "Kari": "D1", "Ola": "D2"}

Et eksempel med flere mulige løsninger

Reallokering løses ved å re-formulere problemet som et standard allokeringsproblem, der hver lege først prioriterer sine egne pasienter. Det er mulig å velge noen parametre i reallokering:

  • Parameteret algorithm kan settes til enten "top_trading_cycles" eller "deferred_acceptance". Dette angir algoritmen som brukes til å løse reallokeringsproblemet.
    • "top_trading_cycles" tillater at bytter blant de som har lav prioritet, selv om det potensielt gjør at det med høy prioritet må vente lengre. Flere blir oftere fornøyde, men på bekostning av at noen blir forbigått.
    • "deferred_acceptance" bryter aldri med prioritetsrekkefølgen, og respekterer derfor individets rett til å ikke bli forbigått fremfor alles rett til å bytte som de ønsker. Bytter er kun tillatt blant de som er foran i legenes prioritering.
  • Parameteret priority kan settes til enten "queue" eller "assignment_status". Dette angir prioriteten som legene bruker til å rangere søkerne som ikke er på sin egen liste.
    • "queue" betyr at kun rekkefølgen på køen brukes som prioritet når legene rangerer pasientene.
    • "assignment_status" betyr at legene først prioriterer de uten lege, deretter de som er tildelt en lege som ikke har full kapasitet, og til slutt de som er tildelt en lege som har full kapasitet. Innad i hver av disse gruppene er det rekkefølgen på køen som bestemmer. Idéen er å hjelpe de som ikke er allokert og de som er allokert til mindre populære leger først.
    • Dersom du ønsker en annen prioritering kan du selv formulere reallokeringsproblemet og bruke én av algoritmene Utsatt Aksept (Deferred Acceptance) eller Bytteringer (Top Trading Cycles) direkte.

Her er et nytt eksempel som viser en mer komplisert situasjon. Hver pasient har fremdeles bare oppgitt én lege, men algoritmen tillater at hver pasient kan legge inn preferanser på et vilkårlig antall leger.

Diagram som viser reallokering av personer mellom grupper

Vi oversetter figuren ovenfor til JSON data til APIet slik:

{"data": {"groups": [{"id": "D1", "capacity": 2, "current": ["p1", "p2"]}, 
                     {"id": "D2", "capacity": 2, "current": ["p3"]}], 
          "queue": [{"person": "p1", "group": "D2", "preference": 1},
                    {"person": "p2", "group": "D2", "preference": 1},
                    {"person": "p5", "group": "D1", "preference": 1}, 
                    {"person": "p4", "group": "D2", "preference": 1},
                    {"person": "p3", "group": "D1", "preference": 1}]}, 
 "parameters": {"algorithm": "top_trading_cycles", "priority": "queue"}}

Med algoritmen Top Trading Cycles og prioritet basert på køen får mange plass:

{"p1": "D2", "p2": "D2", "p3": "D1", "p5": "D1"}

Den eneste som ikke får plass er pasienten p4. Velger vi derimot {"algorithm": "top_trading_cycles", "priority": "assignment_status"} får vi andre resultater. Lege D2 prioriterer p4 fremfor p2, fordi p4 står uten lege. De to blir en match, og det er p4 som får innvilget sitt ønske heller enn p2 og p5.

{"p1": "D2", "p3": "D1", "p4": "D2"}

Du kan selv eksperimentere med ulike eksempler og parametervalg i APIet. Hva som er rettferdig er en subjektiv verdivurdering, og algoritmen tillater ulike innfallsvinkler.

Fordeler

  • Individuell rasjonalitet. Dersom en person oppgir preferanser og ønsker å delta i prosessen, så er han garantert å ikke miste plassen sin. Man kan med andre ord aldri tape noe på å delta.
  • Tilpasses ulike behov. Valget av grunnalgoritme "top_trading_cycles" eller "deferred_acceptance" i kombinasjon med prioritet gir muligheter for å tilpasse til ditt behov. Det er også mulig å bruke helt andre egenskaper til å prioritere personene, f.eks. senioritet. Da må man selv formulere reallokeringsproblemet som et allokeringsproblem og kalle andre APIer. Ta kontakt om du har spørsmål rundt dette.

Eksempler

Du kan teste Reallokering på eksempelene nedenfor i APIet helt gratis. Eksempelene er små for å vise struktur og hva som er mulig. Med betalt tilgang kan du sende inn store datasett. De fleste problemer løses på under ett sekund.

Eksempel 1

Dette er det første eksempelet ovenfor. Når vi setter priority lik "queue" er det rekkefølgen på køen som bestemmer gruppenes (legenes) prioritering. I dette eksempelet betyr det at alle legene prioriterer Emil først, deretter Emma, osv., fordi dette var rekkefølgen de stilte seg i kø.

{"data": {"groups": [{"id": "D1", "capacity": 2, "current": ["Ola"]}, 
                     {"id": "D2", "capacity": 2, "current": ["Kari"]}], 
          "queue": [{"person": "Emil", "group": "D1", "preference": 1},
                    {"person": "Emma", "group": "D2", "preference": 1},
                    {"person": "Ola",  "group": "D2", "preference": 1}, 
                    {"person": "Kari", "group": "D1", "preference": 1}]}, 
  "parameters": {"algorithm": "top_trading_cycles", "priority": "queue"}}

Resultat: 

{"Emil": "D1", "Emma": "D2", "Kari": "D1", "Ola": "D2"}

Eksempel 2

I dette eksempelet er algoritmen satt til deferred_acceptance. Da er det ofte færre som får byttet, fordi individets rett til å ikke bli forbigått respekteres fremfor byttehandler.

{"data": {"groups": [{"id": "D1", "capacity": 2, "current": ["p1", "p2"]}, 
                     {"id": "D2", "capacity": 2, "current": ["p3"]}], 
          "queue": [{"person": "p1", "group": "D2", "preference": 1},
                    {"person": "p2", "group": "D2", "preference": 1},
                    {"person": "p5", "group": "D1", "preference": 1}, 
                    {"person": "p4", "group": "D2", "preference": 1},
                    {"person": "p3", "group": "D1", "preference": 1}]}, 
 "parameters": {"algorithm": "deferred_acceptance", "priority": "assignment_status"}}

Resultat: 

{"p4": "D2"}

Eksempel 3

I dette eksempelet har gruppene ulik kapasitet. Personene har også preferanser over mer enn én gruppe (oppgir mer enn ett ønske). "preference": 1 angir førsteønsket, "preference": 2 andreønsket, osv. I fastlege-eksempelet betyr det at pasienter kan stille seg i kø hos flere fastleger samtidig.

{"data": {"groups": [{"id": "d1", "capacity": 2, "current": ["p1"]}, 
                     {"id": "d2", "capacity": 3, "current": ["p2", "p3"]},
                     {"id": "d3", "capacity": 2, "current": ["p4"]}], 
          "queue": [{"person": "p4", "group": "d1", "preference": 1},
                    {"person": "p6", "group": "d1", "preference": 1},
                    {"person": "p5", "group": "d3", "preference": 3},
                    {"person": "p4", "group": "d2", "preference": 2},
                    {"person": "p5", "group": "d1", "preference": 1},
                    {"person": "p5", "group": "d2", "preference": 2},
                    {"person": "p7", "group": "d1", "preference": 1},
                    {"person": "p1", "group": "d2", "preference": 1}]}, 
  "parameters": {"algorithm": "top_trading_cycles", "priority": "queue"}}

Resultat: 

{"p1": "d2", "p4": "d1", "p5": "d3", "p6": "d1"}