VRP with Breaks

Very often, there are situations when drivers have breaks in their shifts. The most trivial case is a lunch break for example. Those breaks should be considered when planning a tour with the time windows specified for the jobs. Note that in fact, a break can happen anywhere within the break time window. The duration and times properties are required for the breaks. In case a break is defined for a vehicle, the duration of the break is added to the shiftTime. In the example below we have three cars with fixed shifts and breaks and 6 jobs to execute with the specific time windows.

Problem

{
  "fleet": {
    "types": [
      {
        "id": "6290a20b08a7",
        "profile": "car_1",
        "costs": {
          "fixed": 10.0,
          "distance": 0.001,
          "time": 0.006
        },
        "shifts": [
          {
            "start": {
              "time": "2021-08-27T08:03:00Z",
              "location": {
                "lat": 52.530971,
                "lng": 13.384915
              }
            },
            "end": {
              "time": "2021-08-27T16:03:00Z",
              "location": {
                "lat": 52.530971,
                "lng": 13.384915
              }
            },
            "breaks": [
              {
                "duration": 1800,
                "times": [
                  [
                    "2021-08-27T12:03:00Z",
                    "2021-08-27T13:03:00Z"
                  ]
                ]
              }
            ]
          }
        ],
        "capacity": [
          7
        ],
        "limits": {
          "maxDistance": 300000
        },
        "amount": 1
      },
      {
        "id": "973bccabf941",
        "profile": "car_1",
        "costs": {
          "fixed": 12.0,
          "distance": 0.004,
          "time": 0.005
        },
        "shifts": [
          {
            "start": {
              "time": "2021-08-27T08:03:00Z",
              "location": {
                "lat": 52.530971,
                "lng": 13.384915
              }
            },
            "end": {
              "time": "2021-08-27T16:03:00Z",
              "location": {
                "lat": 52.530971,
                "lng": 13.384915
              }
            },
            "breaks": [
              {
                "duration": 1800,
                "times": [
                  [
                    "2021-08-27T11:03:00Z",
                    "2021-08-27T13:03:00Z"
                  ]
                ]
              }
            ]
          }
        ],
        "capacity": [
          3
        ],
        "limits": {
          "maxDistance": 300000
        },
        "amount": 1
      },
      {
        "id": "92d3cd5cca04",
        "profile": "car_1",
        "costs": {
          "fixed": 10.0,
          "distance": 0.004,
          "time": 0.009
        },
        "shifts": [
          {
            "start": {
              "time": "2021-08-27T08:03:00Z",
              "location": {
                "lat": 52.530971,
                "lng": 13.384915
              }
            },
            "end": {
              "time": "2021-08-27T17:03:00Z",
              "location": {
                "lat": 52.530971,
                "lng": 13.384915
              }
            },
            "breaks": [
              {
                "duration": 1800,
                "times": [
                  [
                    "2021-08-27T12:03:00Z",
                    "2021-08-27T13:03:00Z"
                  ]
                ]
              }
            ]
          }
        ],
        "capacity": [
          2
        ],
        "limits": {
          "maxDistance": 300000
        },
        "amount": 1
      }
    ],
    "profiles": [
      {
        "type": "car",
        "name": "car_1"
      }
    ]
  },
  "plan": { 
    "jobs": [ 
      { 
        "id": "job_1", 
        "tasks": { 
          "deliveries": [ 
            { 
              "places": [ 
                { 
                  "times": [ 
                    [ 
                      "2021-08-27T09:03:00Z", 
                      "2021-08-27T10:03:00Z" 
                    ] 
                  ], 
                  "location": { 
                    "lat": 52.59175589353722, 
                    "lng": 13.350747750372257 
                  }, 
                  "duration": 360 
                } 
              ], 
              "demand": [ 
                1 
              ] 
            } 
          ] 
        } 
      }, 
      { 
        "id": "job_2", 
        "tasks": { 
          "deliveries": [ 
            { 
              "places": [ 
                { 
                  "times": [ 
                    [ 
                      "2021-08-27T14:03:00Z", 
                      "2021-08-27T16:03:00Z" 
                    ] 
                  ], 
                  "location": { 
                    "lat": 52.43363386232821, 
                    "lng": 13.403232562191313 
                  }, 
                  "duration": 540 
                } 
              ], 
              "demand": [ 
                1 
              ] 
            } 
          ] 
        } 
      }, 
      { 
        "id": "job_3", 
        "tasks": { 
          "deliveries": [ 
            { 
              "places": [ 
                { 
                  "times": [ 
                    [ 
                      "2021-08-27T10:03:00Z", 
                      "2021-08-27T16:03:00Z" 
                    ] 
                  ], 
                  "location": { 
                    "lat": 52.473321658918245, 
                    "lng": 13.28972099097991 
                  }, 
                  "duration": 660 
                } 
              ], 
              "demand": [ 
                1 
              ] 
            } 
          ] 
        } 
      }, 
      { 
        "id": "job_4", 
        "tasks": { 
          "deliveries": [ 
            { 
              "places": [ 
                { 
                  "times": [ 
                    [ 
                      "2021-08-27T06:03:00Z", 
                      "2021-08-27T17:03:00Z" 
                    ] 
                  ], 
                  "location": { 
                    "lat": 52.54165532725351, 
                    "lng": 13.365047170290309 
                  }, 
                  "duration": 1140 
                } 
              ], 
              "demand": [ 
                1 
              ] 
            } 
          ] 
        } 
      },
      { 
        "id": "job_5", 
        "tasks": { 
          "deliveries": [ 
            { 
              "places": [ 
                { 
                  "times": [ 
                    [ 
                      "2021-08-27T06:03:00Z", 
                      "2021-08-27T17:03:00Z" 
                    ] 
                  ], 
                  "location": { 
                    "lat": 52.569368, 
                    "lng": 13.314579 
                  }, 
                  "duration": 1140 
                } 
              ], 
              "demand": [ 
                1 
              ] 
            } 
          ] 
        } 
      },
      { 
        "id": "job_6", 
        "tasks": { 
          "deliveries": [ 
            { 
              "places": [ 
                { 
                  "times": [ 
                    [ 
                      "2021-08-27T06:03:00Z", 
                      "2021-08-27T17:03:00Z" 
                    ] 
                  ], 
                  "location": { 
                    "lat": 52.593857, 
                    "lng": 13.338440 
                  }, 
                  "duration": 1140 
                } 
              ], 
              "demand": [ 
                1 
              ] 
            } 
          ] 
        } 
      } 
    ] 
  } 
}

Solution

The solution for such a problem will look as follows:

{
    "statistic": {
        "cost": 180.973,
        "distance": 63465,
        "duration": 17918,
        "times": {
            "driving": 6897,
            "serving": 4980,
            "waiting": 4241,
            "break": 1800
        }
    },
    "tours": [
        {
            "vehicleId": "6290a20b08a7_1",
            "typeId": "6290a20b08a7",
            "stops": [
                {
                    "location": {
                        "lat": 52.530971,
                        "lng": 13.384915
                    },
                    "time": {
                        "arrival": "2021-08-27T08:03:00Z",
                        "departure": "2021-08-27T09:43:41Z"
                    },
                    "load": [
                        6
                    ],
                    "activities": [
                        {
                            "jobId": "departure",
                            "type": "departure"
                        }
                    ],
                    "distance": 0
                },
                {
                    "location": {
                        "lat": 52.59175589353722,
                        "lng": 13.350747750372255
                    },
                    "time": {
                        "arrival": "2021-08-27T10:03:00Z",
                        "departure": "2021-08-27T10:09:00Z"
                    },
                    "load": [
                        5
                    ],
                    "activities": [
                        {
                            "jobId": "job_1",
                            "type": "delivery"
                        }
                    ],
                    "distance": 9479
                },
                {
                    "location": {
                        "lat": 52.593857,
                        "lng": 13.33844
                    },
                    "time": {
                        "arrival": "2021-08-27T10:13:08Z",
                        "departure": "2021-08-27T10:32:08Z"
                    },
                    "load": [
                        4
                    ],
                    "activities": [
                        {
                            "jobId": "job_6",
                            "type": "delivery"
                        }
                    ],
                    "distance": 11288
                },
                {
                    "location": {
                        "lat": 52.569368,
                        "lng": 13.314579
                    },
                    "time": {
                        "arrival": "2021-08-27T10:40:26Z",
                        "departure": "2021-08-27T10:59:26Z"
                    },
                    "load": [
                        3
                    ],
                    "activities": [
                        {
                            "jobId": "job_5",
                            "type": "delivery"
                        }
                    ],
                    "distance": 15523
                },
                {
                    "location": {
                        "lat": 52.54165532725351,
                        "lng": 13.365047170290309
                    },
                    "time": {
                        "arrival": "2021-08-27T11:10:41Z",
                        "departure": "2021-08-27T12:33:00Z"
                    },
                    "load": [
                        2
                    ],
                    "activities": [
                        {
                            "jobId": "job_4",
                            "type": "delivery",
                            "location": {
                                "lat": 52.54165532725351,
                                "lng": 13.365047170290309
                            },
                            "time": {
                                "start": "2021-08-27T11:10:41Z",
                                "end": "2021-08-27T11:29:41Z"
                            }
                        },
                        {
                            "jobId": "break",
                            "type": "break",
                            "location": {
                                "lat": 52.54165532725351,
                                "lng": 13.365047170290309
                            },
                            "time": {
                                "start": "2021-08-27T11:29:41Z",
                                "end": "2021-08-27T12:33:00Z"
                            }
                        }
                    ],
                    "distance": 20405
                },
                {
                    "location": {
                        "lat": 52.473321658918245,
                        "lng": 13.28972099097991
                    },
                    "time": {
                        "arrival": "2021-08-27T12:54:53Z",
                        "departure": "2021-08-27T13:05:53Z"
                    },
                    "load": [
                        1
                    ],
                    "activities": [
                        {
                            "jobId": "job_3",
                            "type": "delivery"
                        }
                    ],
                    "distance": 34984
                },
                {
                    "location": {
                        "lat": 52.43363386232821,
                        "lng": 13.403232562191311
                    },
                    "time": {
                        "arrival": "2021-08-27T13:25:38Z",
                        "departure": "2021-08-27T14:12:00Z"
                    },
                    "load": [
                        0
                    ],
                    "activities": [
                        {
                            "jobId": "job_2",
                            "type": "delivery"
                        }
                    ],
                    "distance": 49076
                },
                {
                    "location": {
                        "lat": 52.530971,
                        "lng": 13.384915
                    },
                    "time": {
                        "arrival": "2021-08-27T14:42:19Z",
                        "departure": "2021-08-27T14:42:19Z"
                    },
                    "load": [
                        0
                    ],
                    "activities": [
                        {
                            "jobId": "arrival",
                            "type": "arrival"
                        }
                    ],
                    "distance": 62484
                }
            ],
            "statistic": {
                "cost": 180.973,
                "distance": 63465,
                "duration": 17918,
                "times": {
                    "driving": 6897,
                    "serving": 4980,
                    "waiting": 4241,
                    "break": 1800
                }
            }
        }
    ]
}

From this solution we can see all the routine statistics for the tour like the total cost, distance, duration, and times including time for driving, serving, waiting, and time for the breaks. The shift breaks of the vehicles were considered and the tour was planned regarding those constraints.

Please note that currently breaks functionality is implemented as soft constraints, therefore in some cases, breaks can be skipped by the algorithm in favour of additional jobs (e.g. when inserting the break would lead to a significant increase in the amount of unassigned jobs).

results matching ""

    No results matching ""