top
Articles
  • On Vehicle Routing Problem With Time Windows: A Search Space Analysis   [MASS 2012]
  • Author(s)
  • Lin Tian
  • ABSTRACT
  • This paper studies the search space characteristics for vehicle routing problem with time windows. The ruggedness of the search space is an important predictor of the performance of meta-heuristics. Hence, the ruggedness feature is mainly concerned in this paper. The autocorrelation analysis is used to measure how rugged a search space is, where the ruggedness feature is dependent on which local search operator is adopted. Two commonly used local search operators, i.e. exchange and inversion, are tested and compared through a number of selected benchmark instances, in terms of their corresponding ruggedness features. The results show that exchange operator generally leads to a smoother search space than inversion operator.
  • KEYWORDS
  • autocorrelation analysis; vehichle routing problem with time windows;
  • References
  • [1]
    G. Laporte, "The vehicle routing problem: an overview of exact and approximate algorithms," European Journal of Operational Research, vol.59, pp.345-358, 1992.
    [2]
    F. Maffioli, "The vehicle routing problem: a book review," Quarterly Journal of the Belgian, French and Italian Operations Research Societies, vol.1, pp.149-153, 2003.
    [3]
    M.M. Solomon, "Algorithms for vehicle routing and scheduling problems with time window constraints," Operations Research, vol.35, no.2, 1987.
    [4]
    M.M. Solomon, "Algorithms for the vehicle routing problem with time windows," Transportation Science, vol.29, no.2, pp.156-166, 1995.
    [5]
    H.C. Lau, K.C. Tan, K. Ou, and Y.H. Chew, "Vehicle capacity planning system: a case study on vehicle routing problem with time windows," IEEE Transactions on Systems, Man and Cybernetics, Part A, vol.33, no.2, pp.169-178, 2003.
    [6]
    N. Kohl, "Exact methods for time constrained routing and related scheduling problems," Ph D Thesis, Department of Mathematical Modeling, Technical University of Denmark, 1995.
    [7]
    P. Badeau, M. Gendreau, F. Guertin, J.Y. Potvin, and E. Taillard, "A parallel tabu search heuristic for the vehicle routing problem with time windows," Transportation Research Part C, vol.5, no.2, pp.109- 122, 1997.
    [8]
    Z.J. Czech and P. Czarnas, "Parallel simulated annealing for the vehicle routing problem with time windows," in Proceedings of 10th Euromicro Workshop on Parallel, Distributed and Network-based Processing, pp.376-383, 2002.
    [9]
    S.R. Thangiah, K.E. Nygard, and P.L. Juell, "Gideon: a genetic algorithm system for vehicle routing with time windows," in Proceedings of the Seventh Conference on Artificial Intelligence Applications, pp. 322-325, 1991.
    [10]
    K.C. Tan, K. Ou and L.H. Lee, "A messy genetic algorithm for the vehicle routing problem with time windows constraints," in Proceedings of IEEE Congress on Evolutionary Computation (CEC’01), pp.679-686, 2001.
    [11]
    K.Q. Zhu, "A diversity-controlling adaptive genetic algorithm for the vehicle routing problem with time windows," in Proceedings of the 15th IEEE International Conference on Tools for Artificial Intelligence (ICTAI 2003), pp.176-183, 2003.
    [12]
    B. Ombuki, B.J. Ross, and F. Hanshar, "Multi-objective genetic algorithms for vehicle routing problem with time windows,"Applied Intelligence, vol.24, pp.17-30, 2006.
    [13]
    E.D. Weinberger, "Correlated and uncorrelated fitness landscapes and how to tell the difference," Biological Cybernetics, vol.63, pp.325- 336, 1990.
    [14]
    W. Hordijk, "A measure of landscapes," Evolutionary Computation, vol.4, no.4, pp.335-360, 1997.
    [15]
    G. Ochoa, R. Qu, E.K. Burke, "Analyzing the landscape of a graph based hyper-heuristic for timetabling problems," in Proceedings of The Genetic and Evolutionary Computation Conference, pp.341-348, 2009.

Engineering Information Institute is the member of/source content provider to

http://www.scirp.org http://www.hanspub.org/ http://www.crossref.org/index.html http://www.oalib.com/ http://www.ebscohost.com/ http://www.proquest.co.uk/en-UK/aboutus/default.shtml http://ip-science.thomsonreuters.com/cgi-bin/jrnlst/jlresults.cgi?PC=MASTER&Full=journal%20of%20Bioequivalence%20%26%20Bioavailability http://publishers.indexcopernicus.com/index.php