Mixed-integer programming formulations for the truck scheduling problem with fixed outbound departures Rozwiązywanie problemu harmonogramowania przewozów przy ustalonych załadunkach
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.
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.
Ta witryna wykorzystuje pliki cookies do przechowywania informacji na Twoim komputerze. Pliki cookies stosujemy w celu świadczenia usług na najwyższym poziomie, w tym w sposób dostosowany do indywidualnych potrzeb. Korzystanie z witryny bez zmiany ustawień dotyczących cookies oznacza, że będą one zamieszczane w Twoim komputerze. W każdym momencie możesz dokonać zmiany ustawień dotyczących cookies
Informacja
SZANOWNI CZYTELNICY!
UPRZEJMIE INFORMUJEMY, ŻE BIBLIOTEKA FUNKCJONUJE W NASTĘPUJĄCYCH GODZINACH:
Wypożyczalnia i Czytelnia Główna: poniedziałek – piątek od 9.00 do 19.00