Geodesic
An optimal path planning problem for heterogeneous multi-vehicle systems
International Journal of Applied Mathematics and Computer Science, Tome 26 (2016) no. 2, pp. 297-308.

Voir la notice de l'article provenant de la source Library of Science

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.
Keywords: path planning, multi vehicle system, mixed-integer programming
Mots-clés : planowanie ruchu, system wielopojazdowy, programowanie całkowitoliczbowe 
@article{IJAMCS_2016_26_2_a3,
     author = {Klau\v{c}o, M. and Bla\v{z}ek, S. and Kvasnica, M.},
     title = {An optimal path planning problem for heterogeneous multi-vehicle systems},
     journal = {International Journal of Applied Mathematics and Computer Science},
     pages = {297--308},
     publisher = {mathdoc},
     volume = {26},
     number = {2},
     year = {2016},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/IJAMCS_2016_26_2_a3/}
}
TY  - JOUR
AU  - Klaučo, M.
AU  - Blažek, S.
AU  - Kvasnica, M.
TI  - An optimal path planning problem for heterogeneous multi-vehicle systems
JO  - International Journal of Applied Mathematics and Computer Science
PY  - 2016
SP  - 297
EP  - 308
VL  - 26
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/IJAMCS_2016_26_2_a3/
LA  - en
ID  - IJAMCS_2016_26_2_a3
ER  - 
%0 Journal Article
%A Klaučo, M.
%A Blažek, S.
%A Kvasnica, M.
%T An optimal path planning problem for heterogeneous multi-vehicle systems
%J International Journal of Applied Mathematics and Computer Science
%D 2016
%P 297-308
%V 26
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/IJAMCS_2016_26_2_a3/
%G en
%F IJAMCS_2016_26_2_a3
Klaučo, M.; Blažek, S.; Kvasnica, M. An optimal path planning problem for heterogeneous multi-vehicle systems. International Journal of Applied Mathematics and Computer Science, Tome 26 (2016) no. 2, pp. 297-308. http://geodesic.mathdoc.fr/item/IJAMCS_2016_26_2_a3/

[1] Applegate, D. (2006). The Traveling Salesman Problem: A Computational Study, Princeton Series in Applied Mathematics, Princeton University Press, Princeton, NJ.

[2] Boyd, S. and Vandenberghe, L. (2009). Convex Optimization, 7th Edn., Cambridge University Press, New York, NY.

[3] Fagerholt, K. (1999). Optimal fleet design in a ship routing problem, International Transactions in Operational Research 6(5): 453–464.

[4] 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.

[5] Gurobi Optimization (2013). Gurobi optimizer reference manual, http://www.gurobi.com.

[6] 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.

[7] ILOG (2007). 11.0 users manual, ILOG CPLEX Division, Incline Village, NV.

[8] Kerrigan, E. and Maciejowski, J. (2000). Soft constraints and exact penalty functions in model predictive control, Control 2000 Conference, Cambridge, UK.

[9] 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.

[10] Kvasnica, M. (2008). Efficient Software Tools for Control and Analysis of Hybrid Systems, Ph.D. thesis, ETH Zurich, Zurich.

[11] Löfberg, J. (2004). YALMIP, http://users.isy.liu.se/johanl/yalmip/.

[12] 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.

[13] 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.

[14] Tung, D.V. and Pinnoi, A. (2000). Vehicle routingscheduling for waste collection in Hanoi, European Journal of Operational Research 125(3): 449–468.

[15] Williams, H. (1993). Model Building in Mathematical Programming, 3rd Edn., John Wiley Sons, Hoboken, NJ.