Stuck with using "before" restriction

API
#1

I’m a bit stuck trying to use “before” restriction for my API input. Standard case is where I have e.g. 3 shipments per route (3 pickup locations and 3 dropoff locations).

And I’m trying to avoid cases where RouteXL would plan a same shipment’s dropoff before the pickup. So what I would need to do is set a “before” index for each dropoff location (I guess?).

But I’m creating locations array in foreach loop, something like that:

$locations = array();
foreach ($rows as $row) {

if ($location_type = "dropoff") {
   $before_index = ???
} 

	$locations[] = array(
	'name' => $row->location_id,
	'lat' => $row->lat,
	'lng' => $row->lng,
	'servicetime' => $row->service_time,	
	'restrictions' => array(
		'ready' => $row->ready_time_minutes,
		'due' => $row->due_time_minutes,
		'before' => $before_index
		)
	);

}

But as the locations array is created on-the-fly in the loop, the index might not yet be created when I need to add it as “before” value.

Would really appreciate if you could point me at the right direction.

Thank you in advance!

#2

We think your question is not so much an API issue, but an input data issue. We’re no programming experts but we may give some direction.

It all depends on the data you have in your source $rows. If a $row only has a type (that should probably read $row->location_type) but no pointer which other location is the pickup, it seems impossible to set the order restriction correctly.

So we expect $row to have another field with some kind of pointer to the pickup location. If so, you can probably use the index of $row to set the before index, as you are copying each $rows into $locations. You could use a nested loop construction like this:

if ( $row->location_type == "dropoff" ) {
  foreach( $rows as $id2 => $row2 ) {
    if ( $row->pointer == $row2->location_id ) {
      $before_index = $id2;
      $continue;
}}}
#3

Thank you so much for your quick reply and it seems I have the “before” index working according to your suggestion.

But now it seems the output doesn’t seem to take the before index into account at all:

This is my input:

Array
(
    [0] => Array
        (
            [name] => 1
            [lat] => 39.8353649
            [lng] => -86.1115804
            [servicetime] => 15
            [restrictions] => Array
                (
                    [ready] => 0
                    [due] => 420
                    [before] => 
                )
        )

    [1] => Array
        (
            [name] => 7
            [lat] => 39.9469829
            [lng] => -86.3113336
            [servicetime] => 15
            [restrictions] => Array
                (
                    [ready] => 0
                    [due] => 420
                    [before] => 5
                )
        )

    [2] => Array
        (
            [name] => 5
            [lat] => 41.8860855
            [lng] => -87.6236937
            [servicetime] => 15
            [restrictions] => Array
                (
                    [ready] => 0
                    [due] => 420
                    [before] => 0
                )
        )

    [3] => Array
        (
            [name] => 6
            [lat] => 42.3983342
            [lng] => -82.9317736
            [servicetime] => 15
            [restrictions] => Array
                (
                    [ready] => 0
                    [due] => 420
                    [before] => 4
                )
        )

    [4] => Array
        (
            [name] => 2
            [lat] => 40.7311396
            [lng] => -73.9945268
            [servicetime] => 15
            [restrictions] => Array
                (
                    [ready] => 0
                    [due] => 420
                    [before] => 
                )
        )

    [5] => Array
        (
            [name] => 3
            [lat] => 40.7311396
            [lng] => -73.9945268
            [servicetime] => 15
            [restrictions] => Array
                (
                    [ready] => 0
                    [due] => 420
                    [before] => 
                )
        )

    [6] => Array
        (
            [name] => 4
            [lat] => 40.7312777
            [lng] => -73.9942835
            [servicetime] => 15
            [restrictions] => Array
                (
                    [ready] => 0
                    [due] => 420
                    [before] => 
                )
        )

    [7] => Array
        (
            [name] => 8
            [lat] => 41.8860855
            [lng] => -87.6236937
            [servicetime] => 15
            [restrictions] => Array
                (
                    [ready] => 0
                    [due] => 420
                    [before] => 6
                )
        )
)

And here is the output:

stdClass Object
(
    [id] => dOIvAv9g
    [count] => 8
    [feasible] => 
    [route] => stdClass Object
        (
            [0] => stdClass Object
                (
                    [name] => 1
                    [arrival] => 0
                    [distance] => 0
                )

            [1] => stdClass Object
                (
                    [name] => 7
                    [arrival] => 42
                    [distance] => 28.2
                )

            [2] => stdClass Object
                (
                    [name] => 5
                    [arrival] => 230
                    [distance] => 297.4
                )

            [3] => stdClass Object
                (
                    [name] => 6
                    [arrival] => 534
                    [distance] => 761.4
                )

            [4] => stdClass Object
                (
                    [name] => 3
                    [arrival] => 1181
                    [distance] => 1764.8
                )

            [5] => stdClass Object
                (
                    [name] => 2
                    [arrival] => 1196
                    [distance] => 1764.8
                )

            [6] => stdClass Object
                (
                    [name] => 4
                    [arrival] => 1212
                    [distance] => 1765.6
                )

            [7] => stdClass Object
                (
                    [name] => 8
                    [arrival] => 2017
                    [distance] => 3036.5
                )
        )
)

As you can see, e.g location with a name “7” (dropoff) has before index “5” which corresponds to location name “3” (pickup). So the location with a name “3” should be before location “7”, but in the output it is not for some reason.

What could be the issue?

Thanks again in advance!

#4

If the sorting is not as expected, first thing to try is to set the “after” restriction instead of “before”. If that does not change the result either, there may be a problem in the conversion of your PHP array. In that case we’d like to receive the actual JSON your code sends.

#5

Thank you, but unfortunately using “after” instead of “before” didn’t solve the issue.

Here is the slightly modified route. Input JSON looks like this:

[{"name":"1","lat":40.7312777,"lng":-73.9942835,"servicetime":"15","restrictions":{"ready":0,"due":420,"after":3}},{"name":"3","lat":40.7311396,"lng":-73.9945268,"servicetime":"15","restrictions":{"ready":"0","due":420,"after":2}},{"name":"4","lat":42.3983342,"lng":-82.93177360000001,"servicetime":"15","restrictions":{"ready":"0","due":420,"after":""}},{"name":"6","lat":41.8860855,"lng":-87.62369369999999,"servicetime":"15","restrictions":{"ready":"0","due":420,"after":""}},{"name":"10","lat":39.83536489999999,"lng":-86.1115804,"servicetime":"15","restrictions":{"ready":"0","due":420,"after":3}},{"name":"9","lat":39.9469829,"lng":-86.3113336,"servicetime":"15","restrictions":{"ready":"0","due":420,"after":""}}]

and output:

stdClass Object
(
    [id] => AjGy71hh
    [count] => 6
    [feasible] => 
    [route] => stdClass Object
        (
            [0] => stdClass Object
                (
                    [name] => 1
                    [arrival] => 0
                    [distance] => 0
                )

            [1] => stdClass Object
                (
                    [name] => 3
                    [arrival] => 16
                    [distance] => 0.5
                )

            [2] => stdClass Object
                (
                    [name] => 4
                    [arrival] => 661
                    [distance] => 1004
                )

            [3] => stdClass Object
                (
                    [name] => 6
                    [arrival] => 966
                    [distance] => 1468.4
                )

            [4] => stdClass Object
                (
                    [name] => 10
                    [arrival] => 1171
                    [distance] => 1760.2
                )

            [5] => stdClass Object
                (
                    [name] => 9
                    [arrival] => 1213
                    [distance] => 1788.4
                )
        )
)

In this route e.g. location named “6” should be after location named “10”, but it’s not :frowning:

#6

The output has feasible set to false, so the route is not feasible. Infeasible routes are not meeting one or more restrictions, are unreliable and can not be used.

In this case, all locations have due time 420. The final arrival however is at 1213. The second stop alone requires >1000 km of travel. So the route can never be feasible.

You should remove the due times. If you use the due time to check if the route fits a 7 hour workday, that’s a bad strategy. You’d better remove the due times and check the result if the final arrival is within 7 hours.

Pro tip: you can import the locations JSON on the website, to get a better feel of the distribution of stops, the restrictions and the route.

#7

Thank you for your reply! Unfortunately we’re still struggling to get the expected results. I have now removed all the restrictions like you suggested. It changed the results of the route a bit, but some of the “after” values are still being ignored.

Input:

[{"name":"10","lat":39.83536489999999,"lng":-86.1115804,"servicetime":"15","restrictions":{"ready":"","due":"","after":1}},{"name":"6","lat":41.8860855,"lng":-87.62369369999999,"servicetime":"15","restrictions":{"ready":"","due":"","after":""}},{"name":"4","lat":42.3983342,"lng":-82.93177360000001,"servicetime":"15","restrictions":{"ready":"","due":"","after":""}},{"name":"1","lat":40.7312777,"lng":-73.9942835,"servicetime":"15","restrictions":{"ready":"","due":"","after":1}},{"name":"3","lat":40.7311396,"lng":-73.9945268,"servicetime":"15","restrictions":{"ready":"","due":"","after":2}},{"name":"9","lat":39.9469829,"lng":-86.3113336,"servicetime":"15","restrictions":{"ready":"","due":"","after":""}}]

and output:

stdClass Object
(
    [id] => 1plw0fU5
    [count] => 6
    [feasible] => 1
    [route] => stdClass Object
        (
            [0] => stdClass Object
                (
                    [name] => 10
                    [arrival] => 0
                    [distance] => 0
                )

            [1] => stdClass Object
                (
                    [name] => 6
                    [arrival] => 205
                    [distance] => 293
                )

            [2] => stdClass Object
                (
                    [name] => 4
                    [arrival] => 509
                    [distance] => 757
                )

            [3] => stdClass Object
                (
                    [name] => 1
                    [arrival] => 1156
                    [distance] => 1760.4
                )

            [4] => stdClass Object
                (
                    [name] => 3
                    [arrival] => 1172
                    [distance] => 1760.9
                )

            [5] => stdClass Object
                (
                    [name] => 9
                    [arrival] => 1937
                    [distance] => 2925.4
                )
        )
)

E.g. Location named “1” has an “after” index of “1” which corresponds to location named “6”. So the location named “6” should be after location named “1” on the route, but it’s not.

Thanks again in advance!

#8

I have encountered a similar problem with the results
Example:
Pick-up Point: A
Drop-off Point: B
Expected Route: Origin → A → B → Destination
Incorrect Route Generated: Origin → B → A → Destination

Could a constraint be added to ensure this scenario does not occur?

a. Add an identifier to each pick-up and drop-off point to establish a relationship between them. This can be a simple integer value, e.g., ‘1’ for Pick-up Point A and Drop-off Point A, ‘2’ for Pick-up Point B and Drop-off Point B, and so on.

b. Modify the optimization algorithm to consider these identifiers when calculating the optimal route. The algorithm should be set up to avoid creating a route where a drop-off point with a specific identifier comes before the pick-up point with the same identifier.

#9

Using after instead of before was only meant as a test for your input, e.g. the conversion to JSON. If you change back to using before the results should be as expected.

#10

You can already set the contraint using the index as the identifier. Using before and after establishes the relation. See also the API docs.

The algorithm considers these as soft restrictions. That is: it can create routes where the order is wrong, but it adds a strong penalty to the objective function and it will indicate non-feasibility if the required order is not possible.

#11

Thank you, but as you can see from the data above, it also didn’t work when using “before” identifiers or maybe I’m missing your point.

We have put so much effort on this getting your solution implemented in our live solutions, so we’re hoping a lot for a solution.

But now I read from your reply to another person’s post that “before” and “after” are only soft constraints. I don’t know the background of this, but it seems weird having those as “soft” as it’s impossible to delivery a package when it hasn’t been picked up yet. I’m not an logistics expert, so this is just my simple logic regarding this.

#12

We may be misunderstanding each other. We’ve used this input:

[{"name":"10", "lat":39.83536489999999, "lng":-86.1115804 }, {"name":"6", "lat":41.8860855, "lng":-87.62369369999999, "servicetime":15 }, {"name":"4", "lat":42.3983342, "lng":-82.93177360000001, "servicetime":15 }, {"name":"1", "lat":40.7312777, "lng":-73.9942835, "servicetime": 15, "restrictions":{ "before":1 } }, {"name":"3", "lat":40.7311396, "lng":-73.9945268, "servicetime": 15, "restrictions":{ "before":2 } }, {"name":"9", "lat":39.9469829, "lng":-86.3113336 }]

and got this output:

{ "id": "EG3i7IkW", "count": 6, "feasible": true, "route": { "0": { "name": "10", "arrival": 0, "distance": 0 }, "1": { "name": "1", "arrival": 731, "distance": 1141.2 }, "2": { "name": "3", "arrival": 747, "distance": 1141.7 }, "3": { "name": "4", "arrival": 1392, "distance": 2145.1 }, "4": { "name": "6", "arrival": 1697, "distance": 2609.5 }, "5": { "name": "9", "arrival": 1885, "distance": 2877.5 } } }

which has location “1” before “6” and “3” before “4”. We thought this what is you need.

The penalties for the restrictions are such strong, that the algorithm will always first try to find a feasible solution before minimizing travel time. In the previous examples you also had too strict time restrictions, which prevented a feasible solution anyhow.

Note that you can not draw conclusions from infeasible routes. In other words, if the API returns feasible:false, you can read it as “no route found” and you should not use the result.

#13

Thanks, will do some more tests.

But now just trying to understand when and why would the route be classified as not feasible to prevent a situation where in the production site e.g. 10% or 20% actually fulfillable routes cannot be optimized. End-users would probably be very frustrated when saying them that some routes just don’t work for unknown reason :slight_smile:

For example with this route, it seems to be taking into account the “before” constraints, but “Feasible” is still “No” even though there’s no time restrictions set. And as you were saying, Feasible=False routes cannot be trusted.

This seems like a not too complicated route and it seems like there’s no reason for it to be not feasible.

Thanks and really appreciate your patience!

#14

That deeplink does not have enough information for us to check what happens, but it may related to the settings you have in the options.

If you want more explanation for infeasible routes, you can also try the API V2. That returns additional remarks from the algorithm.

#15

Sorry, I should have added an API input/output here as the Deeplink was just to demonstrate visually that the route is relatively simple and should probably be feasible if no time restrictions set.

I have likely already taken the “most annoying customer of the year” title, but here is just one more effort :slight_smile:

The API input for the deeplink above is:

[{"name":"1","lat":40.7312777,"lng":-73.9942835,"servicetime":"15","restrictions":{"ready":"","due":"","before":""}},{"name":"3","lat":40.7311396,"lng":-73.9945268,"servicetime":"15","restrictions":{"ready":"","due":"","before":""}},{"name":"4","lat":42.3983342,"lng":-82.93177360000001,"servicetime":"15","restrictions":{"ready":"","due":"","before":1}},{"name":"2","lat":39.83536489999999,"lng":-86.1115804,"servicetime":"15","restrictions":{"ready":"","due":"","before":""}},{"name":"5","lat":39.9469829,"lng":-86.3113336,"servicetime":"15","restrictions":{"ready":"","due":"","before":1}},{"name":"6","lat":41.8860855,"lng":-87.62369369999999,"servicetime":"15","restrictions":{"ready":"","due":"","before":0}}]

Output with API version 1:

stdClass Object
(
    [id] => 6bq927B3
    [count] => 6
    [feasible] => 
    [route] => stdClass Object
        (
            [0] => stdClass Object
                (
                    [name] => 1
                    [arrival] => 0
                    [distance] => 0
                )

            [1] => stdClass Object
                (
                    [name] => 3
                    [arrival] => 16
                    [distance] => 0.5
                )

            [2] => stdClass Object
                (
                    [name] => 4
                    [arrival] => 661
                    [distance] => 1004
                )

            [3] => stdClass Object
                (
                    [name] => 2
                    [arrival] => 970
                    [distance] => 1455.6
                )

            [4] => stdClass Object
                (
                    [name] => 5
                    [arrival] => 1012
                    [distance] => 1483.8
                )

            [5] => stdClass Object
                (
                    [name] => 6
                    [arrival] => 1200
                    [distance] => 1753
                )
        )
)

Output with API version 2:

stdClass Object
(
    [id] => RS54E48gfUNJ9X0O6bFE
    [count] => 6
    [feasible] => 1
    [remarks] => 
    [route] => stdClass Object
        (
            [0] => stdClass Object
                (
                    [name] => 1
                    [lat] => 40.7312777
                    [lng] => -73.9942835
                    [arrival] => 0
                    [distance] => 0
                )

            [1] => stdClass Object
                (
                    [name] => 2
                    [lat] => 39.8353649
                    [lng] => -86.1115804
                    [arrival] => 729
                    [distance] => 1138.7
                )

            [2] => stdClass Object
                (
                    [name] => 5
                    [lat] => 39.9469829
                    [lng] => -86.3113336
                    [arrival] => 771
                    [distance] => 1166.9
                )

            [3] => stdClass Object
                (
                    [name] => 4
                    [lat] => 42.3983342
                    [lng] => -82.9317736
                    [arrival] => 1093
                    [distance] => 1634.9
                )

            [4] => stdClass Object
                (
                    [name] => 3
                    [lat] => 40.7311396
                    [lng] => -73.9945268
                    [arrival] => 1740
                    [distance] => 2638.3
                )

            [5] => stdClass Object
                (
                    [name] => 6
                    [lat] => 41.8860855
                    [lng] => -87.6236937
                    [arrival] => 2545
                    [distance] => 3909.3
                )
        )
)

With v1, result in this case looks totally OK, and the “before” restrictions are taken into account. But the route is still not Feasible and therefore shouldn’t be trusted. What could be the reason?

And with v2, it gives totally different order for the same input not considering “before” data at all. But in this case the Route is Feasible.

That seems very strange if I haven’t missed something obvious.

#16

There was indeed a problem in the algorithm that occured for routes a small number of stops, large distances between them, and order restrictions. That has been fixed now.