We consider the pickup and delivery problem where each customer is associated with two demands of goods, one pickup demand and one delivery demand. All pickup demands are to be collected and brought back to the depot and all delivery demands start from the depot. The vehicle’s capacity is limited and must not be exceeded. We allow customers to be visited one or two times. Hence, the two services may be performed simultaneously or non-simultaneously. If a customer is visited twice, the delivery service is performed on the first visit and the pickup service on the second. The consequence is that the final feasible solution can take many shapes, not only the classical Hamiltonian cycle. Examples show that these solutions can be better than the classical ones. We investigate different modifications of some known heuristics to construct feasible solutions to the described pickup and delivery problem.

The dynamic pickup and delivery problem with time windows arises in courier companies making same-day pickup and delivery of letters and small parcels. In this problem solution quality is affected by the way waiting time is distributed along vehicle routes. Four waiting strategies will be introduced and compared. Computational results will be presented.