Districting for parcel delivery services – A two-Stage solution approach and a real-World case study. (October 2020)

• Record Type: Journal Article
• Authors: Bender, Matthias; Kalcsics, Jörg; Meyer, Anne
• Is Part Of: Omega. Volume 96(2020)
• Publication Date: 2020-10
• Subjects: Districting -- Tactical design -- Operational adaptation -- Real-world case study -- Parcel delivery; Management -- Periodicals; 658.4005
• DOI: 10.1016/j.omega.2020.102283
• Languages: English
• ISSNs: 0305-0483

Abstract

Highlights: We propose a novel two-stage solution approach for the assignment of drivers and vehicles to customers that relies on districting instead of vehicle routing techniques and allows for daily adaptations, thereby merging the two most common solution approaches. For the tactical planning level on the first stage, we propose a districting approach that involves the determination of the number of districts and the assignment of heterogeneous resources. This combination has, to the best of our knowledge, not been considered in the districting literature before. We present three integer programming (IP) models for the tactical planning problem, which differ in the level of detail of their input data and in their expected compliance with the drivers' contractual working times. Moreover, we present a heuristic solution procedure for the tactical problem. For the operational level on the second stage, we propose a mixed integer programming model that adapts the tactical districting solution to the concrete demand realization of a day. We perform an extensive case study based on real-world data, to test the effectiveness of our districting based approach. In particular, we analyze the feasibility of using districting approaches for the problem at hand and the suitability of the three tactical planning models, and we investigate the trade-off between compliance with the drivers' contractual working times and service consistency. Abstract: This paper studies a real-world problem arising in the context of parcel delivery. Given a heterogeneous set of resources, i.e., different drivers and different vehicles, the problem for each day consists of assigning a driver and a vehicle to each customer requiring service. Two conflicting aspects must be taken into account. On the one hand, service consistency is desirable, meaning that a customer should always be served by the same driver. On the other hand, daily demand fluctuations and tight resource constraints prohibit fixed resource assignments. With the aim of finding a reasonable compromise between these aspects, we propose a novel two-stage districting approach, which establishes delivery districts in the first stage and adapts them to the daily demand realizations in the second stage. For the first stage problem we propose three models that differ in the level of detail of their input data, their expected compliance with service consistency and the driver's contractual working times, and their computational effort. Our two-stage approach merges the two dominant approaches in the literature, which either determine a priori routes and then adapt them on a daily basis, or derive fixed service regions for drivers. We present a case study based on a real-world data set. The results highlight the differences between the three first stage models and show that only few adaptations of the districts are necessary in the second stage to achieve feasible daily delivery tours along with a very good workload balance for drivers. We also analyze the effects of a homogeneous vs a heterogeneous fleet, of full time drivers vs full and part time drivers, and of the location of the depot and the length of the planning horizon.