A Mathematical Model for the Vehicles Routing Problem with Multiple Depots, Considering the Possibility of Return Using the Tabu Search Algorithm

• Autorzy: Ahmed Alim Al Ayub , Singhal Saurabh , Prakaash A. S. , Dayupay Johnry , Rahadi Irwan , Marhoon Haydar Abdulameer , Iswanto A. Heri , Abbas Saja Fadhil , Aravindhan Surendar

Identyfikatory

DOI

10.2478/fcds-2022-0019

• Języki publikacji: EN

Abstrakty

EN

The current study examines an essential type of vehicle routing problem (VRP). This type is one where customers are served by limited-capacity vehicles from multiple depots and is known as Multi-Depot Capacitated Vehicle Routing Problem (MDCVRP). The novelty of this study is that in the present case, cars, after Leaving the Depot, can go back to any other depot. Those issues seem to occur in most real-world issues where information, messages, or news are sent electronically from somewhere. The purpose of the problem is to minimize the costs associated with routing. Regarding the literature on such issues, it has been proven in previous studies and research that these problems are among the hard-NP problems, and to solve them using the metaheuristic method, the exact methods justify it. After changing the basic model, this study developed a Tabu Search (TS) algorithm. The study results demonstrate that if the equipment can return to any depot, the cost is significantly reduced in contrast to the case where equipment is forced to return to their depot.

Słowa kluczowe

EN

vehicle routing; metaheuristic algorithm; possibility of vehicle return; Tabu Search Algorithm

• Wydawca: Wydawnictwo Politechniki Poznańskiej
• Czasopismo: Foundations of Computing and Decision Sciences
• Rocznik: 2022
• Tom: Vol. 47, No. 4
• Strony: 359--370
• Opis fizyczny: Bibliogr. 24 poz., rys., tab.

Twórcy

autor

Ahmed Alim Al Ayub

• School of Accounting, Jiujiang University, Qianjin Donglu, Jiangxi, China

• https://orcid.org/0000-0003-4836-5423

autor

Singhal Saurabh

• GLA University, Mathura, India

• https://orcid.org/0000-0002-6804-2982

autor

Prakaash A. S.

• Department of Mathematics, Panimalar Institute of Technology Poonamallee Chennai, Chennai, India

autor

Dayupay Johnry

• Graduate School Department, Cebu Technological University, Moalboal, Philippines

• https://orcid.org/0000-0002-4522-4775+

autor

Rahadi Irwan

• Universitas Hamzanwadi, Indonesia

• https://orcid.org/0000-0002-1003-7021

autor

Marhoon Haydar Abdulameer

• Information and Communication Technology Research Group, Scientific Research Center, Al-Ayen University, Thi-Qar, Iraq

• https://orcid.org/0000-0002-2711-1857

autor

Iswanto A. Heri

• Public Health Department, Faculty of Health Science, University of Pembangunan Nasional Veteran Jakarta, Jakarta, Indonesia

• https://orcid.org/0000-0002-1102-0176

autor

Abbas Saja Fadhil

• Al-Nisour University College, Baghdad, Iraq

• https://orcid.org/0000-0002-5264-8517

autor

Aravindhan Surendar

• Department of Pharmacology, Saveetha dental College and hospital, Saveetha institute of medical and technical sciences, Chennai, India

• https://orcid.org/0000-0002-2421-9192

Bibliografia

• [1] Alinaghian M., Tirkolaee E.B., Dezaki Z.K., Hejazi S.R., Ding W., An augmented Tabu search algorithm for the green inventory-routing problem with time windows, Swarm and Evolutionary Computation, 60, 2021, 100802.
• [2] Asghari M., Al-e S. M.J.M., Green vehicle routing problem: a state-of-the-art review, International Journal of Production Economics, 231, 2021, 107899.
• [3] Behnke M., Kirschstein T., Bierwirth C., A column generation approach for an emission-oriented vehicle routing problem on a multigraph, European Journal of Operational Research, 288, 3, 2021, 794-809.
• [4] Escobar J., Duque J., García-Cáceres R., A granular tabu search for the refrigerated vehicle routing problem with homogeneous fleet, International Journal of Industrial Engineering Computations, 13, 1, 2022, 135-150.
• [5] Cordeau J.F., Gendreau M., Laporte G., A tabu search heuristic for periodic and multi‐depot vehicle routing problems, Networks: An International Journal, 30, 2, 1997, 105-119.
• [6] Gendreau M., Hertz A., Laporte G., A tabu search heuristic for the vehicle routing problem, Management science, 40, 10, 1994, 1276-1290.
• [7] Gillett B.E., Miller L.R., A heuristic algorithm for the vehicle-dispatch problem, Operations research, 22, 2, 1974, 340-349.
• [8] Goli A., Malmir B., A covering tour approach for disaster relief locating and routing with fuzzy demand, International Journal of Intelligent Transportation Systems Research, 18, 1, 2020, 140-152.
• [9] Hadjiconstantinou E., Christofides N., Mingozzi A., A new exact algorithm for the vehicle routing problem based onq-paths andk-shortest paths relaxations, Annals of Operations Research, 61,1, 1995, 21-43.
• [10] Kusuma P.D., Kallista M., Multi-depot capacitated vehicle routing problem by using stable marriage and K-means clustering to minimize number of unserved customers and total travel distance, International Journal of Intelligent Engineering and Systems, 14, 6, 2021, 605-615.
• [11] Laporte G., Louveaux F.V., Solving stochastic routing problems with the integer L-shaped method, In Fleet management and logistics (pp. 159-167). Springer, Boston, MA. 1998.
• [12] Li Y., Soleimani H., Zohal M., An improved ant colony optimization algorithm for the multi-depot green vehicle routing problem with multiple objectives, Journal of cleaner production, 227, 2019, 1161-1172.
• [13] Matkivskyi S., Burachok O., Impact of reservoir heterogeneity on the control of water encroachment into gas-condensate reservoirs during CO injection, Management Systems in Production Engineering, 30,1, 2022, 62-68.
• [14] Mojtahedi M., Fathollahi-Fard A.M., Tavakkoli-Moghaddam R., Newton S., Sustainable vehicle routing problem for coordinated solid waste management, Journal of Industrial Information Integration, 23, 2021, 100220.
• [15] Niranjani G., Umamaheswari K., Minimization of sustainable-cost using tabu search for single depot heterogeneous vehicle routing problem with time windows, Wireless Personal Communications, 126, 2, 2022, 1-34.
• [16] Paul A., Kumar R.S., Rout C., Goswami, A., Designing a multi-depot multi-period vehicle routing problem with time window: hybridization of tabu search and variable neighbourhood search algorithm, Sādhanā, 46, 3, 2021, 1-11.
• [17] Pisinger D., Ropke S., A general heuristic for vehicle routing problems, Computers & operations research, 34, 8, 2007, 2403-2435.
• [18] Sacramento D., Pisinger D., Ropke S., An adaptive large neighborhood search metaheuristic for the vehicle routing problem with drones, Transportation Research Part C: Emerging Technologies, 102, 2019, 289-315.
• [19] Schermer D., Moeini M., Wendt O., A hybrid VNS/Tabu search algorithm for solving the vehicle routing problem with drones and en route operations, Computers & Operations Research, 109, 2019, 134-158.
• [20] Singh V.P., Sharma K., Chakraborty D., A Branch-and-Bound-based solution method for solving vehicle routing problem with fuzzy stochastic demands, Sādhanā, 46, 4, 2021, 1-17.
• [21] Theurich F., Fischer A., Scheithauer G., A branch-and-bound approach for a vehicle routing problem with customer costs, EURO Journal on Computational Optimization, 9, 2021, 100003.
• [22] Toth P., Vigo D. (Eds.), The vehicle routing problem. Society for Industrial and Applied Mathematics. 2002.
• [23] Vigo D., A heuristic algorithm for the asymmetric capacitated vehicle routing problem, European Journal of Operational Research, 89,1, 1996, 108-126.
• [24] Zhang H., Ge, H., Yang J., Tong Y., Review of vehicle routing problems: models, classification and solving algorithms, Archives of Computational Methods in Engineering, 29, 1, 2022, 195-221.