Osman PARLAKTUNA, Aydın SİPAHİOĞLU, Ahmet YAZICI

A VRP-Based Route Planning for a Mobile Robot Group

In this study, a vehicle routing problem-based approach is presented to construct non-intersecting routes for the members of a mobile robot team. It is assumed that each robot starts from a central location such as the charging point, completes its route and returns to the starting location. The proposed method consists of three algorithms: a sweep algorithm determines the position of each node in clockwise (or counter clockwise) manner with respect to the starting location; savings algorithm calculates the saving obtained by adding a node to the route of a robot; Dijkstra's shortest path algorithm is used to calculate the shortest distance from any node to another one when the network is sparse. Simulations are performed using some benchmark VRP problems and results are compared with the optimal solution of the same problems. It is shown that our approach constructs routes significantly fast with near optimal energy consumption.

Anahtar Kelimeler:

Turk. J. Elec. Eng. & Comp. Sci., 15, (2007), 187-197. Full text: pdf Other articles published in the same issue: Turk. J. Elec. Eng. & Comp. Sci., vol.15, iss.2.

A VRP-Based Route Planning for a Mobile Robot Group

Keywords:

Turk. J. Elec. Eng. & Comp. Sci., 15, (2007), 187-197. Full text: pdf Other articles published in the same issue: Turk. J. Elec. Eng. & Comp. Sci., vol.15, iss.2.,

PDF

___

R. R. Murphy, Introduction to AI Robotics, The MIT Pres, 2000.
Z. Yu, L. Jinhai, G. Guochang, Z. Rubo, Y. Haiyan, “An implementation of evolutionary computation for path planning of cooperative mobile robots,” in Proc 4th World Congress on Intelligent Control and Automation, pp. 1798-1802, 2002.
S. Somhom, A. Modares, T. Enkawa, “Competition-based neural network for the multiple traveling salesmen problem with min-max objective,” Computers & Operations Research, vol. 26, pp. 395-407, 1999.
Z.X. Cai, Z.H. Peng, “Cooperative Co-evolutionary Adaptive Genetic Algorithm in Path Planning of Cooperative Multi-Mobile Robot Systems”, Journal of Intelligent & Robotic Systems, vol.33 (1), pp.61-71, 2002.
Y. Guo, L. E. Parker, “A distributed and optimal motion planning approach for multiple mobile robots,” in Proc IEEE International Conference on Robotics & Automation Washington DC, pp. 2612-2619, May 2002.
L. Zu , Y. Tian, J. Liu, “Algorithms of task-allocation and cooperation in multi mobile robot system,” in Proc 5th World Congress on Intelligent Control and Automation, Hangzhou, P.R. China, pp. 2841-2845, 2004.
M.C. Clark, S.M. Rock, J.C. Latombe, “Motion Planning For Multiple Mobile Robot Systems Using Dynamic Network”, Proceedings of the 2003 IEEE International Conference on Robotics & Automation, pp.4222-4227, 2003.
C. Ferrari, E. Pagello, J. Ota , T. Arai, “Multi-robot Motion Coordination in Space and Time”, Robotics and Autonomous Systems, vol. 25 (3-4), pp.219-229, 1998.
T. Schouwenaars, B.D. Moor, E. Feron, J. How, “Mixed Integer Programming For Multi-Vehicle Path Planning”, European Control Conference, pp. 2603-2608, 2001.
T. Arai, E. Pagello, L.E. Parker, “Advances in Multi-Robot Systems”, IEEE Transactions on Robotics and Automation, vol. 18 (5), pp.655-661, 2002.
J. Ota, “Multi-Agent Robot Systems as Distributed Autonomous Systems”, Advanced Engineering Informatics, vol.20(1), pp.59-70, 2006.
G. Laporte, “The traveling salesman problem: An overview of exact and approximate algorithms,” EJOR, Vol.59, pp. 231-247, 1992.
A. Punnen, “The traveling salesman problem applications, formulations and variations,” in The traveling salesman problem and its variations, edited by Gutin G., Punnen A.P. Kluwer Academic Publishers, 2002.
R.V. Kulkarni, P.R. Bhave, “Integer programming formulations of vehicle routing problem,” EJOR, Vol. 20, pp. 58-67, 1985.
T. Bektas, “The multiple traveling salesman problem: An overview of formulations and solutions procedures”, Omega-International Journal of Management Science, vol.34, no.3, pp.209-219, 2006.
G. Laporte, “The vehicle routing problem: An overview of exact and approximate algorithms,” EJOR, Vol. 59, pp. 345-358, 1992.
E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy-Kan, D.B. Shmoys, The traveling salesman problem, John Wiley & Sons, Newyork, 1985.
G. Laporte, F. Semet, “Classical heuristics for the capacitated VRP,” in The vehicle routing problem edited by Toth P., Vigo D., SIAM, 2002.
TSPLIB, 2006, Available: http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/
I. Kara, G. Laporte, T. Bekta¸s, “A Note on the Lifted Miller-Tucker Zemlin Sub Tour Elimination Constraints for the Capacitated Vehicle Routing Problem” European Journal of Operational Research, vol.158, pp.793-795, 2004.
B.L. Golden, W.L. Stewart, “Empirical analysis of heuristics”, in The traveling salesman problem, edited by Lawler et al., John Wiley & Sons, New York, 1985.
R.H. Ballou, Business logistics / supply chain management, 5th ed., Pearson and Prentice Hall, 2004.
R.K. Ahuja, T.L. Magnanti, J.B. Orlin, “Network ﬂows, theory algorithms, and applications,” Prentice Hall, 1993.
A. Yazıcı, A. Sipahio˘glu, O. Parlaktuna, U. G¨urel, “A Heuristic-Based Route Planning Approach for a Homo- geneous Multi-robot Team”, Proceedings of the 2006 IEEE International Symposium on Intelligent Control, Munich, Germany, pp.1237-1242, October 2006.
O. Parlaktuna, A. Sipahio˘glu, A. Yazıcı, U. G¨urel, “Tsp Approach For Mobile Robot Dynamic Path Planning,” The 1st International Conference on Control and Optimization with Industrial Application, Abstracts: pg.79, Baku (Azerbaijan), 2005.