Open vehicle routing problem with moving shipments at the cross-docking terminal

Sebastian Reyalt Gnanapragasam, Wasantha Bandara Daundasekera

Abstract


In this study, one of the internal operations at the Cross-docking Terminal (CDT), moving shipments (MS) from receiving doors to shipping doors of CDT is integrated with Open Vehicle Routing Problem (OVRP) and the problem is indicated here as OVRPCD-MS. As an additional feature, asymmetric distance between any two customers is assigned by incorporating a characteristic of one-way routes between cities in real-life transportation. The objective is to minimize the total transportation cost which incurs travelling cost between customers, service cost at customer points, service cost at the receiving and shipping doors of CDT, cost of moving shipments inside the CDT and finally the cost of hiring fleets of vehicles. To solve the OVRPCD-MS problem, a Mixed Integer Linear Programming (MILP) model is developed. The programming models are implemented in LINGO (version 18) optimization software. Branch and Bound algorithm is employed to solve ten small-scale instances generated randomly. The applicability of the proposed MILP model is observed. The required fleets of vehicles to be hired and run time to reach the optimal solution are determined. The study revealed that the average run time is exponential for small-scale instances. Thus, it can be concluded that this proposed model can be used for last-time planning for small-scale instances. Also, the combinatorial nature of the vehicle routing problem makes OVRPCD-MS as NP-hard. Therefore, this study recommends that heuristic or meta-heuristic methods are more appropriate for the large-scale instances of OVRPCD-MS to reach near-optimum solutions.

Keywords: Cross-docking, Moving shipments, Open vehicle routing.

Full Text:

PDF

References


Alinaghian M, Rezaei Kalantari M, Bozorgi-Amiri A, Golghamat Raad N. 2016. A Novel Mathematical Model for Cross Dock Open-Close Vehicle Routing Problem with Splitting. International Journal of Mathematical Sciences and Computing 3(2): 21–31.

https://doi.org/10.5815/ijmsc.2016.03.02

Apte UM, Viswanathan S. 2000. Effective Cross Docking for Improving Distribution Efficiencies. International Journal of Logistics Research and Applications: A Leading Journal of Supply Chain Management 3(3): 291–302. http://dx.doi.org/10.1080/713682769

Baniamerian A, Bashiri M, Zabihi F. 2018a. A modified variable neighborhood search hybridized with genetic algorithm for vehicle routing problems with cross-docking. Electronic Notes in Discrete Mathematics 66: 143–150. https://doi.org/10.1016/j.endm.2018.03.019

Baniamerian A, Bashiri M, Zabihi F. 2018b. Two phase genetic algorithm for vehicle routing and scheduling problem with cross-docking and time windows considering customer satisfaction. Journal of Industrial Engineering International 14(1): 15–30. https://doi.org/10.1007/s40092-017-0203-0

Birim Ş. 2016. Vehicle Routing Problem with Cross Docking: A Simulated Annealing Approach. Procedia - Social and Behavioral Sciences 235(October): 149–158.

https://doi.org/10.1016/j.sbspro.2016.11.010

Buakum D, Wisittipanich W. 2019. A literature review and further research direction in cross-docking. Proceedings of the International Conference on Industrial Engineering and Operations Management MAR: 471–481

Dantzig G, Ramser J. 1959. The Truck Dispatching Problem. Management Science 6(1): 80–91.

https://doi.org/10.1287/mnsc.6.1.80

Dondo R. 2013. A Branch-and-Price Method for the Vehicle Routing Problem with Cross-Docking and Time Windows. Iberoamerican Journal of Industrial Engineering 5(10): 16–25.

https://doi.org/10.13084/2175-8018.v05n10a02

Fakhrzad MB, Sadri Esfahani A. 2014. Modeling the time windows vehicle routing problem in cross-docking strategy using two meta-heuristic algorithms. International Journal of Engineering, Transactions A: Basics 27(7): 1113–1126. https://doi.org/10.5829/idosi.ije.2014.27.07a.13

Gnanapragasam SR, Daundasekera WB. 2022. Optimal Solution to the Capacitated Vehicle Routing Problem with Moving Shipment at the Cross-docking Terminal. International Journal of Mathematical Sciences and Computing 8(4): 60–71. https://doi.org/10.5815/ijmsc.2022.04.06

Gnanapragasam SR, Daundasekera WB. 2023. An Optimization Model for the Hard Time Windows Vehicle Routing Problem with Moving Shipments at the Cross Dock Center. OUSL Journal 18(1): 33–60. https://doi.org/10.4038/ouslj.v18i1.7569

Grangier P, Gendreau M, Lehuédé F, Rousseau LM. 2017. A matheuristic based on large neighborhood search for the vehicle routing problem with cross-docking. Computers and Operations Research 84: 116–126; https://doi.org/10.1016/j.cor.2017.03.004

Gunawan A, Widjaja AT, Siew BGK, Yu VF, Jodiawan P. 2020. Vehicle routing problem for multi-product cross-docking. Proceedings of the International Conference on Industrial Engineering and Operations Management 0(March): 66–77.

Gunawan A, Widjaja AT, Vansteenwegen P, Yu VF. 2020a. A matheuristic algorithm for solving the vehicle routing problem with cross-docking. Proceedings of the 14th Learning and Intelligent OptimizatioN Conference 12096 LNCS(Lion): 9–15. https://doi.org/10.1007/978-3-030-53552-0_2

Gunawan A, Widjaja AT, Vansteenwegen P, Yu VF. 2020b. Adaptive Large Neighborhood Search for Vehicle Routing Problem with Cross-Docking. 2020 IEEE Congress on Evolutionary Computation (CEC): 1–8; https://doi.org/10.1109/CEC48606.2020.9185514

Hasani-Goodarzi A, Tavakkoli-Moghaddam R. 2012. Capacitated Vehicle Routing Problem for Multi-Product Cross- Docking with Split Deliveries and Pickups. Procedia - Social and Behavioral Sciences 62(2010): 1360–1365. https://doi.org/10.1016/j.sbspro.2012.09.232

Larioui S, Reghioui M, Elfallahi A, Elkadiri KE. 2015. A memetic algorithm forthe vehicle routing problema with cross docking. International Journal of Supply and Operations Management 2(3): 833–855.

Lee YH, Jung JW, Lee KM. 2006. Vehicle routing scheduling for cross-docking in the supply chain. Computers and Industrial Engineering 51(2): 247–256. https://doi.org/10.1016/j.cie.2006.02.006

Liao CJ, Lin Y, Shih SC. 2010. Vehicle routing with cross-docking in the supply chain. Expert Systems with Applications 37(10): 6868–6873. https://doi.org/10.1016/j.eswa.2010.03.035

Moghadam SS, Ghomi SMTF, Karimi B. 2014. Vehicle routing scheduling problem with cross docking and split deliveries. Computers and Chemical Engineering 69: 98–107.

https://doi.org/10.1016/j.compchemeng.2014.06.015

Morais VWC, Mateus GR, Noronha TF. 2014. Iterated local search heuristics for the Vehicle Routing Problem with Cross-Docking. Expert Systems with Applications 41(16): 7495–7506.

https://doi.org/10.1016/j.eswa.2014.06.010

Nikolopoulou AI, Repoussis PP, Tarantilis CD, Zachariadis EE. 2016. Adaptive memory programming for the many-to-many vehicle routing problem with cross-docking. International Journal of Operational Research 19(1): 1–38; https://doi.org/10.1007/s12351-016-0278-1

Santos FA, Mateus GR, Salles Da Cunha A. 2011a. A Branch-and-price algorithm for a Vehicle Routing Problem with Cross-Docking. Electronic Notes in Discrete Mathematics 37(C): 249–254; https://doi.org/10.1016/j.endm.2011.05.043

Santos FA, Mateus GR, Salles Da Cunha A. 2011b. A novel column generation algorithm for the vehicle routing problem with cross-docking. Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 6701 LNCS: 412–425; https://doi.org/10.1007/978-3-642-21527-8_47

Tarantilis CD. 2013. Adaptive multi-restart Tabu Search algorithm for the vehicle routing problem with cross-docking. Optimization Letters 7(7): 1583–1596; https://doi.org/10.1007/s11590-012-0558-5

Vahdani B, Reza TM, Zandieh M, Razmi J. 2012. Vehicle routing scheduling using an enhanced hybrid optimization approach. Journal of Intelligent Manufacturing 23(3): 759–774.

https://doi.org/10.1007/s10845-010-0427-y

Vahdani B, Zandieh M. 2010. Scheduling trucks in cross-docking systems: Robust meta-heuristics. Computers and Industrial Engineering 58(1): 12–24; https://doi.org/10.1016/j.cie.2009.06.006

Van Belle J, Valckenaers P, Cattrysse D. 2012. Cross-docking: State of the art. Omega 40(6): 827–846.

https://doi.org/10.1016/j.omega.2012.01.005

Wen M, Larsen J, Clausen J, Cordeau JF, Laporte G. 2009. Vehicle routing with cross-docking. Journal of the Operational Research Society 60(12): 1708–1718. https://doi.org/10.1057/jors.2008.108

Yin PY, Chuang YL. 2016. Adaptive memory artificial bee colony algorithm for green vehicle routing with cross-docking. Applied Mathematical Modelling 40(21–22): 9302–9315.

https://doi.org/10.1016/j.apm.2016.06.013

Yu VF, Jewpanya P, Redi AANP. 2014. A Simulated Annealing Heuristic for the Vehicle Routing Problem with Cross-docking. Logistics Operations, Supply Chain Management and Sustainability: 15–30. https://doi.org/10.1007/978-3-319-07287-6

Yu VF, Jewpanya P, Redi AANP. 2016. Open vehicle routing problem with cross-docking. Computers and Industrial Engineering, 94(January): 6–17. https://doi.org/10.1016/j.cie.2016.01.018


Refbacks

  • There are currently no refbacks.


Creative Commons Licence
Ruhuna Journal of Science by University of Ruhuna is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

eISSN: 2536-8400

Print ISSN: 1800-279X (Before 2014)