REGIONAL DISTRIBUTION PLANNING IN POSTAL SERVICES: A CAPACITYCONSTRAINED P-MEDIAN AND VEHICLE ROUTING APPROACH

Öz

Efficient planning of daily deliveries to hundreds of addresses in postal services is of critical importance for reducing logistics costs and improving service quality. In this study, a distribution area is divided into eight regions using a capacity-constrained p-median modelbased regional clustering approach, assuming that each region is served by a vehicle with a capacity of 8 m³. Using point-based real delivery data (geographical locations, letter and parcel volumes) together with the inter-point distance matrix, eight median locations and their corresponding clusters are obtained through optimization using the CBC (Coin-or Branch-and-Cut) solver. As a result of the clustering process, the total delivery volume in each region is balanced so as not to exceed the 8 m³ vehicle capacity constraint. Subsequently, a Vehicle Routing Problem (VRP) is formulated for each region, and the shortest delivery routes are determined using the Google OR-Tools library. The results indicate that a total of 1,220 delivery points are assigned to eight regions, with regional delivery volumes ranging between approximately 3.45 and 7.90 m³, and route lengths for each vehicle varying between approximately 11.5 and 20.3 km. The proposed approach is further analyzed by visualizing the regions on a map and presenting representative delivery routes. The findings demonstrate that the capacity-constrained p-median approach effectively distributes the workload of postal delivery services across regions and enhances overall distribution efficiency through optimized routing within each region. Finally, potential field applications of the proposed method and directions for future improvements are discussed.

Anahtar Kelimeler

• Postal Services
• Vehicle Routing Problem
• Postal Distribution
• Linear Programming

POSTA HİZMETLERİNDE BÖLGESEL DAĞITIM PLANLAMASI: KAPASİTE KISITLI PMEDYAN VE ARAÇ ROTALAMA YAKLAŞIMI

Öz

Posta hizmetlerinde günlük olarak yüzlerce adrese yapılan teslimatların etkin biçimde planlanması, lojistik maliyetlerin azaltılması ve hizmet kalitesinin artırılması açısından kritik öneme sahiptir. Bu çalışmada, bir dağıtım alanı kapasite kısıtlamalı p-medyan modeli temelli bölgesel kümeleme yaklaşımı kullanılarak 8 bölgeye ayrılmış ve her bir bölgenin 8 m³ kapasiteli bir araç tarafından hizmet alacağı varsayılmıştır. Çalışmada nokta tabanlı gerçek teslimat verileri (coğrafi konumlar, mektup ve kargo hacimleri) ile noktalar arasındaki mesafe matrisi kullanılmış; CBC (Coin-or Branch-and-Cut) çözücüsü aracılığıyla gerçekleştirilen optimizasyon sonucunda 8 adet medyan nokta ve bu noktalara atanan kümeler elde edilmiştir. Kümeleme sonucunda her bölgedeki toplam teslimat hacmi, araç kapasitesi olan 8 m³’ü aşmayacak şekilde dengelenmiştir. Bunu takiben, her bölge için ayrı ayrı Araç Rotalama Problemi (VRP) modellenmiş ve Google OR-Tools kütüphanesi kullanılarak en kısa teslimat rotaları hesaplanmıştır. Elde edilen sonuçlar, toplam 1220 teslimat noktasının 8 bölgeye ayrıldığını; bölgesel teslimat hacimlerinin yaklaşık 3,45–7,90 m³, araç rota uzunluklarının ise yaklaşık 11,5–20,3 km aralığında değiştiğini göstermektedir. Yöntem, bölgelerin harita üzerinde görselleştirilmesi ve örnek rotaların sunulması yoluyla analiz edilmiştir. Bulgular, kapasite kısıtlamalı p-medyan yaklaşımının posta dağıtımında iş yükünü bölgeler arasında dengeli biçimde paylaştırabildiğini ve her bölge içinde optimize edilmiş rotalar sayesinde genel dağıtım verimliliğini artırdığını ortaya koymaktadır. Son bölümde ise yöntemin saha uygulamaları ve gelecekte yapılabilecek iyileştirmelere ilişkin değerlendirmelere yer verilmiştir.

Anahtar Kelimeler

• Posta Hizmetleri
• Araç Rotalama Problemi
• Posta Dağıtımı
• Doğrusal Programlama

Kaynakça

1. Akdoğan, B., Fidan, E. M., & Özbakır, L. (2022). Yerleştirme-rotalama problemi için iki aşamalı bir model: Covid-19 aşılarının dağıtımı. Pamukkale Üniversitesi Mühendislik Bilimleri Dergisi, 28(4), 559-568.
2. Altundaş, A. (2024). An integrated approach for ammunition depot location selection and ammunition distribution network design based on P-median and vehicle routing problems. Container and Modular Design, 1. https://doi.org/10.59543/comdem.v1i.10539
3. Baytur, B., Özceylan, E., Koç, Ç., & Erdoğan, G. (2024). Solving a large-scale multi-depot vehicle routing problem heuristically. In Optimization Essentials (pp. 669–693). Springer International Publishing.
4. Bozyer, Z., Alkan, A., & Fığlalı, A. (2014). Kapasite Kısıtlı Araç Rotalama Probleminin Çözümü için Önce Grupla Sonra Rotala Merkezli Sezgisel Algoritma Önerisi. Bilişim Teknolojileri Dergisi, 7(2), 29-37.
5. Church, R. L., Scaparra, M. P., & Middleton, R. S. (2004). Identifying critical infrastructure: The median and covering facility interdiction problems. Annals of the Association of American Geographers, 94(3), 491–502. https://doi.org/10.1111/j.1467-8306.2004.00410.x
6. Feld, S., Roch, C., Gabor, T., Seidel, C., Neukart, F., Galter, I., Mauerer, W., & Linnhoff-Popien, C. (2019). A hybrid solution method for the capacitated vehicle routing problem using quantum annealing. Frontiers in ICT, 6, 13. https://doi.org/10.3389/fict.2019.00013
7. Forrest, J., & Lougee-Heimer, R. (2005). CBC (Coin-OR branch-and-cut) solver user guide. Computational Infrastructure for Operations Research.
8. Huang, Y., Wang, X., Li, T., & Chen, H. (2022). The location selection of logistics center in city based on particle swarm optimization. Research Square. https://doi.org/10.21203/rs.3.rs-1964001/v1

9. Ji, P., & Chen, K. (2007). The vehicle routing problem: The case of the Hong Kong postal service. Transportation Planning and Technology, 30(2-3), 167–182. https://doi.org/10.1080/03081060701390841.
10. Kabiri, K., & Saadi Mesgari, M. (2017). Optimization of pick up and delivery problem of postal service between the centers by capacitated vehicles based on metaheuristic algorithms. Journal of Geomatics Science and Technology, 6(4), 173-184.
11. Karamahmutoğlu, F., & Tüzemen, A. (2025). Tarımsal gıda sektöründe zaman pencereli araç rotalama problemi: Taşköprü sarımsağı üzerine matematiksel modelleme örneği. Journal of Academic Opinion, 5(2), 66–81.
12. Lee, J. (2025). Capacitated location-routing problem for a combined manned-unmanned teaming system using Lagrangian relaxation and location-based heuristic. International Journal of Industrial Engineering: Theory, Applications and Practice, 32(5). https://doi.org/10.23055/ijietap.2025.32.5.10347
13. León Villalba, A. F., & González La Rotta, E. C. (2022). Solving the vehicle routing problem with time windows using clustering and heuristic algorithms. International Journal of Industrial Engineering Computations, 13(2), 165–184. https://doi.org/10.5267/j.ijiec.2021.12.002
14. Miao, B., Shang, X., & Sun, H. (2024). The optimization of the location-allocation problem of pallet pooling centers. In Proceedings of the Eleventh International Forum on Decision Sciences (pp. 1–12). Springer Nature.
15. Öncan, T. (2007). A survey of the generalized assignment problem and its applications. INFOR: Information Systems and Operational Research, 45(3), 123–141. https://doi.org/10.3138/infor.45.3.123
16. Perron, L., & Furnon, V. (2025). OR-Tools (Version 9.12) [Computer software]. Google. https://developers.google.com/optimization/
17. Rodney, D., Soper, A., & Walshaw, C. (2008). Multilevel approaches applied to the capacitated clustering problem. In Proceedings of the International Conference on Computational Science (ICCS) (pp. 271–277). Springer.
18. Sbai, I., Krichen, S., & Limam, O. (2022). Two meta-heuristics for solving the capacitated vehicle routing problem: the case of the Tunisian Post Office. Operational Research, 22(1), 507–549. https://doi.org/10.1007/s12351-019-00565-2
19. Şensu, Ş. E., Arslan, Z., Ekinci, R. D., & Tuzkaya, G. (2019). A vehicle routing model for postal service operations and an application. International Journal of Advanced Engineering and Pure Sciences, 31(4), 267–272. https://doi.org/10.7240/jeps.453159
20. Wikipedia contributors. (2025, February 15). OR-Tools. In Wikipedia, The Free Encyclopedia. Retrieved 08:21, March 24, 2025, from https://en.wikipedia.org/w/index.php?title=OR-Tools&oldid=1209039445
21. Yıldız, Ç., & Tüzemen, A. (2019). A solution proposal to vehicle routing problem with integer linear programming: A distributor company sample. International Journal of Contemporary Economics and Administrative Sciences, 9(1), 46–78. https://doi.org/10.5281/zenodo.3262231
22. Yüksel, Z., Epcim, D. E., & Mete, S. (2024). First cluster second route approach with collaboration unmanned aerial vehicle in post-disaster humanitarian logistic. Journal of Transportation and Logistics, 8(2), 97–111. https://doi.org/10.26650/JTL.2023.1372701