VRP with Pick-Up and Delivering
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 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
and the vehicle assigned to it with capacity C, this constraint
can be mathematically expressed by: and ; where is the total quantity of goods delivered
to all customers of the path of a route that begins on (depot) and finish at : . denotes the customers visited along
the path from the depot until , including customer .
- Pick-up feasible:
this constraints ensure that the vehicle has enough capacity to pick-up
the goods of all the customers of the route. and ; where is the total quantity of goods picked-up
from all customers along the path of a route up to and including node
, that is: .
- 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 be the vehicle's load just after leaving
customer . Assume that the vehicle leaves the depot
with an initial load .Then the vehicle's load at any
point of the route is . 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 on the path. So a route is load feasible
if and .