VRP with Multiple Shifts and Breaks

Specifying the time windows for the jobs and shift times and breaks for the fleet can be combined and used in a more precise and advanced way building the VRPs with multiple shifts and breaks. It means that vehicles' shifts and breaks and the jobs’ execution time can be specified separately for the different days in a single problem. For example, we need to execute several deliveries or pickups within one week or some other period of time. We assume that in our fleet we have vehicles that have some specific shift and break time which is different for the different days of the week. One way to solve such problems is to build separate problems each time specifying your constraints for the vehicles for each day separately. The Tour Planning API allows you to specify such constraints in one problem for the whole week or some other time period of your choice.

Let's consider a situation when we need to execute 10 jobs within 3 days by a vehicle that has different time shifts during those days. In this case, we should not only specify the vehicle’s shifts time but also the dates for those shifts.

In our specific case, the vehicle is available:

  • from 8:00 to 21:00 on October 23
  • from 8:00 to 15:00 on October 24
  • from 10:00 to 21:00 on October 25 (with a break from 12:03 to 13:03)

So the shifts and the breaks will be specified depending on the exact dates. The same approach will be applied for specifying the jobs' time windows - additionally to the time, we should specify the date if we need those jobs to be executed on the specific dates.

Considering those constraints, our problem will look as follows:

{
    "fleet": {
        "types": [
            {
                "id": "Vehicle_1",
                "profile": "car",
                "costs": {
                    "fixed": 10.0,
                    "distance": 0.002,
                    "time": 0.003
                },
                "shifts": [
                    {
                        "start": {
                            "time": "2021-10-23T08:00:00Z",
                            "location": {
                                "lat": 51.059188,
                                "lng": 13.540317
                            }
                        },
                        "end": {
                            "time": "2021-10-23T21:00:00Z",
                            "location": {
                                "lat": 51.059188,
                                "lng": 13.540317
                            }
                        }
                    },
                    {
                        "start": {
                            "time": "2021-10-24T08:00:00Z",
                            "location": {
                                "lat": 51.059188,
                                "lng": 13.540317
                            }
                        },
                        "end": {
                            "time": "2021-10-24T21:15:00Z",
                            "location": {
                                "lat": 51.059188,
                                "lng": 13.540317
                            }
                        }
                    },
                    {
                        "start": {
                            "time": "2021-10-25T10:00:00Z",
                            "location": {
                                "lat": 51.059188,
                                "lng": 13.540317
                            }
                        },
                        "end": {
                            "time": "2021-10-25T21:00:00Z",
                            "location": {
                                "lat": 51.059188,
                                "lng": 13.540317
                            }
                        },
                        "breaks": [
                          {
                              "duration": 1800,
                              "times": [
                                [
                                    "2021-10-25T12:03:00Z",
                                    "2021-10-25T13:03:00Z"
                            ]
                          ]
                       }
                     ]
                  }
                ],
                "capacity": [
                    10
                ],
                "amount": 1
            }
        ],
        "profiles": [
            {
                "type": "car",
                "name": "car"
            }
        ]
    },
    "plan": {
        "jobs": [
            {
                "id": "Job_1",
                "tasks": {
                    "pickups": [
                        {
                            "places": [
                                {
                                    "times": [
                                        [
                                            "2021-10-23T08:30:00Z",
                                            "2021-10-23T09:00:00Z"
                                        ]
                                    ],
                                    "location": {
                                        "lat": 51.05238,
                                        "lng": 13.74114
                                    },
                                    "duration": 1350
                                }
                            ],
                            "demand": [
                                1
                            ]
                        }
                    ]
                }
            },
            {
                "id": "Job_2",
                "tasks": {
                    "pickups": [
                        {
                            "places": [
                                {
                                    "times": [
                                        [
                                            "2021-10-23T09:05:00Z",
                                            "2021-10-23T09:30:00Z"
                                        ]
                                    ],
                                    "location": {
                                        "lat": 51.06099,
                                        "lng": 13.75245
                                    },
                                    "duration": 1350
                                }
                            ],
                            "demand": [
                                1
                            ]
                        }
                    ]
                }
            },
            {
                "id": "Job_3",
                "tasks": {
                    "pickups": [
                        {
                            "places": [
                                {
                                    "times": [
                                        [
                                            "2021-10-23T09:35:00Z",
                                            "2021-10-23T10:00:00Z"
                                        ]
                                    ],
                                    "location": {
                                        "lat": 51.08511,
                                        "lng": 13.76875
                                    },
                                    "duration": 1350
                                }
                            ],
                            "demand": [
                                1
                            ]
                        }
                    ]
                }
            },
            {
                "id": "Job_4",
                "tasks": {
                    "pickups": [
                        {
                            "places": [
                                {
                                    "times": [
                                        [
                                            "2021-10-23T10:05:00Z",
                                            "2021-10-23T10:30:00Z"
                                        ]
                                    ],
                                    "location": {
                                        "lat": 51.1323847,
                                        "lng": 13.7779515
                                    },
                                    "duration": 1350
                                }
                            ],
                            "demand": [
                                1
                            ]
                        }
                    ]
                }
            },
            {
                "id": "Job_5",
                "tasks": {
                    "pickups": [
                        {
                            "places": [
                                {
                                    "times": [
                                        [
                                            "2021-10-23T10:35:00Z",
                                            "2021-10-23T11:00:00Z"
                                        ]
                                    ],
                                    "location": {
                                        "lat": 51.11716,
                                        "lng": 13.73054
                                    },
                                    "duration": 1350
                                }
                            ],
                            "demand": [
                                1
                            ]
                        }
                    ]
                }
            },
            {
                "id": "Job_6",
                "tasks": {
                    "deliveries": [
                        {
                            "places": [
                                {
                                    "times": [
                                        [
                                            "2021-10-24T15:01:00Z",
                                            "2021-10-24T15:30:00Z"
                                        ]
                                    ],
                                    "location": {
                                        "lat": 51.12308,
                                        "lng": 13.76406
                                    },
                                    "duration": 1350
                                }
                            ],
                            "demand": [
                                1
                            ]
                        }
                    ]
                }
            },
            {
                "id": "Job_7",
                "tasks": {
                    "deliveries": [
                        {
                            "places": [
                                {
                                    "times": [
                                        [
                                            "2021-10-24T15:35:00Z",
                                            "2021-10-24T16:05:00Z"
                                        ]
                                    ],
                                    "location": {
                                        "lat": 51.08588,
                                        "lng": 13.72637
                                    },
                                    "duration": 1350
                                }
                            ],
                            "demand": [
                                1
                            ]
                        }
                    ]
                }
            },
            {
                "id": "Job_8",
                "tasks": {
                    "deliveries": [
                        {
                            "places": [
                                {
                                    "times": [
                                        [
                                            "2021-10-24T16:10:00Z",
                                            "2021-10-24T16:40:00Z"
                                        ]
                                    ],
                                    "location": {
                                        "lat": 51.08588,
                                        "lng": 13.72637
                                    },
                                    "duration": 1350
                                }
                            ],
                            "demand": [
                                1
                            ]
                        }
                    ]
                }
            },
            {
                "id": "Job_9",
                "tasks": {
                    "deliveries": [
                        {
                            "places": [
                                {
                                    "times": [
                                        [
                                            "2021-10-25T16:45:00Z",
                                            "2021-10-25T17:10:00Z"
                                        ]
                                    ],
                                    "location": {
                                        "lat": 51.08588,
                                        "lng": 13.72637
                                    },
                                    "duration": 1350
                                }
                            ],
                            "demand": [
                                1
                            ]
                        }
                    ]
                }
            },
            {
                "id": "Job_10",
                "tasks": {
                    "deliveries": [
                        {
                            "places": [
                                {
                                    "times": [
                                        [
                                            "2021-10-25T17:15:00Z",
                                            "2021-10-25T17:40:00Z"
                                        ]
                                    ],
                                    "location": {
                                        "lat": 51.06866,
                                        "lng": 13.77273
                                    },
                                    "duration": 1350
                                }
                            ],
                            "demand": [
                                1
                            ]
                        }
                    ]
                }
            }
        ]
    }
}

The solution for such a problem will look as follows:

{
    "statistic": {
        "cost": 409.245,
        "distance": 154890,
        "duration": 23155,
        "times": {
            "driving": 9655,
            "serving": 13500,
            "waiting": 0,
            "break": 0
        }
    },
    "tours": [
        {
            "vehicleId": "Vehicle_1_1",
            "typeId": "Vehicle_1",
            "stops": [
                {
                    "location": {
                        "lat": 51.059188,
                        "lng": 13.540317
                    },
                    "time": {
                        "arrival": "2021-10-25T10:00:00Z",
                        "departure": "2021-10-25T16:29:01Z"
                    },
                    "load": [
                        2
                    ],
                    "activities": [
                        {
                            "jobId": "departure",
                            "type": "departure"
                        }
                    ]
                },
                {
                    "location": {
                        "lat": 51.08588,
                        "lng": 13.72637
                    },
                    "time": {
                        "arrival": "2021-10-25T16:45:00Z",
                        "departure": "2021-10-25T17:07:30Z"
                    },
                    "load": [
                        1
                    ],
                    "activities": [
                        {
                            "jobId": "Job_9",
                            "type": "delivery"
                        }
                    ]
                },
                {
                    "location": {
                        "lat": 51.06866,
                        "lng": 13.77273
                    },
                    "time": {
                        "arrival": "2021-10-25T17:16:46Z",
                        "departure": "2021-10-25T17:39:16Z"
                    },
                    "load": [
                        0
                    ],
                    "activities": [
                        {
                            "jobId": "Job_10",
                            "type": "delivery"
                        }
                    ]
                },
                {
                    "location": {
                        "lat": 51.059188,
                        "lng": 13.540317
                    },
                    "time": {
                        "arrival": "2021-10-25T18:01:38Z",
                        "departure": "2021-10-25T18:01:38Z"
                    },
                    "load": [
                        0
                    ],
                    "activities": [
                        {
                            "jobId": "arrival",
                            "type": "arrival"
                        }
                    ]
                }
            ],
            "statistic": {
                "cost": 121.99099999999999,
                "distance": 47660,
                "duration": 5557,
                "times": {
                    "driving": 2857,
                    "serving": 2700,
                    "waiting": 0,
                    "break": 0
                }
            },
            "shiftIndex": 2
        },
        {
            "vehicleId": "Vehicle_1_1",
            "typeId": "Vehicle_1",
            "stops": [
                {
                    "location": {
                        "lat": 51.059188,
                        "lng": 13.540317
                    },
                    "time": {
                        "arrival": "2021-10-23T08:00:00Z",
                        "departure": "2021-10-23T08:15:25Z"
                    },
                    "load": [
                        0
                    ],
                    "activities": [
                        {
                            "jobId": "departure",
                            "type": "departure"
                        }
                    ]
                },
                {
                    "location": {
                        "lat": 51.05238,
                        "lng": 13.74114
                    },
                    "time": {
                        "arrival": "2021-10-23T08:37:14Z",
                        "departure": "2021-10-23T08:59:44Z"
                    },
                    "load": [
                        1
                    ],
                    "activities": [
                        {
                            "jobId": "Job_1",
                            "type": "pickup"
                        }
                    ]
                },
                {
                    "location": {
                        "lat": 51.06099,
                        "lng": 13.75245
                    },
                    "time": {
                        "arrival": "2021-10-23T09:05:00Z",
                        "departure": "2021-10-23T09:27:30Z"
                    },
                    "load": [
                        2
                    ],
                    "activities": [
                        {
                            "jobId": "Job_2",
                            "type": "pickup"
                        }
                    ]
                },
                {
                    "location": {
                        "lat": 51.08511,
                        "lng": 13.76875
                    },
                    "time": {
                        "arrival": "2021-10-23T09:35:29Z",
                        "departure": "2021-10-23T09:57:59Z"
                    },
                    "load": [
                        3
                    ],
                    "activities": [
                        {
                            "jobId": "Job_3",
                            "type": "pickup"
                        }
                    ]
                },
                {
                    "location": {
                        "lat": 51.1323847,
                        "lng": 13.7779515
                    },
                    "time": {
                        "arrival": "2021-10-23T10:08:25Z",
                        "departure": "2021-10-23T10:30:55Z"
                    },
                    "load": [
                        4
                    ],
                    "activities": [
                        {
                            "jobId": "Job_4",
                            "type": "pickup"
                        }
                    ]
                },
                {
                    "location": {
                        "lat": 51.11716,
                        "lng": 13.73054
                    },
                    "time": {
                        "arrival": "2021-10-23T10:38:39Z",
                        "departure": "2021-10-23T11:01:09Z"
                    },
                    "load": [
                        5
                    ],
                    "activities": [
                        {
                            "jobId": "Job_5",
                            "type": "pickup"
                        }
                    ]
                },
                {
                    "location": {
                        "lat": 51.059188,
                        "lng": 13.540317
                    },
                    "time": {
                        "arrival": "2021-10-23T11:15:31Z",
                        "departure": "2021-10-23T11:15:31Z"
                    },
                    "load": [
                        0
                    ],
                    "activities": [
                        {
                            "jobId": "arrival",
                            "type": "arrival"
                        }
                    ]
                }
            ],
            "statistic": {
                "cost": 156.35999999999999,
                "distance": 56971,
                "duration": 10806,
                "times": {
                    "driving": 4056,
                    "serving": 6750,
                    "waiting": 0,
                    "break": 0
                }
            },
            "shiftIndex": 0
        },
        {
            "vehicleId": "Vehicle_1_1",
            "typeId": "Vehicle_1",
            "stops": [
                {
                    "location": {
                        "lat": 51.059188,
                        "lng": 13.540317
                    },
                    "time": {
                        "arrival": "2021-10-24T08:00:00Z",
                        "departure": "2021-10-24T14:54:46Z"
                    },
                    "load": [
                        3
                    ],
                    "activities": [
                        {
                            "jobId": "departure",
                            "type": "departure"
                        }
                    ]
                },
                {
                    "location": {
                        "lat": 51.12308,
                        "lng": 13.76406
                    },
                    "time": {
                        "arrival": "2021-10-24T15:15:22Z",
                        "departure": "2021-10-24T15:37:52Z"
                    },
                    "load": [
                        2
                    ],
                    "activities": [
                        {
                            "jobId": "Job_6",
                            "type": "delivery"
                        }
                    ]
                },
                {
                    "location": {
                        "lat": 51.08588,
                        "lng": 13.72637
                    },
                    "time": {
                        "arrival": "2021-10-24T15:47:30Z",
                        "departure": "2021-10-24T16:32:30Z"
                    },
                    "load": [
                        0
                    ],
                    "activities": [
                        {
                            "jobId": "Job_7",
                            "type": "delivery",
                            "location": {
                                "lat": 51.08588,
                                "lng": 13.72637
                            },
                            "time": {
                                "start": "2021-10-24T15:47:30Z",
                                "end": "2021-10-24T16:10:00Z"
                            }
                        },
                        {
                            "jobId": "Job_8",
                            "type": "delivery",
                            "location": {
                                "lat": 51.08588,
                                "lng": 13.72637
                            },
                            "time": {
                                "start": "2021-10-24T16:10:00Z",
                                "end": "2021-10-24T16:32:30Z"
                            }
                        }
                    ]
                },
                {
                    "location": {
                        "lat": 51.059188,
                        "lng": 13.540317
                    },
                    "time": {
                        "arrival": "2021-10-24T16:47:58Z",
                        "departure": "2021-10-24T16:47:58Z"
                    },
                    "load": [
                        0
                    ],
                    "activities": [
                        {
                            "jobId": "arrival",
                            "type": "arrival"
                        }
                    ]
                }
            ],
            "statistic": {
                "cost": 130.89399999999998,
                "distance": 50259,
                "duration": 6792,
                "times": {
                    "driving": 2742,
                    "serving": 4050,
                    "waiting": 0,
                    "break": 0
                }
            },
            "shiftIndex": 1
        }
    ]
}

From this solution, we can see that the tour was optimized for solving the specific jobs considering their dates and time windows, and vehicle's shifts' schedule within those dates.

  • jobs_9 and job_10 will be executed on October 25
  • job_1, job_2, job_3, job_4, and job_5 - on October 23
  • job_6 job_7 job_8 - on october 24

In the same way, you can plan your tours for any other non-overlapping time periods, up to 7.

results matching ""

    No results matching ""