[Algoritme] Auto&#039;s verhuren met specifieke eisen

woensdag 24 november 2004 11:54

Topicstarter

@LordSnow:
Misschien wel handig om erbij te zetten.

De aanvragen voor de verhuring worden allemaal per maand opgespaard en dan ineens behandeld. Er wordt niet vooruit gekeken naar de volgende maand.

@Fool:
Dus eigenlijk een soort van brute-force op d overgebleven groep?

@DutchTSE
Maar stel nou dat je maar 1 cabrio 3L hebt? En een heleboel van auto's die in meerdere testen kunnen meedoen, maar waarvan je er te weinig hebt.

[ Voor 40% gewijzigd door BestTested! op 24-11-2004 11:51 ]

Acties:

Verwijderd

Is een soort van greedy algoritme niet het makkelijkst?

Als er aanvragen binnenkomen ga je auto's uitlenen gesorteerd op: het aantal testen waarvoor ze gebruikt kunnen worden (moet je wel vantevoren weten) aflopend, en dan het aantal gereden kilometers oplopend.

Op die volgorde ga je ze uitgeven.

Ik weet niet direct of dit ook het meest optimale algoritme is; het hangt een beetje van de opdracht af en of er ook geld verbonden is aan het verhuren van de auto's. Zo ja, dan is het misschien beter om met het verhuren te wachten als een bod niet hoog genoeg is, zo niet, dan is verhuren aan de 1 niet significant anders dan verhuren aan de ander, en kun je auto's beter zo snel mogelijk verhuren, dan zijn ze in elk geval de deur uit (en leveren ze geld op).

Met het risico dat je dan later een order niet meer volledig kunt voldoen. Als halve orders niet mogen is dat natuurlijk een probleem.

Maar je moet vantevoren weten welke orders je gaat krijgen, om hier iets aan te kunnen doen. Als de orders onderdeel zijn van de specificatie, dan wordt het een ander probleem (namelijk: hoe verdeel je de voorraad auto's zodat aan zoveel mogelijk opdrachten voldaan is).

Als de bedoeling is om zoveel mogelijk orders te voldoen, dan handel je de orders af van klein naar groot. Als de bedoeling is om zoveel mogelijk auto's te verhuren, handel je de orders af van groot naar klein.

woensdag 24 november 2004 12:12

Acties:

_fool

Helemaal zo gek nog niet

BestTested! schreef op woensdag 24 november 2004 @ 11:46:
@Fool:
Dus eigenlijk een soort van brute-force op d overgebleven groep?

Nou, eigenlijk niet eens op de overgebleven groep, maar op de hele groep. Het algoritme vindt dan vanzelf die auto's die eenduidig in te delen zijn. Het is inderdaad een tikkie brute force, maar ik weet ook niet of er voor dit probleem een mooie oplossing is, en een oplossing als deze is in ieder geval robuust.

specs

woensdag 24 november 2004 12:13

Acties:

woensdag 24 november 2004 12:15

Topicstarter

Het probleem is inderdaad dat alle order helemaal gevuld moeten worden. Een greedy algortime kan dus uitkomen op een situatie met half gevulde orders.

Ik was zelf meer aan het denken richten een zoekboek voor de overgbleven groep auto's

Je begint met een auto, elke pad naar onder is een mogelijkheid voor een verhuring. Bijvoorbeeld auto 1, heeft paden A,B,C. Dan kom je bij auto 2, die heeft paden B en C. Je zou dan de weg die je kiest kunnen laten afhangen van het gereden kilometers.
Mocht je onderaan komen en een order is nog niet gevuld, dan moet je gaan backtracken.
Het probleem is alleen dat je wanneer er auto's dubbel moeten worden verhuurd je op deze manier geen oplossing krijgt.

@Fool:
Je zou dan zoiets krijgen:
AutoWeek(A B C D E F G H I....)
TopGear(A B C D E....)
etc.

Je stelt dan als regels dat binnen 1 groep geen dubbele mogen voorkomen en dat het totaal aantal dubbelen over de totale groepen zo klein mogelijk moet zijn.
Hier zit nog best iets in. Zoiets is makkelijke implementeren in ProLog natuurlijk.

[ Voor 21% gewijzigd door BestTested! op 24-11-2004 12:17 ]

Acties:

Verwijderd

Is überhaupt gegeven dat het mogelijk is om alle orders te voldoen?

woensdag 24 november 2004 12:20

Acties:

woensdag 24 november 2004 12:25

Topicstarter

Verwijderd schreef op woensdag 24 november 2004 @ 12:15:
Is überhaupt gegeven dat het mogelijk is om alle orders te voldoen?

Gegeven het enorme aantal auto's dat de garage bezit mogen we er vanuit gaan dat dit mogelijk is. Van te voren is er nog wel een check, is dit niet mogelijk, dan wordt de gehele order geschrapt en de klant op de hoogte gesteld.
In het uiteindelijk probleem zitten dus alleen orders die helemaal gevuld kunnen en moeten worden op de meest ideale manier.

Acties:

woensdag 24 november 2004 12:30

Software Architect

Werkt hier

BestTested! schreef op woensdag 24 november 2004 @ 12:13:
Het probleem is inderdaad dat alle order helemaal gevuld moeten worden. Een greedy algortime kan dus uitkomen op een situatie met half gevulde orders.

Je kan natuurlijk ook groepsindelingen aanmaken en zodra er een halve order zou zijn, die indeling schrappen van je lijstje. En daarbij gelijk kijken of een indeling (kostentechnisch) "beter" is dan al bekende indelingen en ook om die reden uitsluiten van verdere beoordeling.
't Is een beetje een naieve/kostbare aanpak, maar levert in theorie wel de beste oplossing op.

Ik geloof dat je een NP-Complete probleem te pakken hebt en daardoor zijn er helaas geen echt efficiente oplossingen die een perfect resultaat opleveren

Acties:

woensdag 24 november 2004 12:39

Wat is het doel nu? Het maximum aantal tests waaraan een enkele auto meedoet minimaliseren? Of gaat het om kilometers per auto minimaliseren? Ik kan me voorstellen dat dat uitmaakt voor het soort oplossingsalgoritme wat in aanmerking komt (al is het eerste een specialisatie van het tweede probleem.)

Acties:

Verwijderd

ACM schreef op woensdag 24 november 2004 @ 12:25:
[...]
Ik geloof dat je een NP-Complete probleem te pakken hebt en daardoor zijn er helaas geen echt efficiente oplossingen die een perfect resultaat opleveren

Kun je beargumenteren waarom je denkt dat het een NP probleem is?

Een reductie tot een NPC probleem zou me bijvoorbeeld overtuigen.

Ik ga even proberen het probleem te recapituleren om te zien of ik het goed begrepen heb:

----------

Een garage bezit N auto's. Elke auto kan voldoen aan een aantal criteria, die we voor het gemak even A, B, C enz. zullen noemen. Bovendien heeft een auto een aantal gereden kilometers.

Ook zijn er een M aantal orders. Elke order omvat een aantal auto's, en een criterium. Alleen auto's die aan het gegeven criterium voldoen mogen geselecteerd worden voor deze order.

Gegeven is verder dat er voldoende auto's N zijn, die voldoen aan de juiste criteria, om aan alle M orders te voldoen.

Gevraagd wordt een algoritme te geven dat alle orders voldoet, zodat het totaal aantal gereden kilometers van alle geselecteerde auto's zo klein mogelijk is.
--------

Klopt? (En dan met name, klopt het exact zo?)

[ Voor 61% gewijzigd door Verwijderd op 24-11-2004 15:29 ]

woensdag 24 november 2004 12:43

Acties:

Infinitive

Je zou dit probleem wellicht met een Integer Linear Programming aan kunnen pakken. Bijvoorbeeld door variabelen u(i, t) te introduceren voor elke auto i en test t met als betekenis wel of niet meedoen aan de test. Ik weet al je voorwaarden niet, dus ik zou niet weten of dat ze wel lineair zijn. Als je niet al te veel auto's en tests hebt kan je een dergelijk probleem zelfs met Microsoft Excel oplossen.

putStr $ map (x -> chr $ round $ 21/2 * x^3 - 92 * x^2 + 503/2 * x - 105) [1..4]

woensdag 24 november 2004 12:46

Acties:

Verwijderd

Volgens mij moet er een aantal entities komen (-als je uitgaat van een database structuur);

- Auto's
- Categorieën (cabrio, 3.0L, etc.)

Een entitie auto heeft een aantal eigenschappen;
- Aantal gereden tests
- Momenteel in gebruik ja/nee

Praktijkvoorbeeld.

Auto entities:
1. BMW 3.0L
- gereden tests: 0
- niet in gebruik

2. Jaguar 3.0L Cabrio
- gereden tests: 1
- niet in gebruik

3. Mazda Cabrio
- gereden tests: 0
- niet in gebruik

- Opdracht 1 - voor 1 december:
Lever 2 drie liter+ wagens
- Opdracht 2 - voor 2 december:
Lever 2 cabrio wagens

Verhuur bepaling

1. selecteer 2 x 3.0L+ wagens
- Bekijk de 3.0L wagens die niet in gebruik zijn, daarna de 3.0Lwagens die momenteel in gebruik zijn.
- Bekijk vervolgens welke 3.0L wagens nog nooit gebruikt zijn, en anders oplopend.

Resultaat:
> BMW 3.0L (status "in gebruik zetten")
> Jaguar 3.0L Cabrio (idem)

2. selecteer 2 cabrio wagens
- Bekijk de cabrio wagens die niet in gebruik zijn, daarna de cabrio wagens die momenteel in gebruik zijn.
- Bekijk vervolgens welke cabrio wagens nog nooit gebruikt zijn, en anders oplopend.

Resultaat:
> Mazda cabrio (status "in gebruik zetten")
> Jaguar 3.0L Cabrio (status in de wacht +1 zetten o.i.d.)

--------------------------

Dit is niet een volledige oplossing maar geeft natuurlijk wel aan hoe je moet denken i.m.o. Denk structureel, denk logisch. Dan is iets dergelijks als deze kwestie vrij simpel op te lossen met behulp van een database.

woensdag 24 november 2004 13:08

Acties:

woensdag 24 november 2004 13:14

Verwijderd schreef op woensdag 24 november 2004 @ 12:39:
[...]
Gevraagd wordt een algoritme te geven dat alle orders voldoet, waarbij het totaal aantal gereden kilometers van de auto's die verhuurd worden geminimaliseerd wordt.

--------

Klopt? (En dan met name, klopt het exact zo?)

Dit kan nooit correct zijn, aangezien het totaal aantal gereden kilometers vantevoren vast ligt

Dat is namelijk de som van het aantal kilometers van alle tests.

Misschien wil TS het maximaal aantal, door één auto gereden, kilometers minimaliseren. Of misschien het gemiddeld aantal door een auto gereden kilometers, wat betekent dat je zoveel mogelijk auto's wilt inzetten.

Ik zou es beginnen met één of ander greedy process waarbij je een aantal regels opstelt om de kosten van een toekenning te representeren.

-kosten voor het aantal kilometers van de auto
-geen kosten voor het aantal kilometers van de test, deze zijn namelijk niet te ontwijken
-bij een test die door veel typen auto kan worden gereden, veel kosten voor een auto die maar voor weinig tests geschikt is en weinig voor een auto die voor veel tests geschikt is
-by een tests die door weinig typen auto kan worden gereden, veel kosten voor een auto die voor veel tests geschikt is en weinig voor een auto die voor weinig tests geschikt is
-veel kosten voor een zeldzame auto
-enz.

Kostenfunctietje van maken en wat spelen met de parameters tot je pretige resultaten krijgt.

[ Voor 55% gewijzigd door RickN op 24-11-2004 13:26 ]

He who knows only his own side of the case knows little of that.

Acties:

Verwijderd

RickN schreef op woensdag 24 november 2004 @ 13:08:
[...]
Dit kan nooit correct zijn, aangezien het totaal aantal gereden kilometers vantevoren vast ligt Dat is namelijk de som van het aantal kilometers van alle tests.

Ik snap niet wat je bedoelt met die laatste opmerking. Maar het aantal gereden kilometers ligt wel vast, maar niet welke auto's geselecteerd worden voor verhuur. Dus van die groep kun je de gereden kilometers minimaliseren (zodat het totaal aantal gereden kilometers van alle auto's na afloop van de test nog steeds minimaal is).

woensdag 24 november 2004 13:18

Acties:

Verwijderd

Formuleren als ILP probleem (integer linear programming), vervolgens mbv Excel of CPLEX oid oplossen.

woensdag 24 november 2004 13:21

Acties:

woensdag 24 november 2004 13:31

Software Architect

Werkt hier

Verwijderd schreef op woensdag 24 november 2004 @ 12:39:
Kun je beargumenteren waarom je denkt dat het een NP probleem is?

Niet goed, dat is te lang geleden om dat allemaal goed overtuigend te brengen. De belangrijkste reden waarom ik het denk, is dat het lijkt op andere NPC problemen. Roosters genereren bijv, 't heeft zelfs wel wat van de travelling salesman, als je per auto gaat kijken.

Ook zijn er een M aantal orders. Elke order omvat een aantal auto's, en een criterium. Alleen auto's die aan het gegeven criterium voldoen mogen geselecteerd worden voor deze order.

Ik vermoed dat er "een of meer criteria" opgegeven kunnen worden.

Gevraagd wordt een algoritme te geven dat alle orders voldoet, waarbij het totaal aantal gereden kilometers van de auto's die verhuurd worden geminimaliseerd wordt.

Het totaal per individuele auto.

Soultaker schreef op woensdag 24 november 2004 @ 12:30:
Wat is het doel nu? Het maximum aantal tests waaraan een enkele auto meedoet minimaliseren? Of gaat het om kilometers per auto minimaliseren? Ik kan me voorstellen dat dat uitmaakt voor het soort oplossingsalgoritme wat in aanmerking komt (al is het eerste een specialisatie van het tweede probleem.)

In theorie is dat natuurlijk een kwestie van een wegingsfactor aan elke test hangen. In het eerste geval allemaal 1, in het tweede geval variabel met het aantal kilometers en/of eventuele andere omstandigheden.

Acties:

woensdag 24 november 2004 14:38

Verwijderd schreef op woensdag 24 november 2004 @ 13:14:
[...]

Ik snap niet wat je bedoelt met die laatste opmerking. Maar het aantal gereden kilometers ligt wel vast, maar niet welke auto's geselecteerd worden voor verhuur. Dus van die groep kun je de gereden kilometers minimaliseren (zodat het totaal aantal gereden kilometers van alle auto's na afloop van de test nog steeds minimaal is).

Hmmm, ik had je functie idd een beetje verkeerd gelezen. Je kunt niet het aantal gereden kilometers van de tests minimaliseren (zoals je hierboven toch wél lijkt te zeggen)
Maar je kunt wel een groep auto's uitkiezen waarvan het totaal aantal gereden kilometers minimaal is (voor de test). Echter, daarmee zeg je niks over de slijtage van individuele auto's.

He who knows only his own side of the case knows little of that.

Acties:

woensdag 24 november 2004 14:55

RickN schreef op woensdag 24 november 2004 @ 13:31:
Maar je kunt wel een groep auto's uitkiezen waarvan het totaal aantal gereden kilometers minimaal is (voor de test). Echter, daarmee zeg je niks over de slijtage van individuele auto's.

Hoe bedoel je dat? Het totaal gereden aantal kilometers staat (net als het totale aantal toegekende auto's, met multipliciteit meegerekend) volgens mij gewoon vast; daar valt niets mee te kiezen.

Acties:

miw

Verwijderd schreef op woensdag 24 november 2004 @ 12:39:
[...]

Kun je beargumenteren waarom je denkt dat het een NP probleem is?

Een reductie tot een NPC probleem zou me bijvoorbeeld overtuigen.

Ik ga even proberen het probleem te recapituleren om te zien of ik het goed begrepen heb:

----------

Een garage bezit N auto's. Elke auto kan voldoen aan een aantal criteria, die we voor het gemak even A, B, C enz. zullen noemen. Bovendien heeft een auto een aantal gereden kilometers.

Ook zijn er een M aantal orders. Elke order omvat een aantal auto's, en een criterium. Alleen auto's die aan het gegeven criterium voldoen mogen geselecteerd worden voor deze order.

Gegeven is verder dat er voldoende auto's N zijn, die voldoen aan de juiste criteria, om aan alle M orders te voldoen.

Gevraagd wordt een algoritme te geven dat alle orders voldoet, waarbij het totaal aantal gereden kilometers van de auto's die verhuurd worden geminimaliseerd wordt.

--------

Klopt? (En dan met name, klopt het exact zo?)

Dit lijkt verdacht veel op het "Knapsack" probleem en het "Bin Packing" probleem. Beide zijn NPC (Google maar even op die termen). Gelukkig zijn er voor kleinschalige problemen nog wel redelijk efficiente oplossingen voor dit soort optimaliseringstoepassingen.

woensdag 24 november 2004 15:27

Acties:

Verwijderd

Aangezien er nogal wat mensen over schijnen te vallen heb ik mijn bewoording aangepast.

woensdag 24 november 2004 20:43

Acties:

woensdag 24 november 2004 20:48

Ik denk dat ik er uit ben. Het probleem is op te lossen binnen redelijke tijd met standaardalgoritmen. Het is, zoals als de topic starter al aangaf, een matching probleem. Ik zal eerst een versimpelde versie bespreken en 'm vervolgens uitbreiden tot de volledige versie en tegelijkertijd aangeven hoe het algoritme aangepast moet worden aan het specifieke probleem.

Matchingproblemen worden meestal voorgesteld als een bipartiete graaf. Ik heb daar even een plaatje van geript:
Afbeeldingslocatie: http://www2.toki.or.id/book/AlgDesignManual/BOOK/BOOK17/IMG1317.GIF

Afbeeldingslocatie: http://www2.toki.or.id/book/AlgDesignManual/BOOK/BOOK17/IMG1317.GIF

Stel je voor dat de punten aan de linkerkant de auto's zijn en de punten aan de rechterkant de tests. Zo'n graaf heet bipartiet omdat er alleen verbindingen zijn tussen twee punten uit twee verschillende klassen (auto's en tests). De verbindingen worden bij dit probleem gevonden door de attributen van de auto's met de eisen voor de tests te vergelijken. Er is een verbinding tussen een auto en een test als die auto voor de test voldoet, en anders niet. Zo zou je in het plaatje kunnen zien dat de tweede en derde auto allebei geschikt zijn voor de vierde test (lijnen van het tweede en derde punt links naar het vierde punt rechts) maar dat de derde auto ook nog geschikt is voor de eerste test (lijn van het derde punt links naar het eerste punt rechts).

Het is duidelijk dat je zo'n graaf kunt tekenen op basis van de invoergegevens; de beschikbare auto's en tests (de knopen in de graaf) zijn gegeven en de verbindingen kun je opstellen aan de hand van de attributen van de auto's en eisen voor de tests die ook zijn gegeven. In zo'n graaf zit alle benodigde informatie verwerkt; welke attributen auto's nu precies hadden is dus niet meer van belang zodra je hebt vastgesteld bij welke tests ze ingezet kunnen worden. Nu eerst een oplossing voor een versimpelde versie van het probleem.

Stel dat voor elke test maar 1 auto nodig is en dat gegeven is dat je toevallig elke auto maar 1 keer hoeft te verhuren om tot een oplossing te komen. Je hoeft dan alleen maar verbindingen zo te kiezen dat aan elke test precies 1 auto gekoppeld is, en aan elke auto maximaal 1 test (voor deze situatie is het vereist dat er meer auto's dan tests zijn, natuurlijk). Dit is een standaardprobleem, dat meestal iets van maximum cardinality bipartite matching genoemd wordt (heb je wat om op te Google'en). In dit geval gaat het zelfs om perfect of complete matching, wat inhoud dat aan elke test (punten aan de rechterkant) een auto is toegekend. Zo'n oplossing vind je door de graaf systematisch om te bouwen naar een netwerk en er een maximum flow-algoritme op los te laten, zoals Ford-Fulkerson (ook daar kun je op zoeken). Ik ga dat in deze post niet verder uitleggen, maar het staat dus vast dat dit goed op te lossen is. Aangezien geen enkele auto meer dan een keer verhuurd wordt is deze oplossing ook optimaal voor het criterium: het maximale aantal tests waaraan een auto meedoet minimaliseren.

Nu moet het versimpelde probleem en het bijbehorende algoritme op twee punten aangepast worden, om tot aan de echte probleemstelling te voldoen. Ten eerste kan een test meer dan 1 auto nodig hebben; als voor een test 5 auto's nodig zijn voldoet het niet om er 1, 2, 3 of 4 toe te kennen. Ten tweede kan een auto meerdere keren uitgeleend worden. Grappig is dat beide punten op bijna dezelfde manier opgelost kunnen worden. Je moet er wel voor begrijpen hoe een bipartiet matchingprobleem omgezet wordt in een flowmaximalisatieprobleem in een netwerk. (Jammer genoeg heb ik daar geen geschikt plaatje voor; zie daarvoor de link helemaal onderaan deze post.)

Voor het eerste punt (meerdere auto's per test vereist) kun je de capaciteiten aan de rechterkant van de punten in het netwerk verhogen en nog steeds een maximum flow-algoritme kunt toepassen, waarmee je een bipartiete graaf hebt waarbij een complete (of perfect) matching een toekennig is waarbij niet langer aan elke test precies 1 auto is toegekend, maar evenveel auto's als er volgens de specificaties nodig waren.

Het tweede punt werkt op dezelfde manier, maar nu verhoog je aan de linkerkant de capaciteiten van de auto's. De capaciteit van een verbinding met een auto representeert het aantal keren dat die auto maximaal uitgeleend mag worden. Op voorhand weet je natuurlijk niet wat dat maximum is, maar je weet wel dat je het zo klein mogelijk wil houden, dus kun je het iteratief bepalen. Je initialiseert die capaciteiten dus gewoon op 1. Als de maximum flow daarmee niet optimaal is (dat is: gelijk aan de capaciteiten van de tests samen) dan moet je de capaciteit blijkbaar verhogen naar 2. Zo ga je door tot je een oplossing hebt; het lijkt me duidelijk dat die dan ook optimaal is met betrekking tot het gevraagde criterium.

Tenslotte heb ik nog een extra beperking achterwege gelaten, die niet zo duidelijk genoemd wordt, maar waar ik wel van aanneem dat hij geldt: elke auto mag maar 1 keer aan eenzelfde test toegekend worden. Ook dit is te realiseren door het netwerk aan te passen; waar je normaal gesproken uitgaat van een oneindige capaciteit in de verbindingen tussen de twee klassen in het netwerk (de lijnen van auto's naar tests), beperk je de capaciteit hier tot 1. Dit heeft tot gevolg dat, zelfs als je eenzelfde auto meerdere keren kan inzetten, je deze enkele auto maar 1 keer kunt toekennen aan eenzelfde test.

Mijn conclusie is dus dat het probleem is te reduceren tot een variant op een bipartiet matchingprobleem. De variaties die nodig zijn om de standaardalgoritmes op dit probleem toe te spitsen zijn niet zo ingrijpend, als je er even over nadenkt en weet waarmee je bezig bent. Uiteindelijk construeer je dus een netwerk waarin je in iteraties de maximale stroom berekend, totdat je de optimale stroom bereikt hebt. Uit de stroom in het netwerk kun je dan een optimale toekenning van de auto's aan tests aflezen.

De theorie over bipartiete matchings en hoe je die oplost met een maximum flow-algoritme in een netwerk, wordt hierin redelijk helder en to-the-point besproken:
http://www.cs.uu.nl/docs/vakken/amc/lecture03-8.pdf
Maar er is nog veel meer informatie over te vinden met Google.

Als mijn verhaal nog wat te onduidelijk is kan ik later nog wel een plaatje maken, dan wordt het misschien wat inzichtelijker.

Acties:

Verwijderd

Hiervoor is maar één sentiment toereikend:

$_/-\o_$

[ Voor 13% gewijzigd door Verwijderd op 24-11-2004 20:48 ]

woensdag 24 november 2004 21:43

Acties:

donderdag 25 november 2004 11:41

Topicstarter

Soultaker schreef op woensdag 24 november 2004 @ 20:43:
....Een uiterst indrukwekkend verhaal....

Wow. $_/-\o_$
Volgens mij is dit een (perfecte) oplossing. Ik moest het wel even 3x opnieuw doorlezen, maar zo moet het inderdaad lukken. Morgen waar weer eens mijn boek over Grafentheorie uit de kast halen en het allemaal netjes uitwerken.
Mochten er nog haken&ogen tevoorschijn komen dan zal ik dat laten weten, echter zijn aan alle voorwaarden netjes voldaan als ik het allemaal goed begrijp.

Bedank aan alle meegeholpen tweakers. Dit getuigt maar weer van het feit dat een groepje geinteresseerden, samenwerkend over internet, in 1 dag tijd een dermate ingewikkeld probleem goed weet op te lossen.

Acties:

donderdag 25 november 2004 12:10

Ik kan iets missen hoor (moet ook toegeven dat ik niet alle referenties heb bekeken), maar mij is niet duidelijk hoe dit algoritme kilometers minimaliseert. Het algoritme vind een maximale matching, maar houdt nog helemaal geen rekening met de kilometerstanden van de auto's. Als je zo elke maand een test moet afwerken heb je kans dat elke keer dezelfde auto's worden uitgekozen, terwijl er een gelijksoortige matching bestaat met auto's die minder kilometers hebben gereden. Dit algoritme garandeerd dus niet dat slijtage over het wagenpark gespreid wordt en als ik me niet vergis was dát juist hetgeen waarnaar geoptimaliseerd werd.

Om dus op je vraag te antwoorden:

Soultaker schreef op woensdag 24 november 2004 @ 14:38:
[...]

Hoe bedoel je dat? Het totaal gereden aantal kilometers staat (net als het totale aantal toegekende auto's, met multipliciteit meegerekend) volgens mij gewoon vast; daar valt niets mee te kiezen.

De auto's hebben kilometerstanden. Ik interpreteerde het probleem zo dat het de bedoeling was een set auto's te kiezen die de tests afdekken, zó dat het totaal van de kilometerstanden van deze auto's minimaal is, of b.v. de gemiddelde kilometerstand van de auto's (na de test) minimaal is.

Niets hiervan vind ik nog terug in bovenstaande oplossing. Mijn eerste indruk is ook dat het niet eenvoudig zal zijn het algoritme hiermee uit te breiden. Het algorithme is geschikt om een flow te maximaliseren, wat je met die flow modeleert bepaald wat je maximaliseert. Echter, in dit geval heb je 2 optimalisatie criteria: 1) het aantal tests dat een correcte wagentoewijzing krijgt moet gemaximaliseert worden en 2) het totaal van de kilometerstanden (of een gemiddelde ofzo) van de gekozen auto's moet geminimaliseert worden. Met dit algoritme is het het één of het ander. You can't have your cake and eat it too....

Je kunt natuurlijk wel alle maximale matchings bepalen en daar dan de meest optimale uit kiezen, maar dat vertraagt de boel weer. (En dat terwijl een naïve implementatie van een matching algoritme al niet echt snel te noemen is, d.w.z. als je niet oppast is het exponentieel, als je wel je best doet polynomiaal)

Maar goed, TS lijkt de oplossing te accepteren, dus wellicht heb ik het probleem verkeerd geinterpreteerd, of zie ik iets over het hoofd.

He who knows only his own side of the case knows little of that.

Acties:

dip

shut up ulé

mijn complimenten aan Soultaker!

It's scientifically known, that base improves the tase of cheezes!

donderdag 25 november 2004 16:08

Acties:

donderdag 25 november 2004 16:10

Topicstarter

Om nog even de verwarring tussen aantal gereden kilometers en aantal testen uit te weg te ruimen deze post.

Ik ben ervan uit gegaan dat er per test een aantal kilometers gereden moeten worden. Wat voor test dat is maakt (bij benadering) niet zoveel uit. Het aantal gereden kilometers is dus direct afhankelijk van het aantal testen waar een auto aan mee doet.

Gereden kilometers in het verleden of in de toekomst worden ook buiten wegen gelaten. Het gaat hier slechts om het aantal testen dat gereden wordt per auto per serie testen die tegelijk binnenkomt.

Aan deze eisen zijn in de oplossing van Soultaker op de juiste manier voldaan.

Acties:

donderdag 25 november 2004 16:39

RickN schreef op donderdag 25 november 2004 @ 11:41:
Ik kan iets missen hoor (moet ook toegeven dat ik niet alle referenties heb bekeken), maar mij is niet duidelijk hoe dit algoritme kilometers minimaliseert. Het algoritme vind een maximale matching, maar houdt nog helemaal geen rekening met de kilometerstanden van de auto's.

Dat klopt; dat was ook waar ik een vraag over stelde. Ik minimaliseer nu het aantal tests waaraan een auto meedoet (en niet noodzakelijkerwijs het totale aantal kilometers). Ik denk trouwens dat dit wel toe te voegen is.

Als je zo elke maand een test moet afwerken heb je kans dat elke keer dezelfde auto's worden uitgekozen, terwijl er een gelijksoortige matching bestaat met auto's die minder kilometers hebben gereden. Dit algoritme garandeerd dus niet dat slijtage over het wagenpark gespreid wordt en als ik me niet vergis was dát juist hetgeen waarnaar geoptimaliseerd werd.

Het algoritme gaat er vanuit dat de auto's en tests allemaal op voorhand bekend zijn. Voor de situatie die jij beschrijft is geen optimaal algoritme te bedenken (in die zin dat de toekenning gegarandeerd ideaal is), omdat je nooit van te voren weet welke tests er dus gaan komen. Je kunt misschien wat heuristieken gebruiken, maar feitelijk kun je nooit voorkomen dat als je moet kiezen uit twee auto's, je net die auto toekent die je volgende maand ook nodig hebt.

Wel zou je verschillende perfecte matchings kunnen genereren en de beste kiezen op basis van andere criteria.

De auto's hebben kilometerstanden. Ik interpreteerde het probleem zo dat het de bedoeling was een set auto's te kiezen die de tests afdekken, zó dat het totaal van de kilometerstanden van deze auto's minimaal is, of b.v. de gemiddelde kilometerstand van de auto's (na de test) minimaal is.

Volgens mij zit daar sowieso een interpretatiefout: het totaal en het gemiddelde (want dat is effectief hetzelfde) zijn constant! Welke auto je ook toekent, als je aan alle tests meedoet (wat gegeven is) dan ga je altijd die kilometers rijden. De vraag is alleen hoe je de kilometers over auto's verdeelt, maar daar heeft de totale of gemiddelde afstand niets mee van doen.

Maar goed, TS lijkt de oplossing te accepteren, dus wellicht heb ik het probleem verkeerd geinterpreteerd, of zie ik iets over het hoofd.

Ik heb alleen meegenomen wat ik duidelijk kon afleiden uit de probleemstelling. Je kunt er natuurlijk nog een heleboel criteria bij verzinnen die redelijk zijn, maar je moet wel bedenken dat dit probleem alleen maar een analogie was voor het werkelijke probleem van de TS. Wat logisch is voor auto's is misschien niet logisch voor machine-onderdelen.

Je hebt in je analyse in principe gelijk, dat je zegt dat het niet gegarandeerd dat allerlei extra criteria efficient toe te voegen zijn. Maar dat geldt altijd; als ik bijvoorbeeld ook de planning van auto's en tests zou wilen meenemen (met overlappende data, bijvoorbeeld) dan wordt het probleem NP-compleet.

Al met al moet je bij de constructie van zo'n algoritme eerst bedenken wat je feitelijk wil modeleren en daarbij niet onnodig veel zaken open laten. De discussie of het algoritme correct is, hangt dus nauw samen met of mijn interpretatie van het probleem volledig en correct is.

Acties:

donderdag 25 november 2004 16:48

Software Architect

Werkt hier

Soultaker schreef op donderdag 25 november 2004 @ 16:10:
Het algoritme gaat er vanuit dat de auto's en tests allemaal op voorhand bekend zijn. Voor de situatie die jij beschrijft is geen optimaal algoritme te bedenken (in die zin dat de toekenning gegarandeerd ideaal is), omdat je nooit van te voren weet welke tests er dus gaan komen. Je kunt misschien wat heuristieken gebruiken, maar feitelijk kun je nooit voorkomen dat als je moet kiezen uit twee auto's, je net die auto toekent die je volgende maand ook nodig hebt.

Wel zou je verschillende perfecte matchings kunnen genereren en de beste kiezen op basis van andere criteria.

Als je in je stal al vier auto's hebt die vorige maand aan een test meededen, dan heb je dus wel degelijk te maken met standen van verschillende maanden. Dat je niet kunt voorspellen wat er gaat komen is natuurlijk wat lastig.

Volgens mij zit daar sowieso een interpretatiefout: het totaal en het gemiddelde (want dat is effectief hetzelfde) zijn constant! Welke auto je ook toekent, als je aan alle tests meedoet (wat gegeven is) dan ga je altijd die kilometers rijden. De vraag is alleen hoe je de kilometers over auto's verdeelt, maar daar heeft de totale of gemiddelde afstand niets mee van doen.

Niet helemaal met je eens. Stel je kunt uit 20 auto's kiezen voor twee tests van 10 auto's. De ene test is per auto 400km, de andere 200.
Als je in totaal 10 auto's aan beide tests samen toekent, krijg je dus een gemiddelde van (400+200)*10/10 = 600km per auto gemiddeld, voor zover ze uitgedeeld zijn.

Bij 2 sets van 10, 20 auto's in totaal uitgedeeld, zou het gemiddelde 300km zijn.
Het totaal aantal kilometers is bij beide gelijk, maar het gemiddelde per uitgedeelde auto niet.

En als dan blijkt dat 2 auto's van die twintig al 600km op de teller hebben staan, ben je beter af door deze maand 2 auto's dubbel uit te lenen.

[ Voor 4% gewijzigd door ACM op 25-11-2004 16:41 ]

Acties:

donderdag 25 november 2004 17:08

BestTested heeft een en ander inmiddels verduidelijkt, dus Soultakers methode is correct.
Overigens snap ik niet helemaal waarom TS alleen naar de instantane slijtage van een test kijkt en niet naar een slijtage geschiedenis en een spreiding daarvan over het héle wagenpark.
Stel nu dat je een jaar lang elke maand de zelfde test krijgt, dan stuur je daar zonder geschiedenis te gebruiken elke maand dezelfde auto's naartoe, waardoor die dus erg hard slijten, terwijl er zeer waarschijnlijk andere auto's in het wagenpark zitten die tenminste een deel van de tests op zich zou kunnen nemen om de slijtage een beetje te spreiden.

Maar stel nou dat je wel het verleden in je berekening mee zou willen nemen. Voor dat geval wil ik mijn observaties nog iets verduidelijken.

Soultaker schreef op donderdag 25 november 2004 @ 16:10:
[...]

Het algoritme gaat er vanuit dat de auto's en tests allemaal op voorhand bekend zijn. Voor de situatie die jij beschrijft is geen optimaal algoritme te bedenken (in die zin dat de toekenning gegarandeerd ideaal is), omdat je nooit van te voren weet welke tests er dus gaan komen. Je kunt misschien wat heuristieken gebruiken, maar feitelijk kun je nooit voorkomen dat als je moet kiezen uit twee auto's, je net die auto toekent die je volgende maand ook nodig hebt.

Ik wilde uiteraard niet voorstellen in de toekomst te kijken nee. Ik wilde de kilometerstanden van de auto's in het wagenpark meenemen in de berekening, omdat die eigenlijk het slijtage verleden modeleren.
Stel je voor dat je van alle auto's in het wagenpark de kilometerstand weet. Vervolgens komt er een aanvraag voor auto's voor een test binnen. Stel nou dat er twee verschillende subsets van je wagenpark voor die test geschikt zouden zijn.
Ik stelde nu voor om in dat geval die subset te nemen waarvan het totaal van de kilometerstanden het kleinst is (dit verschilt per subset van je wagenpark) of om die subset te nemen waarvan het gemiddelde van de kilometerstanden (na de test) het kleinst is. Hiermee zou je de slijtage van meerdere tests over het hele wagenpark verspreiden (voor zover mogelijk natuurlijk)

Wel zou je verschillende perfecte matchings kunnen genereren en de beste kiezen op basis van andere criteria.

Ja, het totaal aantal kilometers dat de auto's in zo'n matching al hebben gereden b.v.

[...]

Volgens mij zit daar sowieso een interpretatiefout: het totaal en het gemiddelde (want dat is effectief hetzelfde) zijn constant! Welke auto je ook toekent, als je aan alle tests meedoet (wat gegeven is) dan ga je altijd die kilometers rijden. De vraag is alleen hoe je de kilometers over auto's verdeelt, maar daar heeft de totale of gemiddelde afstand niets mee van doen.

Het totaal van de kilometerstanden van het héle wagenpark staat natuurlijk vast, en het gemiddelde ook, maar ik bedoelde dus dat je dat per geschikte subset van het wagenpark zou uitrekenen en daar je beslissing op zou baseren.

[...]

Ik heb alleen meegenomen wat ik duidelijk kon afleiden uit de probleemstelling. Je kunt er natuurlijk nog een heleboel criteria bij verzinnen die redelijk zijn, maar je moet wel bedenken dat dit probleem alleen maar een analogie was voor het werkelijke probleem van de TS. Wat logisch is voor auto's is misschien niet logisch voor machine-onderdelen.

Je hebt in je analyse in principe gelijk, dat je zegt dat het niet gegarandeerd dat allerlei extra criteria efficient toe te voegen zijn. Maar dat geldt altijd; als ik bijvoorbeeld ook de planning van auto's en tests zou wilen meenemen (met overlappende data, bijvoorbeeld) dan wordt het probleem NP-compleet.

Al met al moet je bij de constructie van zo'n algoritme eerst bedenken wat je feitelijk wil modeleren en daarbij niet onnodig veel zaken open laten. De discussie of het algoritme correct is, hangt dus nauw samen met of mijn interpretatie van het probleem volledig en correct is.

Inderdaad, vandaar ook dat ik mijn analyse gaf onder de aanname dat mijn interpretatie van het probleem correct was

[ Voor 6% gewijzigd door RickN op 25-11-2004 17:15 ]

He who knows only his own side of the case knows little of that.

Acties:

donderdag 25 november 2004 17:26

ACM schreef op donderdag 25 november 2004 @ 16:39:
Als je in je stal al vier auto's hebt die vorige maand aan een test meededen, dan heb je dus wel degelijk te maken met standen van verschillende maanden.

Accoord. Daar zou je nog wat mee kunnen doen (ik ga daar onderaan deze post nog even op door.) Maar daar heb ik de TS niet over gehoord.

ACM schreef op donderdag 25 november 2004 @ 16:39:
Niet helemaal met je eens. Stel je kunt uit 20 auto's kiezen voor twee tests van 10 auto's. De ene test is per auto 400km, de andere 200.
Als je in totaal 10 auto's aan beide tests samen toekent, krijg je dus een gemiddelde van (400+200)*10/10 = 600km per auto gemiddeld, voor zover ze uitgedeeld zijn.
Bij 2 sets van 10, 20 auto's in totaal uitgedeeld, zou het gemiddelde 300km zijn.
Het totaal aantal kilometers is bij beide gelijk, maar het gemiddelde per uitgedeelde auto niet.

Het punt was juist dat je de kilometers zo gelijke mogelijk wilde verdelen over de auto's die je hebt. Beetje raar om dan auto's die toevallig 0 kilometer gereden hebben niet mee te tellen voor het gemiddelde (en auto's die 1 kilometer hebbben gereden dan weer wel!). Zo wordt het wel een heel vreemd verhaal natuurlijk.

En als dan blijkt dat 2 auto's van die twintig al 600km op de teller hebben staan, ben je beter afdoor deze maand 2 auto's dubbel uit te lenen.

Als je het doel hebt het maximum te minimaliseren, dan zou je dat kunnen doen. Overigens is de huidige oplossing makkelijk aan te passen zodat auto's al beginnen met een aantal tests, en dat een oplossing het totale aantal tests minimaliseert. Dat kun je doen door aan een elke auto nog een X aantal 'fictieve' tests te koppelen, gelijk aan het aantal tests waaraan 'ie al mee had gedaan. Overigens kun je van die X voor elke auto de minimale X van alle auto's aftrekken, omdat het alleen maar gaat om het verschil: als alle auto's al aan 10 tests mee hebben gedaan, is dat hetzelfde als wanneer alle auto's al aan 0 tests mee hadden gedaan.

edit:
Ik denk dat dit ook redelijk tegemoet komt aan RickN's kanttekeningen, als je er van uitgaat dat gereden kilometers proportioneel zijn aan gereden tests. Als je twee geschikte subsets hebt, zullen die elkaar automatisch afwisselen omdat ze hun geschiedenis meenemen.

[ Voor 9% gewijzigd door Soultaker op 25-11-2004 17:20 ]

Acties:

donderdag 25 november 2004 17:45

Software Architect

Werkt hier

Soultaker schreef op donderdag 25 november 2004 @ 17:08:
Accoord. Daar zou je nog wat mee kunnen doen (ik ga daar onderaan deze post nog even op door.) Maar daar heb ik de TS niet over gehoord.

't Was wat ik in eerste instantie eruit interpreteerde

Het punt was juist dat je de kilometers zo gelijke mogelijk wilde verdelen over de auto's die je hebt. Beetje raar om dan auto's die toevallig 0 kilometer gereden hebben niet mee te tellen voor het gemiddelde (en auto's die 1 kilometer hebbben gereden dan weer wel!). Zo wordt het wel een heel vreemd verhaal natuurlijk.

't Verschil is natuurlijk dat die met 0 km's helemaal de garage niet uit geweest zijn. Die zijn dus gewoon niet verhuurd, als je met de voorgaande maanden erbij bekijkt dan kun je dus naar de toename van de slijtage/het verbruik kijken. Maar als je dan de gemiddelde toename wilt weten, moet je wel uitkijken dat je niet steeds de auto's die helemaal niet gebruikt zijn die ronde meeneemt. Want dan is er inderdaad geen minimalisatie van een gemiddelde mogelijk.
't Moet natuurlijk wel zo zijn dat je een zo gelijkmatig mogelijke slijtage over het hele wagenpark wilt hebben, want anders is het niet zo zinvol om die 0-slijtages uit te sluiten.

edit:
Ik denk dat dit ook redelijk tegemoet komt aan RickN's kanttekeningen, als je er van uitgaat dat gereden kilometers proportioneel zijn aan gereden tests. Als je twee geschikte subsets hebt, zullen die elkaar automatisch afwisselen omdat ze hun geschiedenis meenemen.

Mijn reactie op de jouwe was ook mede om RickN's punten te verduidelijken

Acties:

brokenp

Ik denk ook dat de TS eigenlijk vraagt naar een oplossing die een minimum oplevert voor de volgede som:
SOM(a € Auto; (n-a)^2) of SOM(a € Auto; |n-a|)
waarbij n het gemmideld aantal kilometers is over het wagenpark en a het aantal gereden km voor een auto.

Ik denk dat je een oplossing hiervoor moet zoeken door de auto die het verst onder het gemiddelde staat als 1e toe te kennen aan een test (als dit mogelijk is) en hierna op zoek te gaan naar een bipartiete matching,
(PS als deze som geminimaliseerd moet worden, dan lijkt het probleem me toch wel NP-compleet; na het eten ff nadenken over een reductie vanuit TSP ofzo)

donderdag 25 november 2004 18:10

Acties: