How to schedule technicians with skills and multiple dependencies between tasks?

Introduction

In this tutorial we are going to show you how to model a vehicle routing problem where tasks do not only have multiple dependencies, but also require special skills. For example, let us assume we have two technicians called Peter and Stefan. Peter cannot only read the warm water meter, but he can also replace an old meter with a new one. Stefan can just read the meter. To get new warm water meters there is this water meter inventory. To open it one needs to pickup a key before (that needs to be returned). Furthermore, the replacement of a meter requires a special tool that needs to be picked up before as well. Both, Peter and Stefan, can only ride by bike since – much to the joy of everyone involved – their employer recently decided to replace all cars by bikes. Given a number of customers and these requirements, your task is to schedule Stefan and Peter such that the overall transportation costs are minimized. Peter’s and Stefan’s route could look for example like this:

Instructional Content

In our documentation you find the general setup of the json request as well as how to post this request to our servers. What follows is a step-by-step approach to model the problem above, i.e. creating the necessary JSON request.

1. Specify your vehicle type

Both, Peter and Stefan, can only ride by bike. Let us assume that capacity does not play any role then your json snippet should look like this:

"vehicle_types":[ 
   { 
      "type_id": "bike_type", 
      "profile": "bike" 
   } 
] 

Thus you need a “type_id” that can be used to reference it in your vehicles. Additionally, you need to specify the profile “bike” (learn more about the profiles you can choose here). This way transport times and distances are calculated based on a bike network. The results correspond exactly to what you get when operating with our Routing API and GraphHopper Maps.

2. Specify your vehicles

Here, we require two bikes that basically represent Peter and Stefan. Both have skills, Peter can “read” and “replace” the meter. Stefan can just “read”. Furthermore, it is assumed that they can both work from 8am to 6pm (specified in seconds of that day).

"vehicles": [
    {
        "vehicle_id": "peter",
        "start_address": {
            "location_id": "your_home",
            "lon": 13.39238003043599,
            "lat": 52.50385692772726
        },
        "type_id": "bike_type",
        "earliest_start": 28800,
        "latest_end": 64800,
        "skills": ["read","replace"]
    },
    {
        "vehicle_id": "stefan",
        "start_address": {
            "location_id": "your_home",
            "lon": 13.39238003043599,
            "lat": 52.50385692772726
        },
        "type_id": "bike_type",
        "earliest_start": 28800,
        "latest_end": 64800,
        "skills": ["read"]
    }
]

3. Specify the tasks

Tasks can be specified as ordinary services. First, we need to specify tasks to pickup and delivery the inventory key much like this:

"services": [
   {
      "id": "pickup-key",
      "name": "pickup the key for this inventory",
      "address": {
         "location_id": "key-location-id",
         "lon": 9.999,
         "lat": 53.552
      },
      "duration": 200
   },
   {
      "id": "deliver-key",
      "name": "deliver the key for this inventory",
      "address": {
         "location_id": "key-location-id",
         "lon": 9.999,
         "lat": 53.552
      },
      "duration": 200
   }
...

]

Second, to replace the meter, one needs to pickup this special tool.

   {
      "id": "pickup-special-tool",
      "name": "pickup special tool to replace warm water meter",
      "address": {
         "location_id": "tool-location-id",
         "lon": 9.999,
         "lat": 53.552
      },
      "duration": 200
   }
...

Third, there is this inventory with warm water meters that needs to be visited before serving customers with new meters. Here, it is assumed that the inventory has enough meters and that it always takes 1800sec to pick them up.

   {
      "id": "visit-inventory",
      "name": "pickup the required number of warm water meters",
      "address": {
         "location_id": "tool-location-id",
         "lon": 9.999,
         "lat": 53.552
      },
      "duration": 1800
   }
...

Fourth, there are customers with meters to be read and with meters to be read and replaced.

   {
      "id": "serve-customer1",
      "name": "read warm water meter",
      "address": {
         "location_id": "customer1-location-id",
         "lon": 9.999,
         "lat": 53.552
      },
      "duration": 1800,
      "required_skills": ["read"]
   },
   {
      "id": "serve-customer2",
      "name": "read and replace warm water meter",
      "address": {
         "location_id": "customer2-location-id",
         "lon": 9.999,
         "lat": 53.552
      },
      "duration": 1800,
      "required_skills": ["read","replace"]
   }
...

Let us also assume that there is a customer that has a meter to be read and that wants to see Stefan. The specification of this customer would look like this:

   {
      "id": "serve-customer3",
      "name": "read warm water meter and wants to get this done by Stefan",
      "address": {
         "location_id": "customer1-location-id",
         "lon": 9.999,
         "lat": 53.552
      },
      "duration": 1800,
      "required_skills": ["read"],
      "allowed_vehicles": ["stefan"]
   }
...

3. Specify the relations

There are few relations that need to be considered:

• to open the warm water meter inventory one needs a key
• to serve the customers with new meters, one needs to pickup new meters as well as this special tool first

This can be specified in the relation part of the JSON request:

"relations": [
   {
      "type": "in_direct_sequence",
      "ids": ["pickup-key","visit-inventory"]
   },   
   {
      "type": "in_sequence",
      "ids": ["visit-inventory","deliver-key"]
   },
   {
      "type": "in_sequence",
      "ids": ["pickup-special-tool","serve-customer2"] 
   },
   { 
      "type": "in_sequence",
      "ids": ["visit-inventory","serve-customer2"]
   }
   ...
]

This way you can define an arbitrary number of relations of type “in_same_route”, “in_sequence” and “in_direct_sequence”.

Entire example

If you want to play around with relations etc. here you can find an entire example. Just copy the problem to our route editor, solve it and analyse the solution. You can either do it by looking at a map or at the raw json data.

Closing remark

Congratulations! You should now be able to add relations to your traveling salesman and vehicle routing problem. If you want to learn more about the conrete specification of relations, visit our documentation site or just asks questions in our forum.

Happy routing!