Vessel scheduling for an industrial crude oil exploration operation, coming under the category of vehicle routing problem (VRP), is solved under multiobjective optimization framework. Objectives under consideration are minimization of total time, vessel unutilization and missed demand. Two bi-objective and one triple-objective problems are solved (as per requirement of the industry) and Pareto optimal (PO) solutions are generated for all of them. The demands to be supplied at various installations by splitting across the various heterogeneous vessels are considered as the decision variables. Pareto Archived Evolutionary Strategy (PAES), one of the state-of-the-art evolutionary multi-objective optimization (EMO) algorithms, is chosen for this task. The conventional method based on E-constraints, when used to solve one of the three optimization problems mentioned above, is observed to be completely outperformed by PAES in terms of computation time and resources required to solve the problem.