Optimization Approach of the Vehicle Routing Problem with Packing Constraints Using Genetic Algorithm

nurlita gamayanti

Abstract

Vehicle Routing Problem is an issue in item delivery from depot to its customers using several vehicles which have limited capacity with a purpose to minimize transportation cost. The packing constraints exist because the vehicles which are usually used in item delivery have rectangular-box shaped container. Also, the items are commonly in shape of rectangular-box. Therefore, packing or loading method is needed so that containers could load all of the items without causing damage and could ease unloading process. The purpose of this final project is to develop a model and algorithm using metaheuristics method, especially genetics algorithm in order to minimize total delivery distance. A hybrid genetics algorithm and bottom-left fill algorithm also take place to solve the packing process. This algorithm delivered average solution 0.08% worse than ant colony optimization, but had 2.93% better solution than tabu search.

Full Text:

PDF

References

R. K. Ahuja, T. L. Magnanti and J. B. Orlin, Network Flows, Pearson, 1993.

G. Laporte, "The Vehicle Routing Problem : An overview of exact and approximate algorithms," European Journal of Operational Research, pp. 345-358, 1992.

S. Martello, D. Pisinger and D. Vigo, "The Three-Dimensional Bin Packing Problem," Operations Research, pp. 256-267, 2000.

G. Vaira and O. Kurasova, "Genetic Algorithms and VRP: the Behaviour of a Crossover Operator," Baltic Journal of Modern Computing, 2013.

G. Fuellerer, K. F. Doerner, R. F. Hartl and M. Iori, "Metaheuristic for vehicle routing problems with three-dimensional loading constraints," European Journal of Operational Research, pp. 751-759, 2010.

M. Hifi, I. Kacem, S. Negre and L. Wu, "A Linear Programming Approach for the Three-Dimensional Bin Packing Problem," Electronic Notes in Discrete Mathematics, pp. 993-1000, 2010.

I. Prasetyaningrum, "Penyelesaian Kombinasi Vehicle Routing Problem dan Container Loading Problem Menggunakan Algoritma Genetika," Surabaya, 2007.

D. Liu and H. Teng, "An Improved BL-algorithm for genetic algorithm of the orthogonal packing of rectangles," European Journal of Operational Research, pp. 413-420, 1999.

S. Imahori, M. Yagiura and H. Nagamochi, "Practical Algorithms for Two-dimensional Packing," Mathematical Engineering Technical Reports, Tokyo, 2006.

B. S. Baker, E. Coffman, JR and R. L. Rivest, "Orthogonal Packings in Two Dimensions," SIAM Journal on Computing, pp. 846-855, 1980.

M. Gendreau, M. Iori, G. Laporte and S. Martello, "A Tabu Search Algorithm for a Routing and Container Loading Problem," Transportation Science, pp. 342-350, 2006.

M. Gendreau, M. Iori, G. Laporte and S. Martello, "A Tabu Search heuristic for the vehicle routing problem with two dimensional loading constraints," Networks, p. Forthcoming, 2006.

M. Iori and S. Martello, "Routing problem with loading constraint," TOP, 2010.

B. Santosa and P. Willy, Metoda Metaheuristik Konsep dan Implementasi, Surabaya: Guna Widya, 2011.

A. Turkay and E. Emel, "Vehicle Routing Problem with Packing Contraints," in 5th Euro/Informs Joint International Meeting, Istanbul, 2003.

Refbacks

  • There are currently no refbacks.