Mixed-Integer Programming Formulations for the Truck Scheduling Problem With Fixed Outbound Departures

• Autorzy: Pascal Wolff , Jiazhen Huo , Hans-Christian Pfohl

Warianty tytułu

Rozwiązywanie problemu harmonogramowania przewozów przy ustalonych załadunkach

• Języki publikacji: EN

Abstrakty

Wstęp: Harmonogramowanie przewozów oraz cross-dockingu leży w zasięgu zainteresowania uczonych już od ponad 30 lat. W tym okresie zaproponowało wiele różnych modeli programistycznych tablic awizacyjnych. Jednak zaledwie kilka modeli bierze pod uwagę stałe załadunki, które często są stosowane w przewozach niepełno samochodowych oraz kurierskich. Według naszego rozeznania, żaden z dostępnych modeli nie stosuje modelowania czasem w sposób dyskretny lub ciągły dla uzyskania lepszego wyniku. Celem pracy jest uzupełnienie tej luki w badaniach. Dlatego też rozważono wariant problemu harmonogramowania przewozów ze stałymi załadunkami z celem nadrzędnym znalezienia takiego sposobu harmonogramowania aby minimalizował on liczbę opóźnionych przewozów. Metody: Zaproponowano dwa modele, opisujące harmonogramowanie przewozów ze stałymi załadunkami. Problem ten został sformułowany poprzez model programistyczny ze zmienną czasu w ujęciu dyskretnym i ciągłym. Wyniki: Przeprowadzono symulację komputerową w celu określenie działania opracowanych modeli. Porównano wyniki pod względem jakości uzyskanego wyniku oraz niezbędnego czasu dla obliczeń. Wnioski: Na podstawie uzyskanych wyników można stwierdzić, że proponowany model dyskretny może rozwiązywać problem średniej wielkości w czasie niższej niż minuta. Model oparty na czasie ciągłym uzyskał z kolei optymalizację przy małych przypadkach. Wymagało to jednak dłuższego czasu obliczeniowego. Dodatkowo nie uzyskano dla rozwiązań średniej wielkości czasu niższego od 5 minut. Dlatego też wysunięto wniosek, że model dyskretny jest lepszym w porównaniu z modelem ciągłym.(abstrakt oryginalny)

EN

Background: Truck scheduling at cross-docking terminals has received much academic attention over the last three decades. A vast number of mixed-integer programming models have been proposed to assign trucks to dock-doors and time slots. Surprisingly, only a few models assume fixed outbound truck departures that are often applied in the less-than-truckload or small parcel and express delivery industry. To the best of our knowledge, none of these papers explore whether a discrete-time or continuous-time model formulation has a better computational performance. This paper attempts to close this research gap and tries to shed light on which type of formulation is advantageous. Therefore, a variant of the truck scheduling problem with fixed outbound departures is considered. This problem's objective is to find a feasible truck schedule that minimizes the number of delayed freight units. Methods: We propose two model formulations for the described variant of the truck scheduling problem with fixed outbound departures. Specifically, the problem is formulated as a discrete-time and a continuous-time mixed-integer programming model. Results: A computational experiment is conducted in order to assess the computational performance of the presented model formulations. We compare the discrete-time and continuous-time formulation in terms of both the solution quality and computational time. Conclusions: The computational results show that the proposed discrete-time model formulation can solve problem instances of medium size to proven optimality within less than one minute. The continuous-time model formulation, on the other hand, can solve small instances to optimality. However, it requires longer solution times than the discrete-time formulation. Furthermore, it is unable to solve medium-sized instances within a 5-minute time limit. Thus, it can be summarized that the proposed discrete-time model formulation is clearly superior to the continuous-time model formulation.(original abstract)

Słowa kluczowe

PL

Logistyka; Przewozy towarowe; Optymalne przemieszczanie ładunków

EN

Logistics; Cargo transportation; Optimal handling of loads

• Czasopismo: LogForum
• Rocznik: 2021
• Tom: 17
• Numer: nr 2
• Strony: 243-251

Twórcy

autor

Pascal Wolff

• Tongji University, Shanghai, China

autor

Jiazhen Huo

• Tongji University, Shanghai, China

autor

Hans-Christian Pfohl

• Technical University of Darmstadt, Darmstadt, Germany

Bibliografia

• Bartholdi J.J., Gue K.R., Kang K., 2008. Staging protocols for unit-load crossdocking, in Lahmar, M. (Ed.), Facility logistics. Approaches and solutions to next generation challenges, Auerbach Publications, Boca Raton, FL, 153-171, http://doi.org/10.1201/9781420013719.
• Boysen N. Fliedne, M., 2010. Cross dock scheduling: Classification, literature review and research agenda, Omega, 38(6):413- 422, http://doi.org/10.1016/j.omega.2009.10.008
• Boysen N., Briskorn D., Tschöke M., 2013. Truck scheduling in cross-docking terminals with fixed outbound departures, OR Spectrum, 35(2):479-504, http://doi.org/10.1007/s00291-012-0311-6.
• Buijs P., Vis I.F., Carlo H.J., 2014, Synchronization in cross-docking networks: A research classification and framework, European Journal of Operational Research, 239(3):593-608, http://doi.org/10.1016/j.ejor.2014.03.012.
• Chmielewski A., Naujoks B., Janas M., Clausen U., 2009. Optimizing the door assignment in LTL-terminals, Transportation Science, 43(2):198-210, http://doi.org/10.1287/trsc.1090.0271.
• Forger G., 1995. UPS starts world's premiere cross-docking operation, Modern Material Handling, 36-38.
• Gue K.R., 1999. The effects of trailer scheduling on the layout of freight terminals, Transportation Science, 33(4):419-428, http://doi.org/10.1287/trsc.33.4.419.
• Ladier A.L. Alpan G. 2016. Cross-docking operations: Current research versus industry practice, Omega, 62:145-162, http://doi.org/10.1016/j.omega.2015.09.006
• Lamorgese L., Mannino C., 2019, A noncompact formulation for job-shop scheduling problems in traffic management, Operations Research, 67(6):1586-1609, http://doi.org/10.1287/opre.2018.1837.
• Molavi D., Shahmardan A., Sajadieh M.S, 2018. Truck scheduling in a cross docking systems with fixed due dates and shipment sorting, Computers and Industrial Engineering, 117:29-40, http://doi.org/10.1016/j.cie.2018.01.009.
• Rahmanzadeh Tootkaleh S., Fatemi Ghomi S.M., Sheikh Sajadieh M, 2016. Cross dock scheduling with fixed outbound trucks departure times under substitution condition, Computers and Industrial Engineering, 92:50-56, http://doi.org/10.1016/j.cie.2015.12.005.
• Rijal A., Bijvank M., de Koster R, 2019. Integrated scheduling and assignment of trucks at unit-load cross-dock terminals with mixed service mode dock doors, European Journal of Operational Research, 278(3):752-771, http://doi.org/10.1016/j.ejor.2019.04.028.
• Serrano C., Delorme X., Dolgui A, 2017. Scheduling of truck arrivals, truck departures and shop-floor operation in a cross-dock platform, based on trucks loading plans, International Journal of Production Economics, 194:102-112, http://doi.org/10.1016/j.ijpe.2017.09.008.
• Shakeri M., Low M.Y.H., Turner S.J., Lee E.W., 2012. A robust two-phase heuristic algorithm for the truck scheduling problem in a resource-constrained crossdock, Computers and Operations Research, 39(11):2564-2577, http://doi.org/10.1016/j.cor.2012.01.002.
• Stalk G., Evans P., Shulman L.E., 1992. Competing on capabilities: The new rules of corporate strategy, Harvard Business Review, 70(2):57-68.
• Tadumadze G., Boysen N., Emde S., Weidinger F., 2019. Integrated truck and workforce scheduling to accelerate the unloading of trucks, European Journal of Operational Research, 278(1):343-362, http://doi.org/10.1016/j.ejor.2019.04.024.
• Van Belle J., Valckenaers P., Cattrysse D., 2012. Cross-docking: State of the art, Omega, 40(6):827-846, http://doi.org/10.1016/j.omega.2012.01.005
• Van Belle J., Valckenaers P., Vanden Berghe G., Cattrysse D., 2013. A tabu search approach to the truck scheduling problem with multiple docks and time windows, Computers and Industrial Engineering, 66(4):818-826, http://doi.org/10.1016/j.cie.2013.09.024.
• Witt C.E., 1998, Crossdocking: Concepts demand choice, Material Handling Engineering, 53(7):44-49.

Identyfikatory

DOI

10.17270/J.LOG.2021.572