A Model for the Multidepot Multiple Travelling Salesman Problem and Advanced Resolution Strategies

A Model for the Multidepot Multiple Travelling Salesman Problem and Advanced Resolution Strategies Juan Pablo Fiesco , Beatriz Andres(B), and Raul Poler Research Centre on Production Management and Engineering (CIGIP), Universitat Politècnica de València (UPV), Camino de Vera S/N, 46022 Valencia, Spain {jfiesco,bandres,rpoler}@cigip.upv.es Abstract. This paper delves into the Multidepot Multiple Travelling Salesman Problem (MDMTSP), an extension of the TSP that presents additional complexities. A review of the state of the art is performed, from which a MDMTSP mixed integer linear programming model is extracted. For this model, a new objective function and new variables are added to cover the need to balance the number of cities to be visited by each salesman. Various strategies are also investigated to reduce the computation times associated with the NP-Hard MDMTSP. The proposed mathematical model is not only an abstract theory, but will also be integrated into the AI-Delivery Optimiser solution of the AIDEAS project. This integration represents a step towards the manufacturing industry of the future, where artificial intelligence and process optimisation will work together to drive competitiveness and business success. Keywords: Multiple Travelling Salesmen ·Problem Solution Approaches · Modelling 1 Introduction The Multiple Travelling Salesman Problem (MTSP) expands upon the Travelling Salesman Problem (TSP) by introducing multiple salesmen tasked with visiting a set of cities exactly once before returning to their starting point, typically a depot, at the minimum travel cost. The MTSP has applications in optimisation problems like vehicle routing problems (VRPs), task assignments, machine and operator scheduling in manufacturing, inventory management and warehouse replenishment, or order-picking problems in warehouses [1]. The MTSP prohibits multiple visits and subtours by distinguishing it from the task assignment problem. In the scenario with a single depot, all the salesmen initiate and conclude their tours at a sole location, but when multiple depots are present (MDMTSP), each hosts a specific number of salesmen with flexibility to return to either theiroriginalordifferentdepots[2].AstheMDMTSPisaNP-hardproblem,theobjective of this paper is to provide various advanced resolution strategies to reduce computation times. This paper has been done within the scope of the AI-Driven Industrial Equipment © The Author(s), under exclusive license to Springer Nature Switzerland AG 2025 A. A. Juan et al. (Eds.): DSA ISC 2024, LNCS 14778, pp. 353–360, 2025. https://doi.org/10.1007/978-3-031-78238-1_32 354 J. P. Fiesco et al. Product Life Cycle Boosting Agility, Sustainability and Resilience (AIDEAS) Horizon Europe project. AIDEAS proposes a set of intelligent solutions to support the manufacturing phase in the machinery industry. Solutions include the procurement optimiser (AI-PO), the fabrication optimiser (AI-FO) and the delivery optimiser (AI-DO). The current paper focuses on the AI-DO, which is an optimisation solution applied to support the product transportation problem. Accordingly, the paper pays attention to the development of advanced techniques to address the MDMTSP. So this paper is organised as follows: Sect. 2summarises the state of the art. Section 3formulates the MDMTSP and validates the model with short experiments. Section 4describes a set of advanced strategies to reduce the MDMTSP resolution times. Finally, conclusions are discussed in Sect. 5. 2 State of the Art In the MTSP context, the authors discussing the problem coincide with the fact that more efficient heuristic algorithms are required, especially in large-scale datasets, which highlights the need to develop innovative resolution strategies in this domain. Although exact methods promise optimal solutions, they prove impractical for larger instances due to the problem’s complexity. Along these lines, [2] emphasises the efficacy of branchand-bound methods, especially when paired with well-selected initial bounds. A more recent study by [3] underscores the use of both exact and heuristic techniques. Heuristic approaches, such as genetic algorithms (GA) or ant colony (AC), have gained favour for their efficiency in tackling the MTSP. Furthermore, hybrid algorithms that blend metaheuristics with local searches or clustering methods [4] and matheuristics that combine exact methods with heuristics or metaheuristics [5] have surfaced to mitigate computational complexity and convergence time. These diverse solution methodologies reflect a concerted endeavour to efficiently address the MTSP by striving to strike a balance between optimality and practicality. Foritsapplicability, theTSP has traditionallybeen usedintransport, productdistribution, production planning and logistics. Moreover, recent advances in drone technology have led to academy and industry interest being shown in investigating the application of unmanned aerial vehicles (UAVs) [6]. Some studies in the literature focus on the cooperation of trucks and drones for last-mile delivery [7,8]. In light of this, [3] describe eight more possible application areas, including multirobot task allocation and scheduling, disaster management, and monitoring and surveillance. This paper focuses on the MDMTSP, a TSP extension challenge that has been addressed in various ways. The work of [9] is particularly noteworthy, which delves into the application of multiple depots and multiple peddlers to the facility location problem. Their study incorporates crucial factors, such as vehicle autonomy and service frequency requirements, by providing valuable insight into real-world logistics scenarios. Another interesting contribution is that by [10] who introduces the multidepot electric vehicle location routing problem with time windows by extending the classic VRP to include electric vehicles and energy supply options. A Model for the Multidepot Multiple Travelling Salesman Problem 355 3 Problem Formulation The MTSP involves optimising routes for multiple salesmen, each starting and ending their tour at a designated depot while visiting a set of cities exactly once. In the variant MDMTSP, the problem is compounded by considering multiple potential depots from which salesmen can initiate their routes. The objective is to divide the set of cities into subsets, each corresponding to a tour for a specific salesman, to ensure that every city is visited exactly once in each subset. Additionally, each tour must commence and conclude at its respective depot, with a minimum requirement of two nodes visited during each tour. The goal may include minimising the total distance travelled by all the salesmen or balancing their workload. Figure 1depicts a two-route graph by illustrating the paths that each sales person will take to visit cities and to return to their respective depots. Fromthe analysis ofthe stateofthe art,the mixedintegerlinearprogramming(MILP) outlined in [11] is taken as a reference to propose advanced techniques and to improve resolution times. The MILP uses three decision variables: •Xkij =1, if salesperson k visits node j immediately after node i; 0, otherwise. •zi=1, if node i is the starting (origin) node during a tour of any salesperson; 0, otherwise. •ui=visiting rank of node i Objective Function (1) seeks to minimise the total cost, represented by the combined length of m tours. Minimize n i=1n j=1:i=j(dij m k=1Xkij)(1) Subject to: n i=1:i=jm k=1Xkij =1∀j=1,2,...,n(2) n i=1:i=pXkip −n j=1:j=pXkpj =0∀p=1,...,n,k=1,2,...,m(3) n i=1:i=jm k=1Xkij ≥1∀k=1,2,...,m(4) ui−uj+L·m k=1Xkij ≤L−1+L·zj∀i,j=1,2,...,n:i= j(5) 1≤ui≤L∀i=1,2,...,n(6) n i=1zi=m(7) Xkij ∈{0,1}∀i,j=1,...,n:i= j,k=1,2,...,m(8) zi∈{0,1}∀i=1,...,n(9) 356 J. P. Fiesco et al. Constraint (2) ensures that each node is visited exactly once during tours. Flow conservation Constraint Set (3) mandates that if a salesperson visits a node, (s)he must also depart from it. Constraint Set (4) ensures that each salesperson is assigned to a tour. Constraints (5) and (6) prevent undesirable subtours, with L representing the maximum number of nodes that a salesperson can visit, calculated as L=n−2m +2. Furthermore, constraint (5) allows that in the case where index i is the last node visited before arriving its depot node (j), and where uitakes the highest according to its visit order (L or approximately L), the variable Xkij can also take the value one respecting the limitation on the right-hand side of the constraint because zjis equal to one. Constraint (7) specifies the m starting nodes corresponding to m tours. Lastly, constraints (8) and (9) define the decision variables utilised in the model. With this formulation of the problem, what is minimised is the total distance travelled by all the salespersons. However, another aspect to consider is the load of cities assigned by each agent; this amount should be equitable to not saturate a salesperson. Thus [11] propose a new MILP model for the MDTSP with a min-max objective by adding the variable Smax. Inspired by this work, we propose a new MILP that minimises both the total route, and the deviation between the maximum and minimum number of locations to visit, by penalising the solution with an imbalance in route allocation. STMAX =number of locations visited on the longest route. STMIN =number of locations visited on the shortest route. The new Objective Function (10) minimises the total cost of m tours and the bias of the maximum number of locations visited and a minimum number. Constraints (2)– (9) remain the same, while constraints (11) and (12) calculate the maximum and minimum number of locations visited by all the salespersons. Minimise n i=1n j=1:i=j(dij m k=1Xkij)+(STMAX −STMIN)·c(10) n i=1n j=1:i=jXkij ≥STMIN∀k=1,2,...,m(11) n i=1n j=1:i=jXkij ≤STMAX ∀k=1,2,...,m(12) Next a set of experiments validating the proposed model is presented by considering small, medium and large data size instances. A table with the experiment results is offered (Table 1). Each instance is represented by the number of customers, the number of trucks and depots, which are the same, the balance of the number of customers visited by each truck (100% indicates that trucks visit the same number of customers), the total cost, the GAP and the resolution time. The solver software used in this research is GUROBI, which is generally employed to solve MILP problems. The proposed MILP has been implemented as a Python application running on a CPU with 12th Gen Intel(R) Core(TM) i7-12700 2.10 GHz processor (6 GB RAM). The GAP is calculated as the absolute difference between the target value of the best known solution and the current best solution, divided by the absolute value of the best known solution. By analysing the results in Table 1, it can be concluded that the exact method used can achieve optimal solutions in seconds for small instances. However, for large instances, the solution is far from optimal and limits the time to 15 min. This shows the need to explore new strategies to solve the problem. A Model for the Multidepot Multiple Travelling Salesman Problem 357 Fig. 1. Example of an MDMTSP and a solution. Table 1. Instance experiments results. Instance No. Customers No. Trucks No. Depots Balance Total cost GAP Time (sec.) 2_10_S1 10 2 2 100.00% 428 0.00% 2.24 2_54_M1 54 2 2 100.00% 780 13.04% 900 2_89_M2 89 2 2 97.82% 1016 11.27% 900 2_96_M3 96 2 2 100.00% 1068 16.59% 900 2_100_M4 100 2 2 100.00% 1064 19.15% 900 4_30_L1 30 4 4 88.88% 564 26.96% 900 4_73_L2 73 4 4 95.00% 1118 37.31% 900 4_91_L3 91 4 4 95.83% 1324 56.48% 900 4_95_L4 95 4 4 96.00% 1350 55.91% 900 4 Advanced Resolution Strategies for the MDMTSP Solving the MDMTSP entails devising efficient algorithms capable of handling the combinatorial complexity inherent in determining optimal routes while respecting the constraints imposed by multiple depots and the requirement of visiting each city exactly once. The MDMTSP is an NP-hard problem, which means that finding an optimal solution can take an exponential amount of time depending on the size of the problem. This section proposes a set of advanced techniques to improve the MDMTSP resolution times without compromising the solution quality, but by achieving the optimal bounds. 358 J. P. Fiesco et al. (i) Evolutionary approaches: metaheuristics, such as GA, AC or simulated annealing (SA),which experimentwith different parametersettings, suchas populationsizes, mutation rates and stopping criteria, to find the combination that best works for a specific dataset [11]. (ii) Hybrid algorithms: they employ the combination of GA, AC or SA metaheuristics to make the most of the strengths of the different methods and to improve convergence speed [4]. (iii) Improved construction heuristics: it investigates more sophisticated construction heuristics for generating initial routes, such as the modified Nearest Neighbour Algorithm, the Nearest Insertion Algorithm or the Best Insertion Heuristic [12]. (iv) Relaxation approaches: theyare employedtotransformthe MILP intoa continuous problem to obtain initial solutions. They use gradual improvement techniques to arrive at a more optimal solution [13]. (v) Neighbourhood search techniques: they implement neighbourhood search techniques, such as local search or larger neighbourhood search, to explore nearby solutions and iteratively improve the current solution. (vi) Parallelisation techniques: they involve the simultaneous execution of multiple computations to more efficiently solve the problem. Parallel GA use parallelism in the evaluation and evolution of candidate solutions, multiple populations of solutions can be evolved concurrently, and crossover and mutation operations are performed independently on different subsets of the population [14]. (vii) Decomposition Techniques and Clustering: they decompose the problem into several smaller ones, define “clusters” around Depots. They divide the MTSP into a series of subproblems, each representing a tour for an individual salesman. They sequentially optimise each tour, possibly using a TSP solver, and combine solutions to form the overall solution. They divide cities into clusters and assign each cluster to a different salesman. Finally, the routes connecting clusters are optimised [15]. (viii) Matheuristics: this combine exact methods with heuristics or metaheuristics to provide presolutions to the MILP [5]. It can be concluded that there is not an unique resolution strategy for improving the MDMTSP, and that the selected strategies to solve the MDMTSP depend on the problem characteristics and the specific requirements of the application. Experimenting with various techniques and adjusting parameters can help making significant improvements in the speed and quality of solutions. 5 Conclusions and Future Research Lines In conclusion, this paper presents a brief state of the art of the MDMTSP, analyses an MILP proposed by Karabulut et al. (2021) and proposes a new formulation by adding the minimisation of load balance of visited locations to the objective function. Additionally, various strategies are explored to reduce the computation times associated with this combinatorial problem. These strategies include evolutionary approaches, hybrid algorithms, improved construction heuristics, relaxation approaches, neighbourhood search tools, parallelisation techniques, decomposing approaches, clustering and matheuristics. A Model for the Multidepot Multiple Travelling Salesman Problem 359 For a real-world application of this problem, the potential of combining the MTSP with depot management and depot location design problems is highlighted for offering a comprehensive perspective to address logistics and distribution challenges. Computational experiments were carried out on small, medium and large datasets, of which the last ones are capable of simulating real-world problems. Small instances approximate optimal solutions in an average of two seconds with 0% of GAP. Medium instances do not achieve the optimal solution, although longer computation times imply a reduction in the GAP. Finally, the resolution of large datasets exponentially increase computational times without achieving an optimal solution, which demonstrates that the MDMTSP is an NP-hard problem that needs advanced techniques to obtain good solutions in shorter computational times. To all this, a set of nine advanced resolution strategies is proposed. It is noteworthy that this research aligns with the AIDEAS project and its solution, the AIDEASDeliveryOptimiser, an AI-basedtool capableofoptimising productstorage and delivery. This solution not only focuses on optimising storage space, storage conditions and product transportation, but also provides optimisation for logistics planning and scheduling. As future research directions, further exploring the application of the proposed advanced strategies to improve the computational efficiency of the MDMTSP is suggested, as well as integrating these solutions into practical systems like the AIDEAS Delivery Optimiser to enhance logistics management in real business environments. Therefore as a next step to this research, the decomposition of the problem into smaller ones by defining clusters around depots and utilising matheuristics to provide presolutions to the MILP, are proposed to be implemented. Acknowledgements. The research that led to these findings received funding from the Horizon Europe Ref.101057294 “AI-Driven Industrial Equipment Product Life Cycle Boosting Agility, Sustainability, and Resilience (AIDEAS)”; the Regional Department of Innovation, Universities, Science, and Digital Society of the Generalitat Valenciana “Programa Investigo” Ref. INVEST/2022/330, which the European Union supported - NextGenerationEU with Plan de Recuperación, Transformación y Resiliencia; the Regional Department of Innovation, Universities, Science, and Digital Society of the Generalitat Valenciana Ref. CIAEST/2022/39 “Doctoral research staff to carry out research stays in companies in the Valencia Region”; and the Vice-Rectorate for Research of the Universitat Politècnica de València Ref. PAID-06-23 “Intelligent optimisation algorithms and models for production planning and replenishment (ATENNEA)”. References 1. Matai,R., Singh, S.,Lal, M.: Traveling salesmanproblem:an overviewofapplications,formulations, and solution approaches. In: Traveling Salesman Problem, Theory and Applications. InTech (2010). https://doi.org/10.5772/12909 2. Bektas,T.: Themultiple traveling salesmanproblem:an overviewofformulationsand solution procedures. Omega (Westport) 34(3), 209–219 (2006). https://doi.org/10.1016/j.omega.2004. 10.004 3. Cheikhrouhou, O., Khoufi, I.: A comprehensive survey on the multiple traveling salesman problem: applications, approaches and taxonomy. Comput. Sci. Rev. 40. (2021). https://doi. org/10.1016/j.cosrev.2021.100369 360 J. P. Fiesco et al. 4. Jiang, C., Wan, Z., Peng, Z.: A new efficient hybrid algorithm for large scale multiple traveling salesman problems. Expert Syst. Appl. 139 (2020). https://doi.org/10.1016/j.eswa.2019. 112867 5. Guzman, E., Andres, B., Poler, R.: Models and algorithms for production planning, scheduling and sequencing problems: a holistic framework and a systematic review. J. Ind. Inf. Integr. 27 (2022). https://doi.org/10.1016/j.jii.2021.100287 6. Khoufi,I., Laouiti,A., Adjih,C.: Asurveyofrecentextendedvariantsofthetravelingsalesman and vehicle routing problems for unmanned aerial vehicles. Drones 3(3), 1–30 (2019). https:// doi.org/10.3390/drones3030066 7. Zhang, R., Dou, L., Xin, B., Chen, C., Deng, F., Chen, J.: A review on the truck and drone cooperative delivery problem Unmanned Syst. (2023). https://doi.org/10.1142/S23013850 24300014 8. Rinaldi, M., Primatesta, S., Bugaj, M., Rostáš, J., Guglieri, G.: Development of heuristic approaches for last-mile delivery TSP with a truck and multiple drones. Drones 7(7) (2023). https://doi.org/10.3390/drones7070407 9. Chan, Y., Baker, S.F., Chan, Y., Dij, D.: The Multiple Depot, Multiple Traveling Salesmen Facility-LocationProblem:VehicleRange,Service Frequency,andHeuristicImplementations (2005). www.elsevier.corn/locate/mcm 10. Paz, J.C., Granada-Echeverri, M., Escobar, J.W.: The multi-depot electric vehicle location routing problem with time windows. Int. J. Ind. Eng. Comput. 9(1), 123–136 (2018). https:// doi.org/10.5267/j.ijiec.2017.4.001 11. Karabulut, K., Öztop, H., Kandiller, L., Tasgetiren, M.F.: Modeling and optimization of multiple traveling salesmen problems: An evolution strategy approach. Comput. Oper. Res. 129 (2021). https://doi.org/10.1016/j.cor.2020.105192 12. Ursani, Z., Ursani, A.A.: Augmented tour construction heuristics for the travelling salesman problem. Int. J. Ind. Optim. 4(2), 131–144 (2023). https://doi.org/10.12928/ijio.v4i2.7875 13. Ricciardi, L.A., Vasile, M.: Solving multi-objective dynamic travelling salesman problems by relaxation. In: GECCO 2019 Companion - Proceedings of the 2019 Genetic and Evolutionary Computation Conference Companion, pp. 1999–2007. Association for Computing Machinery, Inc., (2019). https://doi.org/10.1145/3319619.3326837 14. Dhanalakshmi, R., Parthiban, P., Anbuchezhian, N.: Optimisation of multiple travelling salesman problem using metaheuristic methods. Int. J. Enterp. Netw. Manag. 13(3), 199–215 (2022). https://doi.org/10.1504/IJENM.2022.125803 15. Romanuke, V.V.: Deep clustering of the traveling salesman problem to parallelize its solution. Comput. Oper. Res. 165 (2024). https://doi.org/10.1016/j.cor.2024.106548