Cardiovascular diseases are the major cause of death in the world. Modern revascularization techniques allow to bypass occluded blood vessels, a typical symptom of atherosclerosis. Among the material and location of the bypass graft, its shape -- in particular the shape of the downstream connection (anastomosis) to the host artery -- plays a crucial role in the success of a bypass surgery. Unnatural blood flow patterns such as vortices in the anastomosis region can trigger an abnormal growth of the vessel wall denoted as intimal hyperplasia. More precisely, the wall shear stress was identified as an important quantity, with low, high and oscillatory values being regarded as critical. To this end, mathematical shape optimization methods are a promising tool to determine anastomosis shapes that minimize wall shear stress related risk factors. Due to its inherent dynamic nature, a stationary model is not feasible for an accurate prediction of these risk factors. Accordingly, the computational demand for these applications is comparably high and due to the dependence of the adjoint problem on the primal state, the memory requirements are very high as well. Furthermore, it is well known that a rigid wall assumption may lead to significant changes in the prediction of wall shear stresses, which calls for fluid-structure interaction (FSI) simulations. Our work focuses on the design of suitable algorithms to overcome the above challenges. In particular, we avoid computationally expensive FSI simulations as much as possible and perform a fully coupled computation of the shape derivative according to only in a few optimization iterations. State-of-the-art methods as investigated in are used to compute shape updates from the shape derivative. The coupling is realized in a partitioned manner, which allows to use dedicated solvers for the fluid and structure subproblem. To this end, the finite volume method is employed on the fluid side, while finite elements are used on the structure side. The simulation approach is used to investigate the effectiveness of several carefully constructed objective functions with regard to a minimization of low, high and oscillatory wall shear stresses.