Markov chains have frequently been applied to match the probable routes with a set of GPS trip data that a pilot vehicle is emitting over a specific graph road network. This class of map- matching (MM) algorithms presently demonstrates and involve statistical and ad-hoc measures to drive the Markov chain transitional probabilities in picking the best route combinations constrained over the graph road network. In this study, we have devised an adaptive scheme to modify the Markov Chain (MC) kernel window as we move along the GPS samples to reduce the mistakes that can happen by the use of narrower MC widths. The measure for temporarily increasing the MC window width is chosen to be the ratio between the geodesic distance of current route to the actual geodesic distance between each pair of GPS samples. This adaptive use of MC has shown to have hardened the results significantly with tolerable computational cost increase. The details of the overall algorithm are depicted by the example routes extracted from various vehicle trips and the results are shown to validate the usefulness of the algorithm in practice.