Cobweb heuristic for multi-objective vehicle routing problem

  • Authors

    • Joseph Okitonyumbe Y. F Institut Supérieur Pédagogique de Mbanza-Ngungu
    • Berthold Ulungu E.-L Institut Supérieur de Techniques Appliquées
    • Joel Kapiamba Nt.
    2015-07-11
    https://doi.org/10.14419/ijamr.v4i3.4317
  • Savings, Heuristics, Multiobjective, Vehicle Routing Problem.

  • Solving a classical vehicle routing problem (VRP) by exact methods presents many difficulties for large dimension problem. Consequently, in multi-objective framework, heuristic or metaheuristic methods are required. Due to particular VRP structure, it seems that a dedicated heuristicis more suitable than a metaheuristic. The aim of this article is to collapse different heuristics solving classical VRP and adapt them for to solve the multi-objective vehicle routing problem (MOVRP). The so-called Cobweb Algorithm simulates spider’s behavior when weaving cobweb. This paper presents the algorithm, a didactic example, concluding remarks and way for further researches.

  • References

    1. [1] Wei Zhou, Tingxin Song, Fei He, and Xi Liu. Multiobjective Vehicle Routing Problem with Route Balance Based on Genetic Algorithm.Discrete Dynamics in Nature and Society, volume 2013, 2013. http://dx.doi.org/10.1155/2013/325686.

      [2] M. M. Solomon, "Algorithms for the vehicle routing and scheduling problems with time window constraints," Operations Research, vol. 35, no. 2, pp. 254–265, 1987. View at Publisher • View at Google Scholar • View at Zentralblatt MATH • View at MathSciNet http://dx.doi.org/10.1287/opre.35.2.254.

      [3] R. Thangiah, K. E. Nygard, and P. L. Juell, "GIDEON: a genetic algorithm system for vehicle routing with time windows," in Proceedings of the 7th IEEE Conference on Artificial Intelligence Applications, pp. 322–328, Miami Beach, Fla, USA, February 1991. View at Scopus http://dx.doi.org/10.1109/caia.1991.120888.

      [4] B. Ombuki, B. J. Ross, and F. Hanshar, "Multi-objective genetic algorithm for vehicle routing problem with time windows," Applied Intelligence, vol. 24, pp. 17–33, 2006. http://dx.doi.org/10.1007/s10489-006-6926-z.

      [5] M. A. Figliozzi, "An iterative route construction and improvement algorithm for the vehicle routing problem with soft time windows," Transportation Research C, vol. 18, no. 5, pp. 668–679, 2010. View at Publisher • View at Google Scholar • View at Scopus http://dx.doi.org/10.1016/j.trc.2009.08.005.

      [6] K. Pang, "An adaptive parallel route construction heuristic for the vehicle routing problem with time windows constraints," Expert Systems with Applications, vol. 38, no. 9, pp. 11939–11946, 2011. View at Publisher • View at Google Scholar • View at Scopus http://dx.doi.org/10.1016/j.eswa.2011.03.088.

      [7] K. Ghoseiri and S. F. Ghannadpour, "Multi-objective vehicle routing problem with time windows using goal programming and genetic algorithm," Applied Soft Computing Journal, vol. 10, no. 4, pp. 1096–1107, 2010. View at Publisher • View at Google Scholar • View at Scopus http://dx.doi.org/10.1016/j.asoc.2010.04.001.

      [8] K. C. Tan, L. H. Lee, Q. L. Zhu, and K. Ou, "Heuristic methods for vehicle routing problem with time windows," Artificial Intelligence in Engineering, vol. 15, no. 3, pp. 281–295, 2001. View at Publisher • View at Google Scholar • View at Scopus http://dx.doi.org/10.1016/S0954-1810(01)00005-X.

      [9] W. Chiang and R. A. Russell, "Simulated annealing metaheuristics for the vehicle routing problem with time windows," Annals of Operations Research, vol. 63, pp. 3–27, 1996. View at Scopus. http://dx.doi.org/10.1007/BF02601637.

      [10] E. D. Taillard, P. Badeau, M. Gendreau, F. Guertin, and J. Potvin, "A tabu search heuristic for the vehicle routing problem with soft time windows," Transportation Science, vol. 31, no. 2, pp. 170–186, 1997. View at Scopus. http://dx.doi.org/10.1287/trsc.31.2.170.

      [11] S. Thangiah, "Vehicle routing with time windows using genetic algorithms," in Applications Handbook of Genetic Algorithms: New Frontiers, Volume II, pp. 253–277, CRC Press, Boca Raton, Fla, USA, 1995.

      [12] N. Jozefowiez, F. Semet, and E. Talbi, "Target aiming Pareto search and its application to the vehicle routing problem with route balancing," Journal of Heuristics, vol. 13, no. 5, pp. 455–469, 2007. View at Publisher • View at Google Scholar • View at Scopus. http://dx.doi.org/10.1007/s10732-007-9022-6.

      [13] G. B. Alvarenga, G. R. Mateus, and G. de Tomi, "A genetic and set partitioning two-phase approach for the vehicle routing problem with time windows," Computers and Operations Research, vol. 34, no. 6, pp. 1561–1584, 2007. View at Publisher • View at Google Scholar • View at Scopus. http://dx.doi.org/10.1016/j.cor.2005.07.025.

      [14] N. Jozefowiez, F. Semet, and E. Talbi, "Multi-objective vehicle routing problems," European Journal of Operational Research, vol. 189, no. 2, pp. 293–309, 2008. View at Publisher • View at Google Scholar • View at Zentralblatt MATH • View at MathSciNet. http://dx.doi.org/10.1016/j.ejor.2007.05.055.

      [15] D. E. Goldberg, Genetic Algorithms Insearch, Optimization and Machine Learning, New York, NY, USA, Addison-Wesley edition, 1989.

      [16] K. C. Tan, Y. H. Chew, and L. H. Lee, "A hybrid multiobjective evolutionary algorithm for solving vehicle routing problem with time windows," Computational Optimization and Applications, vol. 34, no. 1, pp. 115–151, 2006. View at Publisher • View at Google Scholar • View at Zentralblatt MATH • View at MathSciNet. http://dx.doi.org/10.1007/s10589-005-3070-3.

      [17] S. R. Thangiah, "A hybrid genetic algorithms, simulated annealing and tabu search heuristic for vehicle routing problems with time windows," in Practical Handbook of Genetic Algorithms Complex Structures, Volume 3. L. Chambers, pp. 374–381, CRC Press, 1999.

      [18] K. C. Tan, L. H. Lee, and K. Ou, "Hybrid genetic algorithms in solving vehicle routing problems with time window constraints," Asia-Pacific Journal of Operational Research, vol. 18, no. 1, pp. 121–130, 2001. View at Zentralblatt MATH • View at MathSciNet • View at Scopus.

      [19] R. Ba-os, J. Ortega, C. Gil, A. L. Marquez, and F. de Toro, "A hybrid meta-heuristic for multi-objective vehicle routing problems with time windows," Computers and Industrial Engineering, vol. 65, no. 2, pp. 286–296, 2013. http://dx.doi.org/10.1016/j.cie.2013.01.007.

      [20] O.Clarke ET J. Wright, Scheduling of Vehicles from a Central Depot to a Number of Delivery Points, Operations Research, 12(4): 568-581, 1964. http://dx.doi.org/10.1287/opre.12.4.568.

      [21] R.H.Mole and S.R. Jameson,A sequential route-building algorithm employing a generalized saving criterion. Operational Research Quaterly, 27: 503-511, 1976. http://dx.doi.org/10.2307/3008819.

      [22] Toth, Paolo ET D. Vigo: The Vehicle Routing Problem. Philadelphia: Society for Industrial and Applied Mathematics, 2002. http://dx.doi.org/10.1137/1.9780898718515.

      [23] B.E. Gillett and L.R. Miller, A Heuristic Algorithm for the Vehicle-Dispatch Problem, Operations Research, vol. 21, pp. 340-349, 1974. http://dx.doi.org/10.1287/opre.22.2.340.

      [24] J. Teghem, Recherche opérationnelle Tome1: Méthodes d'optimisation, Ellipses 2012.

      [25] Basseur M., F. Seynhaeve, and E-G Talbi. Design of multi-objective evolutionary algorithms: application to the flow shop. In congress off evolutionary capitation, Honolulu Hawaii, IEEE service center USA, 2002.

      [26] Okitonyumbe, Y.F. Optimisation combinatoire multi-objectif: Méthodes exactes et métaheuristiques, Master'sThesis, Université Pédagogique Nationale, Kinshasa/RD CONGO, Septembre 2012.

      [27] Okitonyumbe, Y.F. and Ulungu, E.L. Nouvelle caractérisation des solutions efficaces des problèmes d'optimisation combinatoire multiobjectif. Revue Congolaise des Sciences Nucléaires, 27, Décembre 2013.

      [28] B. Ulungu andJ. Teghem, Multi-objective Combinatorial Optimization Problems: A Survey, Journal of Multi-criteria Decision Analysis, 3: 83-104, 1994. http://dx.doi.org/10.1002/mcda.4020030204.

  • Downloads

  • How to Cite

    Okitonyumbe Y. F, J., Ulungu E.-L, B., & Kapiamba Nt., J. (2015). Cobweb heuristic for multi-objective vehicle routing problem. International Journal of Applied Mathematical Research, 4(3), 430-436. https://doi.org/10.14419/ijamr.v4i3.4317