With　ongoing　global　industrialization,　the　demand　for　refined　oil　products,　particularly　in　developing　countries,　is　increasing　significantly.　Shipping　companies　typically　transport　refined　oil　from　a　primary　refinery　to　multiple　oil　depots,　addressing　various　demand　tasks.　To　manage　uncertain　refined　oil　demand,　shipping　companies　use　both　self-owned　tankers　and　outsourced　tankers,　including　time-chartered　and　voyage-chartered　tankers.　A　time　charter　is　a　contract　where　the　shipping　company　pays　charter　money　for　a　specific　period,　while　a　voyage　charter　involves　payments　based　on　voyage　frequency.　This　paper　develops　a　nonlinear　programming　model　to　optimize　fleet　deployment,　considering　transportation　costs　and　penalty　costs　for　capacity　loss　during　a　planning　period.　Additionally,　the　model　is　extended　to　allow　flexible　charter　types,　meaning　that　time-chartered　and　voyage-chartered　tankers　are　interchangeable　based　on　shipping　demands.　A　heuristic　algorithm　based　on　tabu　search　is　designed　to　solve　the　proposed　models,　and　four　search　operators　are　incorporated　to　enhance　algorithm　efficiency.　The　models　and　algorithms　are　validated　using　a　real　tanker　fleet.　Numerical　experiments　demonstrate　the　efficiency　of　the　improved　tabu　search　algorithm　in　obtaining　exact　solutions　for　small-scale　instances.　The　case　study　indicates　that　the　shipping　company　prefers　waiting　for　tasks　to　avoid　ship　delay　penalties　and　provide　high-quality　services.　Moreover,　the　flexible　charter　strategy　can　reduce　shipping　costs　by　16.34%.　These　findings　offer　management　insights　for　determining　charter　contracts　for　ship　fleets.　©　Higher　Education　Press　2024.