How to solve a traveling salesman problem with a week-planning horizon and driver shifts?

Introduction

A few years ago, we wrote a tutorial to show you how to model a traveling salesman problem with a week-planning horizon. Since then we have been improving our API a lot and I would like to show you how easy it is now to model this with driver shifts.

For example, suppose you have ONE employee who has to visit 25 customers over the next week. Let us also assume that the employee has certain daily working hours and the customers to be visited have several time slots. Your task is to plan his routes from Monday to Friday in such a way that the total transport costs are minimized. The result can be as follows:

Instructional Content

In our documentation you will find the general setup of the Json request and how to submit this request to our servers. In the following I will show step by step how to model the above problem..

1. Specify your vehicle type

Suppose the employee has a car and the capacity doesn’t matter, then your Json specification should look like this:

"vehicle_types":[
   {
      "type_id": "car_type",
      "profile": "car"
   }
]

Therefore you need a “type_id”, with which you can refer to it in your vehicles. In addition, you need to specify the profile “car” (you can read more about the profiles you can select here). In this way, transport times and distances are calculated based on the road network. The results correspond exactly to what you get when working with our Routing API and GraphHopper Maps.

2. Specify your vehicles and shifts

Let us assume the worker can work from Monday to Friday. Now you specify the time either with the recommended Unix time stamp (the number of seconds since 1970-01-01) or for example, you count the seconds from Monday morning 00:00 and define the whole week in seconds. For example, Monday 9am is then represented by 9hour * 3600sec/hour = 32400sec. In turn, Wednesday 1pm corresponds to 2day * 24hour/day * 3600sec/hour + 1day * 13hour/day * 3600sec/hour = 219600sec.

Let us also assume your worker can work 8 hours per day and need to start at 8am. Then you can define your vehicles as follows:

"vehicles": [
{
   "vehicle_id": "fieldworker-1",
   "type_id": "car_type",
   "shifts": [
      {
         "shift_id": "monday",
         "start_address": {
            "location_id": "your_home",
            "lon": 13.39238003043599,
            "lat": 52.50385692772726
         },
         "earliest_start": 28800,
         "latest_end": 57600
      },
      {
         "shift_id": "tuesday",
         "start_address": {
            "location_id": "your_home",
            "lon": 13.39238003043599,
            "lat": 52.50385692772726
         },
         "earliest_start": 115200,
         "latest_end": 144000
      },
      ...
      {
         "shift_id": "friday",
         "start_address": {
            "location_id": "your_home",
            "lon": 13.39238003043599,
            "lat": 52.50385692772726
         },
         "earliest_start": 374400,
         "latest_end": 403200
      }
]
}
]

According to the above example, your vehicles always start and end at the location of “your house” (the coordinates must be given in longitude/latitude). If you want to allow your employee to end his route at a different location, simply enter an “end_address”.

3. Specify your customers

Customers can be specified as ordinary services much like this:

"services": [
   {
      "id": "customer-id",
      "name": "visit pharmacy",
      "address": {
         "location_id": "customer-location-id",
         "lon": 9.999,
         "lat": 53.552
      },
      "duration": 3600
   },
...

]

Here, it is assumed that a visit takes 1 hour (3600 seconds). If this customer can only be visited on Tuesday or Friday, you can assign specific time windows to your services. Let us assume this customer can only be visited on Tuesday. Furthermore, you can only visit him from 9am to 11am or from 2pm to 4pm then you need to specify multiple time windows like this:

"service": [
   {
      "id": "customer-id",
      "name": "visit pharmacy",
      "address": {
         "location_id": "customer-location-id",
         "lon": 9.999,
         "lat": 53.552
      },
      "duration": 3600,
      "time_windows": [
         {
            "earliest": 118800,
            "latest": 126000
         },
         {
            "earliest": 136800,
            "latest": 144000
         }
      ]
   },
...

]

If you have more visits than your worker can serve in a week, you might want to prioritize certain visits over visits that can be postponed. You can do this by assigning priorities (1 = high prio, 2 = normal (default) prio, 3 = low prio) to your jobs, just like this:

"services": [
   {
      "id": "customer-id",
      "name": "visit pharmacy",
      "address": {
         "location_id": "customer-location-id",
         "lon": 9.999,
         "lat": 53.552
      },
      "duration": 3600,
      "priority": 1
   },
...

]

4. Specify the algorithm

Finally, you must specify your optimization goal. If you solely want to minimize overall completion time, specify it like this

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

Entire example

If you want to play around with vehicle (type) definitions like profiles and operation times or customer specifications like time windows 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 model a simple traveling salesman with a week planning horizon and driver shifts. If you want to know, how you can refine your optimization goal to get a more balanced solution in terms of working time or if you want to add additional relations between your visits, e.g. customer A need to be visited directly after customer B, visit our documentation site or just asks questions in our forum.

Happy routing!