The Single Commodity Pickup and Delivery Problem(1-PDP)
The Single Commodity Pickup and Delivery Problem (1-PDP) deals with supplying and collecting one type of commodity from a number of customers, some of them are designated as pickup customers and the others as delivery customers. Each pickup customer provides a certain amount of the commodity, while each delivery customer consumes a certain amount of the same commodity, i.e., the goods collected from pickup customers can be delivered to any delivery customer. All customers are served by one vehicle with a limited capacity, and the journey of the vehicle should start and end at a central depot. The depot can supply or consume any additional amount of the commodity that is not supplied or consumed by the customers. Our goal is to find a feasible and minimum cost route for the vehicle, such that all customers are served without violating the vehicle capacity constraint.
This problem has attracted our interest for several reasons. First, there are many applications for this problem in practice, for example, the commodity could be milk that should be collected from farms and delivered to factories with no restriction on the origin and the destination of the product, or it could be money that should be distributed between the branches of a bank. It can also model any
logistic situation in which some warehouses have an extra supply of some commodity, while others are in short of the same commodity. Second, the problem has not been adequately explored in the literature. Finally, there are other important problems in the literature that are closely related to the (1-PDP). For example, the Travelling Salesman Problem with Pickup and Delivery (TSPPD), is a related problem in which the commodity collected from the pickup customers is different from the commodity delivered to the delivery customers. The depot supplies all the amount needed by the delivery customers and receives all the amount supplied by the pickup customer, and both products must be accommodated in the vehicle without exceeding its capacity. An example of an application of this problem is when empty soft drink bottles are to be collected from homes or shops and delivered to the depot, and at the same time full bottles are to be supplied by the depot to be delivered to some customers. An interesting observation is that an algorithm that solves the 1-PDP can be used to solve the TSPPD, with only a small modification in the TSPPD problem instance
Since this problem is NP-hard, exact algorithms are only suitable for small problem sizes.
In this research we are trying to handle the 1-PDP using a technique based on `perturbation' of the problem instance. The idea is to introduce a small perturbation to the original problem instance P to transform it to a new instance P', for example by making a small change in the coordinates of the cities to be visited in the TSP. This will `fool' a local search heuristic, applied to a solution of the new instance P', into finding better solutions for the original instance, because a local optimum for the original instance is not necessarily a local optimum for the new transformed instance. The new solution is then evaluated relative to the original problem instance to possibly replace the initial solution.
Another technique we attempted in our research is Variable Neighbourhood Search (VNS) hybridized with Simulated Annealing (SA). The algorithm is distinguished by performing the VNS repeatedly, each time starting from the final solution obtained from the previous VNS run. Also, the algorithm isadaptive, in the sense that the maximum neighbourhood size allowed in each VNS run is not fixed and depends on the current stage of the search. Early runs are allowed to perform wider jumps in the solution space from the current solution, using large neighbourhood sizes. Later runs, on the other
hand, are only allowed smaller explorations of the search space, in the vicinity of the current solution, to maintain the solution quality. The stopping criterion for each VNS run is also adaptive
and depends on the improvement realized in the current solution. The basic VNS meta-heuristic systematically increases the neighbourhood size, within which the search is performed, up to a
pre-specified maximum size. In our approach, nevertheless, each VNS run is also terminated when a further increase in the neighbourhood size seems not beneficial, even if the maximum neighbourhood size was not reached. During each VNS run, an SA acceptance criterion is used to allow the algorithm to escape local optima and explore a wider area of the search space.
References and publications can be obtained here