VRP with Pickup and Delivery

• Problem
• Solution

Sometimes it happens that a delivery company needs to pickup and deliver specific items or people along the route. In other words several goods need to be moved from certain pickup locations to other delivery locations. In such cases, we can use the VRP with Pickup and Delivery. The goal of such a VRP is to find optimal routes for a vehicle to visit the pickup and drop-off locations. Each job in such VRP is defined by a specific pickup point, a corresponding delivery point, and a demand to be transported between those locations. The concept of this type of VRP implies that the pickup demand is always equal to the delivery demand, otherwise the problem will not be solved correctly.

One example of implementing this kind of VRP in real life is the Dial-A-Ride service. Dial-A-Ride is an origin-to-destination advanced reservation transportation service for seniors and persons with disabilities. Dial-A-Ride vehicles travel within the specific areas on the local fixed route. The trips must begin and end in this service area. The idea of such a service is to pickup and deliver customers from point A to point B.

Let's consider a simple case where we need to pickup and deliver one item with one vehicle. The problem for such a case would look as follows:

Problem

{
  "fleet": {
    "types": [
      {
        "id": "b0130d2f754d",
        "profile": "car_1",
        "costs": {
          "fixed": 5.0,
          "distance": 0.007,
          "time": 0.02
        },
        "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
              }
            }
          }
        ],
        "capacity": [
          30
        ],
        "amount": 1
      }
    ],
    "profiles": [
      {
        "type": "car",
        "name": "car_1"
      }
    ]
  },
  "plan": {
    "jobs": [
      {
        "id": "job_1",
        "tasks": {
          "pickups": [
            {
              "places": [
                {
                  "location": {
                    "lat": 52.53090538774364,
                    "lng": 13.384692097156309
                  },
                  "duration": 840
                }
              ],
              "demand": [
                1
              ]
            }
          ],
          "deliveries": [
            {
              "places": [
                {
                  "location": {
                    "lat": 52.58919138279804,
                    "lng": 13.462161100698735
                  },
                  "duration": 1020
                }
              ],
              "demand": [
                1
              ]
            }
          ]
        }
      }
    ]
  }
}

Solution

The solution for this problem will be as follows:

{
    "statistic": {
        "cost": 249.22400000000002,
        "distance": 21832,
        "duration": 4570,
        "times": {
            "driving": 2710,
            "serving": 1860,
            "waiting": 0,
            "break": 0
        }
    },
    "tours": [
        {
            "vehicleId": "b0130d2f754d_1",
            "typeId": "b0130d2f754d",
            "stops": [
                {
                    "location": {
                        "lat": 52.530971,
                        "lng": 13.384915
                    },
                    "time": {
                        "arrival": "2021-08-27T08:03:00Z",
                        "departure": "2021-08-27T08:03:00Z"
                    },
                    "load": [
                        0
                    ],
                    "activities": [
                        {
                            "jobId": "departure",
                            "type": "departure"
                        }
                    ],
                    "distance": 0
                },
                {
                    "location": {
                        "lat": 52.53090538774364,
                        "lng": 13.384692097156307
                    },
                    "time": {
                        "arrival": "2021-08-27T08:03:02Z",
                        "departure": "2021-08-27T08:17:02Z"
                    },
                    "load": [
                        1
                    ],
                    "activities": [
                        {
                            "jobId": "job_1",
                            "type": "pickup"
                        }
                    ],
                    "distance": 17
                },
                {
                    "location": {
                        "lat": 52.58919138279804,
                        "lng": 13.462161100698737
                    },
                    "time": {
                        "arrival": "2021-08-27T08:39:07Z",
                        "departure": "2021-08-27T08:56:07Z"
                    },
                    "load": [
                        0
                    ],
                    "activities": [
                        {
                            "jobId": "job_1",
                            "type": "delivery"
                        }
                    ],
                    "distance": 10933
                },
                {
                    "location": {
                        "lat": 52.530971,
                        "lng": 13.384915
                    },
                    "time": {
                        "arrival": "2021-08-27T09:19:10Z",
                        "departure": "2021-08-27T09:19:10Z"
                    },
                    "load": [
                        0
                    ],
                    "activities": [
                        {
                            "jobId": "arrival",
                            "type": "arrival"
                        }
                    ],
                    "distance": 21831
                }
            ],
            "statistic": {
                "cost": 249.22400000000002,
                "distance": 21832,
                "duration": 4570,
                "times": {
                    "driving": 2710,
                    "serving": 1860,
                    "waiting": 0,
                    "break": 0
                }
            }
        }
    ]
}

From this solution, we can see the routine statistics for solving the problem including the total cost, distance, duration, etc., with the calculated route for pickup and delivery of our item considering the depot, pickup, and delivery locations.