Suboptimal (and surprising) vehicle routing

[ACarlotti]

So I was doing some unrelated testing and set up a simple bus route. I was surprised to notice that the bus was taking a route that was four tiles longer than the shortest route, despite having the same number of turns as the shortest route. So I investigated further. The following is some (processed) debugging output I added. The grid shows the entries that were pushed onto the priority queue; where the same location was added to the queue multiple times, the later occurrences are listed at the top.

Code Select Expand


Duplicate location:  Parent (16, 57), ground (17, 57), cost_g 200, heur_f 2180, dir 2, ribi_from 2, count 6
Duplicate location:  Parent (12, 57), ground (11, 57), cost_g 220, heur_f 2360, dir 8, ribi_from 8, count 8
Duplicate location:  Parent (12, 54), ground (12, 55), cost_g 320, heur_f 3340, dir 6, ribi_from 4, count 15
Duplicate location:  Parent (8, 51), ground (7, 51), cost_g 300, heur_f 3140, dir 8, ribi_from 8, count 16
Duplicate location:  Parent (11, 54), ground (12, 54), cost_g 280, heur_f 2900, dir 2, ribi_from 2, count 14
Duplicate location:  Parent (10, 49), ground (11, 49), cost_g 320, heur_f 3210, dir 2, ribi_from 2, count 18
Duplicate location:  Parent (8, 49), ground (7, 49), cost_g 320, heur_f 3340, dir 8, ribi_from 8, count 18
Duplicate location:  Parent (7, 54), ground (6, 54), cost_g 280, heur_f 2970, dir 8, ribi_from 8, count 14
Duplicate location:  Parent (4, 57), ground (4, 56), cost_g 320, heur_f 3360, dir 9, ribi_from 1, count 14
Duplicate location:  Parent (12, 54), ground (12, 53), cost_g 320, heur_f 3260, dir 3, ribi_from 1, count 15
Duplicate location:  Parent (12, 54), ground (13, 54), cost_g 290, heur_f 3030, dir 2, ribi_from 2, count 15
Duplicate location:  Parent (12, 54), ground (12, 55), cost_g 320, heur_f 3340, dir 6, ribi_from 4, count 15
                                                            (9,47)                                                                                             
                                                            (9,48)                                                                                             
                                                            250, 2630                                                                                           
                                                            18, 1, 1                                                                                           
          (4,48)                                            (9,48)                        (12,48)                                                               
          (4,49)                                            (9,49)                        (12,49)                                                               
          390, 4110                                         240, 2530                     370, 3810                                                             
          22, 9, 1                                          17, 1, 1                      20, 3, 1                                                             
(3,49)    (4,49)    (5,49)    (6,49)    (7,49)    (8,49)    (9,49)    (10,49)   (11,49)   (12,49)                                                               
(4,49)    (5,49)    (6,49)    (7,49)    (8,49)    (9,49)    (9,50)    (9,49)    (10,49)   (11,49)                                                               
360, 3780 350, 3670 340, 3560 330, 3450 320, 3340 270, 2860 230, 2420 270, 2780 320, 3210 330, 3310                                                             
22, 8, 8  21, 8, 8  20, 8, 8  19, 8, 8  18, 8, 8  17, 9, 8  16, 1, 1  17, 3, 2  18, 2, 2  19, 2, 2                                                             
          (4,50)                                            (9,50)                        (12,50)                                                               
          (4,49)                                            (9,51)                        (12,49)                                                               
          390, 4070                                         220, 2290                     370, 3700                                                             
          22, 12, 4                                         15, 1, 1                      20, 6, 4                                                             
                                        (7,51)    (8,51)    (9,51)                        ^^FINISH^^                                                               
                                        (8,51)    (9,51)    (9,52)                                                                                             
                                        300, 3140 250, 2600 210, 2160                                                                                           
                                        16, 8, 8  15, 9, 8  14, 1, 1                                                                                           
                              (6,52)                        (9,52)                        (12,52)                       (15,52)                                 
                              (6,53)                        (9,53)                        (12,53)                       (15,53)                                 
                              370, 3800                     200, 2070                     370, 3720                     400, 4070                               
                              16, 1, 1                      13, 1, 1                      16, 1, 1                      19, 1, 1                               
          (4,53)    (5,53)    (6,53)                        (9,53)                        (12,53)                       (15,53)                                 
          (5,53)    (6,53)    (6,54)                        (9,54)                        (12,54)                       (15,54)                                 
          370, 3880 330, 3440 320, 3330                     190, 1970                     320, 3260                     350, 3600                               
          17, 8, 8  16, 9, 8  15, 9, 1                      12, 1, 1                      15, 3, 1                      18, 3, 1                               
                              (6,54)    (7,54)    (8,54)    (9,54)    (10,54)   (11,54)   (12,54)   (13,54)   (14,54)   (15,54)   (16,54)   (17,54)   (18,54)   
                              (7,54)    (8,54)    (9,54)    (9,55)    (9,54)    (10,54)   (11,54)   (12,54)   (13,54)   (14,54)   (15,54)   (16,54)   (17,54)   
                              280, 2970 270, 2860 220, 2320 180, 1880 220, 2250 270, 2770 280, 2900 290, 3030 300, 3140 310, 3240 320, 3350 330, 3460 340, 3570
                              14, 8, 8  13, 8, 8  12, 9, 8  11, 1, 1  12, 3, 2  13, 2, 2  14, 2, 2  15, 2, 2  16, 2, 2  17, 2, 2  18, 2, 2  19, 2, 2  20, 2, 2 
          (4,55)                                            (9,55)                        (12,55)                                           (17,55)             
          (4,56)                                            (9,56)                        (12,56)                                           (17,54)             
          370, 3830                                         170, 1790                     300, 3050                                         370, 3890           
          15, 1, 1                                          10, 1, 1                      9, 1, 1                                           20, 6, 4           
          (4,56)                                            (9,56)                        (12,56)                                                               
          (4,57)                                            (9,57)                        (12,57)                                                               
          320, 3360                                         160, 1700                     250, 2590                                                             
          14, 9, 1                                          9, 1, 1                       8, 9, 1                                                               
          (4,57)    (5,57)    (6,57)    (7,57)              (9,57)    (10,57)   (11,57)   (12,57)   (13,57)   (14,57)   (15,57)   (16,57)   (17,57)   (18,57)   
          (5,57)    (6,57)    (6,58)    (6,57)              (9,58)    (9,57)    (10,57)   (13,57)   (14,57)   (15,57)   (15,58)   (15,57)   (18,57)   (18,58)   
          270, 2900 220, 2360 180, 1920 220, 2290           150, 1610 190, 1980 240, 2500 210, 2230 200, 2100 150, 1580 110, 1210 150, 1650 180, 1890 140, 1520
          13, 8, 8  12, 9, 8  11, 1, 1  12, 3, 2            8, 1, 1   9, 3, 2   10, 2, 2  7, 8, 8   6, 8, 8   5, 9, 8   4, 1, 1   5, 3, 2   8, 9, 8   7, 1, 1   
(3,58)                        (6,58)                        (9,58)                                                      (15,58)                       (18,58)   
(3,59)                        (6,59)                        (9,59)                                                      (15,59)                       (18,59)   
200, 2150                     170, 1830                     140, 1520                                                   100, 1120                     130, 1430
13, 1, 1                      10, 1, 1                      7, 1, 1                                                     3, 1, 1                       6, 1, 1   
(3,59)                        (6,59)                        (9,59)                                  (13,59)             (15,59)                       (18,59)   
(3,60)                        (6,60)                        (9,60)                                  (13,60)             (15,60)                       (18,60)   
150, 1690                     120, 1370                     90, 1060                                50, 590             50, 660                       80, 970   
12, 9, 1                      9, 9, 1                       6, 9, 1                                 2, 9, 1             2, 3, 1                       5, 3, 1   
(3,60)    (4,60)    (5,60)    (6,60)    (7,60)    (8,60)    (9,60)    (10,60)   (11,60)   (12,60)   (13,60)   (14,60)   (15,60)   (16,60)   (17,60)   (18,60)   
(4,60)    (5,60)    (6,60)    (7,60)    (8,60)    (9,60)    (10,60)   (11,60)   (12,60)   (13,60)   (14,60)   START     (14,60)   (15,60)   (16,60)   (17,60)   
110, 1330 100, 1220 90, 1120  80, 1010  70, 910   60, 810   50, 700   40, 600   30, 490   20, 360   10, 230             10, 300   20, 410   30, 510   40, 610   
11, 8, 8  10, 8, 8  9, 8, 8   8, 8, 8   7, 8, 8   6, 8, 8   5, 8, 8   4, 8, 8   3, 8, 8   2, 8, 8   1, 8, 8             1, 2, 2   2, 2, 2   3, 2, 2   4, 2, 2   
                              (6,61)                                            (11,61)                                 (15,61)                                 
                              (6,60)                                            (11,60)                                 (15,60)                                 
                              120, 1450                                         70, 930                                 50, 740                                 
                              9, 12, 4                                          4, 12, 4                                2, 6, 4                             

The expected route is to go east 1 tile, north 3, west 3 and north 7. The actual route is west 5, north 11, east 3, south 1.

I thought this might be due to the latter using more turns, but having examined the code it seems that what is actually happening is that the algorithm is only considering the routes that include the 'cheapest' way to reach each tile. This means that an optimal route might be cut off at some tile by an intersecting route that reaches that tile faster but would then have to turn onto that tile. To fix this, it might be necessary to change the tile marking part of the algorithm to mark tiles with the directions in which they are reached, rather than just directly marking them. This itself would not fully solve the problem in Extended since the cost of a turn is currently added over the two following tiles (so maybe a two tile history is needed). I shall have to think about this some more.

I haven't yet examined whether this is also an issue in Standard.

One further observation is that it looks like the heuristic cost is not currently functioning as intended (which may explain some of the debug warnings about the heuristics failing). I'll probably look into this further at some point.

[jamespetts]

Thank you for this - this is interesting. The vehicle routing algorithm is only peripherally changed from Standard: I have not altered the basic algorithm, but have added checks for things such as weight limits and way constraints. I suspect, therefore, that this is also an issue in Standard.

[ACarlotti]

I can reproduce this in Standard with the same road layout (I've moved the endpoint to the correct location after I got it wrong when first posting).

[Ters]

I have noticed strange route choices for years, but as I have never understood how to look into it without being overwhelmed by an entire Simutrans world ticking, I have just assumed it was because it tried to avoid tiles with much traffic. It may be a combination, though. In some cases, routes that were both longer and had more turns were chosen. I don't remember all the cases, but intersecting possible routes may actually fit some of them.

And isn't it so that a turn followed by another turn in the opposite direction is considered less costly than two individual turns? Might need to consider two tiles in Standard as well.

[prissi]

There is a principal problem in all cases, i.e. that a final turn does not always count as 90 degree turn. Same for an initial turn, since on needs to travel two tiles to find out whether it is diagonal or not.

Usual pathfinder consider the cheapest way to reach a tile also as the best way; I know that one discards occasionally better routes; but one the other hand it is much computationally cheaper to discard these routes and not run all possible routes all the time (or at least all routes until twice the actual costs). But, if you know a way to fix this without impeding too much performance and memory footprint, I am all for improvement. But the marking of tiles certainly has to change, if you put more than one tile into the queue.