A path planning problem for a heterogeneous vehicle is considered. Such a vehicle consists of two parts which have the ability to move individually, but one of them has a shorter range and is therefore required to keep in a close distance to the main vehicle. The objective is to devise an optimal path of minimal length under the condition that at least one part of the heterogeneous system visits all desired waypoints exactly once. Two versions of the problem are considered. One assumes that the order in which the waypoints are visited is known a priori. In such a case we show that the optimal path can be found by solving a mixed-integer second-order cone problem. The second version assumes that the order in which the waypoints are visited is not known a priori, but can be optimized so as to shorten the length of the path. Two approaches to solve this problem are presented and evaluated with respect to computational complexity.
@article{bwmeta1.element.bwnjournal-article-amcv26i2p297bwm,
author = {Martin Klau\v co and Slavom\'\i r Bla\v zek and Michal Kvasnica},
title = {An optimal path planning problem for heterogeneous multi-vehicle systems},
journal = {International Journal of Applied Mathematics and Computer Science},
volume = {26},
year = {2016},
pages = {297-308},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-amcv26i2p297bwm}
}
Martin Klaučo; Slavomír Blažek; Michal Kvasnica. An optimal path planning problem for heterogeneous multi-vehicle systems. International Journal of Applied Mathematics and Computer Science, Tome 26 (2016) pp. 297-308. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-amcv26i2p297bwm/
[000] Applegate, D. (2006). The Traveling Salesman Problem: A Computational Study, Princeton Series in Applied Mathematics, Princeton University Press, Princeton, NJ. | Zbl 1130.90036
[001] Boyd, S. and Vandenberghe, L. (2009). Convex Optimization, 7th Edn., Cambridge University Press, New York, NY. | Zbl 1058.90049
[002] Fagerholt, K. (1999). Optimal fleet design in a ship routing problem, International Transactions in Operational Research 6(5): 453-464.
[003] Garone, E., Determe, J.-F. and Naldi, R. (2012). A travelling salesman problem for a class of heterogeneous multi-vehicle systems, 2012 IEEE 51st Annual Conference on Decision and Control (CDC), Maui, HI, USA, pp. 1166-1171.
[004] Gurobi Optimization (2013). Gurobi optimizer reference manual, http://www.gurobi.com.
[005] Hoff, A., Andersson, H., Christiansen, M., Hasle, G. and Lkketangen, A. (2010). Industrial aspects and literature survey: Fleet composition and routing, Computers & Operations Research 37(12): 2041 - 2061. | Zbl 1231.90091
[006] ILOG (2007). 11.0 users manual, ILOG CPLEX Division, Incline Village, NV.
[007] Kerrigan, E. and Maciejowski, J. (2000). Soft constraints and exact penalty functions in model predictive control, Control 2000 Conference, Cambridge, UK.
[008] Klaučo, M., Blažek, S., Kvasnica, M. and Fikar, M. (2014). Mixed-integer SOCP formulation of the path planning problem for heterogeneous multi-vehicle systems, European Control Conference 2014, Strasbourg, France, pp. 1474-1479.
[009] Kvasnica, M. (2008). Efficient Software Tools for Control and Analysis of Hybrid Systems, Ph.D. thesis, ETH Zurich, Zurich.
[010] Löfberg, J. (2004). YALMIP, http://users.isy.liu. se/johanl/yalmip/.
[011] Mathew, N., Smith, S. and Waslander, S. (2014). Optimal path planning in cooperative heterogeneous multi-robot delivery systems, 11th International Workshop on the Algorithmic Foundations of Robotics, Istanbul, Turkey.
[012] Miller, C.E., Tucker, A.W. and Zemlin, R.A. (1960). Integer programming formulation of traveling salesman problems, Journal of the ACM 7(4): 326-329. | Zbl 0100.15101
[013] Tung, D.V. and Pinnoi, A. (2000). Vehicle routingscheduling for waste collection in Hanoi, European Journal of Operational Research 125(3): 449 - 468. | Zbl 0967.90020
[014] Williams, H. (1993). Model Building in Mathematical Programming, 3rd Edn., John Wiley & Sons, Hoboken, NJ.