In this thesis, the main focus is on the study of a real-world transportation problem with uncertainties, and on the comparison of a centralized and a distributed solution approach in the context of this problem. We formalize the real-world problem, and provide a general framework to extend it with different sources of uncertainty. We apply computer simulations to compare the two solution approaches, and provide experimental results for three uncertainty types. In release-time uncertainty instances, new orders arrive at random times during the execution of previously planned orders. In service-time uncertainty cases, the time spent by the trucks at pick-up or delivery locations are defined according to a random distribution. In truck-breakdown uncertainty instances, some of the trucks break down at random times. Finally, we also examine cases with different combinations of these uncertainties.