A random search algorithm for cyclic delivery synchronization problem

Gdowska, K.; Książek, R.

doi:10.17270/J.LOG.2017.3.2

Artykuł - szczegóły

Tytuł artykułu

A random search algorithm for cyclic delivery synchronization problem

Autorzy

Gdowska K. , Książek R.

Treść / Zawartość

Pełne teksty:

Pobierz

Identyfikatory

DOI

10.17270/J.LOG.2017.3.2

Warianty tytułu

Wykorzystanie algorytmu heurystycznego do rozwiązania problemu synchronizacji dostaw cyklicznych do centrów przeładunkowych

Języki publikacji

Abstrakty

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.

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.

Słowa kluczowe

cyclic delivery synchronization n problem mixed-integer programming optimization heuristic algorithms random search

harmonogramowanie dostaw cyklicznych programowanie całkowitoliczbowe mieszane optymalizacja synchronizacja algorytmy heurystyczne

Wydawca

Wyższa Szkoła Logistyki

Czasopismo

LogForum

Rocznik

2017

Tom

Vol. 13, no. 3

Strony

263--272

Opis fizyczny

Bibliogr. 35 poz., rys., tab.

Twórcy

autor

Gdowska K.

kgdowska@zarz.agh.edu.pl

AGH University of Science and Technology, Faculty of Management Department of Operations Research, 30 Mickiewicza Av., 30-059 Krakow, Poland

autor

Książek R.

rksiazek@zarz.agh.edu.pl

AGH University of Science and Technology, Faculty of Management Department of Operations Research, 30 Mickiewicza Av., 30-059 Krakow, Poland

Bibliografia

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/ICI L2016/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.

Uwagi

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017).

Typ dokumentu

Bibliografia

Identyfikator YADDA

bwmeta1.element.baztech-7956b5bb-23b3-49e6-bb6a-0e129130eac5