PT. X is a company that deals in ship voyage at Surabaya, Jawa Timur. PT. X has problems to fix a schedule for their ships going to East Indonesia. This difficulty is caused by longer travel time compared to West Indonesia. There are policies that the company use that affects in modelling the system in Vehicle Routing Problem with Time Windows (VRPTW). First is the call time, call time defines how many times a month a port has to be visited. This call time splits the initial 15 ports in East Indonesia to 62 locations. Second is the minimal frequency between each visit of the same port. Third is the maximum limit of ports visited by a ship, which is five ports. Ship schedule is then searched using the Insertion Heuristic Method, which is modified according to the case’s condition. Solution generated has a total travel time of 264 days, which is 11,11% more efficient compared to the schedule used by PT. X which has a total travel time of 297 days. Number of ships used is also reduced, which is reduced from 21 ships to 19 ships.