The Vehicle Routing Problem with Pick-up and Delivering (VRPPD) is a VRP in which the possibility that customers return some commodities is contemplated. So in VRPPD it’s needed to take into account that the goods that customers return to the deliver vehicle must fit into it. This restriction make the planning problem more difficult and can lead to bad utilization of the vehicles capacities, increased travel distances or a need for more vehicles.

Hence, it is usually to consider restricted situations where all delivery demands start from the depot and all pick-up demands shall be brought back to the depot, so there are no interchanges of goods between the customers. Another alternative is relaxing the restriction that all customers have to be visited exactly once. Another usual simplification is to consider that every vehicle must deliver all the commodities before picking up any goods.

Objective

The objective is to minimize the vehicle fleet and the sum of travel time, with the restriction that the vehicle must have enough capacity for transporting the commodities to be delivered and those ones picked-up at customers for returning them to the depot.

Feasibility

A solution is feasible if the the total quantity assigned to each route does not exceed the capacity of the vehicle which services the route and the vehicle has enough capacity for picking-up the commodities at customers.

Formulation

The cost of a route is like in the case of VRP, with the additional restriction that a route is feasible if and only if it is delivery-feasible, pick-up-feasible, and load-feasible. First of all, we shall define ${p}$ as a vector of the customer’s pick-up demand.

• Delivery-feasible: this case means that the total amount of commodities to serve in a route must not exceed the vehicle’s capacity. Given a route ${R_{i} = \left\lbrace v_{0}, v_{1}, …, v_{m+1} \right\rbrace}$ and the vehicle assigned to it with capacity ${C}$, this constraint can be mathematically expressed by: ${C_{d}(v_k) \leq C}$ and ${C_{d}(v_{k+1}) > C}$; where ${C_{d}(v_{k})}$ is the total quantity of goods delivered to all customers of the path of a route that begins on ${v_{0}}$ (depot) and finish at ${v_{k}}$: ${C_{d}(v_{k}) = \sum_{v_{i} \in P(1,v_{k})} d_{i}}$. ${P(1,v_{k})}$ denotes the customers visited along the path from the depot until ${v_{k}}$, including customer ${v_{k}}$.
• Pick-up feasible: this constraints ensure that the vehicle has enough capacity to pick-up the goods of all the customers of the route. ${C_{p}(v_{k}) \leq C}$ and ${C_{p}(v_{k+1}) > C}$; where ${C_{p}(v_{k})}$ is the total quantity of goods picked-up from all customers along the path of a route up to and including node ${v_{k}}$, that is: ${C_{p}(v_{k}) = \sum_{v_{i} \in P(1,v_{k})} p_{i}}$.
• Load-feasible: the vehicle’s capacity can be violated at any node of the route. Such a violation will depend on the sequence of the customers. Let ${L(v_{k})}$ be the vehicle’s load just after leaving customer ${v_{k}}$. Assume that the vehicle leaves the depot with an initial load ${L(1) \leq C}$.Then the vehicle’s load at any point of the route is ${L(v_{k}) = C_{p}(v_{k}) + L(1) – C_{d}(i_{k})}$. The vehicle’s load given by this equation can exceed the vehicle’s capacity. This means that the path becomes infeasible because the vehicle can not perform service at next customer ${v_{k+1}}$ on the path. So a route is load feasible if ${L(v_{k}) \leq C}$ and ${L(v_{k+1} \gt C)}$.