We study the Holstein model of spinless fermions, which at half-filling exhibits a quantum phase transition from a metallic Tomonaga-Luttinger liquid phase to an insulating charge-density-wave (CDW) phase at a critical electron-phonon coupling strength. In our work, we focus on the real-time evolution starting from two different types of initial states that are CDW ordered: (i) ideal CDW states with and without additional phonons in the system and (ii) correlated ground states in the CDW phase. We identify the mechanism for CDW melting in the ensuing real-time dynamics and show that it strongly depends on the type of initial state. We focus on the far-from-equilibrium regime and emphasize the role of electron-phonon coupling rather than dominant electronic correlations, thus complementing a previous study of photo-induced CDW melting [H. Hashimoto and S. Ishihara, Phys. Rev. B 96, 035154 (2017)]. The numerical simulations are performed by means of matrix-product-state based methods with a local basis optimization (LBO). Within these techniques, one rotates the local (bosonic) Hilbert spaces adaptively into an optimized basis that can then be truncated while still maintaining a high precision. In this work, we extend the time-evolving block decimation (TEBD) algorithm with LBO, previously applied to single-polaron dynamics, to a half-filled system. We demonstrate that in some parameter regimes, a conventional TEBD method without LBO would fail. Furthermore, we introduce and use a ground-state density-matrix renormalization group method for electron-phonon systems using local basis optimization. In our examples, we account for up to $M_{rm ph} = 40$ bare phonons per site by working with $O(10)$ optimal phonon modes.