Heterogeneous Vehicle Routing Problem with Fixed Cost using Vehicles with Genetic Algorithms

Sayyed Mahdi SADAT KHORASGANI, Farsad ATAII, Mahdi GhAFFARI, Behrooz ABBASI
2.157 848

Abstract


Vehicle routing problem is NP-Complete problem categories. Given the time complexity of these issues is higher degree of polynomials, by increasing the size of the exact solution problem increase with significant rate. The reason for the approximate solution of such issues and innovative creative solutions has been proposed.  Vehicle routing problem with heterogeneous fleet regarding fixed cost of using a vehicle is examined. The problem is presented. The mathematical model of the problem, due to the nature of the problem is NP-Complete, innovative genetic algorithm for the problem-informed has been developed.  Then for several examples of genetic algorithm, compared with the solution and the solution algorithm and answer exactly (by Lingo software) have been studied. The results show that the genetic algorithm, the performance is acceptable and in reasonable time give an answer with negligible error.


Keywords


Heterogeneous vehicle routing problem, using fixed fee vehicle, GA

Full Text:

PDF


References


Renauld, J., boctor, F. and laporte, G., "An Improved Petal Heuristic for The vehicle Routing problem", journal of the Oper. Res., Vol. 47, pp. 329-336. 1996

fhisher, m. l. and jaikumar, R, "A General Assignment Heuristic for vehicle Routing", J. of Networks, Vol. 11, pp. 109-124. 1981

Clarke, G. and Write, J. W, "Scheduling of Vehicles from a Central Depot to a Number of Delivery Points", Oper. Res., Vol. 12, pp. 568-581. 1964

laporte, G. "The vehicle Routing problem: An overview of Exact & Approximate Algorithm", Euro. J. of Oper. Res., Vol. 59, pp. 345-358. 1992

Lawer, E. L., einnoy, J. K., kan, A. H. G. and shmoys, D. B, The Traveling Saleman problem, wiley, New York. 1985

stern, H. and dror, M., "Routing electric meter readers", J. of Comp. Oper. Res., Vol. 6, pp. 209-223. 1979

Golden, B. L. and wang, F., "Capacited arc Routing problems", J. of Networks, Vol. 11, pp. 305-315. 1981

zhang, X. and tang, L., "A New Hybrid Ant Colony Optimization Algorithm for the Vehicle Routing Problem", Pattern Recognition Letters, Vol. 30, pp. 2009

Ai-ling, C., gen-ke, y. and zhi-ming, w., "Hybrid Discrete Particle Swarm Optimization Algorithm for Capacited Vehicle Routing Problem", J. of Zhejinang University, Vol. 7, pp. 607-614. 2006

lin, S. W., lee, Z. J., ying, k. c. and lee, c. y., "Applying Hybrid Meta-Heuristics for Capacited Vehicle Routing Problem", Expert Systems with Applicatins, Vol. 36, pp. 1505-1512. 2009

Holland, J. H., Adaptation in natural and artificial systems: An introductory analysis with applications to biology, control, and artificial intelligence, U Michigan Press, 1975