A constrained multi-objective optimization model for the low-carbon vehicle routing problem (VRP) is established. A carbon emission measurement method considering various practical factors is introduced. It minimizes both the total carbon emissions and the longest time consumed by the sub-tours, subject to the limited number of available vehicles. According to the characteristics of the model, a region enhanced discrete multi-objective fireworks algorithm is proposed. A partial mapping explosion operator, a hybrid mutation for adjusting the sub-tours, and an objective-driven extending search are designed, which aim to improve the convergence, diversity, and spread of the non-dominated solutions produced by the algorithm, respectively. Nine low-carbon VRP instances with different scales are used to verify the effectiveness of the new strategies. Furthermore, comparison results with four state-of-the-art algorithms indicate that the proposed algorithm has better performance of convergence and distribution on the low-carbon VRP. It provides a promising scalability to the problem size.