Maritime inventory routing problem is addressed in this paper to satisfy the demand at different ports during the planning horizon. It explores the possibilities of integrating slow steaming policy as mentioned in Kontovas et al. (2011) and Norstad et al. (2011) within ship routing. A mixed integer non-linear programming model is presented considering various scheduling and routing constraints, loading/unloading constraints and vessel capacity constraints. Non-linear equation between fuel consumption and vessel speed has been incorporated to capture the sustainability aspects. Several time window constraints are inculcated in the mathematical model to enhance the service level at each port. Penalty costs are incurred if the ship arrives early before the starting of the time window or if it finishes its operation after the ending of the time window. Costs associated with the violation of time window helps in maintaining a proper port discipline. Now, owing to the inherent complexity of the aforementioned problem, an effective search heuristics named Particle Swarm Optimization for Composite Particle (PSO-CP) is employed. Particle Swarm Optimization – Differential Evolution (PSO-DE), Basic PSO and Genetic Algorithm (GA) are used to validate the result obtained from PSO-CP. Computational results provided for different problem instances shows the superiority of PSO-CP over the other algorithms in terms of the solution obtained.