This　paper　is　concerned　with　the　routing　problem　of　a　mixed　vehicle　fleet　composed　by　both　electric　and　conventional　vehicles.　A　bi-objective　model　with　the　aim　of　minimizing　carbon　emissions　and　maximising　customer　satisfaction　is　established.　To　further　tackle　the　challenges　posed　by　the　distinct　constraints　of　electric　and　conventional　vehicles,　a　partial　variable-length　coding　method　is　introduced　to　facilitate　chromosome　generation　in　the　model.　Then,　a　novel　NSGA-II　including　the　above　designed　coding　method　is　proposed　for　solving　the　optimization　problem.　By　comparing　the　experiments　results　of　solving　separate　single-objective　optimization　and　the　two　conflict　optimization　objectives　simultaneously,　it　is　verified　that　the　proposed　encoding　approach　and　algorithm　is　effective.　The　results　suggest　that　the　bi-objective　model　is　well-established,　demonstrating　the　anticipated　conflict　between　the　two　objectives.　Additionally,　the　partial　variable-length　coding　method　is　shown　to　be　effective　in　achieving　chromosome　generation　tasks.　©　2024　Technical　Committee　on　Control　Theory,　Chinese　Association　of　Automation.