A Comparison of Acceptance Criteria for the Daily Car-Pooling Problem

Citation

Swan J, Drake J, Ozcan E, Goulding J & Woodward J (2013) A Comparison of Acceptance Criteria for the Daily Car-Pooling Problem. In: Gelenbe E & Lent R (eds.) Computer and Information Sciences III: 27th International Symposium on Computer and Information Sciences. 27th International Symposium on Computer and Information Sciences, Paris, France, 03.10.2012-04.10.2012. London: Springer, pp. 477-483. http://link.springer.com/chapter/10.1007%2F978-1-4471-4594-3_49; https://doi.org/10.1007/978-1-4471-4594-3_49

Abstract
Previous work on the Daily Car-Pooling problem includes an algorithm that consists of greedy assignment alternating with random perturbation. In this study, we examine the effect of varying the move acceptance policy, specifically Late-acceptance criteria with and without reheating. Late acceptance-based move acceptance criteria were chosen because there is strong empirical evidence in the literature indicating their superiority. Late-acceptance compares the objective values of the current solution with one which was obtained at a fixed number of steps prior to the current step during the search process in order to make an acceptance decision. We observe that the Late-acceptance criteria also achieve superior results in over 75 % of cases for the Daily Car-Pooling problem, the majority of these results being statistically significant.