Vehicle　routing　problem　(VRP)　plays　a　vital　role　in　logistics　management.　Among　which,　the　transportation　of　hazardous　material　attracts　much　attention　especially　in　China.　The　hazardous　material　multi-depot　vehicle　routing　problem　(HMDVRP)　considers　the　transportation　of　hazardous　material　and　multiple　depots　based　on　VRP.　This　paper　develops　a　new　HMDVRP　bi-objective　optimization　model.　Some　new　decision　variables　are　introduced　to　the　model　to　describe　the　sequence　of　customers　and　simplify　the　model　expression.　Moreover,　the　risk　measurement　of　the　model　considers　the　change　of　the　loading,　which　reflects　the　nature　of　hazardous　material　transportation.　HMDVRP　is　NP-hard,　and　the　heuristic　algorithms　are　the　main　method　used　for　solving　it.　This　paper　proposes　a　two-stage　heuristic　algorithm　to　solve　the　new　HMDVRP　model.　Numerical　experiments　show　that　the　two-stage　heuristic　algorithm　can　solve　the　HMDVRP　model　effectively　and　efficiently.