Minimization of the total traveling distance and maximum distance by using a transformed-based encoding EDA to solve the multiple traveling salesmen problem
type: Item
instance of: scholarly article
title: Minimization of the total traveling distance and maximum distance by using a transformed-based encoding EDA to solve the multiple traveling salesmen problem
zbMATH Open document ID: 1394.90476
DOI: 10.1155/2015/640231
author: Y. Aharonov
published in: Mathematical Problems in Engineering
publication date: 2018-08-27T00:00:00Z
review text: Summary: Estimation of distribution algorithms (EDAs) have been used to solve numerous hard problems. However, their use with in-group optimization problems has not been discussed extensively in the literature. A well-known in-group optimization problem is the multiple traveling salesmen problem (mTSP), which involves simultaneous assignment and sequencing procedures and are shown in different forms. This paper presents a new algorithm, named \(\mathrm{EDA}_{\mathrm{MLA}}\), which is based on self-guided genetic algorithm with a minimum loading assignment (MLA) rule. This strategy uses the transformed-based encoding approach instead of direct encoding. The solution space of the proposed method is only \(n!\). We compare the proposed algorithm against the optimal direct encoding technique, the two-part encoding genetic algorithm, and, in experiments on 34 TSP instances drawn from the TSPLIB, find that its solution space is \(n! {n - 1 \choose m - 1} \). The scale of the experiments exceeded that presented in prior studies. The results show that the proposed algorithm was superior to the two-part encoding genetic algorithm in terms of minimizing the total traveling distance. Notably, the proposed algorithm did not cause a longer traveling distance when the number of salesmen was increased from 3 to 10. The results suggest that EDA researchers should employ the MLA rule instead of direct encoding in their proposed algorithms.
Mathematics Subject Classification ID: 90C27
zbMATH DE Number: 6926879
Wikidata QID: Q59119208
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1155/2015/640231
OpenAlex ID: W1747072561
cites work: A decomposition based estimation of distribution algorithm for multiobjective traveling salesman problems
cites work: A self-guided genetic algorithm for permutation flowshop scheduling problems
cites work: A new approach to solving the multiple traveling salesperson problem using genetic algorithms
cites work: An Optimal Solution Method for Large-Scale Multiple Traveling Salesmen Problems
cites work: A Cutting Planes Algorithm for the m-Salesmen Problem
cites work: A multiple traveling salesman problem model for hot rolling scheduling in Shanghai Baoshan Iron \& Steel Complex
cites work: A genetic algorithm for service level based vehicle scheduling
cites work: A GROUPING GENETIC ALGORITHM FOR THE MULTIPLE TRAVELING SALESPERSON PROBLEM
cites work: A Novel Approach to Solve Multiple Traveling Salesmen Problem by Genetic Algorithm
cites work: A particle swarm optimizer for grouping problems
cites work: A genetic algorithm for hybrid flowshops with sequence dependent setup times and machine eligibility
cites work: A survey of optimization by building and using probabilistic models
cites work: Towards a new evolutionary computation. Advances on estimation of distribution algorithms.
cites work: An estimation of distribution algorithm for minimizing the total flowtime in permutation flowshop scheduling problems
cites work: Variable neighborhood search: Principles and applications
cites work: Q5555372
cites work: Data mining. Concepts and techniques
cites work: The multiple depot, multiple traveling salesmen facility-location problem: Vehicle range, service frequency, and heuristic implementations
cites work: A Lagrangian-based algorithm for a multiple depot, multiple traveling salesmen problem
cites work: Computational Experience with an M-Salesman Traveling Salesman Algorithm
cites work: Some Simple Applications of the Travelling Salesman Problem
cites work: A heuristic approach to the overnight security service problem
cites work: A crane scheduling method for port container terminals
cites work: Vehicle routing problem with time windows and simultaneous delivery and pick-up service based on MCPSO
cites work: Efficient coordinated motion.
description: scientific article; zbMATH DE number 6926879