Optimal Solution to the Capacitated Vehicle Routing Problem with Moving Shipment at the Cross-docking Terminal

Full Text (PDF, 438KB), PP.60-71

Author(s)

1. Department of Mathematics, the Open University of Sri Lanka, Nawala, Nugegoda, Sri Lanka

* Corresponding author.

Received: 12 Jul. 2022 / Revised: 8 Aug. 2022 / Accepted: 22 Aug. 2022 / Published: 8 Oct. 2022

Index Terms

Cross- docking, moving shipments, supply chain, vehicle routing

Abstract

An innovative and creative docking technique known as cross- docking (CD) strategy was initiated in 1930s to make supply chain fast and productive. However, it only became popular from 1980s. Vehicle routing between suppliers/customers to CD terminal (CDT) is one of operational level problems at CDT. Moreover, moving unloaded products from indoors to outdoors of CDT is one of the internal operations inside a CDT. The main difference between this study and the existing studies which find in the literature is that to consider the activities inside CDT. Also, loading or unloading shipments at all the nodes including CDT are taken into account. Moreover, homogenous fleets of vehicles within pickup or delivery process are assumed, but heterogeneous fleets of vehicles between pickup and delivery processes are assumed in this study. A mixed integer non-linear programming model is developed to address this problem. In our proposed model, costs of transportation between nodes, service at nodes including CDT, moving shipments inside CDT and vehicle operation are considered as the contributors to the total cost. The proposed model was tested for fifteen randomly generated small scale problems using Branch and Bound algorithm and the algorithm was run using LINGO (version 18) optimization software. The average computational time to reach the optimal solution is estimated. The study revealed that for small scale problems, the convergence rate of the problems rises to polynomial with degree 6. Also, the study shows that for moderately large and large scale problems the computational time to reach the optimal solution is exponential. Therefore, this study recommends using a suitable evolutionary algorithm to reach a near optimal solution for moderately large and large scale problems. It further recommends that, this model can be used for last time planning for similar small scale problems.

Cite This Paper

Sebastian. R. Gnanapragasam, Wasantha. B. Daundasekera, "Optimal Solution to the Capacitated Vehicle Routing Problem with Moving Shipment at the Cross-docking Terminal", International Journal of Mathematical Sciences and Computing(IJMSC), Vol.8, No.4, pp. 60-71, 2022. DOI: 10.5815/ijmsc.2022.04.06

Reference

[1]Apte UM, Viswanathan S. Effective Cross Docking for Improving Distribution Efficiencies. Int J Logist Res Appl A Lead J Supply Chain Manag [Internet]. 2000;3(3):291–302. Available from: http://dx.doi.org/10.1080/713682769

[2]Vahdani B, Zandieh M. Scheduling trucks in cross-docking systems: Robust meta-heuristics. Comput Ind Eng [Internet]. 2010;58(1):12–24. Available from: http://dx.doi.org/10.1016/j.cie.2009.06.006

[3]Dantzig G., Ramser J. The Truck Dispatching Problem. Manage Sci. 1959;6(1):80–91.

[4]Lee YH, Jung JW, Lee KM. Vehicle routing scheduling for cross-docking in the supply chain. Comput Ind Eng. 2006;51(2):247–56.

[5]Mavi RK, Goh M, Mavi NK, Jie F, Brown K, Biermann S, et al. Cross-Docking : A Systematic Literature Review. Sustain 2020, MDPI. 2020;12(11):1–19.

[6]Buakum D, Wisittipanich W. A literature review and further research direction in cross-docking. Proc Int Conf Ind Eng Oper Manag. 2019;(MAR):471–81.

[7]Liao CJ, Lin Y, Shih SC. Vehicle routing with cross-docking in the supply chain. Expert Syst Appl [Internet]. 2010;37(10):6868–73. Available from: http://dx.doi.org/10.1016/j.eswa.2010.03.035

[8]Hasani-Goodarzi A, Tavakkoli-Moghaddam R. Capacitated Vehicle Routing Problem for Multi-Product Cross- Docking with Split Deliveries and Pickups. Procedia - Soc Behav Sci [Internet]. 2012;62(2010):1360–5. Available from: http://dx.doi.org/10.1016/j.sbspro.2012.09.232

[9]Vahdani B, Reza TM, Zandieh M, Razmi J. Vehicle routing scheduling using an enhanced hybrid optimization approach. J Intell Manuf. 2012;23(3):759–74.

[10]Yin PY, Chuang YL. Adaptive memory artificial bee colony algorithm for green vehicle routing with cross-docking. Appl Math Model [Internet]. 2016;40(21–22):9302–15. Available from: http://dx.doi.org/10.1016/j.apm.2016.06.013

[11]Birim Ş. Vehicle Routing Problem with Cross Docking: A Simulated Annealing Approach. Procedia - Soc Behav Sci. 2016;235(October):149–58.

[12]Yu VF, Jewpanya P, Redi AANP. Open vehicle routing problem with cross-docking. Comput Ind Eng [Internet]. 2016;94(January):6–17. Available from: http://dx.doi.org/10.1016/j.cie.2016.01.018

[13]Yu VF, Jewpanya P, Redi AANP. A Simulated Annealing Heuristic for the Vehicle Routing Problem with Cross-docking. Logist Oper Supply Chain Manag Sustain [Internet]. 2014;15–30. Available from: http://link.springer.com/10.1007/978-3-319-07287-6

[14]Gunawan A, Widjaja AT, Vansteenwegen P, Yu VF. A matheuristic algorithm for solving the vehicle routing problem with cross-docking. Proc 14th Learn Intell Optim Conf. 2020;12096 LNCS(Lion):9–15.

[15]Gunawan A, Widjaja AT, Vansteenwegen P, Yu VF. Adaptive Large Neighborhood Search for Vehicle Routing Problem with Cross-Docking. 2020 IEEE Congr Evol Comput. 2020;1–8.

[16]Gunawan A, Widjaja AT, Siew BGK, Yu VF, Jodiawan P. Vehicle routing problem for multi-product cross-docking. Proc Int Conf Ind Eng Oper Manag. 2020;0(March):66–77.

[17]Wen M, Larsen J, Clausen J, Cordeau JF, Laporte G. Vehicle routing with cross-docking. J Oper Res Soc [Internet]. 2009;60(12):1708–18. Available from: http://dx.doi.org/10.1057/jors.2008.108

[18]Tarantilis CD. Adaptive multi-restart Tabu Search algorithm for the vehicle routing problem with cross-docking. Optim Lett. 2013;7(7):1583–96.

[19]Morais VWC, Mateus GR, Noronha TF. Iterated local search heuristics for the Vehicle Routing Problem with Cross-Docking. Expert Syst Appl [Internet]. 2014;41(16):7495–506. Available from: http://dx.doi.org/10.1016/j.eswa.2014.06.010

[20]Moghadam SS, Ghomi SMTF, Karimi B. Vehicle routing scheduling problem with cross docking and split deliveries. Comput Chem Eng [Internet]. 2014;69:98–107. Available from: http://dx.doi.org/10.1016/j.compchemeng.2014.06.015

[21]Grangier P, Gendreau M, Lehuédé F, Rousseau LM. A matheuristic based on large neighborhood search for the vehicle routing problem with cross-docking. Comput Oper Res. 2017;84:116–26.

[22]Baniamerian A, Bashiri M, Zabihi F. A modified variable neighborhood search hybridized with genetic algorithm for vehicle routing problems with cross-docking. Electron Notes Discret Math [Internet]. 2018;66:143–50. Available from: https://doi.org/10.1016/j.endm.2018.03.019

[23]Nikolopoulou AI, Repoussis PP, Tarantilis CD, Zachariadis EE. Adaptive memory programming for the many-to-many vehicle routing problem with cross-docking. Int J Oper Res. 2016;19(1):1–38.

[24]Santos FA, Mateus GR, Salles da Cunha A. A Branch-and-price algorithm for a Vehicle Routing Problem with Cross-Docking. Electron Notes Discret Math [Internet]. 2011;37(C):249–54. Available from: http://dx.doi.org/10.1016/j.endm.2011.05.043

[25]Santos FA, Mateus GR, Salles Da Cunha A. A novel column generation algorithm for the vehicle routing problem with cross-docking. Lect Notes Comput Sci (including Subser Lect Notes Artif Intell Lect Notes Bioinformatics). 2011;6701 LNCS:412–25.

[26]Dondo R. A Branch-and-Price Method for the Vehicle Routing Problem with Cross-Docking and Time Windows. Iberoam J Ind Eng. 2013;5(10):16–25.

[27]Fakhrzad MB, Sadri Esfahani A. Modeling the time windows vehicle routing problem in cross-docking strategy using two meta-heuristic algorithms. Int J Eng Trans A Basics. 2014;27(7):1113–26.

[28]Alinaghian M, Rezaei Kalantari M, Bozorgi-Amiri A, Golghamat Raad N. A Novel Mathematical Model for Cross Dock Open-Close Vehicle Routing Problem with Splitting. Int J Math Sci Comput. 2016;3(2):21–31.