Cobweb Heuristic for solving Multi-Objective Vehicle Routing Problem

Okitonyumbe Y.F., Joseph and Ulungu, Berthold E.-L. and Kapiamba Nt., Joel (2015): Cobweb Heuristic for solving Multi-Objective Vehicle Routing Problem. Published in: International Journal of Applied Mathematical Research , Vol. 4, No. 3 (11 July 2015): pp. 430-436.

Abstract

Abstract 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 heuristic is 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.

• Item Type: MPRA Paper
• Language: English
• Keywords: Keywords: Savings, Cobweb, Heuristics, Multiobjective, Vehicle Routing Problem.
• Subjects: C - Mathematical and Quantitative Methods > C6 - Mathematical Methods ; Programming Models ; Mathematical and Simulation Modeling > C61 - Optimization Techniques ; Programming Models ; Dynamic Analysis

References

References 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.

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.

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.

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.

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.

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.

B.E. Gillett and L.R. Miller, A Heuristic Algorithm for the Vehicle-Dispatch Problem, Operations Research, vol. 21, pp. 340-349, 1974.

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.

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

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.

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.

R.H. Mole and S.R. Jameson, A sequential route-building algorithm employing a generalized saving criterion. Operational Research Quaterly, 27: 503-511, 1976.

Okitonyumbe, Y.F. Optimisation combinatoire multi-objectif : Méthodes exactes et métaheuristiques, Master’s Thesis, Université Pédagogique Nationale, Kinshasa/RD CONGO, Septembre 2012.

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.

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.

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.

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.

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.

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 ·

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.

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.

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.

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.

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.

J. Teghem, Recherche opérationnelle Tome1 : Méthodes d’optimisation, Ellipses 2012.

Toth, Paolo and D. Vigo :The Vehicle Routing Problem. Philadelphia: Society for Industrial and Applied Mathematics, 2002. Ulungu E.-L. and J. Teghem, Multi-objective Combinatorial Optimization Problems : A Survey, Journal of Multi-criteria Decision Analysis, 3: 83-104, 1994.