Using a Hybrid Simulated Annealing and Genetic Algorithms for Non Fixed Destination Multi-depot Multiple Traveling Salesmen Problem with Time Window and Waiting Penalty
-
2291
Downloads
-
3038
Views
Authors
M. T. Shirafkan
- Department of industrial engineering, Mazandaran University of Science and Technology, Babol, Iran
H. Seidgar
- Department of industrial engineering, Mazandaran University of Science and Technology, Babol, Iran
J. Rezaian-Zeidi
- Department of industrial engineering, Mazandaran University of Science and Technology, Babol, Iran
N. Javadian
- Department of industrial engineering, Mazandaran University of Science and Technology, Babol, Iran
Abstract
The non-fixed destination multi-depot multiple traveling salesmen problem (MmTSP) is a generalization of well-known MTSP with several salesmen in each depot. In this research, time window is defined for each depot (city).the salesmen only can service the customers within these time windows and also some penalties are considered for any deviation of start time. The objective function of problem is to minimize the total costs and penalties of the tours. This problem is of a great complexity and belongs to NP-complete class of problems. So the exact algorithms cannot perform the best solution in problems with big dimension. So Meta heuristics algorithm is used to solve these problems efficiently. In this research we used hybrid simulated annealing and genetic algorithms.
Share and Cite
ISRP Style
M. T. Shirafkan, H. Seidgar, J. Rezaian-Zeidi, N. Javadian, Using a Hybrid Simulated Annealing and Genetic Algorithms for Non Fixed Destination Multi-depot Multiple Traveling Salesmen Problem with Time Window and Waiting Penalty, Journal of Mathematics and Computer Science, 4 (2012), no. 3, 428--435
AMA Style
Shirafkan M. T., Seidgar H., Rezaian-Zeidi J., Javadian N., Using a Hybrid Simulated Annealing and Genetic Algorithms for Non Fixed Destination Multi-depot Multiple Traveling Salesmen Problem with Time Window and Waiting Penalty. J Math Comput SCI-JM. (2012); 4(3):428--435
Chicago/Turabian Style
Shirafkan, M. T., Seidgar, H., Rezaian-Zeidi, J., Javadian, N.. "Using a Hybrid Simulated Annealing and Genetic Algorithms for Non Fixed Destination Multi-depot Multiple Traveling Salesmen Problem with Time Window and Waiting Penalty." Journal of Mathematics and Computer Science, 4, no. 3 (2012): 428--435
Keywords
- Multiple traveling salesmen
- Genetic algorithm
- simulated annealing
- Time window
MSC
References
-
[1]
R. A. Russell, An effective heuristic for the m-tour traveling salesman problem with some side conditions, Operations Research, 25 (1977), 517--524
-
[2]
J. Y. Potvin, G. Lapalme, J. M. Rousseau, A generalized k-opt exchange procedure for the MTSP, INFOR: Information Systems and Operational Research, 27 (1989), 474--481
-
[3]
D. B. Fogel, A parallel processing approach to a multiple traveling salesman problem using evolutionary programming”, In: Proceedings of the fourth annual symposium on parallel processing, Proceedings of the fourth annual symposium on parallel processing, 1990 (1990), 318--326
-
[4]
E. Wacholder, J. Han, R. C. Mann, A neural network algorithm for the multiple traveling salesmen problem, Biology in Cybernetics, 61 (1989), 11--19
-
[5]
S. Somhom, A. Modares, T. Enkawa, Competition-based neural network for the multiple traveling salesmen problem with minmax objective, Computers and Operations Research, 26 (1999), 395--407
-
[6]
C. Y. Hsu, M. H. Tsai, W. M. Chen, A study of feature-mapped approach to the multiple travelling salesmen problem, IEEE International Symposium on Circuits and Systems, 3 (1991), 1589--1592
-
[7]
A. Modares, S. Somhom, T. Enkawa, A self-organizing neural network approach for multiple traveling salesman and vehicle routing problems, International Transactions in Operational Research, 6 (1999), 591--606
-
[8]
T. Zhang, W. A. Gruver, M. H. Smith, Team scheduling by genetic search, Proceedings of the second international conference on intelligent processing and manufacturing of materials, 2 (1999), 839--844
-
[9]
Z. Yu, L. Jinhai, G. Guochang, Z. Rubo, Y. Haiyan, An implementation of evolutionary computation for path planning of cooperative mobile robots, Proceedings of the 4th World Congress on Intelligent Control and Automation, 2002 (2002), 1798--1802
-
[10]
R. F. Da Silva, S. Urrutia, A General VNS heuristic for the traveling salesman problem with time windows, Discrete Optimization, 7 (2010), 203--211