A SMART-SELECTION-BASED GENETIC ALGORITHM FOR DELIVERY AND PICKUP PROBLEM WITH ORDER TIME WINDOWS

Abstract

In a highly competitive environment, businesses strive to optimize their distribution networks to reduce logistics costs. This study focuses on solving vehicle routing problems involving simultaneous delivery and pickup with time windows, addressing both backhaul and divisible delivery and pickup scenarios. A novel hybrid genetic algorithm incorporating smart selection and harem-based crossover methods is proposed to minimize transportation costs while adhering to capacity and time constraints. The smart selection method expedites the solution process by pre-selecting feasible vehicle-route combinations, significantly reducing the computational complexity. Computational experiments on real-world data from the automotive supply industry demonstrate that the proposed algorithm outperforms traditional approaches, achieving substantial cost reductions and high-quality solutions within shorter computation times.

Keywords

• Vehicle Routing Problem
• Delivery and Pickup Problem
• Genetic Algorithm
• Smart Selection
• Hybrid Optimization

References

1. Anily, S. (1996). The vehicle‐routing problem with delivery and back‐haul options. Naval Research Logistics (NRL), 43(3), 415-434.
2. Ashouri, M., & Yousefikhoshbakht, M. (2017). A Combination of Meta-heuristic and Heuristic Algorithms for the VRP, OVRP and VRP with Simultaneous Pickup and Delivery. BRAIN. Broad Research in Artificial Intelligence and Neuroscience, 8(2), 81-95.
3. Baker, B. M., & Ayechew, M. A. (2003). A genetic algorithm for the vehicle routing problem. Computers & Operations Research, 30(5), 787-800.
4. Brown, R. D., Jones, G., Willett, P., & Glen, R. C. (1994). Matching two-dimensional chemical graphs using genetic algorithms. Journal of Chemical Information and Computer Sciences, 34(1), 63-70.
5. Çiçekli U.G. (2012). Çok Kriterli Dağıtım Rotası Probleminin Melez Bir Model İle Optimizasyonu: Genetik Algoritma Temelli Melez Model Uygulaması, Lambert Academic Publishing, Mauritius.
6. Çiçekli UG, Kaymaz Y (2016) A genetic algorithm for the allocation of dangerous goods containers in a storage yard for freight villages and dry ports. Gazi Üniversitesi İktisadi ve İdari Bilimler Fakültesi Dergisi, 18:264-282
7. Dantzig, G. B., & Ramser, J. H. (1959). The truck dispatching problem. Management science, 6(1), 80-91.
8. Dell’Amico, M., Righini, G., & Salani, M. (2006). A branch-and-price approach to the vehicle routing problem with simultaneous distribution and collection. Transportation science, 40(2), 235-247.

9. Dethloff, J. (2001). Vehicle routing and reverse logistics: the vehicle routing problem with simultaneous delivery and pick-up. OR-Spektrum, 23(1), 79-96.
10. Engelbrecht, A. P. (2007). Computational intelligence: an introduction. John Wiley & Sons.
11. Eshelman, L. J., & Schaffer, J. D. (1993). Real-coded genetic algorithms and interval-schemata. In Foundations of Genetic Algorithms (Vol. 2, pp. 187-202). Elsevier.
12. Gajpal, Y., & Abad, P. (2009). An ant colony system (ACS) for vehicle routing problem with simultaneous delivery and pickup. Computers & Operations Research, 36(12), 3215-3223.
13. Goetschalckx, M., & Jacobs-Blecha, C. (1989). The vehicle routing problem with backhauls. European Journal of Operational Research, 42(1), 39-51.
14. Goldberg, D. E. (1991). Real-coded genetic algorithms, virtual alphabets, and blocking. Complex systems, 5(2), 139-167.
15. Grefenstette, J. J. (1992, September). Genetic algorithms for changing environments. In Ppsn (Vol. 2, pp. 137-144).
16. Herrera, F., Lozano, M., & Verdegay, J. L. (1998). Tackling real-coded genetic algorithms: Operators and tools for behavioural analysis. Artificial intelligence review, 12(4), 265-319.
17. Hsiao, S. W., Chiu, F. Y., & Lu, S. H. (2010). Product-form design model based on genetic algorithms. International Journal of Industrial Ergonomics, 40(3), 237-246.
18. Lenstra, J. K., & Kan, A. R. (1981). Complexity of vehicle routing and scheduling problems. Networks, 11(2), 221-227.
19. Lim, A., & Chew, H. K. (1997). Joining of compacted cells using genetic algorithm. Electronics Letters, 33(23), 1944-1945.
20. Liu, R., Xie, X., Augusto, V., & Rodriguez, C. (2013). Heuristic algorithms for a vehicle routing problem with simultaneous delivery and pickup and time windows in home health care. European Journal of Operational Research, 230(3), 475-486.
21. Michalewicz, Z., Vignaux, G. A., & Hobbs, M. (1991). A nonstandard genetic algorithm for the nonlinear transportation problem. ORSA Journal on computing, 3(4), 307-316.
22. Min, H. (1989). The multiple vehicle routing problem with simultaneous delivery and pick-up points. Transportation Research Part A: General, 23(5), 377-386.
23. Osman, I. H., & Laporte, G. (1996). Metaheuristics: A bibliography. Annals of Operations research, 63, 511-623.
24. Poon, P. W., & Carter, J. N. (1995). Genetic algorithm crossover operators for ordering applications. Computers & Operations Research, 22(1), 135-147.
25. Wang, H. F., & Chen, Y. Y. (2013). A coevolutionary algorithm for the flexible delivery and pickup problem with time windows. International Journal of Production Economics, 141(1), 4-13.
26. Whitley, D. (1994). A genetic algorithm tutorial. Statistics and Computing, 4(2), 65-85.
27. Wright, A. H. (1991). Genetic algorithms for real parameter optimization. In Foundations of Genetic Algorithms (Vol. 1, pp. 205-218). Elsevier.
28. Yadav, S. L., & Sohal, A. (2017). Comparative study of different selection techniques in genetic algorithm. International Journal of Engineering, Science and Mathematics, 6(3), 174-180.
29. Zhong, Y., & Cole, M. H. (2005). A vehicle routing problem with backhauls and time windows: a guided local search solution. Transportation Research Part E: Logistics and Transportation Review, 41(2), 131-144.