Zápočtový projekt pro předmět IZI437 - Modelování znalostí

Copyright © květen 2000   Martin Přikryl, Aleš Dvorák a Vratislav Šimáček

Obsah

  1. Formulace úlohy
  2. Metoda řešení
  3. Popis metody řešení
  4. Popis rolí
  5. Doménová ontologie
  6. Přílohy
  7. Použitá literatura a zdroje

Formulace úlohy

Pokoušíme se vyvinout znalostní systém určený pro malé speditérské firmy.

Speditérské firmy realizují zakázky, při nichž přepravují zboží z místa naložení do cílového místa pomocí vlastních nákladních automobilů. Při delších trasách využívají pronajatých meziskladů.

Při realizaci svých zakázek k nim musí firma efektivně přiřazovat dostupné zdroje. Základní využívané zdroje jsou vlastní nákladní automobily, pronajaté mezisklady a řidiči. Při přiřazování zdrojů se zohledňuje zisk ze zakázek, náklady na zdroje, které se odvozují z velikosti přepravovaného nákladu, kapacity a spotřeby vozidel, jednotkových nákladů na uskladnění v meziskladech a jejich kapacity.

Firmy vlastní nákladní automobily s různými kapacitami nákladového prostoru. Nákladové prostory automobilů mohou být kryté (plachta nebo box) a nekryté, případně se mohou lišit svým vybavením (chlazení vnitřního prostoru, přihrádky atd.). Spotřeba nákladních automobilů je v průměru přímo úměrná kapacitě a typu nákladového prostoru. Některé firmy provádějí zakázky i v zahraničí, z tohoto důvodu musejí některé automobily splňovat další podmínky (dálniční známky, pojištění, technické parametry ...).

Jak již bylo výše řečeno, firmy využívají pro svou činnost pronajaté sklady. Mají uzavřené smlouvy s různými firmami po celém území, kam zasahuje jejich podnikatelská činnost. Sklady se od sebe liší kapacitou, vnitřním vybavením, náklady na pronájem 1 m2, geografickým umístěním ...

Speditérské firmy zaměstnávají řidiče. Zaměstnaní řidiči se liší ochotou jezdit do zahraničí, schopností obsluhovat specializované zařízení nákladního automobilu, dále se liší finančním ohodnocením za provedenou zakázku ...

Problémem je přiřadit k těmto zakázkám jednotlivé řidiče, vozidla s různými kapacitami a jízdními vlastnostmi a v neposlední řadě efektivně řešit uložení zboží v konkrétních celních skladech.

Metoda řešení

Klikněte pro zvětšení diagramu. Metoda řešení (6 kB)

Popis metody řešení

Přijatá zakázka je na základě jejích atributů zařazena do obecné třídy zakázek (abstrakce). Na základě známých omezení (dostupné automobily, řidiči...) je rozhodnuto (compute) o přijetí resp. nepřijetí zakázky. Tím dojde ke specializaci třídy zakázka do tříd přijatá zakázka resp. nepřijatá zakázka.

Pokud je rozhodnuto o přijetí zakázky, dochází k výběru a přiřazení (asociaci) automobilu a řidiče k provedení této zakázky. Obého je dosaženo stejným postupem. Ze seznamu automobilů resp. řidičů (collection of objects) jsou cyklicky vybírány jednotlivé instance tříd automobil resp. řidič a testována (compute) jejich vhodnost pro přiřazení k zakázce.

Po nalezení vhodného řidiče a automobilu dojde k jejich asociaci a vytvoření instance třídy Realizovatelná zakázka (Assemble). U ní je na základě omezení (kapacita, ...) rozhodnuto (compute), jestli je třeba použít skladu. Pokud ano, je vybrán vhodný sklad ze seznamu skladů (collection of objects).

Výsledkem je zakázka připravená k realizaci.

Popis rolí

Classify
Vstup: PROBLEM (Zakazka)
Výstup: CLASSIFICATION (Druh zakazky)
Compute
Vstup: CONSTRAINT (Omezeni), CLASSIFICATION (Druh zakazky), SOLUTION (Prijata zakazka, Realizovatelna zakazka), ELEMENT (Vybrany ridic, Vybrany automobil)
Výstup: SOLUTION (Odmitnuta zakazka, Prijata zakazka), DECISION (Nevyhovujici ridic, Nevyhovujici automobil, Vyhovujici ridic, Vyhovujici automobil), CONCLUSION (Zakazka pripravena k realizaci, Zakazka potrebujici sklad)
Select
Vstup: CONSTRAINT (Ridici, Automobily, Sklady), DECISION (Nevyhovujici ridic, Nevyhovujici automobil), CONCLUSION (Zakazka potrebujici sklad)
Výstup: ELEMENT(Vybrany ridic, Vybrany automobil), CONCLUSION (Zakazka pripravena k realizaci)
Assemble
Vstup: SOLUTION (Prijata zakazka), DECISION (Vyhovujici ridic, Vyhovujici automobil)
Výstup: SOLUTION (Realizovatelna zakazka)

Doménová ontologie

Klikněte pro zvětšení diagramu. Doménová ontologie (5 kB)

Vazba mezi automobilem, řidičem a skladem
Vazba mezi automobilem, řidičem a skladem (3 kB)

Při návrhu doménového modelu jsme vycházeli z ontologie JOB-ASSIGNMENT-TASK v knihovně Ontolingua.

V této ontologii jsou nadefinovány třídy Assignment-object, Source, Target, Resource a Job. Ontologie je určena k řešení problému přiřazování dostupných zdrojů k určitým úkolům. V našem případě jsou zdroji automobily, řidiči a sklady a úkolem je zakázka. Třída Zdroj je nadefinována nad třídou Resource, jako společný základ pro naše zdroje, důvodem je společný atribut Zakazka, který slouží k přiřazení zdrojů k zakázce.

Na druhém diagramu je zobrazena vznikající vazba mezi automobilem, řidičem a alternativně i skladem, které spolu se zadanou zakázkou vytvoří instanci třídy realizovatelná zakázka.

Přílohy

Ontology JOB-ASSIGNMENT-TASK

(in-package "ONTOLINGUA-USER")

(define-ontology JOB-ASSIGNMENT-TASK (frame-ontology simple-time)
    "This ontology defines a task ontology for the job assignment task.
The job assignment task, which is a class of sheduling problems, is a
problem of assigning all given jobs to the available resources within
the time range, while satisfying various constraints."
  :maturity :moderate
  :generality :low

    :issues ((:copyright "(C) Copyright IBM Corp. 1992
 This file is included in the IBM Research Report RT0084,
 \"Task-Specific Language Constructs for Describing Constrints in
  Job Assignment Probelms\" by T.Hama, M.Hori, and Y.Nakamura.")))

(in-ontology 'JOB-ASSIGNMENT-TASK)

(define-class ASSIGNMENT-OBJECT (?object)
    "ASSIGNMENT-OBJECT denotes an object appearing generally in
assignment problems."
    :def (individual ?object)
    :axiom-def (subclass-partition
                ASSIGNMENT-OBJECT
                (setof source target))
)

(define-class SOURCE (?source)
    "SOURCE denotes an object to be assigned to an object of TARGET."
    :def (assignment-object ?source)
)

(define-class TARGET (?target)
    "TARGET denotes an object to which an object of SOURCE is to be
assigned."
    :def (assignment-object ?target)
)

(define-function ASSIGNMENT (?source) :-> ?target
    "ASSIGNMENT denotes a mapping from SOURCE to TARGET."
    :def (and (source ?source)
              (target ?target))
)


(define-class JOB (?job)
    "JOB is an abstract class that denotes an object to be assigned to
     a resource, or a collection of such objects."
    :def (source ?job)
)

(define-class TEMPORALLY-FIXED-JOB-CLASS (?class)
    "TEMPORALLY-FIXED-JOB-CLASS denotes a job whose assignment to a
time range is predefined."
    :iff-def (and (class ?class)
                  (subclass-of ?class job)
                  (cardinality assigned-time-range ?class 1))
)

(define-class FIXED-LENGTH-JOB-CLASS (?class)
    "FIXED-LENGTH-JOB-CLASS  denotes a job whoes length is independent
of a resource and fixed."
    :iff-def (and (class ?class)
                  (subclass-of ?class job)
                  (cardinality fixed-length-job.length ?class 1))
)

(define-class UNIT-LENGTH-JOB-CLASS (?class)
    "UNIT-LENGTH-JOB denotes a job whose length is the same."
    :iff-def (and (fixed-length-job-class ?class)
                  (cardinality JOB-UNIT-LENGTH ?class 1)
                  (forall ?i (=> (instance-of ?i ?class)
                                 (= (fixed-length-job.length ?i)
                                    (job-unit-length ?class)))))
)

(define-function JOB-UNIT-LENGTH (?job-class) :-> ?length
    "Each job class of unit-length-job-class has its own length."
    :def (and (unit-length-job-class ?job-class)
              (duration ?length))
)

(define-function JOB.LENGTH (?job ?res) :-> ?length
    "JOB.LENGTH returns a duration of the job."
    :def (and (job ?job)
              (resource ?res)
              (duration ?length))
)

(define-function FIXED-LENGTH-JOB.LENGTH (?job) :-> ?length
    "FIXED-LENGTH-JOB.LENGTH returns a duration of the job. The length
does not depend on resources."
    :def (and (job ?job)
              (duration ?length))
)

(define-function JOB.TIME-RANGE (?job) :-> ?time-range
    "JOB-TIME-RAGNE returns a time range where a job is permitted to
     be assigned"
    :def (and (job ?job)
              (time-range ?time-range))
)

(define-class RESOURCE (?resource)
    "RESOURCE is an abstract class that denotes an object to which a
     job is assigned, or a collection of such objects."
    :def (target ?resource)
)

(define-class JAT-TIME-RANGE (?time-range)
    "JAT-TIME-RANGE denotes a time range which is referred to in the
job assignment task."
    :def (and (time-range ?time-range)
              (target ?time-range))
)

(define-class DISCRETE-TIME-RANGE-CLASS (?class)
    "DISCRETE-TIME-RANGE-CLASS denotes a time range whose start time
and end time are measured by a time-range-unit."
    :iff-def (and (class ?class)
                  (cardinality TIME-RANGE-UNIT ?class 1)
                  (forall ?i (=> (instance-of ?i ?class)
                                 (and (measured-by
                                       (start-time-of ?i)
                                       (time-range-unit ?class))
                                      (measured-by
                                       (end-time-of ?i)
                                       (time-range-unit ?class))))))
)

(define-function TIME-RANGE-UNIT (?tr-class) :-> ?unit
    "A time-range class of discrete-time-range-class has its own
minimun unit of duration."
    :def (and (discrete-time-range-class ?tr-class)
              (duration ?unit))
)

(define-relation MEASURED-BY (?tp ?unit)
    "A time point ?tp can be measured by a unit of duration ?unit."
    :def (and (time-point ?tp)
              (duration ?unit))
)

(define-class UNIT-TIME-RANGE-CLASS (?class)
    "UNIT-TIME-RANGE-CLASS deontes a time ragne whose duration is a
unit length."
    :iff-def (and (discrete-time-range-class ?class)
                  (forall ?i (=> (instance-of ?i ?class)
                                 (= (duration-of ?i)
                                    (time-range-unit ?class)))))
)


(define-function ASSIGNED-RESOURCE (?job) :-> ?res
    "ASSIGNED-RESOURCE returns a resouce to which a job is assinged."
    :def (and (job ?job)
              (resource ?res))
    :axiom-def (subrelation-of assigned-resource assignment)
)

(define-function ASSIGNED-TIME-RANGE (?job) :-> ?time-range
    "ASSIGNED-TIME_RANGE returns a time range to which a job is assigned."
    :def (and (job ?job)
              (jat-time-range ?time-range))
    :axiom-def (subrelation-of assigned-time-range assignment)
)

Použitá literatura a zdroje

  1. Tansley, D. S. W., Hayball, C. C.: Knowledge-Based Systems Analysis and Design, Prentice Hall Intl. Ltd., U.K. 1993
  2. Řepa, V., Chlapek, D.: Materiály ke strukturované analýze, VŠE, Praha 1997
  3. Reusabilní zdroj znalostí - ontologie JOB-ASSIGNMENT-TASK (součást knihovny Ontolingua) na adrese: http://www-ksl-svc-lia.dia.fi.upm.es:5915/
  4. Materiály z přednášek k předmětu IZI437

Poznámka: Součástí archívu ke stažení jsou kromě tohoto dokumentu i datové soubory.