This paper defines a Multi-Objective Large-Scale Single Depot Capacitated Vehicle Routing Problem with semi soft time windows using a lexicographic or goal programming approach. The primary objective of the problem is to minimize the number of customer orders that are tardy and use series of other objectives viz., the total distance traveled, the total tardiness and number of vehicles with their waiting times to bring in business context to solve very large problems. A mathematical formulation of the problem is presented, and an efficient Lexicographic Variable Neighborhood Search Algorithm (LVNSA) has been developed that iteratively uses the objectives in a lexicographic manner to generate good and better solutions on smaller benchmark problems and very large instances with 10000s of customers from real-life case data. A comparative evaluation from a practical sense is demonstrated with business implications.