The pickup and delivery problem with alternative locations and overlapping time windows

Online second-hand marketplaces have seen a vast increase in transactions in recent years, although sending and receiving parcels can be an inconvenience for private buyers and sellers in C2C settings. To facilitate transportation providers expanding their product portfolio with alternative concepts, we consider the pickup and delivery problem (PDP) with alternative locations and overlapping time windows. The transportation requests have to be served by a fleet of homogeneously capacitated vehicles. Each request may have multiple roaming pickup locations throughout the day with non-overlapping time windows (since the product cannot be in two places at once). A request may also have many roaming delivery locations, and additionally an alternative recipient with their own set of roaming locations. As such, several persons in different locations can be available simultaneously to accept a delivery. Recipients could also use 24-hour locker boxes if these are conveniently located. We propose a solution approach based on a multi-start, adaptive, large neighborhood search with problem specific operators, to solve the pickup and delivery problem with alternative locations. We compare our algorithm with similar problems from the literature and examine in detail different scenarios based on real data provided by an Austrian logistics provider. In particular, we explore the benefits of locker boxes, roaming locations, alternative recipients, and mixed customer profiles based on different preferences concerning data sharing and convenience. We found that an increase in flexibility and convenience for the customers translates into cost savings up to almost 30% for the carriers.