Logistics planning is an important problem in industry, where goods have to be parceled appropriately to meet delivery dates or reduce shipping costs. This optimization problem is classically solved offline using standard algorithms and focused heuristics, e.g. bin packing or route planning. However, in practical work environments constraints may change flexibly (e.g. when custom-tailored goods with variable size have to be handled) and it is often not clear what an optimal solution looks like. Further, logistics planning consists of multiple steps that often are handled by different human employees in different departments. In this paper we propose an interactive approach using human-guided optimization, where solution spaces can be interactively explored, manipulated, and constrained at runtime. Based on an analysis of the problem of multi-step logistics planning, we present a system that supports users in solving this optimization problem, and we report first evaluation results obtained in the first two iterations of an user-centered design process.