Integer Linear Programming Approach for the Personnel Shuttles Routing Problem in Yıldız Campus in Istanbul
DOI:
https://doi.org/10.31181/jscda11202326Keywords:
Vehicle routing problem, Personnel shuttle routing problem, School bus routing problem, Integer linear programming, Decision analyticsAbstract
The Vehicle Routing Problem (VRP) revolves around the challenge of determining optimal vehicle routes for a company to efficiently serve a specific number of customers while minimizing costs. The Personnel Shuttle Routing Problem (PSRP) is a specialized variation of the VRP which focuses on optimizing shuttle or transportation services for individuals or small groups in specific contexts like universities, institutions or corporate campuses. The PSRP is of interest mostly in developed countries as it can lead to improved transportation efficiency, reduced environmental impact, and enhanced passenger satisfaction. This article details an optimization study conducted to address the PSRP within Yildiz Technical University’s Yildiz campus in 2021. The primary objective is to identify routes that minimize travel distances while ensuring balanced service coverage, all while adhering to specific constraints. The optimization approach leverages Integer Linear Programming to formulate a mathematical decision model. Data and information pertinent to the problem were acquired through consultations with the Yildiz Technical University General Secretary Support Unit managers. The resulting decision model was implemented using the GAMS 34.3.0 software package as a decision analytic programme, and the problem was solved by splitting it into two parts, addressing the Anatolian and European sides of the campus separately. The study culminated in a notable achievement: a reduction of 10.88% in the travel distances associated with Yildiz campus personnel shuttle routes.
References
Asghari, M., & Al-e, S. M. J. M. (2021). Green vehicle routing problem: A state-of-the-art review. International Journal of Production Economics, 231, 107899. https://doi.org/10.1016/j.ijpe.2020.107899.
Ashtineh, H., & Pishvaee, M. S. (2019). Alternative fuel vehicle-routing problem: A life cycle analysis of transportation fuels. Journal of Cleaner Production, 219, 166-182. https://doi.org/10.1016/j.jclepro.2019.01.343.
Atmaca, E. (2012). Bir kargo şirketinde araç rotalama problemi ve uygulaması. Tübav Bilim Dergisi, 5(2), 12-27. https://dergipark.org.tr/tr/download/article-file/200962.
Bektaş, T. ve S. Elmastaş (2004). Okul Araç Rotalama Probleminin Tamsayılı Programlama ile Çözümü. 24. Yöneylem Araştırması /Endüstri Mühendisliği Ulusal Kongresi YA/EM’2004, 15 -18 Haziran, Gaziantep–Adana, 3. https://web.itu.edu.tr/~celebid/OPT_files/AR.pdf.
Bektaş, T., & Elmastaş, S. (2007). Solving school bus routing problems through integer programming. Journal of the operational Research Society, 58(12), 1599-1604. https://doi.org/10.1057/palgrave.jors.2602305.
Bektaş, T., & Laporte, G. (2011). The pollution-routing problem. Transportation Research Part B: Methodological, 45(8), 1232-1250. https://doi.org/10.1016/j.trb.2011.02.004.
Bowerman, R., Hall, B., & Calamai, P. (1995). A multi-objective optimization approach to urban school bus routing: Formulation and solution method. Transportation Research Part A: Policy and Practice, 29(2), 107-123. https://doi.org/10.1016/0965-8564(94)E0006-U.
Christofides, N., Mingozzi, A., & Toth, P. (1981). Exact algorithms for the vehicle routing problem, based on spanning tree and shortest path relaxations. Mathematical programming, 20, 255-282. https://doi.org/10.1007/BF01589353.
Christofides, N., Mingozzi, A., & Toth, P. (1981). State‐space relaxation procedures for the computation of bounds to routing problems. Networks, 11(2), 145-164. https://doi.org/10.1002/net.3230110207.
Clarke, G., & Wright, J. W. (1964). Scheduling of vehicles from a central depot to a number of delivery points. Operations research, 12(4), 568-581. https://doi.org/10.1287/opre.12.4.568.
Dantzig, G. B., & Ramser, J. H. (1959). The Truck Dispatching Problem. Management Science, 6(1), 80–91. https://doi.org/10.1287/mnsc.6.1.80.
Dethloff, J. (2001). Vehicle routing and reverse logistics: The vehicle routing problem with simultaneous delivery and pick-up: Fahrzeugeinsatzplanung und Redistribution: Tourenplanung mit simultaner Auslieferung und Rückholung. OR-spektrum, 23, 79-96. https://doi.org/10.1007/PL00013346.
Düzakın, E., & Demircioğlu, M. (2009). Araç rotalama problemleri ve çözüm yöntemleri. Çukurova Üniversitesi İktisadi ve İdari Bilimler Fakültesi Dergisi, 13(1), 68-87. https://dergipark.org.tr/tr/pub/cuiibfd/issue/4151/54476.
Laporte, G., & Nobert, Y. (1987). Exact algorithms for the vehicle routing problem. In North-Holland mathematics studies (Vol. 132, pp. 147-184). North-Holland. https://doi.org/10.1016/S0304-0208(08)73235-3.
Laporte, G., & Osman, I. H. (1995). Routing problems: A bibliography. Annals of operations research, 61, 227-262. https://doi.org/10.1007/bf02098290.
Laporte, G., Desrochers, M., & Nobert, Y. (1984). Two exact algorithms for the distance‐constrained vehicle routing problem. Networks, 14(1), 161-172. https://doi.org/10.1002/net.3230140113.
Laporte, G., Toth, P., & Vigo, D. (2013). Vehicle routing: historical perspective and recent contributions. EURO Journal on Transportation and Logistics, 2, 1-4. https://doi.org/10.1007/s13676-013-0020-6.
Lekburapa, A., Boonperm, A. A., & Sintunavarat, W. (2021). A new integer programming model for solving a school bus routing problem with the student assignment. In Intelligent Computing and Optimization: Proceedings of the 3rd International Conference on Intelligent Computing and Optimization 2020 (ICO 2020) (pp. 287-296). Springer International Publishing. https://doi.org/10.1007/978-3-030-68154-8_28.
Li, L. Y., & Fu, Z. (2002). The school bus routing problem: a case study. Journal of the Operational Research Society, 53, 552-558. https://doi.org/10.1057/palgrave.jors.2601341.
Lin, C., Choy, K. L., Ho, G. T., Chung, S. H., & Lam, H. Y. (2014). Survey of green vehicle routing problem: past and future trends. Expert systems with applications, 41(4), 1118-1138. https://doi.org/10.1016/j.eswa.2013.07.107.
Moghdani, R., Salimifard, K., Demir, E., & Benyettou, A. (2021). The green vehicle routing problem: A systematic literature review. Journal of Cleaner Production, 279, 123691. https://doi.org/10.1016/j.jclepro.2020.123691.
Özkök, B. A., & Kurul, F. C. (2014). Araç rotalama problemine tam sayılı lineer programlama modeli ve gıda sektöründe bir uygulama. Istanbul University Journal of the School of Business Administration, 43(2). https://dergipark.org.tr/tr/download/article-file/98210
Palmer, A. (2007). The development of an integrated routing and carbon dioxide emissions model for goods vehicles, Doctoral Thesis. https://dspace.lib.cranfield.ac.uk/handle/1826/2547.
Schittekat, P., Sevaux, M., & Sorensen, K. (2006, October). A mathematical formulation for a school bus routing problem. In 2006 international conference on service systems and service management (Vol. 2, pp. 1552-1557). IEEE. https://doi.org/10.1109/ICSSSM.2006.320767.
Uzumer, E., & Tamer, E. R. E. N. (2012). Okul servisi rotalama problemi: bir uygulama. International Journal of Engineering Research and Development, 4(2), 26-29. https://dergipark.org.tr/tr/pub/umagd/issue/31724/346034.
Xiao, Y., Zuo, X., Huang, J., Konak, A., & Xu, Y. (2020). The continuous pollution routing problem. Applied Mathematics and Computation, 387, 125072. https://doi.org/10.1016/j.amc.2020.125072.
Yuan, Y., Cattaruzza, D., Ogier, M., & Semet, F. (2020). A note on the lifted Miller–Tucker–Zemlin subtour elimination constraints for routing problems with time windows. Operations Research Letters, 48(2), 167-169. https://doi.org/10.1016/j.orl.2020.01.008.
Downloads
Published
Issue
Section
License
Copyright (c) 2023 Journal of Soft Computing and Decision Analytics
This work is licensed under a Creative Commons Attribution 4.0 International License.