Pickup and Delivery Problems with Handling Operations

In pickup and delivery problems, a fleet of vehicles based at a depot is used to complete a set of requests. A request consists of transporting goods from a specific pickup location, where the item is loaded, to a specific delivery location, where the item is unloaded. We consider rear-loaded vehicles that are operated in a last-in-first-out (LIFO) fashion. If a load must be unloaded that was not loaded last, additional handling operations are needed to unload and reload other loads that block access. These additional handling operations take time and effort, and therefore we take them into account when generating vehicle routes. We introduce two different problems. The first problem is the pickup and delivery traveling salesman problem with handling costs (PDTSPH). In this problem, we consider a single vehicle and associate penalty costs with the additional handling operations. The aim of the PDTSPH is to find a feasible route such that the total costs, consisting of travel costs and penalty costs, are minimized. We propose a large neighborhood search heuristic to solve the problem. We provide new best known solutions on benchmark instances for special cases of the problem. The second problem, which is called the pickup and delivery problem with time windows and handling operations (PDPTWH), considers a fleet of homogeneous vehicles of limited capacity, incorporates time windows and includes additional time for each handling operation. For the PDPTWH, we define two different policies for the additional handling operations. A branch-price-and-cut algorithm is developed for both policies. Computational results are reported on known instances for the pickup and delivery problem with time windows.  

Registration to the secretary's office of the econometric institute, eb-secr@ese.eur.nl, is required for availability of lunch.