Hintergrund

Das AI Strategy Office, dem ich angehöre, veranstaltet ein internes "AI Trouble Consultation Meeting", um Lösungen zu finden, indem vorhandene Tools und Bibliotheken kombiniert werden, um die Anforderungen von "Können Sie das nicht tun?" Zu erfüllen. Wir machen auch Geschäfte.

Zum Beispiel gibt es einen Dienst namens LIFULL HOME'S Living Counter. Dies ist ein Service, mit dem Sie sich kostenlos mit einem engagierten Berater für Wohnungssuche in Bezug auf Wohnungsbau und Wohnungssuche beraten lassen können.

Ist es möglich, den Mechanismus zur Erstellung einer Schicht für diesen Berater für Wohnungssuche zu automatisieren und zu optimieren? Heute möchte ich eine der Möglichkeiten vorstellen, die ich dort gefunden habe, um Google OR-Tools zu verwenden.

Beispiel

Sie haben sich für eine Schicht von 5 Heimjagdberatern entschieden.
Da es zur Veranschaulichung geeignet ist, werde ich es Ichihana, Nino, Sanku, Yotsuba und May nennen.
Um das Problem zu vereinfachen, sollten Sie nur eine Schicht berücksichtigen.
Es gibt 3 Slots pro Tag x 7 Tage, die reserviert werden können.
Angenommen, es gibt nur einen Beratungsraum und zwei Personen können nicht gleichzeitig Kunden bedienen (Reservierungen erhalten).
Angenommen, die Beratungsarbeit ist schwierig, sodass der Berater nur einen Slot pro Tag verschieben kann.
Es ist wünschenswert, dass unter den fünf Personen so wenig Zeitverzerrung wie möglich besteht.
Es ist wünschenswert, Schichten zu machen, um den Wunsch des Beraters zu erfüllen, so viel wie möglich zu arbeiten.

Lösen Sie als Problem der Einschränkungszufriedenheit

Solche Planungsprobleme können manchmal als Constraint Fulfillment Problems (CSPs) gelöst werden.

Es gibt einige Bedingungen, die erfüllt sein müssen, aber sie sind groß

Bedingungen, unter denen die Einschränkung erfüllt sein muss
Bedingungen, die Sie optimieren möchten

Wenn Sie es separat betrachten können, können Sie es mit einem Löser lösen.

Sie müssen lediglich den Löser bitten, die Lösung zu berechnen, die die Einschränkungsbedingungen erfüllt, und dann die Bedingungen angeben, die Sie optimieren möchten. Hier,

Zwei Personen können nicht gleichzeitig in derselben Schicht sein
Berater können nur einen Slot pro Tag verschieben
Versuchen Sie, Zeitverzerrungen so weit wie möglich zu vermeiden

Als Randbedingung

Erfüllen Sie so viele Berater wie möglich

Lassen Sie uns den Wert optimieren.

Deklarieren Sie das Modell

Bereiten Sie zunächst ein Modell des Lösers vor. Hier verwenden wir das CP-SAT-Modell. Weitere Informationen finden Sie unter https://developers.google.com/optimization/cp/cp_solver.

from ortools.sat.python import cp_model

model = cp_model.CpModel()

Variablen vorbereiten

Bereiten Sie als Nächstes eine Variable für das Planungsflag vor.

Wenn Sie beispielsweise für n Berater eine Verschiebung von s Rahmen für d Tage vornehmen, können Sie die folgende Verschiebungstabelle erstellen.

Um die obige Tabelle als Berechnungsergebnis auszugeben, zerlegen Sie sie wie folgt und machen sie zu einem "dreidimensionalen Array" von n, d, s,

Wenn 1 im Element enthalten ist, gehen Sie zur Arbeit
Wenn 0 eingegeben wird, gehen Sie nicht zur Arbeit

Kann als angesehen werden.

Mit anderen Worten wurde die Frage, wo das Flag in das "dreidimensionale Array" von "n, d, s" gesetzt werden soll, reduziert.

Definieren wir eine Konstante gemäß diesem Beispiel.

    num_advisers = 5
    num_shifts = 3
    days = ["Tag", "Mond", "Feuer", "Wasser", "Holz", "Geld", "Boden"]
    num_days = len(days)
    adviser_name = ["Kann", "Ichihana", "Nino", "Sanku", "Yotsuba"]
    all_advisers = range(num_advisers)
    all_shifts = range(num_shifts)
    all_days = range(num_days)

Die Variable zum Setzen des Flags 0 oder 1 und zum Lösen durch den Solver wird als Instanz der Klasse "ortools.sat.python.cp_model.IntVar" erstellt. Sie sieht also wie ein pseudo-mehrdimensionales Array mit dict aus. Ich werde etwas vorbereiten, das verwendet werden kann.

    shifts = {}
    for n in all_advisers:
        for d in all_days:
            for s in all_shifts:
                shifts[(n, d, s)] = model.NewBoolVar('shift_n%id%is%i' % (n, d, s))

Setzen Sie Einschränkungen

Einschränkungen werden mit model.Add () eingegeben.

** Zwei Personen können nicht gleichzeitig in derselben Schicht sein: ** Stellen Sie sicher, dass nur ein Flag gesetzt ist, wenn das Diagramm "3D-Array" von "oben" angezeigt wird.

    for d in all_days:
        for s in all_shifts:
            model.Add(sum(shifts[(n, d, s)] for n in all_advisers) == 1)

** Berater können nur einen Slot pro Tag verschieben: ** Stellen Sie sicher, dass nur ein Flag gesetzt ist, wenn das Diagramm "3D-Array" von vorne betrachtet wird.

    for n in all_advisers:
        for d in all_days:
            model.Add(sum(shifts[(n, d, s)] for s in all_shifts) <= 1)

** Vermeiden Sie Zeitverzerrungen so weit wie möglich: ** Da es einen 3 × 7 = 21-Frame gibt, setzen Sie den 21 // 5 = 4-Frame als Untergrenze. Es scheint, dass es keine Verzerrung gibt, wenn der Rahmen "(21 // 5) + 1 = 5" als Obergrenze für jeden Berater festgelegt wird. Fügen Sie im Diagramm "3D-Array" alle Flags in der Ebenentabelle für jeden Advisor hinzu, sodass das Ergebnis größer oder gleich der Untergrenze und kleiner oder gleich der Obergrenze ist.

    min_shifts_per_adviser = (num_shifts * num_days) // num_advisers
    max_shifts_per_adviser = min_shifts_per_adviser + 1
    for n in all_advisers:
        num_shifts_worked = sum(
            shifts[(n, d, s)] for d in all_days for s in all_shifts)
        model.Add(min_shifts_per_adviser <= num_shifts_worked)
        model.Add(num_shifts_worked <= max_shifts_per_adviser)

Zeitzonenwünsche akzeptieren

Als nächstes quantifizieren Sie den Wunsch, "in diese Schicht des Tages einzutreten!" Dies kann ein einfacher Wert von 0 oder 1 sein. Bereiten Sie ihn daher gehorsam als mehrdimensionales Array vor.

Wenn 1 im Element enthalten ist, möchten Sie zur Arbeit gehen
Wenn das Element 0 enthält, möchten Sie nicht zur Arbeit gehen

Wenn Sie sich entscheiden, können Sie die Schichtwünsche für 5 Personen als folgendes 3D-Array quantifizieren.

    shift_requests = [
            [[0, 0, 1], [0, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 0, 1]],
            [[0, 0, 0], [0, 0, 0], [0, 1, 0], [0, 1, 0], [1, 0, 0], [0, 0, 0], [0, 0, 1]],   #Ichihana
            [[0, 1, 0], [0, 1, 0], [0, 0, 0], [1, 0, 0], [0, 0, 0], [0, 1, 0], [0, 0, 0]],
            [[0, 0, 1], [0, 0, 0], [1, 0, 0], [0, 1, 0], [0, 0, 0], [1, 0, 0], [0, 0, 0]],
            [[0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 0, 0], [1, 0, 0], [0, 1, 0], [0, 0, 0]]
            ]

Wenn Verschiebungen einen Wert enthalten, wenn die Berechnung von "Verschiebungsanforderungen [n] [d] [s] * Verschiebungen [(n, d, s)]" für jedes Element durchgeführt wird, Das Berechnungsergebnis ist nur dann 1, wenn "das Element den Wünschen des Beraters entspricht". Indem Sie dies an eine Funktion namens model.Maximize übergeben, können Sie den Solver über die Optimierungsbedingungen informieren.

    model.Maximize(
        sum(shift_requests[n][d][s] * shifts[(n, d, s)] for n in all_advisers
            for d in all_days for s in all_shifts))

https://developers.google.com/optimization/scheduling/employee_scheduling

Ganzes Programm

from ortools.sat.python import cp_model


def main():
    # This program tries to find an optimal assignment of advisers to shifts
    # (3 shifts per day, for 7 days), subject to some constraints (see below).
    # Each adviser can request to be assigned to specific shifts.
    # The optimal assignment maximizes the number of fulfilled shift requests.
    num_advisers = 5
    num_shifts = 3
    days = ["Tag", "Mond", "Feuer", "Wasser", "Holz", "Geld", "Boden"]
    num_days = len(days)
    adviser_name = ["Kann", "Ichihana", "Nino", "Sanku", "Yotsuba"]
    all_advisers = range(num_advisers)
    all_shifts = range(num_shifts)
    all_days = range(num_days)
    shift_requests = [
            [[0, 0, 1], [0, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 0, 1]],
            [[0, 0, 0], [0, 0, 0], [0, 1, 0], [0, 1, 0], [1, 0, 0], [0, 0, 0], [0, 0, 1]],
            [[0, 1, 0], [0, 1, 0], [0, 0, 0], [1, 0, 0], [0, 0, 0], [0, 1, 0], [0, 0, 0]],
            [[0, 0, 1], [0, 0, 0], [1, 0, 0], [0, 1, 0], [0, 0, 0], [1, 0, 0], [0, 0, 0]],
            [[0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 0, 0], [1, 0, 0], [0, 1, 0], [0, 0, 0]]
            ]
    # Creates the model.
    model = cp_model.CpModel()

    # Creates shift variables.
    # shifts[(n, d, s)]: adviser 'n' works shift 's' on day 'd'.
    shifts = {}
    for n in all_advisers:
        for d in all_days:
            for s in all_shifts:
                shifts[(n, d, s)] = model.NewBoolVar('shift_n%id%is%i' % (n, d, s))

    # Each shift is assigned to exactly one adviser in .
    for d in all_days:
        for s in all_shifts:
            model.Add(sum(shifts[(n, d, s)] for n in all_advisers) == 1)

    # Each adviser works at most one shift per day.
    for n in all_advisers:
        for d in all_days:
            model.Add(sum(shifts[(n, d, s)] for s in all_shifts) <= 1)

    # min_shifts_assigned is the largest integer such that every adviser can be
    # assigned at least that number of shifts.
    min_shifts_per_adviser = (num_shifts * num_days) // num_advisers
    max_shifts_per_adviser = min_shifts_per_adviser + 1
    for n in all_advisers:
        num_shifts_worked = sum(
            shifts[(n, d, s)] for d in all_days for s in all_shifts)
        model.Add(min_shifts_per_adviser <= num_shifts_worked)
        model.Add(num_shifts_worked <= max_shifts_per_adviser)

    model.Maximize(
        sum(shift_requests[n][d][s] * shifts[(n, d, s)] for n in all_advisers
            for d in all_days for s in all_shifts))
    # Creates the solver and solve.
    solver = cp_model.CpSolver()
    solver.Solve(model)
    for d in all_days:
        print(days[d] + "Tag:")
        for s in all_shifts:
            for n in all_advisers:
                if solver.Value(shifts[(n, d, s)]) == 1:
                    if shift_requests[n][d][s] == 1:
                        print('Adviser', adviser_name[n], 'works shift', s, '(requested).')
                    else:
                        print('Adviser', adviser_name[n], 'works shift', s, '(not requested).')
        print()

    # Statistics.
    print()
    print('Statistics')
    print('  - Number of shift requests met = %i' % solver.ObjectiveValue(), '(out of', num_advisers * min_shifts_per_adviser, ')')
    print('  - wall time       : %f s' % solver.WallTime())


if __name__ == '__main__':
    main()

Ausgabeergebnis:

Sonntag:
Berater Yotsuba arbeitet Schicht 0(not requested).
Berater Nino arbeitet Schicht 1(requested).
Berater Sanku arbeitet Schicht 2(requested).

Montag:
Berater Ichihana arbeitet Schicht 0(not requested).
Berater Nino arbeitet Schicht 1(requested).
Berater Yotsuba arbeitet Schicht 2(requested).

Dienstag:
Berater Sanku arbeitet Schicht 0(requested).
Berater Ichihana arbeitet Schicht 1(requested).
Berater Yotsuba arbeitet Schicht 2(not requested).

Mittwoch:
Berater Nino arbeitet Schicht 0(requested).
Berater Ichihana arbeitet Schicht 1(requested).
Berater May arbeitet Schicht 2(not requested).

Donnerstag:
Berater Yotsuba arbeitet Schicht 0(requested).
Berater Sanku arbeitet Schicht 1(not requested).
Berater May arbeitet Schicht 2(requested).

Freitag:
Berater Sanku arbeitet Schicht 0(requested).
Berater Mai arbeitet Schicht 1(requested).
Berater Ichihana arbeitet Schicht 2(not requested).

Samstag:
Berater Nino arbeitet Schicht 0(not requested).
Berater Yotsuba arbeitet Schicht 1(not requested).
Berater May arbeitet Schicht 2(requested).


Statistics
  - Number of shift requests met = 13 (out of 20 )
  - wall time       : 0.007237 s

Wir konnten die Lösung ausgeben, die den Schichtwünschen des Beraters am besten entsprach.

Enjoy!

[PYTHON] Füllen Sie 5 gleiche Schichten aus