New feature: balance completion time AND activities

Directions API Route Optimization API
1

We are happy to announce another objective function. It balances your routes’s completion times first, and, second, it balances activites over all available routes. To put it in other words, it minimizes the overall makespan of a vehicle route plan, and - given this makespan - it distributes activities equally over all available drivers. This usually results in a number of solutions with balanced activities. From this set of solutions, it chooses the solution that minimizes total transport costs.

It can be specified as follows:

"objectives": [
    {
      "type": "min-max",
      "value": "completion_time"
    },
    {
        "type":"min-max",
        "value":"activities"
    }
]
1 Like
2

Let me illustrate the differences by a simple example. Assume 4 drivers at the depot marked in green and 10 customers in Berlin. The following objective, min vehicles first, and, completion time second:

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

yields a typical round tour with a single vehicle.

57

If you change objective to:

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

you will be provided with the following solution:

10

But still, there is one idle vehicle which obviously cannot contribute to min max completion time, but if you still want to employ it, you can change the objective to:

 "objectives": [
        {
          "type": "min-max",
          "value": "activities"
        }
    ]

It results in:
25

This is much better when it comes to the number of vehicles employed. However, as you can see, the longest route from the previous example now got two more activites and therefore got even longer, and, there is this very short route marked in red.

To balance this more reasonable, there is this new objective function:

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

which yields this nice solution:
40

3

Thanks!

Do you have some use cases for using “min-max completion time” vs. “min-max completion time and activities”? Is the latter combination used e.g. when you have independent drivers and you want a fair spread or what could be a typical scenario?

And is there a use case for “min-max activities” alone or is this almost always used in combination with min-max completion time?

4

This blog post might illustrate the new feature better: https://www.graphhopper.com/blog/2018/04/11/balance-load-among-all-vehicles/

1 Like
5

I tried optimization without time widows and capacity, just simple addresses and duration (15 mins or 20 mins).
But there are some unassigned jobs sometimes although vehicle is 24 hr available.
Is it because of min-max completion time?

1 Like
6

@myominlin Would you mind to provide us with an example? If you want you can also send this per mail. This way it is much easier to analyse. Thanks.

7

@myominlin It was a bug and it is fixed now. Thanks for dedecting and providing us with an example.

1 Like
8

Thanks @stefan for quick fix.
I already tried, it’s working fine now.