Integrating packing and distribution problems and optimization through mathematical programming

Abstract: This paper analyzes the integration of two combinatorial problems that frequently arise in production and distribution systems. One is the Bin Packing Problem (BPP) problem, which involves finding an ordering of some objects of different volumes to be packed into the minimal number of containers of the same or different size. An optimal solution to this NP-Hard problem can be approximated by means of meta-heuristic methods. On the other hand, we consider the Capacitated Vehicle Routing Problem with Time Windows (CVRPTW), which is a variant of the Travelling Salesman Problem (again a NP-Hard problem) with extra constraints. Here we model those two problems in a single framework and use an evolutionary meta-heuristics to solve them jointly. Furthermore, we use data from a real world company as a test-bed for the method introduced here.

How to cite this paper

 Miguel, F., Frutos, M., Tohmé, F & Méndez, M. (2016). Integrating packing and distribution problems and optimization through mathematical programming.Decision Science Letters , 5(2), 317-326.

Refrences

Baumgartner, L., Schmid, V., & Blum, C. (2011, January). Solving the Two-Dimensional Bin Packing Problem with a Probabilistic Multi-start Heuristic. InLION (pp. 76-90).

Bennell, J. A., Lee, L. S., & Potts, C. N. (2013). A genetic algorithm for two-dimensional bin packing with due dates. International Journal of Production Economics, 145(2), 547-560.

Br?ysy, O. (2003). A reactive variable neighborhood search for the vehicle-routing problem with time windows. INFORMS Journal on Computing, 15(4), 347-368.

Escobar, J. W., Linfati, R., Toth, P., & Baldoquin, M. G. (2014). A hybrid granular tabu search algorithm for the multi-depot vehicle routing problem.Journal of Heuristics, 20(5), 483-509.

Frutos, M., & Tohmé, F. (2012). A New Approach to the Optimization of the CVRP through Genetic Algorithms. American Journal of Operations Research,2(04), 495.

Goldberg, D. E. (1989). Genetic Algorithms in Search, Optimization and Machine Learning. Addison Wesley Publishing Company, Inc.

Iori, M., Salazar-Gonz?lez, J. J., & Vigo, D. (2007). An exact approach for the vehicle routing problem with two-dimensional loading constraints.Transportation Science, 41(2), 253-264.

Kallehauge, B., Larsen, J., & Madsen, O. B. (2006). Lagrangian duality applied to the vehicle routing problem with time windows. Computers & Operations Research, 33(5), 1464-1487.

Kao, Y., & Chen, M. (2013). Solving the CVRP Problem Using a Hybrid PSO Approach. In Computational Intelligence (pp. 59-67). Springer Berlin Heidelberg.

Kok, A. L., Meyer, C. M., Kopfer, H., & Schutten, J. M. J. (2010). A dynamic programming heuristic for the vehicle routing problem with time windows and European Community social legislation. Transportation Science, 44(4), 442-454.

Lodi, A., Martello, S., & Vigo, D. (2002). Recent advances on two-dimensional bin packing problems. Discrete Applied Mathematics, 123(1), 379-396.

Ma, R., D?sa, G., Han, X., Ting, H. F., Ye, D., & Zhang, Y. (2013). A note on a selfish bin packing problem. Journal of Global Optimization, 56(4), 1457-1462.

Mula, J., Peidro, D., D?az-Madro?ero, M., & Vicens, E. (2010). Mathematical programming models for supply chain production and transport planning.European Journal of Operational Research, 204(3), 377-390.

Oyola, J., & L?kketangen, A. (2014). GRASP-ASP: An algorithm for the CVRP with route balancing. Journal of Heuristics, 20(4), 361-382.

Sitek, P. (2014). A hybrid approach to the two-echelon capacitated vehicle routing problem (2E-CVRP). In Recent Advances in Automation, Robotics and Measuring Techniques (pp. 251-263). Springer International Publishing.

Theys, C., Br?ysy, O., Dullaert, W., & Raa, B. (2010). Using a TSP heuristic for routing order pickers in warehouses. European Journal of Operational Research, 200(3), 755-763.