GraphHopper.com | Forum | GitHub | Maps | Blog

How deliver parcels as early as possible on a route?


#1

Our drivers deliver around 150 parcels per day. They should deliver each parcel as soon as possible on the route. That means delivery addresses located close to the starting point should come first. Addresses far away from the starting point should be delivered afterwards.

However, the Graphhopper route optimization algorithm sometimes navigates the drivers to delivery stops which are quire far away and on the return way lets them stop at waypoints which are located quite close to the starting point of the route.
The algorithm even navigates the drivers to a certain street twice but suggests to stop on the return route instead of the outward journey.
How can we change the requests to fix this problem? The current route suggestions of the Graphhopper algorithm are quite counterintuitive for humans.

Thanks for your support!


#2

One option might be to specify "return_to_depot": false.

Would you mind to send us an example of a counter-intuitive solution? Then we can elaborate solutions based on the example.


#3

We also use smth like load-dependent transport costs. It can be used to deliver items, e.g. parcels, as soon as possible. To find out whether it can be used for your use case, it would be great to have an example as well.


#4

BTW: If you dont want to share the example here, you can also send it per mail - https://www.graphhopper.com/contact-form/


#5

If you do it per mail, you can also send the job_id and we can fetch the problem ourselves.


#6

Hi Stefan,
thanks for your quick response! Here is one example, which shows 6 stops. The last one (6) is the closest one to the starting point (1), but should be number 2. Stops 4 and 5 should be after stop 2 and stop 3 should be the last one, because it is the furthest from the starting point. See attachment. Here is the request:

{
“configuration”: {
“routing”: {
“calc_points”: true
}
},
“objectives”: [
{
“type”: “min”,
“value”: “transport_time”
}
],
“vehicles”: [
{
“vehicle_id”: “my_vehicle”,
“type_id”: “vehicle_type_1”,
“start_address”: {
“location_id”: “pasteurstr”,
“lon”: 13.435368,
“lat”: 52.533016
}
}
],
“vehicle_types”: [
{
“type_id”: “vehicle_type_1”,
“profile”: “car”,
“capacity”: [
80
]
}
],
“services”: [
{
“id”: “leipzigerstr”,
“name”: “leipzigerstr”,
“type”: “delivery”,
“duration”: 300,
“size”: [
10
],
“address”: {
“location_id”: “leipzigerstr”,
“lon”: 13.400349,
“lat”: 52.51103
}
},
{
“id”: “kemperplatz”,
“name”: “kemperplatz”,
“type”: “delivery”,
“duration”: 300,
“size”: [
10
],
“address”: {
“location_id”: “kemperplatz”,
“lon”: 13.37211,
“lat”: 52.510769
}
},
{
“id”: “mohrenplatz”,
“name”: “mohrenplatz”,
“type”: “delivery”,
“duration”: 300,
“size”: [
10
],
“address”: {
“location_id”: “mohrenplatz”,
“lon”: 13.394984,
“lat”: 52.512388
}
},
{
“id”: “past”,
“name”: “past”,
“type”: “delivery”,
“duration”: 300,
“size”: [
10
],
“address”: {
“location_id”: “past”,
“lon”: 13.432512,
“lat”: 52.534537
}
},
{
“id”: “werderschermarkt”,
“name”: “werderschermarkt”,
“type”: “delivery”,
“duration”: 300,
“size”: [
10
],
“address”: {
“location_id”: “werderschermarkt”,
“lon”: 13.397602,
“lat”: 52.51547
}
}
]
}


#7

I attached another more extrem example. The numbers in the tooltips are the order number of the stops. Stops number 27, 28 ad 29 are on the route from stop number 3 to stop number 4 and 5, but they are supposed to be skipped. I have no JSON for this example, but its the same approach as in the example request in my previous comment.
Why are stops number 27, 28 and 29 not after stop number 3?


#8

Just by specifying "return_to_depot": false you will be provided with this solution:
13


#9

When it comes to your second example, it is hard judge just by looking at the figure. In general, GraphHopper tries to minimize transportation costs and does not know the concept of intuitive solutions. However, we might specify and operationalize the problem such that what we regard as intuitive is also reflected in the costs so that the algorithm can consider them as well. Therefore, again - if you could us with the job_id or the json of your second example, I am sure we can model it such that we find an intuitive solution.