comp.lang.ada
 help / color / mirror / Atom feed
* Dijkstra and graphs
@ 2021-08-26 12:26 Björn Lundin
  2021-08-26 12:48 ` Dmitry A. Kazakov
  0 siblings, 1 reply; 3+ messages in thread
From: Björn Lundin @ 2021-08-26 12:26 UTC (permalink / raw)


Hi,
I'm looking to update myself on graphs a bit while I
have a problem at hand that would benefit from Dijkstra's traveling 
salesman problem.

The problem at hand is a large conveyor system at a warehouse.
The PLC will scan a box and tell me "box-id 123 is here, should I go 
straight or divert'

I know the final destination of the box. So I'll look it up and say
'turn first right here' and the box diverts to the second lane on the 
right. It then keeps going until it is scanned again and the procedure 
repeats.

        e-------f
        |       |
a------B-------C-----d
        |       |
        g-------h

Box 1 starts at a - final destination is d
Scanners at B and C
Box 1 scanned at B 'go straight'
Here I'd like to increase weight B->C

Box 2 starts at a - final destination is d
Box 2 scanned at B 'go left' - since B->C has become more expensive
Here I'd like to increase weight B->e

Box 1 scanned at C 'go straight'
Here I'd like to decrease weight B->C

Box 3 starts at a - final destination is d
Box 3 scanned at B 'go straight' - since this is cheapest route again, 
now when box 1 has left the area
Here I'd like to increase weight B->C because of box 3

You get the idea.


I have one solution (not handling this congestion) but I think I'd like 
to look closer at Dijkstra. It has some advantages I like - like easy to 
configure. Current solution will gt messy with hundreds of vertexes.

There is one implementation at
https://rosettacode.org/wiki/Dijkstra%27s_algorithm#Ada

which does basically what I want.

However - I cannot see what to add for me to update the weight in the 
Edge array.

This implementation takes the weight between two locations or vertexes.
But this is static.

The more boxes between two locations the less I'd like to use that route.

In other words I'd like to dynamically change the weights.

Any hints ?




-- 
Björn

^ permalink raw reply	[flat|nested] 3+ messages in thread

end of thread, other threads:[~2021-08-26 14:10 UTC | newest]

Thread overview: 3+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2021-08-26 12:26 Dijkstra and graphs Björn Lundin
2021-08-26 12:48 ` Dmitry A. Kazakov
2021-08-26 14:10   ` Björn Lundin

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox