Изследвания · Оптимизация и планиране

Най-доброто решение при ограничения, и обяснението, когато такова няма

Графици на екипи, маршрути на техници, разпределяне на доставки, разкрояване на материали, производствен микс: тези решения имат най-добър отговор, който може да бъде изчислен. VVL ви позволява да ги опишете в няколко реда и ги предава на решател на ограничения. Езиковият модел може да помогне при писането на модела, но решението се изчислява, а не се отгатва.

Как работи

Четири елемента, един решател

Една задача се декларира с четири елемента: решенията, които трябва да се вземат, и техните граници, ограниченията, които трябва да се спазват безусловно, предпочитанията, които могат да бъдат пожертвани с определена тежест, и целта, която да се максимизира или минимизира. VVL компилира това описание за решателя CP-SAT на Google OR-Tools.

Езикът предлага инструменти около решателя: валидиране на модела, обяснение, генериране на код, отчет на естествен език и най-вече диагностика, когато задачата няма решение. Слой за планиране добавя бизнес понятия: хоризонт, ресурси, задачи, продължителности, предшествания, ресурси, които не могат да вършат две неща едновременно. Функции за геолокация предоставят разстоянията между адресите за маршрутите.

Без нито едно извикване на езиковия модел по време на решаването.

optimize:problemVVL

[optimize:problem "prod"
  [decision $x Integer [min 0] [max 10]]
  [decision $y Integer [min 0] [max 10]]
  [assert (($x + $y) <= 12)]          # capacité totale de l'atelier
  [maximize ((3 * $x) + (5 * $y))]]   # marge à maximiser

[optimize:solve "prod" [time_limit 5] [backend "cp-sat"]]

Резултат, получен на сървъра: x = 2, y = 10, статус ОПТИМАЛНО, марж 56.

Примери от бизнеса

Графици, маршрути, обекти

График на екип за една седмица

Трима души, пет дни, поне двама присъстващи всеки ден, най-много четири дни за всеки, Alice отсъства в сряда. Търси се графикът, който ангажира най-малко дни общо.

Резултат, получен на сървъра: оптимален график от 10 човекодни, двама души всеки ден, Alice отсъства в сряда.

смениVVL

$jours  = [list "lun" "mar" "mer" "jeu" "ven"]
$equipe = [list "alice" "bob" "carol"]
[optimize:problem Roulement
  [for $e $equipe [for $j $jours
    [decision "w_${e}_${j}" Integer [min 0] [max 1]]]]
  [for $j $jours
    [assert ([sum $e $equipe "w_${e}_${j}"] >= 2)]]     # au moins deux présents
  [for $e $equipe
    [assert ([sum $j $jours "w_${e}_${j}"] <= 4)]]     # quatre jours au plus
  [assert ($w_alice_mer == 0)]                         # Alice absente mercredi
  [minimize [sum $e $equipe [sum $j $jours "w_${e}_${j}"]]]]
[optimize:solve Roulement]

Разпределяне на доставките

Всяка поръчка трябва да бъде доставена веднъж, а всеки куриер поема най-много две поръчки. Ако целта се замени със сумата от разстоянията между куриерите и клиентите, същият модел се превръща в оптимизация на маршрути.

Резултат, получен на сървъра: и четирите поръчки са разпределени, нито един куриер с повече от две, статус ОПТИМАЛНО.

маршрутиVVL

$livreurs  = [list "L1" "L2" "L3"]
$commandes = [list "C1" "C2" "C3" "C4"]
[optimize:problem Tournees
  [for $l $livreurs [for $c $commandes
    [decision "x_${l}_${c}" Integer [min 0] [max 1]]]]
  [for $c $commandes
    [assert ([sum $l $livreurs "x_${l}_${c}"] == 1)]]   # chaque commande servie une fois
  [for $l $livreurs
    [assert ([sum $c $commandes "x_${l}_${c}"] <= 2)]]  # capacité par livreur
  [minimize [sum $l $livreurs [sum $c $commandes "x_${l}_${c}"]]]]
[optimize:solve Tournees]

# variante tournée : minimiser les kilomètres
# [minimize [sum $l $livreurs [sum $c $commandes
#     ([geo:distance "${l}" "${c}"] * "x_${l}_${c}")]]]

Планиране на обект

Техници, превозно средство, предшествания

Монтажът изисква техник и превозното средство, а тестът изисква техник и може да започне едва след монтажа. Всеки ресурс върши само едно нещо в даден момент. Целта е работата да приключи възможно най-рано.

Предшестване монтаж → тест, само една задача наведнъж за всеки ресурс.

planning:problemVVL

[planning:problem Chantier
  [horizon 0 480]
  [resource "tech_thomas" [kind "technician"]]
  [resource "tech_sarah"  [kind "technician"]]
  [resource "utilitaire"  [kind "vehicle"]]
  [task "pose" [duration 240]]
  [task "test" [duration 60]]
  [on-resource-group "pose" "installer" [resources "tech_thomas" "tech_sarah"]]
  [on-resource-group "pose" "vehicle"   [resources "utilitaire"]]
  [on-resource-group "test" "installer" [resources "tech_thomas" "tech_sarah"]]
  [no-overlap-resource "tech_thomas"]
  [no-overlap-resource "tech_sarah"]
  [no-overlap-resource "utilitaire"]
  [precedence "pose" "test"]
  [objective minimize-makespan]]
[optimize:solve Chantier]

Резултат, получен на сървъра: монтаж от 0 до 240 минути, тест от 240-ата минута, край на работата на 300-ата минута, оптимално решение.

Маршрути на техници по поддръжка

Казус от поддръжката на котли: пет посещения, които трябва да се разпределят между техниците според тяхната квалификация, времевите им прозорци и района им. Моделът съдържа 20 решения, 13 твърди ограничения и 3 претеглени предпочитания.

Документиран резултат: оптимално решение за 0,04 секунди, и петте посещения в района на техника. Версията, която минимизира реалните километри въз основа на адресите, достига 32 km за целия автопарк.

Когато няма решение

Да откриеш конфликта, а не само да откажеш

Производствена цел, която е невъзможно да бъде постигната с наличните капацитети. Решателят изолира най-малкото множество от несъвместими ограничения, така че отговорникът да знае кое от тях да предоговори.

Диагностика на конфликта

Заявеният обем надвишава сумата от двата капацитета: нито една комбинация не е възможна.

Резултат, получен на сървъра: конфликт между три ограничения, заявения обем и двата капацитета; премахването на което и да е от тях прави задачата решима.

why-infeasibleVVL

[optimize:problem Objectif
  [decision $a Integer [min 0] [max 10]]
  [decision $b Integer [min 0] [max 10]]
  [assert (($a + $b) >= 15)]     # volume demandé
  [assert ($a <= 3)]              # capacité de la ligne A
  [assert ($b <= 4)]              # capacité de la ligne B
  [maximize ($a + $b)]]
[optimize:solve Objectif]           # no solution (status=INFEASIBLE)
[optimize:why-infeasible Objectif]

Описание на задачата на естествен език

За първа чернова задачата може да бъде описана на естествен език. Езиковият модел пише модела, който можете да прегледате, след което решателят го решава. Допълнително намерение се добавя по същия начин.

на естествен езикVVL

[optimize "Une équipe de trois personnes, Alice, Bob et Carol, doit assurer la présence pendant deux jours. Chaque jour il faut au moins deux personnes au poste. Alice ne peut travailler qu'un seul jour. On veut minimiser le nombre total de jours travaillés." "Planning"]
[print [optimize:code Planning]]                           # le modèle généré, lisible
$sol = [optimize:solve Planning]
[intent "Alice doit travailler au moins un jour" "Planning"]
$sol2 = [optimize:solve Planning]

Гаранции

Какво гарантира и какви са ограниченията

Решение, обявено за оптимално, е оптимално за описания модел: това е доказателство от решателя, а не оценка.
Невъзможността се обяснява с минималното множество от конфликтни ограничения.
Моделът остава четим и може да се версионира, включително когато е написан от езиковия модел.
Моделите са линейни: произведения на две решения, деления и степени не се приемат, а печатна грешка в ключова дума се съобщава, вместо да бъде пренебрегната.

Към практиката

Да приложите тези разработки към вашите процеси?

Тези инструменти са инструкции на езика VVL: нашите партньори ги внедряват при своите клиенти върху платформите на ProSuite.

Станете партньор Всички теми