Mathematical Models for Milk Dispatching Problem

Abstract

This study considers the milk dispatching problem for a small-sized distribution company. The milk dispatching problem can be seen in many real-life applications. Under a social responsibility project, several organizations, including companies and municipalities, distribute bottled milk for children to primary schools and impoverished families without any charge. These companies generally use capacitated vehicles for distribution and should consider available hours of the schools as well as the families. The planners generally want to minimize their expenses, such as fuel oil and storage costs. Under those restrictions, the problem turns out to be a capacitated vehicle routing problem with time windows (CVRPTW). One of the main objectives is to minimize total traveled distance considering the vehicle type to reduce the fuel consumption of the vehicles. Another objective is to minimize serving the customers late to reduce the storage cost of undelivered milk. To achieve those objectives, we formulated mixed-integer linear programming (MILP) and constraint programming (CP) models for the problem. To verify and compare our mathematical models, we modified well-known instances from the literature, including problem-specific parameters. The comprehensive computational results show that both models are very competitive for the problem. However, it should be noted that the MILP model outperforms the CP model in terms of solution quality and CPU time for the instances with a long planning horizon.

Keywords

• Milk Dispatching Problem
• Capacitated Vehicle Routing Problem with Time Windows
• Mixed Integer Linear Programming Model
• Constraint Programming Model

References

1. Amorim, P., Parragh, S. N., Sperandio, F., & Almada-Lobo, B. (2014). A rich vehicle routing problem dealing with perishable food: A case study. TOP, 22(2), 489-508. https://doi.org/10.1007/s11750-012-0266-4 google scholar
2. Bae, H., & Moon, I. (2016). Multi-depot vehicle routing problem with time windows considering delivery and installation vehicles. Applied Mathematical Modelling, 40(13-14), 6536-6549. https://doi.org/10.1016/j. apm.2016.01.059 google scholar
3. Booth, K. E. C., & Beck, J. C. (2019). A Constraint Programming Approach to Electric Vehicle Routing with Time Windows. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (Vol. 11494 LNCS, pp. 129-145). Springer Verlag. https://doi.org/10.1007/978-3-030-19212- 9_9 google scholar
4. Braekers, K., Ramaekers, K., & Van Nieuwenhuyse, I. (2016, September 1). The vehicle routing problem: State of the art classification and review. Computers and Industrial Engineering. Elsevier Ltd. https:// doi.org/10.1016/j.cie.2015.12.007 google scholar
5. Butler, M., Herlihy, P., & Keenan, P. B. (2005). Integrating information technology and operational research in the management of milk collection. Journal of Food Engineering, 70(3), 341-349. https://doi. org/10.1016/j.jfoodeng.2004.02.046 google scholar
6. Caramia, M., & Guerriero, F. (2010). A milk collection problem with incompatibility constraints. Interfaces, 40(2), 130-143. https://doi.org/10.1287/inte.1090.0475 google scholar
7. Claassen, G. D. H., & Hendriks, T. H. B. (2007). An application of Special Ordered Sets to a periodic milk collection problem. European Journal of Operational Research, 180(2), 754-769. https://doi. org/10.1016/j.ejor.2006.03.042 google scholar
8. De Backer, B., Furnon, V., Shaw, P., Kilby, P., & Prosser, P. (2000). Solving vehicle routing problems using constraint programming and metaheuristics. Journal of Heuristics, 6(4), 501-523. https://doi. org/10.1023/A:1009621410177 google scholar

9. El-Sherbeny, N. A. (2010). Vehicle routing with time windows: An overview of exact, heuristic and metaheuristic methods. Journal of King Saud University - Science, 22(3), 123- 131. https://doi. org/10.1016/j.jksus.2010.03.002 google scholar
10. Fatih Demiral, M. (2013a). Bulanık Doğrusal Programlama ile Süt Endüstrisinde Bir Uygulama - A Case Study at Dairy Industry with Fuzzy Linear Programming. Süleyman Demirel Üniversitesi İktisadi ve İdari Bilimler Fakültesi Dergisi, 18(2), 373-397. google scholar
11. Fatih Demiral, M. (2013b). Süt Endüstrisinde Optimizasyon İmkanları ve Bir Model Önerisi - Optimization Opportunities At Dairy Industry And A Model Proposal. Mehmet Akif Ersoy Üniversitesi Sosyal Bilimler Enstitüsü Dergisi, 5(8), 36-57. https://doi.org/10.20875/sb.18524 google scholar
12. Gong, W., & Fu, Z. (2010). ABC-ACO for perishable food vehicle routing problem with time windows. In Proceedings - 2010 International Conference on Computational and Information Sciences, ICCIS 2010 (pp. 1261-1264). https://doi.org/10.1109/ICCIS.2010.311 google scholar
13. Guimarans, D., Herrero, R., Ramos, J. J., & Padron, S. (2011). Solving Vehicle Routing Problems Using Constraint Programming and Lagrangean Relaxation in a Metaheuristics Framework. International Journal of Information Systems and Supply Chain Management (IJISSCM), 4(2), 61-81. google scholar
14. Ha, M. H., Nguyen, T. D., Nguyen Duy, T., Pham, H. G., Do, T., & Rousseau, L. M. (2020). A new constraint programming model and a linear programming-based adaptive large neighborhood search for the vehicle routing problem with synchronization constraints. Computers and Operations Research, 124, 105085. https://doi.org/10.1016/j.cor.2020.105085 google scholar
15. Hentenryck, P. Van. (1999). The OPL Optimization Programming Language. MIT Press, Cambridge, MA, USA. google scholar
16. Hentenryck, P. Van. (2002). Constraint and Integer Programming in OPL. Informs Journal on Computing, 14(4), 345-372. https://doi.org/10.1287/ijoc.14.4.345.2826 google scholar
17. Hojabri, H., Gendreau, M., Potvin, J.-Y., & Rousseau, L.-M. (2018). Large neighborhood search with constraint programming for a vehicle routing problem with synchronization constraints. Computers and Operations Research, 92, 87-97. https://doi.org/10.1016/j.cor.2017.11.011 google scholar
18. Johnson, D. S., & Garey, R. M. (1979). A Guide to the Theory of NP-Completeness. Computers and Intractability. google scholar
19. Kumar, S. N., & Panneerselvam, R. (2012). A Survey on the Vehicle Routing Problem and Its Variants. Intelligent Information Management, 04(03), 66-74. https://doi.org/10.4236/iim.2012.43010 google scholar
20. Lahrichi, N., Crainic, T. G., Gendreau, M., Rei, W., & Rousseau, L. M. (2015). Strategic analysis of the dairy transportation problem. Journal of the Operational Research Society, 66(1), 44-56. https://doi. org/10.1057/jors.2013.147 google scholar
21. Li, J. qing, Han, Y qi, Duan, P yong, Han, Y yan, Niu, B., Li, C. dong, ... Liu, Y ping. (2020). Meta-heuristic algorithm for solving vehicle routing problems with time windows and synchronized visit constraints in prefabricated systems. Journal of Cleaner Production, 250, 119464. https://doi.org/10.1016/j.jclepro.2019.119464 google scholar
22. Masson, R., Lahrichi, N., & Rousseau, L. M. (2016). A two-stage solution method for the annual dairy transportation problem. European Journal of Operational Research, 251(1), 36-43. https://doi. org/10.1016/j.ejor.2015.10.058 google scholar
23. Nalepa, J., & Blocho, M. (2016). Adaptive memetic algorithm for minimizing distance in the vehicle routing problem with time windows. Soft Computing, 20(6), 2309-2327. https://doi.org/10.1007/s00500-015-1642-4 google scholar
24. Öztop, H., Kizilay, D., & Çil, Z. A. (2020). Mathematical models for the periodic vehicle routing problem with time windows and time spread constraints. International Journal of Optimization and Control: Theories and Applications, 11(1), 10-23. https://doi.org/10.11121/IJOCTA.01.2021.00899 google scholar
25. Paredes-Belmar, G., Lüer-Villagra, A., Marianov, V, Cortes, C. E., & Bronfman, A. (2017). The milk collection problem with blending and collection points. Computers and Electronics in Agriculture, 134, 109-123. https://doi.Org/10.1016/j.compag.2017.01.015 google scholar
26. Paredes-Belmar, G., Marianov, V., Bronfman, A., Obreque, C., & Lüer-Villagra, A. (2016). A milk collection problem with blending. Transportation Research Part E: Logistics and Transportation Review, 94, 26-43. https://doi.org/10.1016/j.tre.2016.07.006 google scholar
27. Paredes-Belmar, G., Montero, E., & Leonardini, O. (2021). A milk transportation problem with milk collection centers and vehicle routing. ISA Transactions. https://doi.org/10.1016/j.isatra.2021.04.020 google scholar
28. Prive, J., Renaud, J., Boctor, F., & Laporte, G. (2006). Solving a vehicle-routing problem arising in soft-drink distribution. Journal of the Operational Research Society, 57(9), 1045- 1052. https://doi.org/10.1057/ palgrave.jors.2602087 google scholar
29. Rossi, F., Van Beek, P., & Walsh, T. (2006). Handbook of Constraint Programming (Foundations of Artificial Intelligence). USA: Elsevier Science Inc. google scholar
30. Sethanan, K., & Pitakaso, R. (2016). Differential evolution algorithms for scheduling raw milk transportation. Computers and Electronics in Agriculture, 121, 245-259. https://doi.org/10.1016/j.compag.2015.12.021 google scholar
31. Sitek, P., Wikarek, J., Rutczynska-Wdowiak, K., Bocewicz, G., & Banaszak, Z. (2021). Optimization of capacitated vehicle routing problem with alternative delivery, pick-up and time windows: A modified hybrid approach. Neurocomputing, 423, 670-678. https://doi.org/10.1016/j.neucom.2020.02.126 google scholar
32. Sitek, Pawel, & Wikarek, J. (2019). Capacitated vehicle routing problem with pick-up and alternative delivery (CVRPPAD): model and implementation using hybrid approach. Annals of OperationsResearch, 273(1-2), 257-277. https://doi.org/10.1007/s10479-017-2722-x google scholar
33. Solomon, M. M. (1987). Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints. Operations Research, 35(2), 254-265. https://doi.org/10.1287/opre.35.2.254 google scholar
34. Tarantilis, C. D., & Kiranoudis, C. T. (2001). A meta-heuristic algorithm for the efficient distribution of perishable foods. Journal of Food Engineering, 50(1), 1-9. https://doi.org/10.1016/S0260-8774(00)00187-4 google scholar
35. Tebaldi, L., Murino, T., & Bottani, E. (2020). An adapted version of the water wave optimization algorithm for the capacitated vehicle routing problem with time windows with application to a real case using probe data. Sustainability (Switzerland), 12(9), 3666. https://doi.org/10.3390/su12093666 google scholar