Help

What is the difference between the minimization of completion time and minimizing transport time?

Every optimization requires an objective ie. a goal to which the results should be optimize for. Here, we want to illustrate the differences between two objectives: min transport time and min completion time. Using the GraphHopper Directions API the specification of these goals is as simple and intuitive as the following json snippets:

"objectives": [
    {
      "type": "min",
      "value": "transport_time"
    }
  ]

or

"objectives": [
    {
      "type": "min",
      "value": "completion_time"
    }
  ]

Transport time is the time your driver spends on the road to transport items from one location to another. The total transport time of a route is the sum of each leg’s transport time. A leg is what happens between one activity location and another.
The completion time of a route is the total time your driver takes from the start to the end of his route.
Therefore, transport time is included in the completion time of the route. To be more precise:
The completion time of a route = the sum of route leg’s transport time + sum of route’s waiting time + sum of route’s activity duration.

Therefore, the difference between min transport time and min completion time is that in contrary to min transport time, min completion time takes waiting time and activity duration into account. Waiting time and activity duration become part of the objective function. Since activity duration is usually constant (it cannot contribute to improve the objective), the main difference between transport and completion time is waiting time.

Waiting time only occurs in scenarios with time windows. No time windows, no waiting. Therefore, min transport time and min completion time should yield the same results if no time windows are specified.
If you specified time windows, waiting time only occurs if your driver arrives too early at an activity location, i.e. before the earliest_start of an activity.

Let us give you an illustrative example. Assume there is a bicycle messenger that starts at 8am to deliver parcels to 3 locations: West, East and North. West and East have time windows and only allow you to deliver parcels from 9am to 11am. North, however, can be delivered anytime. Min transport time results in the following solution (Figure 1):

min_tpt
Figure 1: minimize transport time

This is the expected solution when solely looking at transport times. However, one might ask why the driver waits for almost an hour at West. Instead of just waiting, he should deliver location North first. This is exactly what min completion time takes into account. Waiting times become part of the objective function and thus it results in the following solution (Figure 2).

min_ct
Figure 2: Minimize completion time

To make this even more visible, lets compare the solutions in a table.

table_minTp

As you can see min transport time ignores the potential waiting time savings of 45 min and solely focuses on transport time. Thus, transport time and distance are lower than when minimizing completion time. However, waiting times and thus completion time can be reduced significantly by minimizing completion time which comes with slightly higher overall transport times.