Minimizing Indirect Contacts in Urban Pick-Up and Delivery Services During COVID-19 Pandemic

COVID-19 has had a significant impact on urban pick-up and delivery services, including meal delivery and online ride-hailing. In this article, we propose a decision framework for minimizing the indirect contact in pick-up and delivery services as a way to control the cost of precautionary measures, manage the risk of resurgence, and contain the spread of COVID-19. We present integer linear programming models of the order assignment and vehicle routing problems to minimize indirect contact as well as its extension with multiple objectives. We prove that the problem is NP-hard even with a fixed number of drivers, but polynomial under two special cases that are commonly seen in real-life situations. Exact methods with dominance rules and a heuristic algorithm for the dynamic problem are proposed. We conducted an extensive numerical study on real-world meal delivery data. Apart from the computational advancement of our algorithms, the experimental results also show that minimizing indirect contact does not significantly increase the transportation cost and is applicable to the vehicle routing system of service providers.