Wiskundeforum

Beste allemaal,

Ik ben op dit moment bezig met het oplossen van een probleem voor mijn opleiding. Het ziet er als volgt uit. Ik heb een graaf met verschillende locaties. Deze locaties zijn niet allen verbonden. De verbindingen staan in een afstandenmatrix. Daarnaast zijn er trucks. Deze trucks staan op een bepaalde plek en hebben de licentie om in twee landen te mogen rijden. Het probleem is opgedeeld in twee stukken:

1 Vind het kortste pad van locatie A naar B en welke trucks delen van de route rijden. Hierbij moet je rekening houden met de afstand die de truck eerst moet afleggen om op het startpunt van dat deel van de route te komen. Dit stuk is in orde en werkt zoals ik het wil.
2 Het tweede deel van het probleem is bijna hetzelfde maar in deel een hoef je voor de berekening van de kortste pad geen rekening te houden met de afstand die de trucks eerst moeten afleggen terwijl dit wel van belang kan zijn.

Het tweede deel van het probleem is waar ik vast loop. Is er iemand die weet hoe dit op te lossen is.

Alvast Bedankt!

Michiel

Mogelijk kan je iets meer uitleg geven hoe we dit moeten zien:
hoeveel steden/locaties zijn er ongeveer per land, hoe is aangegeven in welk land welke stad ligt, hoe is gedefinieerd welke vrachtwagen in welk land mag rijden?

Zonder deze informatie zou je zeggen dat je direct het kortste pad algoritme van Dijkstra kan gebruiken: volg het kortste pad en laat de vrachtwagens achtereenvolgens naar een punt op dit pad komen om de lading over te zetten. De afgelegde weg is dan gelijk aan de lengte van het kortste pad.

Dit gaat echter mis als geen enkele vrachtwagen de grens van land_i naar land_(i+1) op dat pad over mag. Je zal dan een route via andere landen moeten zoeken.

Vandaar graag iets meer toelichting.

Er zijn in totaal 14 locaties en 11 trucks. Hieronder de data van de locatie:

(100, 'Tilburg', 'NL'),
(101, 'Rotterdam', 'NL'),
(102, 'Breda', 'NL'),
(103, 'Venlo', 'NL'),
(104, 'Groningen', 'NL'),
(200, 'Hamburg', 'DE'),
(201, 'Passau', 'DE'),
(202, 'Duisburg', 'DE'),
(300, 'Gdansk', 'PL'),
(301, 'Warsaw', 'PL'),
(400, 'Kiew', 'UK'),
(500, 'Vienna', 'AT'),
(600, 'Basel', 'CH'),
(700, 'Milano', 'IT');

Daarnaast heb ik een tabel met trucks en daarnaast een tabel met licensies.

Trucks:

('N10001', 100, 0),
('N10002', 102, 0),
('N10003', 102, 0),
('D10001', 201, 0),
('D10002', 201, 0),
('D10003', 201, 0),
('D10004', 201, 0),
('P10001', 300, 0),
('P10002', 300, 0),
('S10001', 600, 0),
('S10002', 700, 0);

Licensies

('N10001','NL'),
('N10001','DE'),

('N10002','NL'),
('N10002','DE'),

('N10003','NL'),
('N10003','DE'),

('D10001','NL'),
('D10001','DE'),

('D10002','NL'),
('D10002','DE'),

('D10003','PL'),
('D10003','DE'),

('D10004','AT'),
('D10004','DE'),

('P10001','DE'),
('P10001','PL'),

('P10002','UK'),
('P10002','PL'),

('S10001','CH'),
('S10001','DE'),

('S10002','CH'),
('S10002','IT');

Het kortste pad algoritme van Dijkstra heb ik bij het eerste deel van de opdracht gebruikt. Het kan echter zo zijn dat het goedkoper is om een andere truck te nemen die een groter deel van de route kan rijden. Dan werkt dus de kortste pad methode niet. Hoop dat dit duidelijkheid schept

Het is me nog niet helemaal duidelijk wat je hiermee bedoelt:
- "de afstand die de trucks eerst moeten afleggen", en:
- "het kan echter zo zijn dat het goedkoper is om een andere truck te nemen die een groter deel van de route kan rijden"

Even een eenvoudig voorbeeld:
- je hebt 3 landen P, Q en R en 4 steden A, B, C, D:
A ligt in P
B en C in Q
D in R

Je wil een transport van A naar D.
Er zijn 2 vrachtwagens, V en W:
V mag rijden in P en Q en staat in A
W mag rijden in Q en R en staat in C.

Afstanden:
AB=1
BC=3
BD=4
CD=2

Het kortste pad van A naar D is dus ABD met lengte 5.

Er zijn nu deze mogelijkheden voor het transport:
[10] V rijdt eerst naar B dan naar C, overslag, W rijdt naar D: padlengte ABCD = 6
[20] V rijdt naar B, W rijdt naar B, overslag, W rijdt naar D.
[20a] afstand die W van C naar B rijdt telt niet mee: totale afstand = AB+BD = 5 (=kortste pad)
[20b] afstand die W van C naar B rijdt telt wel mee: totale afstand = AB+CB+BD = 8

Indien de afstand die W van C naar B zou rijden niet meetelt levert [20a] het kortste pad.
Indien de afstand die W van C naar B zou rijden wel meetelt levert [10] het kortste pad.


Je hebt jouw probleem opgedeeld in 2 stukken: 1 en 2:
- klopt het dat bovenstaand voorbeeld het onderscheid aangeeft tussen jouw 2 opdrachten?
- zo ja, welk van jouw problemen (1 of 2) komt overeen met mogelijkheid [20a] en welke met [20b]?

En is "de afstand die de trucks eerst moeten afleggen" = de afstand die W hier van C naar B zou moeten rijden?

In optie 1 kijk je eerst naar de kortste afstand van A naar B en bepaald dan iedere keer op basis van de licentie welke truck gaat rijden. Logischerwijs pak je daarbij de truck die het dichtsbij het beginputn van de route staat:

Voorbeeld methode 1:
Kortste route van A via B en C naar D.
Truck 1 mag in A en B komen en staat in A
Truck 2 mag in A, B en C rijden maar staat in E (waar hij ook mag komen)
Truck 2 mag in C en D komen maar staat in F (waar hij ook mag komen)
In dit geval rijd dus truck 1 A-B
In dit geval rijd dus truck 1 E-B-C
In dit geval rijd dus truck 2 F-C-D

Voorbeeld methode 2:
Kortste route van A via B en C naar D
Truck 1 mag in A,B komen en staat in A
Truck 2 mag in A,B,C komen maar staat in E
Truck 3 mag in C,D en staat in F
Nu kun je dus de volgende trucks gebruiken:
Truck 1 rijdt van A-B
Truck 2 rijdt van E-B-C
Truck 3 rijdt van F-C-D
Maar ook:
Truck 2 rijdt van E-A-B-C
Truck 3 rijdt van F-C-D
Dus Als E-A < E-B dan moet je juist kiezen voor truck 2 om dat dit goedkoper zou zijn

Hoop dat nu duidelijk wordt wat ik bedoel wan 20b is een voorbeeld van mijn probleem 1. Probleem 2 is anders gedefinieerd (zie het gegeven voorbeeld)

Voorbeeld 1 is duidelijk: de lading gaat over het korste pad en dat bepaalt de kosten : kosten = lengte van het korste pad.

Voorbeeld 2 is nog net niet helemaal duidelijk:
(a) enerzijds laat je de lading over het kortste pad gaan en minimaliseer je vervolgens de som van de extra afstanden die de vrachtwagens leeg moeten afleggen om bij het pad te komen (en daar de lading over te nemen)
(b) anderzijds spreek je over de goedkoopste oplossing, maar dat zou het geval zijn als de totale afstand die de vrachtwagens afleggen minimaal is.

Hiertussen zit een subtiel verschil:

Neem plaatsen A, B, C, D en E.
AB=2
AC=1
BD=2
CD=1
DE=2
De lading moet van A naar E.
Trucks:
T1 staat in A mag komen in A, B, D en E
T2 staat in A mag komen in A, C en D.

(a):
Het korste pad van A naar E = ACDE = 1+1+2 = 4
Als de lading over dit korste pad moet, dan moet T2 het deel ACD op zich nemen en T1 DE.
In dit geval kost T2 1+1 = 2 en T1 2+2+2 = 6 (T1 moet eerst van A naar D om daar de lading over te nemen), in totaal kost dit 2+6 = 8.

(b):
De goedkoopste oplossing is echter dat T1 direct de lading van A naar E rijdt (via route ABDE die T1 toch moet rijden), kosten = 2+2+2 = 6.
T2 kan in A achterblijven. De lading gaat nu dus niet over het korste pad, maar de totale kosten zijn wel minder.

Voor welke variant ((a) of (b)) zoek je een oplossing?

Ik zoek voor punt 2 een oplossing

Heb je hier een efficient algoritme voor, of moet je dit via heuristische zoekmethoden oplossen?

Bedankt voor dit algoritme