Network　softwarization　makes　it　easy　to　quickly　deploy　various　and　different　network　services　with　the　composition　of　virtual　network　functions　(VNFs)　that　can　be　launched,　modified　and　stopped　at　any　time.　Nowadays,　several　VNF　servers　supporting　different　types　of　VNFs　exist.　Therefore,　to　minimize　the　cost　of　deploying　network　services,　VNFs　should　not　only　be　placed　on　the　best　servers　but　also　chained　in　an　optimal　way.　In　this　paper,　we　propose　a　new　approach　to　solve　the　NP-hard　VNF　placement　and　chaining　problem　(VNFPC　problem).　After　proving　that　VNFPC　problem　can　be　transformed　to　a　variant　of　the　multi-constrained　routing　problem　where　the　number　of　additive　metrics　is　part　of　the　problem,　we　proposed　efficient　heuristic　reducing　the　worst-case　time　complexity　while　ensuring　high　quality　solutions.　Simulation　results　show　that　our　constrained　shortest　paths-based　heuristics　allows　to　determine　solutions　close　to　the　optima　by　keeping　small　number　of　paths　on　nodes.　©　2023　IEEE.