Shipments are delivered based on earliest time with causing strange waiting time

Directions API Route Optimization API
1

Hi,

We use the optimisation api with shipments using time windows. These are persons transported with different waiting times (expressed in the time windows). The objective is to have a minimum completion time of the whole trip.
The parameter sent to the api is the following:

{
“vehicles”: [
{
“vehicle_id”: “vehicle_21”,
“type_id”: “vehicle_type_21”
}
],
“vehicle_types”: [
{
“type_id”: “vehicle_type_21”,
“capacity”: [
5,
2
],
“profile”: “car”,
“speed_factor”: 1
}
],
“shipments”: [
{
“id”: “person_101”,
“pickup”: {
“address”: {
“location_id”: “address_23”,
“lon”: 12.9243038,
“lat”: 50.8275202
},
“duration”: 180,
“time_windows”: [
{
“earliest”: 0,
“latest”: 86400
}
]
},
“delivery”: {
“address”: {
“location_id”: “address_22”,
“lon”: 12.981500001,
“lat”: 50.9857286
},
“time_windows”: [
{
“earliest”: 25200,
“latest”: 27000
}
],
“preparation_time”: 600
},
“size”: [
0,
1
]
},
{
“id”: “person_104”,
“pickup”: {
“address”: {
“location_id”: “address_21”,
“lon”: 12.922956,
“lat”: 50.832833
},
“duration”: 600,
“time_windows”: [
{
“earliest”: 0,
“latest”: 86400
}
]
},
“delivery”: {
“address”: {
“location_id”: “address_22”,
“lon”: 12.981500001,
“lat”: 50.9857286
},
“time_windows”: [
{
“earliest”: 25200,
“latest”: 27000
}
],
“preparation_time”: 600
},
“size”: [
2,
0
]
},
{
“id”: “person_107”,
“pickup”: {
“address”: {
“location_id”: “address_25”,
“lon”: 12.9688128,
“lat”: 50.8739834
},
“duration”: 60,
“time_windows”: [
{
“earliest”: 0,
“latest”: 86400
}
]
},
“delivery”: {
“address”: {
“location_id”: “address_22”,
“lon”: 12.981500001,
“lat”: 50.9857286
},
“time_windows”: [
{
“earliest”: 26100,
“latest”: 27900
}
],
“preparation_time”: 600
},
“size”: [
1,
0
]
}
],
“objectives”: [
{
“type”: “min”,
“value”: “completion_time”
}
],
“configuration”: {
“routing”: {
“calc_points”: false
}
}
}

The algorithm drops the persons as early as possible (based on the earliest time) exactly on 25200. However, due to all shipments are delivered at the same address, we witnessed a strange waiting time of 900 seconds on the shipment delivery where it has to be delivered at earliest on 26100.
We are wondering why does the algorithm produces this strange waiting time especially that it could be possible to avoid it when not targeting basically the earliest time window, but a time within that delivery time window with considering the waiting times ?

2

Hi,

Thanks for your example.

I see that from a transported person point of view, it does not make much sense, but where do you think you can save waiting times? As far as I can see, you always have to wait unit 08:15 no matter how you order the deliverShipment activities. If you would add a duration for these activities, the order does matter. You can play with the order here: https://explorer.graphhopper.com/

Best,
Stefan

3

This “preparation_time” only occurs before the first delivery activity. From then on, there is no more activity duration. Then it doesn’t matter in which order it is processed, at least in relation to the total time (not in relation to those waiting, of course). However, if each activity still has a duration in itself, the order will certainly change (I hope)).

4

Hi Stefan,

thank you for your answer.

The"preparation_time" is needed in this case as all the persons are dropped off at the same address and therefore the time spent for delivering these 3 persons at the same location has to be counted once.
However, we use time windows to provide a timespan during which a person should be dropped off. In this example, 2 of the 3 persons should be dropped off between “7:00” and “7:30”. The person where the strange waiting time happens should be dropped off between “7:15” and “7:45”.
We assume that the waiting time could be avoided if the algorithm considers these time windows in the solution. Therefore, all persons could be for example dropped off at “7:15” which still fulfils the time windows without strange waiting time.
This is obviously not the case as the algorithm delivers all persons considering the earliest time as far as we witness it. Then, it recognises that the deliverShipment of one person should start later and causes these strange 15 minutes waiting time.
We wonder if this is the intended behaviour of the algorithm ? Or do we mis-use the time windows ?

5

To be more precise, the goal is to drop/deliver each shipment closest to its latest corresponding time window. Until now, we see that it is dropped as earliest as possible.

6

No, no, you’re already using the time window correctly. In this case, however, you can’t avoid the waiting time at all. This is mainly due to the fact that your vehicle starts at 0 AND the fact that we do not optimize the driver’s departure time. If you give the driver a more realistic departure time, the result is more likely to be what you expect. For example:

{
  "vehicles": [
    {
      "vehicle_id": "vehicle_21",
      "type_id": "vehicle_type_21",
      "earliest_start":23200
    }
  ],
  "vehicle_types": [
    {
      "type_id": "vehicle_type_21",
      "capacity": [
        5,
        2
      ],
      "profile": "car",
      "speed_factor": 1
    }
  ],
  "shipments": [
    {
      "id": "person_101",
      "pickup": {
        "address": {
          "location_id": "address_23",
          "lon": 12.9243038,
          "lat": 50.8275202
        },
        "duration": 180,
        "time_windows": [
          {
            "earliest": 0,
            "latest": 86400
          }
        ]
      },
      "delivery": {
        "address": {
          "location_id": "address_22",
          "lon": 12.981500001,
          "lat": 50.9857286
        },
        "time_windows": [
          {
            "earliest": 25200,
            "latest": 27000
          }
        ],
        "preparation_time": 600
      },
      "size": [
        0,
        1
      ]
    },
    {
      "id": "person_104",
      "pickup": {
        "address": {
          "location_id": "address_21",
          "lon": 12.922956,
          "lat": 50.832833
        },
        "duration": 600,
        "time_windows": [
          {
            "earliest": 0,
            "latest": 86400
          }
        ]
      },
      "delivery": {
        "address": {
          "location_id": "address_22",
          "lon": 12.981500001,
          "lat": 50.9857286
        },
        "time_windows": [
          {
            "earliest": 25200,
            "latest": 27000
          }
        ],
        "preparation_time": 600
      },
      "size": [
        2,
        0
      ]
    },
    {
      "id": "person_107",
      "pickup": {
        "address": {
          "location_id": "address_25",
          "lon": 12.9688128,
          "lat": 50.8739834
        },
        "duration": 60,
        "time_windows": [
          {
            "earliest": 0,
            "latest": 86400
          }
        ]
      },
      "delivery": {
        "address": {
          "location_id": "address_22",
          "lon": 12.981500001,
          "lat": 50.9857286
        },
        "time_windows": [
          {
            "earliest": 26100,
            "latest": 27900
          }
        ],
        "preparation_time": 600
      },
      "size": [
        1,
        0
      ]
    }
  ],
  "objectives": [
    {
      "type": "min",
      "value": "completion_time"
    }
  ],
  "configuration": {
    "routing": {
      "calc_points": false
    }
  }
}
7

Okay, first of all: thank you!

The reason why we set the driver’s departure to 0:00 is, that we calculate it from the optimized route later. It is not a optimization target and therefore depends on the shipments and their time windows. the driver starts as early or late as the trips demands.

Is there no way to tell the algorithm that it optimizes towards the time_windows.latest?

More precise, this is what we want to achieve:

  • each shipment has a time_window for their deliveries, more clear: the school bells time
  • but most persons can be dropped of minutes earlier, some 30, some 15 and so on
  • they should be dropped of as close as possible to their time_window.latest (school bells/start of lessons)

We don’t fear recalculating the times, we do this already due to the fact, that the pickup times are all very close to 0:00 (because they don’t have a narrow time window).

But what we need is an optimized route, based on the latest time_window.latest time or something similar.

I hope you understand our demand. Is there something what we could do?

  • List item
8

Thank you for your posts and use case.

No, this is not possible and - I guess - it only makes sense if we optimized departure times.

If you estimate the departure time in a kind of post-processing anyway, couldn’t you determine a number of probable departure times and solve your problem for each departure time? I assume that the problems themselves are not that big, i.e. the computing time should be negligible. For example: The driver starts sometime between 6:00 and 7:00, so you solve the problem for the following departure times: 6:00, 6:15, 6:30, 6:45, 7:00 and take the solution with which you can just about get all your students to school?

9

Hm, interesting approach. But would’t this consume the multiple factor of credits as well?

Also, it’s not only about the driver. If we ignore the driver for an instance, we still have the problem with the shipments.

A shiptment can be delivered at any time between time_window.earliest and time_window.latest. But the result are optimized towards the time_window.earliest. This is as you say, because you don’t optimize the delivery time. We don’t “want” to drop the students at their earliest dropoff-time as default, only if the optimization demands it.

Therefore, this use case can not be modeled with the API yet, I suppose, right?