The transport sector in general, and freight traffic in particular, significantly contribute to global CO2 emissions. Because of climate change and EU Green Deal regulations the entire logistics sector will face major challenges and a need for further optimization in the near future. One way to bring this sector to a new level in terms of sustainability is to introduce cross-company optimization rather than concentrating on the optimization of single company processes which are already highly optimized. In this paper we will introduce a collaborative planning problem for freight delivery, and an effective heuristic search algorithm for the specified problem. We present an experimental evaluation on a benchmark dataset comprising 225 problem instances and thereby show the optimization potential of collaboration in the logistics sector.