Article Preview
TopIntroduction
The traveling Salesman Problem (TSP) is one of the most studied NP-hard problems in combinatorial optimization (Lawler, Lenstra, & Kan, 1985). This is due to the large number of related real-world applications. In the basic version of TSP, a salesman starts from a depot city and visits a set of cities each once and then returns back to the starting depot with the minimum total travel cost, distance or time. Many variants of TSP are studied in the literature under different constraints and objectives. Some variants consider one salesman (TSP), other variants consider many salesmen (mTSP). Most of the variants search for the optimal tour(s) that minimizes the travel cost.
In this paper, the Multiple Objective multiple Traveling Salesmen Problem (MOmTSP) variant of TSP was considered. MOmTSP is a real-world problem in diverse contexts such as scheduling environment, food industry, and maintenance activities. In general, several people travel to perform many tasks in different locations. Every task requires a processing time and has to be executed by only one person. In this case, two different parameters are to be considered in the problem: the traveling distances (or times) between the cities and the processing times of the tasks to be executed in the cities. Two famous applications of the studied problem are the postal services and the maintenance activities realized by electricity and water companies. Such companies need to assign their daily tasks located in different areas to different teams. The main objective is to accomplish these tasks as soon as possible with the minimum traveled distance. Thus, finding the shortest tour to be traveled by each person will lead to time, fuel and therefore money saving. Another important factor that needs to be considered is load balancing. In fact, employees of such companies are paid on monthly basis regardless of the quantity of work they perform. Balancing their daily workloads will increase their job satisfaction and feeling of fairness.
Many algorithms and heuristics have been published to provide efficient solutions to TSP variants such as single objective mTSP and Multiple Objective TSP (MOTSP). In (Bektas, 2006), the authors surveyed the exact and heuristic solutions to solve the mTSP. Since then, research has been done to tackle the mTSP problem. A general variable neighborhood search algorithm for the single depot mTSP was proposed in (Soylu, 2015). Two objectives were considered separately, the minimization of the length of the longest tour and the total travelled distance by all salesmen. The proposed method succeeded to solve small mTSP instances. In (Chen, Jia, Ai, Yang, & Jianqiao, 2017), a modified two-part wolf pack search algorithm outperformed the algorithm of (Soylu, 2015). In (Onder, Kara, & Derya, 2017), the authors developed a Mixed Integer Linear Programming (MILP) formulation of the mTSP with single depot but with different termination points for m repairmen. In each city, a waiting time (latency of a customer) is defined as the time passed from the beginning of the travel until the customer’s service is completed. The objective was to find a Hamiltonian tour that minimizes the total waiting time of customers. The proposed MILP solves optimally instances of a maximum 39 cities for two, four and eight salesmen. The authors in (Aguayo, Sarin, & Sherali, 2017) proposed an algorithm to solve the asymmetric mTSP by generating violated sub-tour elimination constraints from specific integer solutions. The algorithm was able to generate optimal solutions to small and large-sized instances of up to 1001 cities within one hour of CPU execution time.
Tackling Multiple Objective problems like the MOTSP is not always an easy task. The objectives may have different degrees of priority. For this reason, many authors developed approaches that generate Pareto optimal solutions without prioritizing the objectives. The challenge in this case is to find an optimal Pareto front where no solution dominates the others for any of the objectives. In (Psychas, Delimpasi, & Marinakis, 2015) two hybrid evolutionary algorithms based on differential evolution in addition to a hybridized version of the NSGA II were developed to generate Pareto optimal solutions to solve the MOTSP with two to five objective functions. While in (Florios & Mavrotas, 2014), the authors developed a Multi-Objective Mathematical Programming (MOMP) method that was capable of generating the exact Pareto optimal front for a MOTSP problem with two objectives and 100 cities.