A Google Maps based novel approach to the optimization of multiple Traveling Salesman problem for limited distribution systems
Keywords:
mTSP, VRP, genetic algorithm, multi-chromosome, optimizationAbstract
The Vehicle Routing Problem (VRP) is a complex combinatorial optimization problem that can be described as follows: given a fleet of vehicles with uniform capacity, a common depot, and several costumer demands; find the set of routes with overall minimum route cost which service all the demands. The multiple traveling salesman problem (mTSP) is a generalization of the well-known traveling salesman problem (TSP), where more than one salesman is allowed to be used in the solution. It is well-known that mTSP based algorithms can also be utilized in several VRPs by incorporating some additional constraints. There are several exact algorithms of the mTSP with relaxation of some constraints of the problem. These approaches have serious importance because the solution what is supplied is optimal. Furthermore, due to the combinatorial complexity of mTSP, it is necessary to apply some heuristic in the solution, especially in real-sized applications. The aim of this paper is to discuss how genetic algorithms can be applied to solve these problems. It reviews the previous approaches with their disadvantages and proposes a novel, interpretable representation based algorithm. In this work, the effectiveness of the developed novel algorithm which based on the proposed representation will be demonstrated by several examples. The paper pans out about the implemented software solutions, like a new tool for calculation of distance table (on real routes) based on Google Maps API and a user-friendly tool for the drawing of the vehicle round trips. Furthermore, it proposes a complete framework and methodology to solve real problems. The new algorithm, a novel tool, and the resulted routes provide economically effective solutions for logistics which is proved by a real application.
References
Ali, A. I., Kennington, J. L. (1986). The asymmetric m-traveling salesmen problem: a duality based branch-and-bound algorithm. Discrete Applied Mathematics, 13. 2–3. 259–276. https://doi.org/10.1016/0166-218X(86)90087-9
Bektas, T. (2006). The multiple traveling salesman problem: an overview of formulations and solution procedures. Omega, 34. 3. 209–219. https://doi.org/10.1016/j.omega.2004.10.004
Bhide, S., John, N., Kabuka, M. R. (1993). A boolean neural network approach for the traveling salesman problem. IEEE Transactions on Computers, 42. 10. 1271–1278. https://doi.org/10.1109/12.257714
Burns, L. D., Hall, R. W., Blumenfeld, D. E., and Daganzo, C. F. (1985). Distribution strategies that minimize transportation and inventory costs. Operations Research, 33. 3. 469–490. https://doi.org/10.1287/opre.33.3.469
Carter, A. E., Ragsdale, C. T. (2006). A new approach to solving the multiple traveling salesperson problem using genetic algorithms. European Journal of Operational Research, 175. 1. 246–257. https://doi.org/10.1016/j.ejor.2005.04.027
Cavill, R., Smith, S., Tyrrell, (2005). A. Multi-chromosomal genetic programming. In Proceedings of the 2005 conference on Genetic and evolutionary computation, ACM New York, NY, USA, 1753–1759. https://doi.org/10.1145/1068009.1068300
Christopher, M. (1999). Logistics and supply chain management: strategies for reducing cost and improving service. International Journal of Logistics Research and Applications, 2. 1. 103–104. https://doi.org/10.1080/13675569908901575
Finke, G. (1986). Network flow based branch and bound method for asymmetric traveling salesman problems. In XI Symposium on Operations Research, Darmstadt, 117–119.
Glover, F. (1990). Artificial intelligence, heuristic frameworks and tabu search. Managerial and Decision Economics, 11. 5. 365–375. https://doi.org/10.1002/mde.4090110512
Goldberg, D. E. (1989). Genetic algorithms in search, optimization and machine learning. Addison-Wesley Longman Publishing Co., Inc. Boston, MA, USA
Gromicho, J., Paixao, J., Bronco, I. (1992). Exact solution of multiple traveling salesman problems. Combinatorial optimization: new frontiers in theory and practice, 291–292. https://doi.org/10.1007/978-3-642-77489-8_27
Holland, J. H. (1975). Adaptation in natural and artificial systems. The University of Michigan Press
Király A., Abonyi J. (to be published in 2011). Optimization of multiple traveling salesmen problem by a novel representation based genetic algorithm. In M. Koeppen, G. Schaefer, A. Abraham, and L. Nolle, editors, Intelligent Computational Optimization in Engineering: Techniques & Applications, Advances in Intelligent and Soft Computing. Springer. https://doi.org/10.1007/978-3-642-21705-0_9
Laporte, G., Nobert, Y. (1980). A cutting planes algorithm for the msalesmen problem. Journal of the Operational Research Society, 31. 11. 1017–1023. https://doi.org/10.1057/jors.1980.188
Malmborg, C. J. (1996). A genetic algorithm for service level based vehicle scheduling. European Journal of Operational Research, 93. 1. 121–134. https://doi.org/10.1016/0377-2217(95)00185-9
Miliotis, P. (1978). Using cutting planes to solve the symmetric travelling salesman problem. Mathematical Programming, 15. 1. 177–188. https://doi.org/10.1007/BF01609016
Park, Y.-B. (2001). A hybrid genetic algorithm for the vehicle scheduling problem with due times and time deadlines. International Journal of Productions Economics, 73. 2. 175–188. https://doi.org/10.1016/S0925-5273(00)00174-2
Pierrot, H. J., Hinterding, R. (1997). Multi-chromosomal genetic programming, vol. 1342/1997 of Lecture Notes in Computer Science. Springer, Berlin / Heidelberg, ch. Using multi-chromosomes to solve a simple mixed integer problem, 137–146. https://doi.org/10.1007/3-540-63797-4_66
Ronald, S., Kirkby, S. (1998). Compound optimization. solving transport and routing problems with a multi-chromosome genetic algorithm. In The 1998 IEEE International Conference on Evolutionary Computation, ICEC'98, 365–370.
Ross, S. M. (1984). Introduction to Probability Models. Macmillian, New York
Tanga, L., Liu, J., Rongc, A., Yanga, Z. (2000). A multiple traveling salesman problem model for hot rolling scheduling in shangai baoshan iron & steel complex. European Journal of Operational Research, 124. 2. 267–282. https://doi.org/10.1016/S0377-2217(99)00380-X
Toth, P., Vigo, D. (1987) The vehicle routing problem. Society for Industrial Mathematics
Yoshiji, F., Yuki, A., Tsuyoshi, Y. (2001). Applying the genetic algorithm with multi-chromosomes to order problems. Proceedings of the Annual Conference of JSAI, 13. 468–471.
Yu Z, Jinhai L, Guochang G, Rubo Z, and Haiyan Y. (2002). An implementation of evolutionary computation for path planning of cooperative mobile robots. Proceedings of the fourth world congress on intelligent control and automation, 3. 1798–1802.
Zhang, T., Gruver, W., Smith, M. (1999). Team scheduling by genetic search. Proceedings of the second international conference on intelligent processing and manufacturing of materials, 2. 839–844. https://doi.org/10.1109/IPMM.1999.791495
Downloads
Published
Issue
Section
License
Copyright (c) 2010 Király András, Abonyi János
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
