The heterogeneous pickup and delivery problem with configurable vehicle capacity

Various forms of the pickup and delivery problem (PDP) have been studied extensively over the past decades. This paper introduces a new version of the heterogeneous PDP in which the capacity of each vehicle can be modified by reconfiguring its interior to satisfy different types of customer demands. The work was motivated by a daily route planning problem arising at a senior activity center. A fleet of configurable vans is available each day to transport participants to and from the center as well as to secondary facilities for rehabilitative and medical treatment. The number of participants and support equipment that a van can accommodate depends on how it is configured. The problem is modeled as a mixed‐integer program much the same way as a PDP but with side constraints that add another level of complexity. To find solutions, we developed a two‐phase heuristic that makes use of ideas from greedy randomized adaptive search procedures with multiple starts. In phase I, a set of good feasible solutions is constructed using a series of randomized procedures. A representative subset of those solutions is selected as candidates for improvement by solving a max diversity problem. In phase II, an adaptive large neighborhood search (ALNS) heuristic is used to find local optima by reconstructing portions of the feasible routes. Specialized removal and insertion heuristics were designed for this purpose. Also, a specialized route feasibility check with vehicle type reassignment is introduced to take full advantage of the heterogeneous nature of vehicles. The effectiveness of the proposed methodology is demonstrated by comparing the solutions it provided over a period of several weeks with those that were used in practice and derived manually. The analysis indicates that anywhere from 30% to 40% savings can be achieved with the multi‐start ALNS heuristic.