An adaptive large neighborhood search for the pickup and delivery problem with transfers

摘要

The pickup and delivery problem (PDP), an extension of the vehicle routing problem, (VRP) consists of defining a set of minimum cost routes in order to satisfy a set of transportation requests. Each transportation request has a known origin called the pickup point and a destination called the delivery point. Several users can share a vehicle as long as its capacity is not exceeded. The PDP is either static (request is known in advance), or in a dynamic version (new requests may be integrated at any time). If time windows on requests are considered, the problem is called the pickup and delivery problem with time windows (PDPTW). The problem varies in terms of transportation of goods or people and various objective functions. The research work considers a static case problem related to the transportation of people with disabilities and the objective function is to minimize the total distance traveled. It offers an extension of the PDPTW, called the pickup and delivery problem with transfers (PDPT), where requests can be transferred from one vehicle to another at intermediate points between the pickup and delivery points. The focus of the paper is to design a method of efficiently exploring the search space of the problem by relaxing few practical constraints. Therefore it considers a homogeneous fleet of vehicles and ride time is limited because of adequate time windows. New heuristics capable of efficiently inserting requests through transfer points have been proposed. These heuristics are embedded into an adaptive large neighborhood search (ALNS). The method was evaluated on generated instances and applied to the transportation of people with disabilities. In order to evaluate the potential output of transfers, solutions of the ALNS with and without considering transfer points were compared. Besides to provide a lower bound on the savings, a comparison is made between upper bounds of the PDPT solutions with lower bounds of PDPTW solutions. (30 refs.)