Bi-objective routing in a dynamic network: An application to maritime logistics

• Autorzy: Maskooki Alaleh , Nikulin Yury
• Języki publikacji: EN

Abstrakty

EN

A bi-objectiveMILP model for optimal routing in a dynamic network with moving targets (nodes) is developed, where all targets are not necessarily visited. Hence, our problem extends the moving target travelling salesman problem. The two objectives aim at finding the sequence of targets visited in a given time horizon by minimizing the total travel distance and maximizing the number of targets visited. Due to a huge number of binary variables, such a problem often becomes intractable in the real life cases. To reduce the computational burden, we introduce a measure of traffic density, based on which we propose a time horizon splitting heuristics. In a real-world case study of greenhouse gas emissions control, using Automatic Identification System data related to the locations of ships navigating in the Gulf of Finland, we evaluate the performance of the proposed method. Different splitting scenarios are analysed numerically. Even in the cases of a moderate scale, the results show that near-efficient values for the two objectives can be obtained by our splitting approach with a drastic decrease in computational time compared to the exact MILP method. A linear value function is introduced to compare the Pareto solutions obtained by different splitting scenarios. Given our results, we expect that the present study is valuable in logistic applications, specifically maritime management services and autonomous navigation.

Słowa kluczowe

EN

travelling salesman; time dependent network; multi-objective optimization; integer programming

• Wydawca: Systems Research Institute, Polish Academy of Sciences
• Czasopismo: Control and Cybernetics
• Rocznik: 2020
• Tom: Vol. 49, No. 2
• Strony: 211--232
• Opis fizyczny: Bibliogr. 29 poz., rys., tab.

Twórcy

autor

Maskooki Alaleh

• University of Turku, Department of Mathematics and Statistics, FI-20014 Turku, Finland

autor

Nikulin Yury

• University of Turku, Department of Mathematics and Statistics, FI-20014 Turku, Finland

Bibliografia

• ABELEDO, H., FUKASAWA, R., PESSOA, A. AND UCHOA, E. (2013) The time dependent traveling salesman problem: Polyhedra and algorithm. Mathematical Programming Computation, 5, 27–55.
• ANDROUTSOPOULOS, K. AND ZOGRAFOS, K. (2009) Solving the multi-criteria timedependent routing and scheduling problem in a multimodal fixed scheduled network. European Journal of Operational Research, 192, 18–28.
• APPLEGATE, D., BIXBY, R., CHV´ATAL, V. AND COOK, W. (2007) The Traveling Salesman Problem: A Computational Study. Princeton University Press, Princeton, NJ, USA, 2007.
• BIANCO, L., MINGOZZI, A. AND RICCIARDELLI, S. (1993) The traveling salesman problem with cumulative costs. Networks, 23, 81–91.
• BRANKE, J., DEB, K., MIETTINEN, K. AND SŁOWI´NSKI, R. (2008) Multiobjective Optimization: Interactive and Evolutionary Approaches. Springer-Verlag, Berlin, Heidelberg, Germany, 2008.
• FOX, K. (1973) Production scheduling on parallel lines with dependencies. Ph.D. dissertation, Johns Hopkins University, Baltimore, Md, 1973.
• FOX, K., GAVISH, B. AND GRAVES, S. (1980) An n-constraint formulation of the (time-dependant) traveling salesman problem. Operations Research, 28, 1019–1021.
• FURINI, F., PERSIANI, C. AND TOTH, P. (2016) The time dependent traveling salesman planning problem in controlled airspace. Transportation Research Part B: Methodological, 90, 38–55.
• GAREY, M. AND JOHNSON, D. (1979) Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York, NY, USA, 1979.
• Github (2020) Github Repository Dynamic-TSP project, Online; accessed June 2020.
• GROBA, C., SARTAL, A. AND V´A ZQUEZ, X. (2015) Solving the dynamic travelling salesman problem using a genetic algorithm with trajectory prediction: An application to fish aggregating devices. Computers and Operations Research, 56, 22–32.
• HELVIG, C., ROBINS, G. AND ZELIKOVSKY, A. (2003) The moving-target travelling salesman problem. Journal of Algorithms, 49, 153–174.
• HEWGLEY, C. AND YAKIMENKO, O. (2012) Precision guided airdrop for vertical replenishment of naval vessels. 20th AIAA Aerodynamic Decelerator Systems Technology Conference and Seminar, May 2009, Seattle, Washington, 2012.
• LUCENA, A. (1990) Time-dependant traveling salesman problem-the deliveryman case. Networks, 20, 753–763.
• MALANDRAKI, C. AND DASKIN, M. (1992) Time dependent vehicle routing problems: Formulations, properties and heuristic algorithms. Transportation Science, 26, 185–200.
• MARLOW, D., KILBY, P. AND MERCER, G. (2007) The travelling salesman problem in maritime surveillance-techniques, algorithms and analysis. Proceedings of the International Congress on Modelling and Simulation, 2007, 684–690.
• MIETTINEN, K. (1998) Nonlinear Multiobjective Optimization. Kluwer Academic Publishers, Springer, Boston, MA, 1998.
• MIKKONEN, M. (2019) Järjestö: Maailman suurimman risteilyvarustamon laivat äästivät Euroopassa rikkiä kymmenen kertaa enemm¨an kuin kaikki autot yhteensä. Helsingin Sanomat, published June 8, 2019.
• PAPADIMITRIOU, C. AND STEIGLITZ, K. (1982) Combinatorial Optimization: Algorithms and Complexity, Prentice-Hall, Inc., NJ, USA, 1982.
• PICARD, J. AND QUEYRANNE, M. (1978) The time-dependent traveling salesman problem and its application to the tardiness problem in one-machine scheduling, Operations Research, 26, 86–110.
• REGO, C., GAMBOA, D., GLOVER, F. AND OSTERMAN, C. (2011) Traveling salesman problem heuristics: Leading methods, implementations and latest advances. European Journal of Operational Research, 211, 427–441.
• RIQUELME, N., LÜCKEN, C. AND BAR´A N, B. (2015) Performance metrics in multiobjective optimization. Latin American Computing Conference (CLEI), 2015.
• TAŞ , D., GENDREAU, M., JABALI, O. AND LAPORTE, G. (2016) The traveling salesman problem with time-dependent service times. European Journal of Operational Research, 248, 372–383.
• VANDER WIEL, R. AND SAHINIDIS, N. (1996) An exact solution approach for the time-dependent traveling-salesman problem. Naval Research Logistics, 43, 797–820.
• VIRJONEN, P., NEVALAINEN, P., PAHIKKALA, T. AND HEIKKONEN, J. (2018) Ship movement prediction using k-NN method. Proceedings of the Baltic Geodetic Congress (Geomatics), Olsztyn, Poland, 2018, No. 56.
• VU, D., HEWITT, M., BOLAND, N. AND SAVELSBERGH, M. (2019) Dynamic Discretization Discovery for Solving the Time Dependent Traveling Salesman Problem with Time Windows. Transportation Science, 54, 703–720.
• VÄYLÄ VIRASTO (2019)Väylävirasto (Finnish Transport InfrastructureAgency), vayla.fi. Online; accessed October 2019.
• WIERZBICKI, A. (1982) A mathematical basis for satisficing decision making. Mathematical Modelling, 3, 391–405.
• ZITZLER, E., KNOWLES, J. AND THIELE, L. (2008) Quality Assessment of Pareto Set Approximations. In: J. Branke et al., eds.,: Multiobjective Optimization, LNCS 5252, 373-404, Springer- Verlag Berlin Heidelberg, 2008.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2021).