[en] We examine the melting of commensurate and incommensurate vortex lattices interacting with square pinning arrays through the use of numerical simulations. For weak pinning strength in the commensurate case we observe an order-order transition from a commensurate square vortex lattice to a triangular floating solid phase as a function of temperature. This floating solid phase melts into a liquid at still higher temperature. For strong pinning there is only a single transition from the square pinned lattice to the liquid state. For strong pinning in the incommensurate case, we observe a multistage melting in which the interstitial vortices become mobile first, followed by the melting of the entire lattice, consistent with recent imaging experiments. The initial motion of vortices in the incommensurate phase occurs by an exchange process of interstitial vortices with vortices located at the pinning sites. We have also examined the vortex melting behavior for higher matching fields and find that a coexistence of a commensurate pinned vortex solid with an interstitial vortex liquid occurs while at higher temperatures the entire vortex lattice melts. For triangular arrays at incommensurate fields higher than the first matching field we observe that the initial vortex motion can occur through a correlated ring excitation where a number of vortices can rotate around a pinned vortex. We also discuss the relevance of our results to recent experiments of colloidal particles interacting with periodic trap arrays