Erwägungen:
1.
X._ war von Ende Februar 2010 bis Anfang März 2011 an der Lagerung sowie an landesinternen und grenzüberschreitenden Transporten von rund 6,4 kg Kokaingemisch und ca. 75 kg Streckmitteln beteiligt. Drahtzieher und Organisator der einzelnen Tätigkeiten und insbesondere verantwortlich für den Absatz des Kokains und der Streckmittel war Y._.
Das Bezirksgericht Zürich verurteilte X._ am 27. Februar 2014 wegen mehrfacher qualifizierter Widerhandlungen gegen das Betäubungsmittelgesetz (Handlungen bezüglich 4,4 kg reines Kokain und 75 kg Streckmittel) zu einer Freiheitsstrafe von vier Jahren.
Das Obergericht des Kantons Zürich erkannte ein strafbares Verhalten nur hinsichtlich der Handlungen mit 4,4 kg Kokain und sprach X._ von den Vorwürfen des Anstalten-Treffens im Zusammenhang mit Streckmitteln frei. Es verurteilte ihn wegen mehrfacher qualifizierter Widerhandlungen gegen das BetmG zu einer Freiheitsstrafe von drei Jahren und neun Monaten.
Die hiergegen geführte Beschwerde in Strafsachen (6B_1224/2014) hiess das Bundesgericht am 9. April 2015 wegen formeller Fehler gut und wies die Sache zur neuen Beurteilung der Strafe an das Obergericht zurück (<ref-ruling>).
2.
Das Obergericht verurteilte X._ am 29. Oktober 2015 im schriftlichen Berufungsverfahren wegen mehrfacher (qualifizierter) Widerhandlungen gegen das BetmG erneut zu einer Freiheitsstrafe von drei Jahren und neun Monaten.
X._ führt Beschwerde in Strafsachen. Er wendet sich gegen die Strafzumessung und den Vollzug der Strafe und macht eine unrichtige Sachverhaltsfeststellung sowie eine Verletzung der Begründungspflicht geltend. Zudem habe die Vorinstanz in Überschreitung und Missbrauch ihres Ermessens rechtlich erhebliche Kriterien bei der Strafzumessung ausser Acht gelassen respektive falsch gewichtet. X._ beantragt, er sei zu einer teilbedingten Freiheitsstrafe von drei Jahren zu verurteilen, deren Vollzug im Umfang von 18 Monaten aufzuschieben sei. Eventualiter sei die Sache zur neuen Strafzumessung und/oder zur Beurteilung des Vollzugs an die Vorinstanz zurückzuweisen.
3.
3.1. Der angefochtene Entscheid verletzt Bundesrecht. Die Vorinstanz verkennt Umfang und Tragweite des bundesgerichtlichen Rückweisungsentscheides. Das Bundesgericht hat im Rückweisungsurteil zwar auch darauf hingewiesen, dass die Vorinstanz als Berufungsgericht ein eigenes Urteil zu fällen hat und sich nicht mit der Rechtsüberprüfung der erstinstanzlichen Strafzumessungserwägungen hätte begnügen dürfen. Die Vorinstanz übersieht jedoch, dass das Bundesgericht das Urteil vom 27. Februar 2014 in erster Linie aufgehoben und zurückgewiesen hat, da dessen Erwägungen aufgrund der unklaren und übermässigen Verweise teilweise missverständlich und widersprüchlich sowie einer Überprüfung durch das Bundesgericht nicht zugänglich waren (vgl. Rückweisungsurteil, <ref-ruling> E. 1.3.1 und 1.3.2; Art. 112 Abs. 1 lit. b BGG i.V.m. Art. 82 Abs. 4 StPO). Dies ist vorliegend erneut der Fall. Die Vorinstanz nimmt zwar eine eigene Strafzumessung vor, jedoch ist nur ansatzweise ersichtlich, welche Sachverhaltsfeststellungen sie ihren Strafzumessungserwägungen zugrunde legt und worauf sie diese abstützt, da sie "in sinngemässer Anwendung von Art. 82 Abs. 4 StPO auf die Erwägungen der faktisch in Rechtskraft erwachsenen Teile im aufgehobenen Entscheid" verweist, die jedoch bereits einer bundesgerichtlichen Überprüfung nicht zugänglich waren und zur Rückweisung geführt haben.
3.2. Zudem erweist sich die Rechtsanwendung der Vorinstanz trotz entsprechenden Hinweises des Bundesgerichts im Rückweisungsurteil erneut als fehlerhaft. Das Bundesgericht hatte im Rückweisungsurteil moniert, dass die Vorinstanz das BetmG sowohl in der zur Tatzeit als auch im Zeitpunkt der Urteilsfällung geltenden Fassungen anwendet. Dies ist vorliegend erneut der Fall. Die Vorinstanz stützt ihre rechtlichen Erwägungen auf das BetmG in seiner zur Tatzeit geltenden Fassung, stellt aber abweichend hiervon im Dispositiv fest, dass die in Anwendung des aktuellen BetmG ergangenen Schuldsprüche des Bezirksgerichts in Rechtskraft erwachsen seien.
4.
Ob die Kostenverteilung der Vorinstanz, angesichts der im Berufungsverfahren erfolgten Freisprüche von knapp der Hälfte der Anklagevorwürfe lediglich zu 1/6 der Verfahrenskosten auf die Staatskasse zu nehmen, bundesrechtskonform ist, ist nicht mehr zu überprüfen. Die Kostenregelung war nicht Gegenstand der ersten Beschwerde und demnach auch nicht des Rückweisungsentscheides. Sie kann im vorliegenden Verfahren nicht mehr angefochten werden.
5.
Die Beschwerde ist im Verfahren nach Art. 109 BGG im Hauptpunkt gutzuheissen. Der Beschwerdeführer unterliegt nur im Nebenpunkt der vorinstanzlichen Kostenverteilung, weshalb es sich rechtfertigt, von einer Kostenauflage abzusehen (Art. 66 Abs. 1 BGG). Der Kanton Zürich trägt ebenfalls keine Gerichtskosten (Art. 66 Abs. 4 BGG), hat jedoch den Beschwerdeführer für das bundesgerichtliche Verfahren angemessen zu entschädigen (Art. 68 Abs. 2 BGG).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird teilweise gutgeheissen, das Urteil des Obergerichts des Kantons Zürich vom 29. Oktober 2015 aufgehoben und die Sache zu neuer Entscheidung an die Vorinstanz zurückgewiesen. Im Übrigen wird die Beschwerde abgewiesen, soweit darauf einzutreten ist.
2.
Es werden keine Gerichtskosten erhoben.
3.
Der Kanton Zürich hat den Beschwerdeführer für das bundesgerichtliche Verfahren mit Fr. 2'000.- zu entschädigen.
4.
Dieses Urteil wird den Parteien und dem Obergericht des Kantons Zürich, II. Strafkammer, schriftlich mitgeteilt.
Lausanne, 27. Juni 2016
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Denys
Der Gerichtsschreiber: Held