Optimization Approach of the Vehicle Routing Problem with Packing Constraints Using Genetic Algorithm
DOI:
https://doi.org/10.12962/j25796216.v1.i2.27Abstract
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.
Keywords: Routing, Optimization, Genetics Algorithm, Packing, Bottom-Left Fill
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.
Downloads
Published
Issue
Section
License
Copyright
Submission of a manuscript implies that the submitted work has not been published before (except as part of a thesis or report, or abstract); that it is not under consideration for publication elsewhere; that its publication has been approved by all co-authors. If and when the manuscript is accepted for publication, the author(s) still hold the copyright and retain publishing rights without restrictions. Authors or others are allowed to multiply article as long as not for commercial purposes. For the new invention, authors are suggested to manage its patent before published. The license type is CC-BY-NC 4.0.
Disclaimer
No responsibility is assumed by publisher and co-publishers, nor by the editors for any injury and/or damage to persons or property as a result of any actual or alleged libelous statements, infringement of intellectual property or privacy rights, or products liability, whether resulting from negligence or otherwise, or from any use or operation of any ideas, instructions, procedures, products or methods contained in the material therein.
