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

Introduction

In this tutorial we are going to show you how to model a traveling salesman problem with a week-planning horizon. For example, let us assume you have ONE worker that needs to visit 25 customers in the course of the next week. Let us also assume that the worker has specific daily working hours and the customers to be visited have multiple time windows. Your task is to plan his routes from Monday to Friday such that overall transportation costs are minimized. The result can look 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

Let us assume the worker has a car and capacity does not play any role then your json snippet should look like this:

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

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

2. Specify your vehicles and working days

The easiest way to tackle this is to define a separate vehicle for each working day. Since we will define non-overlapping operation time windows for each vehicle, i.e. "earliest_start" and "latest_end", it can be interpreted as one vehicle with multiple employment time windows where each time window represents one working day. 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 much like this:

"vehicles": [
   {
      "vehicle_id": "monday",
      "start_address": {
         "location_id": "your-home",
         "lon": 11.028771,
         "lat": 50.977723
      },
      "type_id": "car_type",
      "earliest_start": 28800,
      "latest_end": 57600
   },
   {
      "vehicle_id": "tuesday",
      "start_address": {
         "location_id": "your-home",
         "lon": 11.028771,
         "lat": 50.977723
      },
      "type_id": "car_type",
      "earliest_start": 115200,
      "latest_end": 144000
   }

...

   {
      "vehicle_id": "friday",
      "start_address": {
         "location_id": "your-home",
         "lon": 11.028771,
         "lat": 50.977723
      },
      "type_id": "car_type",
      "earliest_start": 374400,
      "latest_end": 403200
   }
]

According to the example above your vehicles always start and end at “your-home” location (coordinates need to be in longitude/latitude). If you want to let your worker to end its route at another location, just specify 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 have two options to model this. You can either specifically assign the Tuesday- and Friday-vehicles as follows:

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

]

or 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:

"services": [
   {
      "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 transport time, specify it like this

"objectives" : [{
   "type": "min",
   "value": "transport_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 where visits can have multiple time windows. 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!