Vehicle routing with private and shared delivery locations

Abstract The rapid growth of e-commerce has led to an increase of home delivery requests. Providing efficient distribution systems for services on the last mile has become a challenging issue for logistics companies, where a trade-off between the classical approaches, attended home delivery (AHD) and usage of shared delivery locations (SDLs) has been identified. AHD provides a higher quality of service but implies very high costs for the company, while usage of SDL requires customers to perform the very last mile by themselves. For companies, this bears the risk of a decrease in the perceived service quality. However, due to consolidation effects, transportation costs can be considerably mitigated. We propose a mixed delivery approach, which combines AHD and SDL usage in an innovative way. Customers can either be served at home during their preferred time window, or they can be asked to pick up their parcel at one of the SDLs. For each customer served using an SDL, the company pays a compensation price in order to reduce the perceived decrease in service quality. The newly introduced decision problem is formulated mathematically. We propose two matheuristics to efficiently solve large instances. In an extensive numerical study, we show that the new approach clearly outperforms standard ones. We observe an increase in solution quality of up to 40%, while customers’ perceived quality of service is not affected. Additionally, the results reveal that the obtained improvements are robust for different customer-specific time-window preferences, accepted travel times needed to reach an SDL, and different compensation schemes.