Distribution Path Segmentation Using Route Relocation and Savings Heuristics for Multi-Depot Vehicle Routing





Route Relocation, Savings Heuristic, Computational Intelligence, Routing Heuristics, Genetic Algorithm


This paper uses routing segmentation optimization for the planning of optimal distribution networks between urban depots and their respective customers. In this experiment, three steps are proposed in concession: search for the initial solution using local search properties, improve the solution using route relocation and perturb the solution using tabu search incorporating the savings heuristic. By applying multi-depot simultaneous deployment with ideal scheduling strategies and routing heuristics ensuring cost-optimal routing, the study presents an alternative to enhanced scheduling system optimization. Based on repopulation and sequential insertion algorithms, the initial solution is created, while route relocation and tabu swap mechanisms constitute the improvement strategy and perturbation. Test results comparing the proposed solution strategy to the previous genetic algorithm solution result in a better arrangement of route segregation aspects representing customer clusters. This strategy has proven to be more successful in optimizing route segregation than the original genetic algorithm solution. This demonstrates a significant improvement in route optimization.


V. Kastrati and A. Ahmeti, “Solving Vehicle Routing and Scheduling with Delivery and Installation of Machines using ILS,” 13th Int. Conf. Pract. Theory Autom. Timetabling, vol. I, pp. 207–223, 2021.

Y. Christopher, S. Wahyuningsih, and D. Satyananda, “Study of variable neighborhood descent and tabu search algorithm in VRPSDP,” J. Phys. Conf. Ser., vol. 1872, no. 1, 2021.

S. Nucamendi-Guillén, A. Gómez Padilla, E. Olivares-Benitez, and J. M. Moreno-Vega, “The multi-depot open location routing problem with a heterogeneous fixed fleet,” Expert Syst. Appl., vol. 165, no. August 2020, 2021.

B. Li, G. Wu, Y. He, M. Fan, and W. Pedrycz, “An Overview and Experimental Study of Learning-Based Optimization Algorithms for the Vehicle Routing Problem,” IEEE/CAA J. Autom. Sin., vol. 9, no. 7, pp. 1115–1138, 2022.

H. El Fahim, “An Iterated Local Search with Multiple Perturbation Operatorsand a Varying Perturbation Strength for the Capacitated TeamOrienteering Problem with Time Windows,” no. May, pp. 1–12, 2022.

S. Wahyuningsih and D. Satyananda, “Improvement of solution using local search method by perturbation on VRPTW variants,” J. Phys. Conf. Ser., vol. 1581, no. 1, 2020.

D. Marković, G. Petrović, Ž. Ćojbašić, and A. Stanković, “The vehicle routing problem with stochastic demands in an Urban area – A case study,” Facta Univ. Ser. Mech. Eng., vol. 18, no. 1, pp. 107–120, 2020.

J. F. Castaneda Londono, R. A. G. Rendon, and E. M. T. Ocampo, “Iterated local search multi-objective methodology for the green vehicle routing problem considering workload equity with a private fleet and a common carrier,” Int. J. Ind. Eng. Comput., vol. 12, no. 1, pp. 115–130, 2020.

S. Chandana Kaja, “A New Approach for Solving the Disruption in Vehicle Routing Problem During the Delivery A Comparative Analysis of VRP Meta-Heuristics,” no. May, pp. 135–146, 2020.

Y. U. Kasanah, N. N. Qisthani, and A. Munang, “Solving the Capacitated Vehicle Routing Problem with Heterogeneous Fleet Using Heuristic Algorithm in Poultry Distribution,” J. Ilm. Tek. Ind., vol. 21, no. 1, pp. 104–112, 2022.

F. Tunnisaki and Sutarman, “Clarke and Wright Savings Algorithm as Solutions Vehicle Routing Problem with Simultaneous Pickup Delivery (VRPSPD),” J. Phys. Conf. Ser., vol. 2421, no. 1, p. 012045, 2023.

S. Kunnapapdeelert and C. Thawnern, “Capacitated vehicle routing problem for thailand’s steel industry via saving algorithms,” J. Syst. Manag. Sci., vol. 11, no. 2, pp. 171–181, 2021.

N. A. Fitriani, R. A. Pratama, S. Zahro, P. H. Utomo, and T. S. Martini, “Solving capacitated vehicle routing problem using saving matrix, sequential insertion, and nearest neighbor of product ‘X’ in Grobogan district,” AIP Conf. Proc., vol. 2326, 2021.

H. Li, K. Xiong, and X. Xie, “Multiobjective Contactless Delivery on Medical Supplies under Open-Loop Distribution,” Math. Probl. Eng., vol. 2021, 2021.

C.-M. Chen, S. Lv, J. Ning, and J. M.-T. Wu, “A Genetic Algorithm for the Waitable Time-Varying Multi-Depot Green Vehicle Routing Problem,” Symmetry (Basel)., vol. 15, no. 1, p. 124, 2023.




How to Cite

F. Morsidi, “Distribution Path Segmentation Using Route Relocation and Savings Heuristics for Multi-Depot Vehicle Routing”, Malaysian J. Sci. Adv. Tech., vol. 3, no. 2, pp. 72–80, May 2023.