The vehicle routing problem with heterogeneous locker boxes

Central European Journal of Operations Research - Tập 29 Số 1 - Trang 113-142 - 2021
Jasmin Grabenschweiger1, Karl F. Doerner1, Richard F. Hartl2, Martin W. P. Savelsbergh3
1Josef Ressel Center for Adaptive Optimization in Dynamic Environments, Department of Business Decisions and Analytics, University of Vienna, Vienna, Austria
2Department of Business Decisions and Analytics, University of Vienna, Vienna, Austria
3H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, USA

Tóm tắt

AbstractTo achieve logistic efficiency and customer convenience in last-mile delivery processes, a system with alternative delivery points in the form of locker box stations can be used. In such a system, customers can be served either at their home address within a certain time window, or at a locker box station where parcels can be picked up at any time. Customers can get a compensation payment when being served at a locker box. They can have a request of more than one parcel and the parcels can be of different sizes. At a locker box station, a limited number of slots of different sizes is available; we assume that parcels of one customer can be stored together in a slot. We consider the vehicle routing problem with heterogeneous locker boxes, where the total cost—consisting of routing and compensation costs—has to be minimized while taking into account the packing of parcels into locker boxes. We provide a mathematical formulation of the problem and propose a metaheuristic solution method. Instances and results from the literature for the problem with a single parcel and a single slot size are used to benchmark our metaheuristic solution method. For the problem with different sizes, we compare a unit-size model to a multi-size model, packing being considered in the latter. Finally, we analyze how different configurations of locker box stations work for different demand scenarios.

Từ khóa


Tài liệu tham khảo

Campbell AM, Savelsbergh M (2004) Efficient insertion heuristics for vehicle routing and scheduling problems. Transport Sci 38(3):369–378

Delorme M, Iori M (2020) Enhanced pseudo-polynomial formulations for bin packing and cutting stock problems. INFORMS J Comput 32(1):101–119

Friesen DK, Langston MA (1986) Variable sized bin packing. SIAM J Comput 15(1):222–230

Fuellerer G, Doerner KF, Hartl RF, Iori M (2009) Ant colony optimization for the two-dimensional loading vehicle routing problem. Comput Oper Res 36(3):655–673

Gendreau M, Laporte G, Semet F (2004) Heuristics and lower bounds for the bin packing problem with conflicts. Comput Oper Res 31(3):347–358

Grabenschweiger J, Doerner KF, Hartl RF, Savelsbergh MWP (2020) The vehicle routing problem with heterogeneous locker boxes (instances). Mendeley Data V1. https://doi.org/10.17632/8xrvghrkbn.1

Haouari M, Serairi M (2009) Heuristics for the variable sized bin-packing problem. Comput Oper Res 36(10):2877–2884

Hemmelmayr VC, Cordeau J-F, Crainic TG (2012) An adaptive large neighborhood search heuristic for two-echelon vehicle routing problems arising in city logistics. Comput Oper Res 39(12):3215–3228

Iori M, Salazar-González J-J, Vigo D (2007) An exact approach for the vehicle routing problem with two-dimensional loading constraints. Transport Sci 41(2):253–264

Jansen K (1999) An approximation scheme for bin packing with conflicts. J Comb Optim 3(4):363–377

Kang J, Park S (2003) Algorithms for the variable sized bin packing problem. Eur J Oper Res 147(2):365–372

Kovacs AA, Parragh SN, Doerner KF, Hartl RF (2012) Adaptive large neighborhood search for service technician routing and scheduling problems. J Sched 15(5):579–600

Lloyd S (1982) Least squares quantization in PCM. IEEE Trans Inf Theory 28(2):129–137

Mancini S, Gansterer M (2020a) VRP with private and shared delivery locations (instances). Mendeley Data V1. https://doi.org/10.17632/55x6z7r5bf.1

Mancini S, Gansterer M (2020b) VRP with private and shared delivery locations. Technical report, University of Klagenfurt, Department of Operations, Energy, and Environmental Management

Orenstein I, Raviv T, Sadan E (2019) Flexible parcel delivery to automated parcel lockers: models, solution methods and analysis. EURO J Transport Logist 8(5):683–711

Ortega EJA, Schilde M, Doerner KF (2020) Matheuristic search techniques for the consistent inventory routing problem with time windows and split deliveries. Oper Res Perspect 7:100–152

Reyes D, Savelsbergh M, Toriello A (2017) Vehicle routing with roaming delivery locations. Transport Res Part C Emerg Technol 80:71–91

Ropke S, Pisinger D (2006) An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transport Sci 40(4):455–472

Savelsbergh M, Van Woensel T (2016) 50th anniversary invited article—city logistics: challenges and opportunities. Transport Sci 50(2):579–590

Schwerdfeger S, Boysen N (2020) Optimizing the changing locations of mobile parcel lockers in last-mile distribution. Eur J Oper Res 285(3):1077–1094

Sitek P, Wikarek J (2019) Capacitated vehicle routing problem with pick-up and alternative delivery (CVRPPAD): model and implementation using hybrid approach. Ann Oper Res 273(1–2):257–277

Solomon MM (1987) Algorithms for the vehicle routing and scheduling problems with time window constraints. Oper Res 35(2):254–265

Zhou L, Baldacci R, Vigo D, Wang X (2018) A multi-depot two-echelon vehicle routing problem with delivery options arising in the last mile distribution. Eur J Oper Res 265(2):765–778

Thông tin
Thông tin xuất bản

Central European Journal of Operations Research

Tập 29 Số 1

113-142

Thông tin tác giả