BazEkon - Biblioteka Główna Uniwersytetu Ekonomicznego w Krakowie

BazEkon home page

Meny główne

Autor
Gdowska Katarzyna (AGH University of Science and Technology, Poland), Książek Roger (AGH University of Science and Technology, Poland)
Tytuł
A Random Search Algorithm for Cyclic Delivery Synchronization Problem
Wykorzystanie algorytmu heurystycznego do rozwiązania problemu synchronizacji dostaw cyklicznych do centrów przeładunkowych
Die Inanspruchnahme des Heuristischen Algorithmus für die Lösung des Problems der Synchronisation von Zyklischen Lieferungen zu Umschlagzentren
Źródło
LogForum, 2017, vol. 13, nr 3, s. 263-272, rys., tab., bibliogr. 35 poz.
Słowa kluczowe
Łańcuch dostaw, Harmonogram, Transport, Optymalizacja
Supply chain, Schedule, Transport, Optimalization
Uwagi
summ., streszcz., zfsg., This work was supported by AGH statutory fund - grant No. 15/11.200.357 and grant No. 15/11.200.356.
Abstrakt
Wstęp: W pracy przedstawiono problem synchronizowania dostaw cyklicznych do centrów przeładunkowych. Dostawy realizowane są na stałych trasach: pojazd, obsługujący daną trasę ma dostarczyć towar do centrum przeładunkowego, załadować tam inny towar i przewieźć go do kolejnego punktu trasy lub wykonać pusty przejazd do punktu załadunku. Punktami synchronizacji obsługi tras są centra logistyczne, w których niejednokrotnie towar przywieziony przez jeden pojazd, wyrusza w dalszą drogę innym. Dostawy na każdej trasie realizowane są ze stałą częstotliwością. Trasy dostaw oraz ilości przewożonego towaru są znane. Celem w zadaniu synchronizacji dostaw cyklicznych jest maksymalizacja liczby synchronizacji przyjazdów i pobytu pojazdów w centrach logistycznych tak, aby możliwe było grupowanie ich obsługi w bloki rozładunkowo-załadunkowe.
Metody: Na podstawie opracowanego wcześniej modelu matematycznego dla problemu synchronizowania dostaw cyklicznych do centrów przeładunkowych został zbudowany algorytm heurystyczny poszukujący rozwiązań poprzez ukierunkowane losowanie. W artykule przedstawiono opracowany algorytm losowego przeszukiwania.
Wyniki: Eksperyment obliczeniowy polegał na rozwiązaniu zestawu zadań synchronizowania dostaw cyklicznych przy pomocy opracowanego algorytmu i porównaniu uzyskanych wyników ze znanymi rozwiązaniami dokładnymi.
Wnioski: Przedstawiony algorytm heurystyczny dla zadania synchronizowania dostaw cyklicznych pozwala na uzyskanie rozwiązań zbliżonych do wyników otrzymanych przy zastosowaniu modelu programowania matematycznego. Zaletą zastosowanego algorytmu jest znaczne skrócenie czasu poszukiwania rozwiązania, co może mieć znaczenie dla praktycznego wykorzystania zaproponowanej metody. (abstrakt oryginalny)

Background: The paper is devoted to the cyclic delivery synchronization problem with vehicles serving fixed routes. Each vehicle is assigned to a fixed route: the series of supplier's and logistic centers to be visited one after another. For each route the service frequency is fixed and known in advance. A vehicle loads at a supplier's, then it delivers goods to a logistic center and either loads other goods there and delivers them to the next logistic center along the route or goes to another logistic center. Each logistic center can belong to several routes, so goods are delivered there with one vehicle and then they departure for the further journey with another truck. The objective of this cyclic delivery synchronization problem is to maximize the total number of synchronizations of vehicles arrivals in logistic centers and their load times, so that it is possible to organize their arrivals in repeatable blocks.
Methods: Basing on the previously developed mathematical model for the cyclic delivery synchronization problem we built a random search algorithm for cyclic delivery synchronization problem. The random heuristic search utilizes objective-oriented randomizing. In the paper the newly-developed random search algorithm for cyclic delivery synchronization problem is presented.
Results: A computational experiment consisted of employing the newly-developed random search algorithm for solving a series of cyclic delivery synchronization problems. Results obtained with the algorithm were compared with solutions computed with the exact method.
Conclusions: The newly-developed random search algorithm for cyclic delivery synchronization problem gives results which are considerably close to the ones obtained with mixed-integer programming. The main advantage of the algorithm is reduction of computing time; it is relevant for utilization of this method in practice, especially for large-sized problems. (original abstract)
Pełny tekst
Pokaż
Bibliografia
Pokaż
  1. Ait Haddadene S.R., Labadie N., Prodhon C., 2016, A GRASP × ILS for the vehicle routing problem with time windows, synchronization and precedence constraints, Expert Systems with Applications, 66, 274-294, http://dx.doi.org/10.1016/j.eswa.2016.09.002.
  2. Akkerman R., Farahani P., Grunow M., 2010, Quality, safety and sustainability in food distribution: a review of quantitative operations management approaches and challenges, OR Spectrum 32, 863-904, http://dx.doi.org/10.1007/s00291-010-0223-2.
  3. Azadeh A., Elahi S., Hosseinabadi Farahani M., Nasirian B., 2017, A genetic algorithm-Taguchi based approach to inventory routing problem of a single perishable product with transshipment, Computers & Industrial Engineering, 104, 124-133, http://dx.doi.org/10.1016/j.cie.2016.12.019
  4. Campbell A.M., Hardin J.R., 2005, Vehicle minimization for periodic deliveries, European Journal of Operational Research, 165, 668-684, http://dx.doi.org/10.1016/j.ejor.2003.09.036
  5. Ceder A., Golany B., Tal O., 2001, Creating bus timetables with maximal synchronization, Transportation Research Part A, 35, 913-928. Available on the Internet: https://web.iem.technion.ac.il/images/userfiles/golany/papers/TR_A_01.pdf (02/25/2017)
  6. Ching-Ter Ch., Hsiao-Ching Ch., 2013, A coordination system for seasonal demand problems in the supply chain, Applied Mathematical Modelling, 37, 3674-3686, http://dx.doi.org/10.1016/j.apm.2012.07.061.
  7. Chitsaz M., Divsalar A., Vansteenwegen P., 2016, A two-phase algorithm for the cyclic inventory routing problem, European Journal of Operational Research, 254, 410-426, http://dx.doi.org/10.1016/j.ejor.2016.03.056
  8. De Giovanni P., Reddy P.V., Zaccour G., 2016, Incentive strategies for an optimal recovery program in a closed-loop supply chain, European Journal of Operational Research, 149(2), 605-617, http://dx.doi.org/10.1016/j.ejor.2015.09.021
  9. Ekici A., Özener O., Kuyzu G., 2015, Cyclic Delivery Schedules for an Inventory Routing Problem, Transportation Science, 49(4), 817-829, http://dx.doi.org/10.1287/trsc.2014.0538.
  10. Emde S., Gendreau M., 2017, Scheduling inhouse transport vehicles to feed parts to automotive assembly lines, European Journal of Operational Research, 260(1), 255-267, http://dx.doi.org/10.1016/j.ejor.2016.12.012
  11. Eranki A., 2004, A model to create bus timetables to attain maximum synchronization considering waiting times at transfer stops, masters' thesis, Department of Industrial and Management System Engineering, University of South Florida. Available on the Internet: http://scholarcommons.usf.edu/cgi/viewcontent.cgi?article=2024&context=etd (02/25/2017).
  12. Gdowska K.Z., Książek R., 2013, Cyclic delivery scheduling problem for customers with different priorities. LogForum 9(4), 283-292. Available on the Internet: http://www.logforum.net/pdf/9_4_7_13.pdf (03/25/2017).
  13. Gdowska K.Z., Książek R., 2015, Cyclic delivery-scheduling problem with synchronization of vehicles' arrivals at logistic centers. LogForum 11(4), 341-350, http://dx.doi.org/10.17270/J.LOG.2015.4.3
  14. Gudehus T., Kotzab H., 2009, Comprehensive Logistics, Springer, Berlin Heidelberg New York.
  15. Groenevelt H., Johansen J., Lederer P.J., 1992, Cyclic Planning, University of Rochester, New York.
  16. Huynha C.H., So K.C., Gurnani H., 2016, Managing a closed-loop supply system with random returns and a cyclic delivery schedule, European Journal of Operational Research, 255, 787-796, http://dx.doi.org/10.1016/j.ejor.2016.05.035
  17. Ibarra-Rojas O.J., Rios-Solis Y.A., 2012, Synchronization of bus timetabling, Transportation Research Part B, 46, 599-614, http://dx.doi.org/10.1016/j.trb.2012.01.006.
  18. Kazan O., Dawande M., Sriskandarajah Ch., Stecke K.E., 2012, Balancing perfectly periodic service schedules: An application from recycling and waste management, Naval Research Logistics (NRL), 59(2), 160-171, http://dx.doi.org/10.1002/nav.21479.
  19. Korcyl A., Książek R., Gdowska K., 2016, A MILP model for route optimization problem in a municipal multi-landfill waste collection system, In: T. Sawok (ed.), 13th International Conference on Industrial Logistics, ICIL 2016 - Conference Proceedings, 109-118. Available on the Internet: http://www.icil.zarz.agh.edu.pl/images/ICIL2016/ICIL2016_conference_proceedings_final.pdf (03/28/2017).
  20. Laporte G., Ortega F.A., Pozo M.A., Puerto J., 2017, Multi-objective integration of timetables, vehicle schedules and user routings in a transit network, Transportation Research Part B, 98, 94-112, http://dx.doi.org/10.1016/j.trb.2016.12.018.
  21. Lee S.-D., Fu Y.-C., 2014, Joint production and delivery lot sizing for a make-to-order producer-buyer supply chain with transportation cost, Transportation Research Part E, 66, 23-35, http://dx.doi.org/10.1016/j.tre.2014.03.002.
  22. Lefever W., Aghezzaf E.-H., Hadj-Hamou K., 2016, A convex optimization approach for solving the single-vehicle cyclic inventory routing problem, Computers & Operations Research, 72, 97-106, http://dx.doi.org/10.1016/j.cor.2016.02.010.
  23. Leunga J.Y.-T., Chen Z.-L., 2013, Integrated production and distribution with fixed delivery departure dates, Operations Research Letters, 41(3), 290-293, http://dx.doi.org/10.1016/j.orl.2013.02.006.
  24. Mes M., Schutten M., Rivera A.P., 2014, Inventory routing for dynamic waste collection, Waste Management, 34(9), 1564-1576, http://dx.doi.org/10.1016/j.wasman.2014.05.011.
  25. Mirzapour Al-e-hashem S.M.J., Rekik Y., 2014, Multi-product multi-period Inventory Routing Problem with a transshipment option: A green approach, International Journal of Production Economics, 157, 80-88, http://dx.doi.org/10.1016/j.ijpe.2013.09.005
  26. Raa B., 2014, Cyclic Versus Reactive Planning for Inventory Routing, Procedia - Social and Behavioral Sciences, 111, 909-917, http://dx.doi.org/10.1016/j.sbspro.2014.01.125.
  27. Raa B., 2015, Fleet optimization for cyclic inventory routing problems, International Journal of Production Economics, 160, 172-181, http://dx.doi.org/10.1016/j.ijpe.2014.10.006
  28. Raa B., Dullaert W., 2007, Fleet and Route Design for Cyclic Distribution Problems [in:] Evolutionary and deterministic methods for design, optimization and control. Proceedings of EUROGEN 2007: Evolutionary and deterministic methods for design, optimization and control with applications to industrial and societal problems, 416-421.
  29. Raa B., Dullaert W., 2017, Route and fleet design for cyclic inventory routing, European Journal of Operational Research, 256, 404-411, http://dx.doi.org/10.1016/j.ejor.2016.06.009
  30. Rad R.H., Razmi J., Sangari M.S., Ebrahimi Z.F., 2014, Optimizing an integrated vendor-managed inventory system for a single-vendor two-buyer supply chain with determining weighting factor for vendor's ordering cost, International Journal of Production Economics, 153, 295-308, http://dx.doi.org/10.1016/j.ijpe.2014.03.013
  31. Qin L., Miao L., Ruan Q., Zhang Y., 2014, A local search method for periodic inventory routing problem, Expert Systems with Applications, 41(2), 765-778, http://dx.doi.org/10.1016/j.eswa.2013.07.100.
  32. Ullrich Ch.A., 2013, Integrated machine scheduling and vehicle routing with time windows, European Journal of Operational Research, 227, 152-165, http://dx.doi.org/10.1016/j.ejor.2012.11.049
  33. Vansteenwegen P., Mateo M., 2014, An iterated local search algorithm for the single-vehicle cyclic inventory routing problem, European Journal of Operational Research, 237(3), 802-813, http://dx.doi.org/10.1016/j.ejor.2014.02.020
  34. Vose M.D., 1999, Random heuristic search, Theoretical Computer Science, 229(1-2), 103-142, http://dx.doi.org/10.1016/S0304-3975(99)00120-6.
  35. Zheng J., Meng Q., Sun Z., 2015, Liner huband-spoke shipping network design, Transportation Research Part E, 75, (2015) 32-48, http://dx.doi.org/10.1016/j.tre.2014.12.014.
Cytowane przez
Pokaż
ISSN
1895-2038
Język
eng
URI / DOI
http://dx.doi.org/10.17270/J.LOG.2017.3.2
Udostępnij na Facebooku Udostępnij na Twitterze Udostępnij na Google+ Udostępnij na Pinterest Udostępnij na LinkedIn Wyślij znajomemu