This thesis is about Two-dimensional loading time dependent vehicle routing problem. This problem considers delivery of rectangular shaped items to customers that are located in an urban area. In urban areas, the travel time between two nodes depends not only on distance between two nodes, but also on departure time from the origin. The aim is to find optimal allocation of customers to the vehicles so that total service time is minimized and a feasible two-dimensional allocation of the items into the loading surface exists. Two mathematical models are proposed. The first model is a single-objective model that considers total service time. The second model is a bi-objective model.The first objective is total service time and the second objective considers load balance. The general objective is minimization of these two objectives. Two metaheuristics named IMproved Genetic Algorithm (IMGA) and Simulated Annealing (SA) are proposed to solve single-objective model. For validating these methods, some small scale problems are solved and results are compared to an exact method. The comparison of results shows that these methods are trustable for solving the model. For investigating their efficiency in dealing with real world problems, somelarge scale problems are solved and the results are compared tothe results of Genetic Algorithm (GA). Results show that IMGA and SA are more efficient than GA. A new metaheuristic named Elitist Non-dominated Sorting Local Search (ENSLS) is implemented to solve bi-objective model. Some small scale problems are solved to examine its validation. Also the model solved with an exact method. The computational results indicate efficiency of this method. Also some large scale problems are solved to show its efficiency in solving real world problems. The results are compared tothe results of two other methods:Non-dominated Sorting Genetic Algorithm-II (NSGA-II) and Strength Pareto Evolutionary Algorithm 2 (SPEA2). Itisshown that ENSLS outperforms NSGA-II and SPEA2. Keywords: Two-dimensional loading time dependent vehicle routing problem, improved genetic algorithm, simulated annealing, elitist non-dominated sorting local search