Strange optimization result when using Shipments

Directions API
1

Hi,

we are using shipments to let the API optimize our routes. We mostly have really good results, but now we have some strange ones.

This is our setting:

  • We use the optimization API
  • We use shipments
  • We only have one vehicle and one vehicle-type set
  • the objective is set to:
    • objective.Value(“type”) = “min”
    • objective.Value(“value”) = “transport_time”

AS you can see, we try to let the route optimize by transportive, not by the shortest way.

If you now look on the screenshot I attached, the order of the points are false. Currently it is settee 1 - 2 - 3, but the shortest travel-time would be 2 - 3 - 1.

We do not show the ways from the depot to the first point. You can see the on the image where the depot is located. It seems that the router still optimizes the route by the shortest way, not the shortest travel time of the shipments.

Can you help me?

Strange%20Optimazation
Strange Optimazation.jpg2152×1758 478 KB

2

Hello Lars,

Would you mind to send us the entire json (you can also send it by email or private message if you prefer) or the corresponding job_id? This way it is much easier to analyse.

Best,
Stefan

3

sure, here’s the full json:

{
"configuration":
{
    "routing":
    {
        "calc_points": false
    }
},    "objectives":
[
    {
        "type": "min",
        "value": "transport_time"
    }
],
"vehicles":
[
    {
        "vehicle_id": "vehicle_Start_Endpunkt",
        "start_address":
        {
            "location_id": "location_start_Start_Endpunkt",
            "lat": 50.614959,
            "lon": 12.273825
        },
        "type_id": "vehicletype_Start_Endpunkt_small_truck",
        "return_to_depot": false
    }
],
"vehicle_types":
[
    {
        "type_id": "vehicletype_Start_Endpunkt_small_truck",
        "profile": "small_truck",
        "capacity":
        [
            8
        ],
        "speed_factor": 1,
        "service_time_factor": 1
    }
],
"shipments":
[
    {
        "id": "halt_482",
        "name": "sm1",
        "pickup":
        {
            "address":
            {
                "location_id": "start_halt_482",
                "name": "sm1_pu",
                "lat": 50.477632,
                "lon": 12.454383
            },
            "duration": 180
        },
        "delivery":
        {
            "address":
            {
                "location_id": "end_halt_482",
                "name": "sm1_del",
                "lat": 50.5092789652797,
                "lon": 12.3996090223395
            },
            "duration": 180
        },
        "size":
        [
            1
        ],
        "priority": 3
    },
    {
        "id": "halt_480",
        "name": "sm2",
        "pickup":
        {
            "address":
            {
                "location_id": "start_halt_480",
                "name": "sm2_pu",
                "lat": 50.3808528584173,
                "lon": 12.4819549495164
            },
            "duration": 180
        },
        "delivery":
        {
            "address":
            {
                "location_id": "end_halt_480",
                "name": "sm2_del",
                "lat": 50.503788,
                "lon": 12.396245
            },
            "duration": 180
        },
        "size":
        [
            1
        ],
        "priority": 3
    },
    {
        "id": "halt_481",
        "name": "sm3",
        "pickup":
        {
            "address":
            {
                "location_id": "start_halt_481",
                "name": "sm3_pu",
                "lat": 50.392224986264,
                "lon": 12.4948111436965
            },
            "duration": 180
        },
        "delivery":
        {
            "address":
            {
                "location_id": "end_halt_481",
                "name": "sm3_del",
                "lat": 50.503788,
                "lon": 12.396245
            },
            "duration": 180
        },
        "size":
        [
            1
        ],
        "priority": 3
    }
]

}

4

Thanks.
I am not sure whether I understand why the solution is strange. It is because halt_481 is conducted after halt_480?

5

But isn’t it so, that the optimization API optimizes also the pickup-order? If I change the order of the shipment input of the function, the same result comes out, or am I wrong?

6

To be more precise:

if the API should optimizes the pickups and deliveries by “travel time”, then it should order the waypoints in that way, that the sum of the travel time of all shipments is the smallest. No matter how long the whole route would be.

The result we get in the example above is optimized by the amount of length of the route. It’s the shortest track the vehicle can move. But its not the route with the shortest delivery times.

7

But its not the route with the shortest delivery times.

No, it is the route with the shortest travel time (not delivery time).

8

… and in your example there are two solutions with the same travel time (pickup1,pickup2,pickup3 and pickup1, pickup3, pickup2) and since these are pickups, i.e. items will be loaded, there is a slight preference to pickup later than earlier (since it is assumed that more load means higher energy consumption).

9

Okay, I understand.

Do you have a suggestion how to achieve the shortest delivery time?

10

We already offer this for ordinary traveling salesman problems, and we work on a more general solution to apply it to these vehicle routing problems as well. Still it is not that easy since many customers want pickups to be conducted as late as possible. If we found a solution, I would let you know.

BTW: Even we found a solution, it would not change anything regarding the delivery times of your shipments.

Would you mind to explain why you have such a strong preference for 1,2,3 rather than 1,3,2 even though the overall solution as well as delivery times of the involved shipments does not change? This way I might understand the urgency of this much better.

11

We don’t use your API for calculation shipments like packages or something. We calculate the routes of cars with students (pupils) in the students transportation.

The objective here is to have the shortest travel time for the students.

The current solution above let the first student (P1) to long in the car, even if the track is shorter. The solution we expected was that P1 is the last pickup in the row. What we need is the 2 - 3 - 1 solution, not the 1 - 2 - 3 as it is today.

In conclusion: we need to optimize the route so that the shipments spend as little time in the car as possible.

1 Like
12

Thanks a lot for your description. Now I understand much better. You want to reduce the transportation time of your passengers, i.e. the time your passengers spent in the vehicle, and you would also accept higher overall travel times of your driver to reduce the in-vehicle time of your passengers. This is a whole different goal. I assume that the best solution in this regard is to set the capacity to one single passenger so that each passenger is transported to its destination on the direct way. This is obviously not what you want to achieve. Thus, it should be a solution somewhere in between min -> travel_time of driver and min -> travel_time of individual passenger. An intuitive way to get such a solution is to define a level of service for your passengers. For example, promise your passengers that they do not need longer than direct_travel_time * 1.5, i.e. 50% more than the direct travel time. This can then be specified in the field "max_time_in_vehicle" as follows:

{
"configuration":
{
    "routing":
    {
        "calc_points": true
    }
},    "objectives":
[
    {
        "type": "min",
        "value": "transport_time"
    }
],
"vehicles":
[
    {
        "vehicle_id": "vehicle_Start_Endpunkt",
        "start_address":
        {
            "location_id": "location_start_Start_Endpunkt",
            "lat": 50.614959,
            "lon": 12.273825
        },
        "type_id": "vehicletype_Start_Endpunkt_small_truck",
        "return_to_depot": false
    }
],
"vehicle_types":
[
    {
        "type_id": "vehicletype_Start_Endpunkt_small_truck",
        "profile": "small_truck",
        "capacity":
        [
            8
        ],
        "speed_factor": 1,
        "service_time_factor": 1
    }
],
"shipments":
[
    {
        "id": "halt_482",
        "name": "sm1",
        "pickup":
        {
            "address":
            {
                "location_id": "start_halt_482",
                "name": "sm1_pu",
                "lat": 50.477632,
                "lon": 12.454383
            },
            "duration": 180
        },
        "delivery":
        {
            "address":
            {
                "location_id": "end_halt_482",
                "name": "sm1_del",
                "lat": 50.5092789652797,
                "lon": 12.3996090223395
            },
            "duration": 180
        },
        "size":
        [
            1
        ],
        "priority": 3,
        "max_time_in_vehicle": 1440
    },
    {
        "id": "halt_480",
        "name": "sm2",
        "pickup":
        {
            "address":
            {
                "location_id": "start_halt_480",
                "name": "sm2_pu",
                "lat": 50.3808528584173,
                "lon": 12.4819549495164
            },
            "duration": 180
        },
        "delivery":
        {
            "address":
            {
                "location_id": "end_halt_480",
                "name": "sm2_del",
                "lat": 50.503788,
                "lon": 12.396245
            },
            "duration": 180
        },
        "size":
        [
            1
        ],
        "priority": 3,
        "max_time_in_vehicle": 2790
    },
    {
        "id": "halt_481",
        "name": "sm3",
        "pickup":
        {
            "address":
            {
                "location_id": "start_halt_481",
                "name": "sm3_pu",
                "lat": 50.392224986264,
                "lon": 12.4948111436965
            },
            "duration": 180
        },
        "delivery":
        {
            "address":
            {
                "location_id": "end_halt_481",
                "name": "sm3_del",
                "lat": 50.503788,
                "lon": 12.396245
            },
            "duration": 180
        },
        "size":
        [
            1
        ],
        "priority": 3,
        "max_time_in_vehicle": 2430
    }
]

}

Et voilà:

48
Screen Shot 2018-06-25 at 14.24.48.jpg600×600 190 KB

2 Likes
13

Exactly! Sometimes it’s hard to describe a problem in different languages and from different perspectives.

So, in this solution we first need to request the strait route of each passenger over the API and then use this result in our “main” shipment-request, right?

1 Like
14

So, in this solution we first need to request the strait route of each passenger over the API and then use this result in our “main” shipment-request, right?

Yes, you can ask the Routing API how long it takes to get from pickup.location to delivery.location.

15

Okay thank you! We’ll try this out.

The solution sounds more like a workaround, though. Do you have any plans to add an optimization mode for “shortest delivery time”?

16

I think “shortest delivery time” is still misleading. It is probably more min -> customer dissatisfaction or max -> customer satisfaction. The way I described is a very typical and common way to model this (in literature). It might have a slight more focus on transportation costs, i.e. it is min -> total transportation costs subject to discomfort constraints of passenger like time windows and in-vehicle time. However, transportation costs are always important from an operator’s point of view.
To answer your question, currently there are no plans to add smth like max -> customer satisfaction, but it is always helpful and interesting to model such a problem from different perspectives.

17

Hey Stefan,

sorry for the late response.

We changed some things in our software and we implemented your suggested solution.

For the example we made, it totally perfect. The route we get from your API is what we expect, even though we needed to set the multiplication to “2”, instead of the 1.5 you said. Anyway.

Our current problem is now, that if we add another shipment/Point to the route, which fits perfect into the route, but extends this, then that the result isn’t that optimal as before. Please see the attached screenshot.

Your API forces to deliver one student first to his target and then get the other ones.

Why is that so?

58
Bildschirmfoto 2018-07-04 um 07.51.58.jpg1000×1157 324 KB

18

Hi Lars,

Would you mind to send me the corresponding problem in json or job_id?

Thanks,
Stefan

19

sure, I could have come to it by myself.

Here’s the json:

{"configuration":{"routing":{"calc_points":false}},"objectives":[{"type":"min","value":"transport_time"}],"vehicles":[{"vehicle_id":"vehicle_Start_Endpunkt","start_address":{"location_id":"location_start_Start_Endpunkt","lat":50.614958999999999,"lon":12.273825},"type_id":"vehicletype_Start_Endpunkt_small_truck","return_to_depot":false}],"vehicle_types":[{"type_id":"vehicletype_Start_Endpunkt_small_truck","profile":"small_truck","capacity":[8],"speed_factor":1.0,"service_time_factor":1.0}],"shipments":[{"id":"halt_565","name":"<div class=\"popup_header einstieg_popup\">Einstieg | <b>06:08<br>Rautenkranzer Straße 7, 08209 Auerbach<\/b><\/div><div class=\"popup_content\"><b>Lehmann, Lars<\/b> | 111116876786<br>Einstieg - 3 Minute(n)<\/div>","pickup":{"address":{"location_id":"start_halt_565","name":"<div class=\"popup_header einstieg_popup\">Einstieg | <b>06:08<br>Rautenkranzer Straße 7, 08209 Auerbach<\/b><\/div><div class=\"popup_content\"><b>Lehmann, Lars<\/b> | 111116876786<br>Einstieg - 3 Minute(n)<\/div>","lat":50.477632,"lon":12.454383},"duration":180},"delivery":{"address":{"location_id":"end_halt_565","name":"<div class=\"popup_header ausstieg_popup\">Ausstieg | <b>07:30<br>Kaiserstraße  65, 08209 Auerbach<\/b><\/div><div class=\"popup_content\"><b>Bednorz, Dustin<\/b> | 14892<br>Ausstieg - 3 Minute(n)<\/div><div class=\"popup_content\"><b>Schlosser, Laura<\/b> | 14893<br>Ausstieg - 3 Minute(n)<\/div><div class=\"popup_content\"><b>Lehmann, Lars<\/b> | 111116876786<br>Ausstieg - 3 Minute(n)<\/div>","lat":50.503788,"lon":12.396245},"duration":180},"size":[1],"priority":3,"max_time_in_vehicle":1466},{"id":"halt_562","name":"<div class=\"popup_header einstieg_popup\">Einstieg | <b>06:41<br>Klingenthal, Bahnhof<\/b><\/div><div class=\"popup_content\"><b>Petzold, Tim<\/b> | 15209<br>Einstieg - 3 Minute(n)<\/div>","pickup":{"address":{"location_id":"start_halt_562","name":"<div class=\"popup_header einstieg_popup\">Einstieg | <b>06:41<br>Klingenthal, Bahnhof<\/b><\/div><div class=\"popup_content\"><b>Petzold, Tim<\/b> | 15209<br>Einstieg - 3 Minute(n)<\/div>","lat":50.357392303812603,"lon":12.4635052028478},"duration":180},"delivery":{"address":{"location_id":"end_halt_562","name":"<div class=\"popup_header ausstieg_popup\">Ausstieg | <b>07:41<br>Schillerstraße  2, 08228 Rodewisch<\/b><\/div><div class=\"popup_content\"><b>Petzold, Tim<\/b> | 15209<br>Ausstieg - 3 Minute(n)<\/div>","lat":50.529121000000004,"lon":12.405787},"duration":180},"size":[1],"priority":3,"max_time_in_vehicle":4138},{"id":"halt_563","name":"<div class=\"popup_header einstieg_popup\">Einstieg | <b>06:50<br>Klingenthal III, Post<\/b><\/div><div class=\"popup_content\"><b>Bednorz, Dustin<\/b> | 14892<br>Einstieg - 3 Minute(n)<\/div>","pickup":{"address":{"location_id":"start_halt_563","name":"<div class=\"popup_header einstieg_popup\">Einstieg | <b>06:50<br>Klingenthal III, Post<\/b><\/div><div class=\"popup_content\"><b>Bednorz, Dustin<\/b> | 14892<br>Einstieg - 3 Minute(n)<\/div>","lat":50.380852858417299,"lon":12.4819549495164},"duration":180},"delivery":{"address":{"location_id":"end_halt_563","name":"<div class=\"popup_header ausstieg_popup\">Ausstieg | <b>07:30<br>Kaiserstraße  65, 08209 Auerbach<\/b><\/div><div class=\"popup_content\"><b>Bednorz, Dustin<\/b> | 14892<br>Ausstieg - 3 Minute(n)<\/div><div class=\"popup_content\"><b>Schlosser, Laura<\/b> | 14893<br>Ausstieg - 3 Minute(n)<\/div><div class=\"popup_content\"><b>Lehmann, Lars<\/b> | 111116876786<br>Ausstieg - 3 Minute(n)<\/div>","lat":50.503788,"lon":12.396245},"duration":180},"size":[1],"priority":3,"max_time_in_vehicle":3214},{"id":"halt_564","name":"<div class=\"popup_header einstieg_popup\">Einstieg | <b>06:57<br>Klingenthal, Gasth Stern<\/b><\/div><div class=\"popup_content\"><b>Schlosser, Laura<\/b> | 14893<br>Einstieg - 3 Minute(n)<\/div>","pickup":{"address":{"location_id":"start_halt_564","name":"<div class=\"popup_header einstieg_popup\">Einstieg | <b>06:57<br>Klingenthal, Gasth Stern<\/b><\/div><div class=\"popup_content\"><b>Schlosser, Laura<\/b> | 14893<br>Einstieg - 3 Minute(n)<\/div>","lat":50.392224986263997,"lon":12.4948111436965},"duration":180},"delivery":{"address":{"location_id":"end_halt_564","name":"<div class=\"popup_header ausstieg_popup\">Ausstieg | <b>07:30<br>Kaiserstraße  65, 08209 Auerbach<\/b><\/div><div class=\"popup_content\"><b>Bednorz, Dustin<\/b> | 14892<br>Ausstieg - 3 Minute(n)<\/div><div class=\"popup_content\"><b>Schlosser, Laura<\/b> | 14893<br>Ausstieg - 3 Minute(n)<\/div><div class=\"popup_content\"><b>Lehmann, Lars<\/b> | 111116876786<br>Ausstieg - 3 Minute(n)<\/div>","lat":50.503788,"lon":12.396245},"duration":180},"size":[1],"priority":3,"max_time_in_vehicle":2802}]}

(I edited it recently)

20

“max_time_in_vehicle”: 4138 for halt_562 is not sufficient to bundle all shipments in this nice single “round” tour.

“max_time_in_vehicle”: 4143 works.