Using a Hybrid Simulated Annealing and Genetic Algorithms for Non Fixed Destination Multi-depot Multiple Traveling Salesmen Problem with Time Window and Waiting Penalty

Volume 4, Issue 3, pp 428--435 http://dx.doi.org/10.22436/jmcs.04.03.17

Download PDF

Download XML

• Export citations
  • CITATIONS & REFERENCES
  • EndNote (.ENW)
  • Mendeley, JabRef (.BIB)
  • Papers, Zotero, Reference Manager, RefWorks (.RIS)
  • ARTICLE CITATION
  • EndNote (.ENW)
  • Mendeley, JabRef (.BIB)
  • Papers, Zotero, Reference Manager, RefWorks (.RIS)
  • REFERENCES
  • EndNote (.ENW)
  • Mendeley, JabRef (.BIB)
  • Papers, Zotero, Reference Manager, RefWorks (.RIS)

• 2186 Downloads
• 2906 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

Keywords

• Multiple traveling salesmen
• Genetic algorithm
• simulated annealing
• Time window

MSC

•  90C29
•  90C59

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
  • View Article
  • Google Scholar


• [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
  • View Article
  • Google Scholar


• [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
  • Google Scholar


• [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
  • View Article
  • Google Scholar


• [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
  • View Article
  • Google Scholar


• [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
  • View Article
  • Google Scholar


• [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
  • View Article
  • Google Scholar


• [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
  • View Article
  • Google Scholar


• [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
  • View Article
  • Google Scholar


• [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
  • View Article
  • Google Scholar