PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2016 | 26 | 2 | 297-308
Tytuł artykułu

An optimal path planning problem for heterogeneous multi-vehicle systems

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
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.
Rocznik
Tom
26
Numer
2
Strony
297-308
Opis fizyczny
Daty
wydano
2016
otrzymano
2015-06-24
poprawiono
2015-11-05
zaakceptowano
2016-01-16
Twórcy
  • Institute of Information Engineering, Automation and Mathematics, Slovak University of Technology in Bratislava, Radlinského 9, Bratislava, Slovakia
  • Institute of Information Engineering, Automation and Mathematics, Slovak University of Technology in Bratislava, Radlinského 9, Bratislava, Slovakia
  • Institute of Information Engineering, Automation and Mathematics, Slovak University of Technology in Bratislava, Radlinského 9, Bratislava, Slovakia
Bibliografia
  • Applegate, D. (2006). The Traveling Salesman Problem: A Computational Study, Princeton Series in Applied Mathematics, Princeton University Press, Princeton, NJ.
  • Boyd, S. and Vandenberghe, L. (2009). Convex Optimization, 7th Edn., Cambridge University Press, New York, NY.
  • Fagerholt, K. (1999). Optimal fleet design in a ship routing problem, International Transactions in Operational Research 6(5): 453-464.
  • 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.
  • Gurobi Optimization (2013). Gurobi optimizer reference manual, http://www.gurobi.com.
  • 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.
  • ILOG (2007). 11.0 users manual, ILOG CPLEX Division, Incline Village, NV.
  • Kerrigan, E. and Maciejowski, J. (2000). Soft constraints and exact penalty functions in model predictive control, Control 2000 Conference, Cambridge, UK.
  • 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.
  • Kvasnica, M. (2008). Efficient Software Tools for Control and Analysis of Hybrid Systems, Ph.D. thesis, ETH Zurich, Zurich.
  • Löfberg, J. (2004). YALMIP, http://users.isy.liu. se/johanl/yalmip/.
  • 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.
  • 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.
  • Tung, D.V. and Pinnoi, A. (2000). Vehicle routingscheduling for waste collection in Hanoi, European Journal of Operational Research 125(3): 449 - 468.
  • Williams, H. (1993). Model Building in Mathematical Programming, 3rd Edn., John Wiley & Sons, Hoboken, NJ.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-amcv26i2p297bwm
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.