DECOMPOSITION OF THE TOUR USING MATHEMATICAL PROGRAMMING
Keywords:
Route-First Cluster-Second, Mathematical Programming, Vehicle Routing Problem, Xpress-IveAbstract
To solve tasks focused on the vertex service of the transport network, it is necessary to pay attention not only to the optimal sequence of vertices with respect to the selected optimization criterion (e.g. the total distance traveled), but also to other limitations that follow from the practical needs. The submitted contribution deals with introducing a decomposition method using mathematical programming based on the Route-First Cluster-Second approach. Firstly, the optimal route of the service vehicle is determined and then it can be decomposed into partial tours taking into account the capacity of the service vehicle. Mathematical models that can be used to implement this approach are presented in the text. The whole decomposition procedure is illustrated by specific examples, too.
Downloads
References
(2) JANÁČEK, J. Optimalizace na dopravních sítích. Žilina: Edis, 2002. 248 s. ISBN 80-8070-031-1.
(3) POMP, M., KOZEL, P., MICHALCOVÁ, Š., ORLÍKOVÁ, L. Using the Sweep Algorithm for decomposing a set of vertices and subsequent solution of the traveling salesman problém decomposed subsets In Proceedings of 35th International Conference Mathematical Methods in Economics 2017. Hradec Kralove: University of Hradec Kralove. Faculty of Informatics and Management, 2017.
(4) SKIENA, S., PEMMARAJU, S. Computational Discrete Mathematics. New York: Cambridge University Press, 2003. 480 s. ISBN 0-521-80686-0.
(5) JANÁČEK, J. Matematické programování. Žilina: Edis, 2003. 225 s. ISBN 80-8070-054-0.
(6) XPRESS-Mosel „User Guide“. Blisworth: Dash Associates, United Kingdom, 2005.
(7) FRIEDRICH, V. Matematika na počítači pro nematematiky. Ostrava: Vydavatelství VŠB-TU Ostrava, 2013. 268 s. ISBN 978-80-248-3162-6.
