Use of hybrid methods to contribute in solving the Vehicle Routing Problem


Abstract in English

n this research, we are studying the possibility of contribution in solving the Vehicle Routing Problem (VRP), which is one of the optimization problems that, because of its Real Life applications, has attracted a lot of attention at the present time. It is a problem of the NP-hard type. However, because of the complication of polynomial time there is still no algorithm providing us with the optimal solution of this problem. All the used algorithms give solutions that are close to the optimal one . In this research, we will present the Hybrid Algorithm (HA) in two phases .In the first phase the Sweep Algorithm (SW) is applied, and in the second one the Ant Colony Algorithm and the local search 3-opt are applied. we will then compare the quality of the solution resulted from this hybrid approach with the results of well-known standard tests to determine the effectiveness of the presented approach .

References used

DANTZIG, G.B.; RAMSER, J. H., “The Truck Dispatching Problem," Management Science, Vol. 6, No. 1, 1959, pp. 79-89
LAPORTE, G., “The Vehicle Routing Problem : An Overview of Exact and Approximate of Operational Research," Vol. 59, No. 3, 1992, pp. 345-358
FISHER .M., "Vehicle Routing. Handbooks of Operations Research and Management Science," chap.1, 1995, pp.8:1-31
GILLETT, B.E.; L.R. MILLER, "A Heuristic Algorithm for the Vehicle Dispatch Problem," Oper Res, 1974, pp.22:341–347
GOLEN, B.L; ASSAD,A.A., "Vehicle Routing: Methods and Studies," eds. North Holland, Amsterdam,1988

Download